operations.hpp

Go to the documentation of this file.

//
// immer: immutable data structures for C++
// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
//
// This software is distributed under the Boost Software License, Version 1.0.
// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
//

#pragma once

#include <algorithm>
#include <memory>
#include <numeric>
#include <utility>

#include <immer/config.hpp>
#include <immer/heap/tags.hpp>
#include <immer/detail/util.hpp>
#include <immer/detail/rbts/position.hpp>
#include <immer/detail/rbts/visitor.hpp>

namespace immer {
namespace detail {
namespace rbts {

template <typename T>
struct array_for_visitor : visitor_base<array_for_visitor<T>>
{
    using this_t = array_for_visitor;

    template <typename PosT>
    static T* visit_inner(PosT&& pos, size_t idx)
    { return pos.descend(this_t{}, idx); }

    template <typename PosT>
    static T* visit_leaf(PosT&& pos, size_t)
    { return pos.node()->leaf(); }
};

template <typename T>
struct region_for_visitor : visitor_base<region_for_visitor<T>>
{
    using this_t = region_for_visitor;
    using result_t = std::tuple<T*, size_t, size_t>;

    template <typename PosT>
    static result_t visit_inner(PosT&& pos, size_t idx)
    { return pos.towards(this_t{}, idx); }

    template <typename PosT>
    static result_t visit_leaf(PosT&& pos, size_t idx)
    { return { pos.node()->leaf(), pos.index(idx), pos.count() }; }
};

template <typename T>
struct get_visitor : visitor_base<get_visitor<T>>
{
    using this_t = get_visitor;

    template <typename PosT>
    static const T& visit_inner(PosT&& pos, size_t idx)
    { return pos.descend(this_t{}, idx); }

    template <typename PosT>
    static const T& visit_leaf(PosT&& pos, size_t idx)
    { return pos.node()->leaf() [pos.index(idx)]; }
};

struct for_each_chunk_visitor : visitor_base<for_each_chunk_visitor>
{
    using this_t = for_each_chunk_visitor;

    template <typename Pos, typename Fn>
    static void visit_inner(Pos&& pos, Fn&& fn)
    { pos.each(this_t{}, fn); }

    template <typename Pos, typename Fn>
    static void visit_leaf(Pos&& pos, Fn&& fn)
    {
        auto data = pos.node()->leaf();
        fn(data, data + pos.count());
    }
};

struct for_each_chunk_p_visitor : visitor_base<for_each_chunk_p_visitor>
{
    using this_t = for_each_chunk_p_visitor;

    template <typename Pos, typename Fn>
    static bool visit_inner(Pos&& pos, Fn&& fn)
    { return pos.each_pred(this_t{}, fn); }

    template <typename Pos, typename Fn>
    static bool visit_leaf(Pos&& pos, Fn&& fn)
    {
        auto data = pos.node()->leaf();
        return fn(data, data + pos.count());
    }
};

struct for_each_chunk_left_visitor : visitor_base<for_each_chunk_left_visitor>
{
    using this_t = for_each_chunk_left_visitor;

    template <typename Pos, typename Fn>
    static void visit_inner(Pos&& pos,
                            size_t last, Fn&& fn)
    {
        auto l = pos.index(last);
        pos.each_left(for_each_chunk_visitor{}, l, fn);
        pos.towards_oh(this_t{}, last, l, fn);
    }

    template <typename Pos, typename Fn>
    static void visit_leaf(Pos&& pos,
                           size_t last,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        auto l = pos.index(last);
        fn(data, data + l + 1);
    }
};

struct for_each_chunk_right_visitor : visitor_base<for_each_chunk_right_visitor>
{
    using this_t = for_each_chunk_right_visitor;

    template <typename Pos, typename Fn>
    static void visit_inner(Pos&& pos,
                            size_t first, Fn&& fn)
    {
        auto f = pos.index(first);
        pos.towards_oh(this_t{}, first, f, fn);
        pos.each_right(for_each_chunk_visitor{}, f + 1, fn);
    }

    template <typename Pos, typename Fn>
    static void visit_leaf(Pos&& pos,
                           size_t first,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        auto f = pos.index(first);
        fn(data + f, data + pos.count());
    }
};

struct for_each_chunk_i_visitor : visitor_base<for_each_chunk_i_visitor>
{
    using this_t = for_each_chunk_i_visitor;

    template <typename Pos, typename Fn>
    static void visit_relaxed(Pos&& pos,
                              size_t first, size_t last,
                              Fn&& fn)
    {
        // we are going towards *two* indices, so we need to do the
        // relaxed as a special case to correct the second index
        if (first < last)  {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            if (f == l) {
                auto sbh = pos.size_before(f);
                pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn);
            } else {
                assert(f < l);
                pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
                pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
                pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
            }
        }
    }

    template <typename Pos, typename Fn>
    static void visit_regular(Pos&& pos,
                              size_t first, size_t last,
                              Fn&& fn)
    {
        if (first < last)  {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            if (f == l)
                pos.towards_oh(this_t{}, first, f, last, fn);
            else {
                assert(f < l);
                pos.towards_oh(for_each_chunk_right_visitor{}, first, f, fn);
                pos.each_i(for_each_chunk_visitor{}, f + 1, l, fn);
                pos.towards_oh(for_each_chunk_left_visitor{}, last - 1, l, fn);
            }
        }
    }

    template <typename Pos, typename Fn>
    static void visit_leaf(Pos&& pos,
                           size_t first, size_t last,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        if (first < last) {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            fn(data + f, data + l + 1);
        }
    }
};

struct for_each_chunk_p_left_visitor
    : visitor_base<for_each_chunk_p_left_visitor>
{
    using this_t = for_each_chunk_p_left_visitor;

    template <typename Pos, typename Fn>
    static bool visit_inner(Pos&& pos,
                            size_t last, Fn&& fn)
    {
        auto l = pos.index(last);
        return pos.each_pred_left(for_each_chunk_p_visitor{}, l, fn)
            && pos.towards_oh(this_t{}, last, l, fn);
    }

    template <typename Pos, typename Fn>
    static bool visit_leaf(Pos&& pos,
                           size_t last,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        auto l = pos.index(last);
        return fn(data, data + l + 1);
    }
};

struct for_each_chunk_p_right_visitor
    : visitor_base<for_each_chunk_p_right_visitor>
{
    using this_t = for_each_chunk_p_right_visitor;

    template <typename Pos, typename Fn>
    static bool visit_inner(Pos&& pos,
                            size_t first, Fn&& fn)
    {
        auto f = pos.index(first);
        return pos.towards_oh(this_t{}, first, f, fn)
            && pos.each_pred_right(for_each_chunk_p_visitor{}, f + 1, fn);
    }

    template <typename Pos, typename Fn>
    static bool visit_leaf(Pos&& pos,
                           size_t first,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        auto f = pos.index(first);
        return fn(data + f, data + pos.count());
    }
};

struct for_each_chunk_p_i_visitor : visitor_base<for_each_chunk_p_i_visitor>
{
    using this_t = for_each_chunk_p_i_visitor;

    template <typename Pos, typename Fn>
    static bool visit_relaxed(Pos&& pos,
                              size_t first, size_t last,
                              Fn&& fn)
    {
        // we are going towards *two* indices, so we need to do the
        // relaxed as a special case to correct the second index
        if (first < last)  {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            if (f == l) {
                auto sbh = pos.size_before(f);
                return pos.towards_oh_sbh(this_t{}, first, f, sbh, last - sbh, fn);
            } else {
                assert(f < l);
                return pos.towards_oh(for_each_chunk_p_right_visitor{}, first, f, fn)
                    && pos.each_pred_i(for_each_chunk_p_visitor{}, f + 1, l, fn)
                    && pos.towards_oh(for_each_chunk_p_left_visitor{}, last - 1, l, fn);
            }
        }
        return true;
    }

    template <typename Pos, typename Fn>
    static bool visit_regular(Pos&& pos,
                              size_t first, size_t last,
                              Fn&& fn)
    {
        if (first < last)  {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            if (f == l)
                return pos.towards_oh(this_t{}, first, f, last, fn);
            else {
                assert(f < l);
                return pos.towards_oh(for_each_chunk_p_right_visitor{}, first, f, fn)
                    && pos.each_pred_i(for_each_chunk_p_visitor{}, f + 1, l, fn)
                    && pos.towards_oh(for_each_chunk_p_left_visitor{}, last - 1, l, fn);
            }
        }
        return true;
    }

    template <typename Pos, typename Fn>
    static bool visit_leaf(Pos&& pos,
                           size_t first, size_t last,
                           Fn&& fn)
    {
        auto data = pos.node()->leaf();
        if (first < last) {
            auto f = pos.index(first);
            auto l = pos.index(last - 1);
            return fn(data + f, data + l + 1);
        }
        return true;
    }
};

struct equals_visitor : visitor_base<equals_visitor>
{
    using this_t = equals_visitor;

    struct this_aux_t : visitor_base<this_aux_t>
    {
        template <typename PosR, typename PosL,typename Iter>
        static bool visit_inner(PosR&& posr,
                                count_t i, PosL&& posl,
                                Iter&& first, size_t idx)
        { return posl.nth_sub(i, this_t{}, posr, first, idx); }

        template <typename PosR, typename PosL,typename Iter>
        static bool visit_leaf(PosR&& posr,
                               count_t i, PosL&& posl,
                               Iter&& first, size_t idx)
        { return posl.nth_sub_leaf(i, this_t{}, posr, first, idx); }
    };

    struct rrb : visitor_base<rrb>
    {
        template <typename PosR, typename Iter, typename Node>
        static bool visit_node(PosR&& posr, Iter&& first,
                               Node* rootl, shift_t shiftl, size_t sizel)
        {
            assert(shiftl <= posr.shift());
            return shiftl == posr.shift()
                ? visit_maybe_relaxed_sub(rootl, shiftl, sizel,
                                          this_t{}, posr, first, size_t{})
                : posr.first_sub_inner(rrb{}, first, rootl, shiftl, sizel);
        }
    };

    template <typename Iter>
    static auto equal_chunk_p(Iter&& iter)
    {
        return [iter] (auto f, auto e) mutable {
            if (f == &*iter) {
                iter += e - f;
                return true;
            }
            for (; f != e; ++f, ++iter)
                if (*f != *iter)
                    return false;
            return true;
        };
    }

    template <typename PosL, typename PosR, typename Iter>
    static bool visit_relaxed(PosL&& posl, PosR&& posr,
                              Iter&& first, size_t idx)
    {
        auto nl = posl.node();
        auto nr = posr.node();
        if (nl == nr)
            return true;
        auto cl = posl.count();
        auto cr = posr.count();
        assert(cr > 0);
        auto sbr = size_t{};
        auto i = count_t{};
        auto j = count_t{};
        for (; i < cl; ++i) {
            auto sbl = posl.size_before(i);
            for (; j + 1 < cr && (sbr = posr.size_before(j)) < sbl; ++j);
            auto res = sbl == sbr
                ? posr.nth_sub(j, this_aux_t{}, i, posl, first, idx + sbl)
                : posl.nth_sub(i, for_each_chunk_p_visitor{},
                               this_t::equal_chunk_p(first + (idx + sbl)));
            if (!res) return false;
        }
        return true;
    }

    template <typename PosL, typename PosR, typename Iter>
    static std::enable_if_t<is_relaxed_v<PosR>, bool>
    visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
    {
        return this_t::visit_relaxed(posl, posr, first, idx);
    }

    template <typename PosL, typename PosR, typename Iter>
    static std::enable_if_t<!is_relaxed_v<PosR>, bool>
    visit_regular(PosL&& posl, PosR&& posr, Iter&& first, size_t idx)
    {
        return posl.count() >= posr.count()
            ? this_t::visit_regular(posl, posr.node())
            : this_t::visit_regular(posr, posl.node());
    }

    template <typename PosL, typename PosR, typename Iter>
    static bool visit_leaf(PosL&& posl,
                           PosR&& posr, Iter&& first, size_t idx)
    {
        if (posl.node() == posr.node())
            return true;
        auto cl = posl.count();
        auto cr = posr.count();
        auto mp = std::min(cl, cr);
        return
            std::equal(posl.node()->leaf(),
                       posl.node()->leaf() + mp,
                       posr.node()->leaf()) &&
            std::equal(posl.node()->leaf() + mp,
                       posl.node()->leaf() + posl.count(),
                       first + (idx + mp));
    }

    template <typename Pos, typename NodeT>
    static bool visit_regular(Pos&& pos, NodeT* other)
    {
        auto node = pos.node();
        return node == other
            || pos.each_pred_zip(this_t{}, other);
    }

    template <typename Pos, typename NodeT>
    static bool visit_leaf(Pos&& pos, NodeT* other)
    {
        auto node = pos.node();
        return node == other
            || std::equal(node->leaf(), node->leaf() + pos.count(),
                          other->leaf());
    }
};

template <typename NodeT>
struct update_visitor : visitor_base<update_visitor<NodeT>>
{
    using node_t = NodeT;
    using this_t = update_visitor;

    template <typename Pos, typename Fn>
    static node_t* visit_relaxed(Pos&& pos, size_t idx, Fn&& fn)
    {
        auto offset  = pos.index(idx);
        auto count   = pos.count();
        auto node    = node_t::make_inner_sr_n(count, pos.relaxed());
        try {
            auto child = pos.towards_oh(this_t{}, idx, offset, fn);
            node_t::do_copy_inner_sr(node, pos.node(), count);
            node->inner()[offset]->dec_unsafe();
            node->inner()[offset] = child;
            return node;
        } catch (...) {
            node_t::delete_inner_r(node, count);
            throw;
        }
    }

    template <typename Pos, typename Fn>
    static node_t* visit_regular(Pos&& pos, size_t idx, Fn&& fn)
    {
        auto offset  = pos.index(idx);
        auto count   = pos.count();
        auto node    = node_t::make_inner_n(count);
        try {
            auto child = pos.towards_oh_ch(this_t{}, idx, offset, count, fn);
            node_t::do_copy_inner(node, pos.node(), count);
            node->inner()[offset]->dec_unsafe();
            node->inner()[offset] = child;
            return node;
        } catch (...) {
            node_t::delete_inner(node, count);
            throw;
        }
    }

    template <typename Pos, typename Fn>
    static node_t* visit_leaf(Pos&& pos, size_t idx, Fn&& fn)
    {
        auto offset  = pos.index(idx);
        auto node    = node_t::copy_leaf(pos.node(), pos.count());
        try {
            node->leaf()[offset] = std::forward<Fn>(fn) (
                std::move(node->leaf()[offset]));
            return node;
        } catch (...) {
            node_t::delete_leaf(node, pos.count());
            throw;
        }
    }
};

struct dec_visitor : visitor_base<dec_visitor>
{
    using this_t = dec_visitor;

    template <typename Pos>
    static void visit_relaxed(Pos&& p)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each(this_t{});
            node_t::delete_inner_r(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_regular(Pos&& p)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each(this_t{});
            node_t::delete_inner(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_leaf(Pos&& p)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            node_t::delete_leaf(node, p.count());
        }
    }
};

template <typename NodeT>
void dec_leaf(NodeT* node, count_t n)
{
    make_leaf_sub_pos(node, n).visit(dec_visitor{});
}

template <typename NodeT>
void dec_inner(NodeT* node, shift_t shift, size_t size)
{
    visit_maybe_relaxed_sub(node, shift, size, dec_visitor());
}

template <typename NodeT>
void dec_relaxed(NodeT* node, shift_t shift)
{
    make_relaxed_pos(node, shift, node->relaxed()).visit(dec_visitor());
}

template <typename NodeT>
void dec_regular(NodeT* node, shift_t shift, size_t size)
{
    make_regular_pos(node, shift, size).visit(dec_visitor());
}

template <typename NodeT>
void dec_empty_regular(NodeT* node)
{
    make_empty_regular_pos(node).visit(dec_visitor());
}

template <typename NodeT>
struct get_mut_visitor : visitor_base<get_mut_visitor<NodeT>>
{
    using node_t  = NodeT;
    using this_t  = get_mut_visitor;
    using value_t = typename NodeT::value_t;
    using edit_t  = typename NodeT::edit_t;

    template <typename Pos>
    static value_t& visit_relaxed(Pos&& pos, size_t idx,
                                  edit_t e, node_t** location)
    {
        auto offset  = pos.index(idx);
        auto count   = pos.count();
        auto node    = pos.node();
        if (node->can_mutate(e)) {
            return pos.towards_oh(this_t{}, idx, offset,
                                  e, &node->inner()[offset]);
        } else {
            auto new_node = node_t::copy_inner_sr_e(e, node, count);
            try {
                auto& res = pos.towards_oh(this_t{}, idx, offset,
                                           e, &new_node->inner()[offset]);
                pos.visit(dec_visitor{});
                *location = new_node;
                return res;
            } catch (...) {
                dec_relaxed(new_node, pos.shift());
                throw;
            }
        }
    }

    template <typename Pos>
    static value_t& visit_regular(Pos&& pos, size_t idx,
                                  edit_t e, node_t** location)
    {
        assert(pos.node() == *location);
        auto offset  = pos.index(idx);
        auto count   = pos.count();
        auto node    = pos.node();
        if (node->can_mutate(e)) {
            return pos.towards_oh_ch(this_t{}, idx, offset, count,
                                     e, &node->inner()[offset]);
        } else {
            auto new_node = node_t::copy_inner_e(e, node, count);
            try {
                auto& res = pos.towards_oh_ch(this_t{}, idx, offset, count,
                                              e, &new_node->inner()[offset]);
                pos.visit(dec_visitor{});
                *location = new_node;
                return res;
            } catch (...) {
                dec_regular(new_node, pos.shift(), pos.size());
                throw;
            }
        }
    }

    template <typename Pos>
    static value_t& visit_leaf(Pos&& pos, size_t idx,
                               edit_t e, node_t** location)
    {
        assert(pos.node() == *location);
        auto node = pos.node();
        if (node->can_mutate(e)) {
            return node->leaf() [pos.index(idx)];
        } else {
            auto new_node = node_t::copy_leaf_e(e, pos.node(), pos.count());
            pos.visit(dec_visitor{});
            *location = new_node;
            return new_node->leaf() [pos.index(idx)];
        }
    }
};

template <typename NodeT, bool Mutating = true>
struct push_tail_mut_visitor
    : visitor_base<push_tail_mut_visitor<NodeT, Mutating>>
{
    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    using this_t = push_tail_mut_visitor;
    using this_no_mut_t = push_tail_mut_visitor<NodeT, false>;
    using node_t = NodeT;
    using edit_t = typename NodeT::edit_t;

    template <typename Pos>
    static node_t* visit_relaxed(Pos&& pos, edit_t e, node_t* tail, count_t ts)
    {
        auto node        = pos.node();
        auto level       = pos.shift();
        auto idx         = pos.count() - 1;
        auto children    = pos.size(idx);
        auto new_idx     = children == size_t{1} << level || level == BL
            ? idx + 1 : idx;
        auto new_child = static_cast<node_t*>(nullptr);
        auto mutate      = Mutating && node->can_mutate(e);

        if (new_idx >= branches<B>)
            return nullptr;
        else if (idx == new_idx) {
            new_child = mutate
                ? pos.last_oh_csh(this_t{}, idx, children, e, tail, ts)
                : pos.last_oh_csh(this_no_mut_t{}, idx, children, e, tail, ts);
            if (!new_child) {
                if (++new_idx < branches<B>)
                    new_child = node_t::make_path_e(e, level - B, tail);
                else
                    return nullptr;
            }
        } else
            new_child = node_t::make_path_e(e, level - B, tail);

        if (mutate) {
            auto count = new_idx + 1;
            auto relaxed = node->ensure_mutable_relaxed_n(e, new_idx);
            node->inner()[new_idx]  = new_child;
            relaxed->d.sizes[new_idx] = pos.size() + ts;
            relaxed->d.count = count;
            return node;
        } else {
            try {
                auto count    = new_idx + 1;
                auto new_node = node_t::copy_inner_r_e(e, pos.node(), new_idx);
                auto relaxed  = new_node->relaxed();
                new_node->inner()[new_idx] = new_child;
                relaxed->d.sizes[new_idx] = pos.size() + ts;
                relaxed->d.count = count;
                if (Mutating) pos.visit(dec_visitor{});
                return new_node;
            } catch (...) {
                auto shift = pos.shift();
                auto size  = new_idx == idx ? children + ts : ts;
                if (shift > BL) {
                    tail->inc();
                    dec_inner(new_child, shift - B, size);
                }
                throw;
            }
        }
    }

    template <typename Pos, typename... Args>
    static node_t* visit_regular(Pos&& pos, edit_t e, node_t* tail, Args&&...)
    {
        assert((pos.size() & mask<BL>) == 0);
        auto node        = pos.node();
        auto idx         = pos.index(pos.size() - 1);
        auto new_idx     = pos.index(pos.size() + branches<BL> - 1);
        auto mutate      = Mutating && node->can_mutate(e);
        if (mutate) {
            node->inner()[new_idx] =
                idx == new_idx  ? pos.last_oh(this_t{}, idx, e, tail)
                /* otherwise */ : node_t::make_path_e(e, pos.shift() - B, tail);
            return node;
        } else {
            auto new_parent  = node_t::make_inner_e(e);
            try {
                new_parent->inner()[new_idx] =
                    idx == new_idx  ? pos.last_oh(this_no_mut_t{}, idx, e, tail)
                    /* otherwise */ : node_t::make_path_e(e, pos.shift() - B, tail);
                node_t::do_copy_inner(new_parent, node, new_idx);
                if (Mutating) pos.visit(dec_visitor{});
                return new_parent;
            } catch (...) {
                node_t::delete_inner_e(new_parent);
                throw;
            }
        }
    }

    template <typename Pos, typename... Args>
    static node_t* visit_leaf(Pos&& pos, edit_t e, node_t* tail, Args&&...)
    { IMMER_UNREACHABLE; }
};

template <typename NodeT>
struct push_tail_visitor : visitor_base<push_tail_visitor<NodeT>>
{
    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    using this_t = push_tail_visitor;
    using node_t = NodeT;

    template <typename Pos>
    static node_t* visit_relaxed(Pos&& pos, node_t* tail, count_t ts)
    {
        auto level       = pos.shift();
        auto idx         = pos.count() - 1;
        auto children    = pos.size(idx);
        auto new_idx     = children == size_t{1} << level || level == BL
            ? idx + 1 : idx;
        auto new_child = static_cast<node_t*>(nullptr);
        if (new_idx >= branches<B>)
            return nullptr;
        else if (idx == new_idx) {
            new_child = pos.last_oh_csh(this_t{}, idx, children, tail, ts);
            if (!new_child) {
                if (++new_idx < branches<B>)
                    new_child = node_t::make_path(level - B, tail);
                else
                    return nullptr;
            }
        } else
            new_child = node_t::make_path(level - B, tail);
        try {
            auto count       = new_idx + 1;
            auto new_parent  = node_t::copy_inner_r_n(count, pos.node(), new_idx);
            auto new_relaxed = new_parent->relaxed();
            new_parent->inner()[new_idx] = new_child;
            new_relaxed->d.sizes[new_idx] = pos.size() + ts;
            new_relaxed->d.count = count;
            return new_parent;
        } catch (...) {
            auto shift = pos.shift();
            auto size  = new_idx == idx ? children + ts : ts;
            if (shift > BL) {
                tail->inc();
                dec_inner(new_child, shift - B, size);
            }
            throw;
        }
    }

    template <typename Pos, typename... Args>
    static node_t* visit_regular(Pos&& pos, node_t* tail, Args&&...)
    {
        assert((pos.size() & mask<BL>) == 0);
        auto idx         = pos.index(pos.size() - 1);
        auto new_idx     = pos.index(pos.size() + branches<BL> - 1);
        auto count       = new_idx + 1;
        auto new_parent  = node_t::make_inner_n(count);
        try {
            new_parent->inner()[new_idx] =
                idx == new_idx  ? pos.last_oh(this_t{}, idx, tail)
                /* otherwise */ : node_t::make_path(pos.shift() - B, tail);
        } catch (...) {
            node_t::delete_inner(new_parent, count);
            throw;
        }
        return node_t::do_copy_inner(new_parent, pos.node(), new_idx);
    }

    template <typename Pos, typename... Args>
    static node_t* visit_leaf(Pos&& pos, node_t* tail, Args&&...)
    { IMMER_UNREACHABLE; }
};

struct dec_right_visitor : visitor_base<dec_right_visitor>
{
    using this_t = dec_right_visitor;
    using dec_t  = dec_visitor;

    template <typename Pos>
    static void visit_relaxed(Pos&& p, count_t idx)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each_right(dec_t{}, idx);
            node_t::delete_inner_r(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_regular(Pos&& p, count_t idx)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each_right(dec_t{}, idx);
            node_t::delete_inner(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_leaf(Pos&& p, count_t idx)
    { IMMER_UNREACHABLE; }
};

template <typename NodeT, bool Collapse=true, bool Mutating=true>
struct slice_right_mut_visitor
    : visitor_base<slice_right_mut_visitor<NodeT, Collapse, Mutating>>
{
    using node_t = NodeT;
    using this_t = slice_right_mut_visitor;
    using edit_t = typename NodeT::edit_t;

    // returns a new shift, new root, the new tail size and the new tail
    using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
    using no_collapse_t = slice_right_mut_visitor<NodeT, false, true>;
    using no_collapse_no_mut_t = slice_right_mut_visitor<NodeT, false, false>;
    using no_mut_t = slice_right_mut_visitor<NodeT, Collapse, false>;

    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    template <typename PosT>
    static result_t visit_relaxed(PosT&& pos, size_t last, edit_t e)
    {
        auto idx = pos.index(last);
        auto node = pos.node();
        auto mutate = Mutating && node->can_mutate(e);
        if (Collapse && idx == 0) {
            auto res = mutate
                ? pos.towards_oh(this_t{}, last, idx, e)
                : pos.towards_oh(no_mut_t{}, last, idx, e);
            if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
            return res;
        } else {
            using std::get;
            auto subs = mutate
                ? pos.towards_oh(no_collapse_t{}, last, idx, e)
                : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
            auto next = get<1>(subs);
            auto ts   = get<2>(subs);
            auto tail = get<3>(subs);
            try {
                if (next) {
                    if (mutate) {
                        auto nodr = node->ensure_mutable_relaxed_n(e, idx);
                        pos.each_right(dec_visitor{}, idx + 1);
                        node->inner()[idx] = next;
                        nodr->d.sizes[idx] = last + 1 - ts;
                        nodr->d.count = idx + 1;
                        return { pos.shift(), node, ts, tail };
                    } else {
                        auto newn = node_t::copy_inner_r_e(e, node, idx);
                        auto newr = newn->relaxed();
                        newn->inner()[idx] = next;
                        newr->d.sizes[idx] = last + 1 - ts;
                        newr->d.count = idx + 1;
                        if (Mutating) pos.visit(dec_visitor{});
                        return { pos.shift(), newn, ts, tail };
                    }
                } else if (idx == 0) {
                    if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
                    return { pos.shift(), nullptr, ts, tail };
                } else if (Collapse && idx == 1 && pos.shift() > BL) {
                    auto newn = pos.node()->inner()[0];
                    if (!mutate) newn->inc();
                    if (Mutating) pos.visit(dec_right_visitor{}, count_t{2});
                    return { pos.shift() - B, newn, ts, tail };
                } else {
                    if (mutate) {
                        pos.each_right(dec_visitor{}, idx + 1);
                        node->ensure_mutable_relaxed_n(e, idx)->d.count = idx;
                        return { pos.shift(), node, ts, tail };
                    } else {
                        auto newn = node_t::copy_inner_r_e(e, node, idx);
                        if (Mutating) pos.visit(dec_visitor{});
                        return { pos.shift(), newn, ts, tail };
                    }
                }
            } catch (...) {
                assert(!mutate);
                assert(!next || pos.shift() > BL);
                if (next)
                    dec_inner(next, pos.shift() - B,
                              last + 1 - ts - pos.size_before(idx));
                dec_leaf(tail, ts);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_regular(PosT&& pos, size_t last, edit_t e)
    {
        auto idx = pos.index(last);
        auto node = pos.node();
        auto mutate = Mutating && node->can_mutate(e);
        if (Collapse && idx == 0) {
            auto res = mutate
                ? pos.towards_oh(this_t{}, last, idx, e)
                : pos.towards_oh(no_mut_t{}, last, idx, e);
            if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
            return res;
        } else {
            using std::get;
            auto subs = mutate
                ? pos.towards_oh(no_collapse_t{}, last, idx, e)
                : pos.towards_oh(no_collapse_no_mut_t{}, last, idx, e);
            auto next = get<1>(subs);
            auto ts   = get<2>(subs);
            auto tail = get<3>(subs);
            try {
                if (next) {
                    if (mutate) {
                        node->inner()[idx] = next;
                        pos.each_right(dec_visitor{}, idx + 1);
                        return { pos.shift(), node, ts, tail };
                    } else {
                        auto newn  = node_t::copy_inner_e(e, node, idx);
                        newn->inner()[idx] = next;
                        if (Mutating) pos.visit(dec_visitor{});
                        return { pos.shift(), newn, ts, tail };
                    }
                } else if (idx == 0) {
                    if (Mutating) pos.visit(dec_right_visitor{}, count_t{1});
                    return { pos.shift(), nullptr, ts, tail };
                } else if (Collapse && idx == 1 && pos.shift() > BL) {
                    auto newn = pos.node()->inner()[0];
                    if (!mutate) newn->inc();
                    if (Mutating) pos.visit(dec_right_visitor{}, count_t{2});
                    return { pos.shift() - B, newn, ts, tail };
                } else {
                    if (mutate) {
                        pos.each_right(dec_visitor{}, idx + 1);
                        return { pos.shift(), node, ts, tail };
                    } else {
                        auto newn = node_t::copy_inner_e(e, node, idx);
                        if (Mutating) pos.visit(dec_visitor{});
                        return { pos.shift(), newn, ts, tail };
                    }
                }
            } catch (...) {
                assert(!mutate);
                assert(!next || pos.shift() > BL);
                assert(tail);
                if (next) dec_regular(next, pos.shift() - B, last + 1 - ts);
                dec_leaf(tail, ts);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_leaf(PosT&& pos, size_t last, edit_t e)
    {
        auto old_tail_size = pos.count();
        auto new_tail_size = pos.index(last) + 1;
        auto node          = pos.node();
        auto mutate        = Mutating && node->can_mutate(e);
        if (new_tail_size == old_tail_size) {
            if (!Mutating) node->inc();
            return { 0, nullptr, new_tail_size, node };
        } else if (mutate) {
            destroy_n(node->leaf() + new_tail_size,
                      old_tail_size - new_tail_size);
            return { 0, nullptr, new_tail_size, node };
        } else {
            auto new_tail = node_t::copy_leaf_e(e, node, new_tail_size);
            if (Mutating) pos.visit(dec_visitor{});
            return { 0, nullptr, new_tail_size, new_tail };
        }
    }
};

template <typename NodeT, bool Collapse=true>
struct slice_right_visitor : visitor_base<slice_right_visitor<NodeT, Collapse>>
{
    using node_t = NodeT;
    using this_t = slice_right_visitor;

    // returns a new shift, new root, the new tail size and the new tail
    using result_t = std::tuple<shift_t, NodeT*, count_t, NodeT*>;
    using no_collapse_t = slice_right_visitor<NodeT, false>;

    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    template <typename PosT>
    static result_t visit_relaxed(PosT&& pos, size_t last)
    {
        auto idx = pos.index(last);
        if (Collapse && idx == 0) {
            return pos.towards_oh(this_t{}, last, idx);
        } else {
            using std::get;
            auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
            auto next = get<1>(subs);
            auto ts   = get<2>(subs);
            auto tail = get<3>(subs);
            try {
                if (next) {
                    auto count = idx + 1;
                    auto newn  = node_t::copy_inner_r_n(count, pos.node(), idx);
                    auto newr  = newn->relaxed();
                    newn->inner()[idx] = next;
                    newr->d.sizes[idx] = last + 1 - ts;
                    newr->d.count = count;
                    return { pos.shift(), newn, ts, tail };
                } else if (idx == 0) {
                    return { pos.shift(), nullptr, ts, tail };
                } else if (Collapse && idx == 1 && pos.shift() > BL) {
                    auto newn = pos.node()->inner()[0];
                    return { pos.shift() - B, newn->inc(), ts, tail };
                } else {
                    auto newn = node_t::copy_inner_r(pos.node(), idx);
                    return { pos.shift(), newn, ts, tail };
                }
            } catch (...) {
                assert(!next || pos.shift() > BL);
                if (next) dec_inner(next, pos.shift() - B,
                                    last + 1 - ts - pos.size_before(idx));
                if (tail) dec_leaf(tail, ts);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_regular(PosT&& pos, size_t last)
    {
        auto idx = pos.index(last);
        if (Collapse && idx == 0) {
            return pos.towards_oh(this_t{}, last, idx);
        } else {
            using std::get;
            auto subs = pos.towards_oh(no_collapse_t{}, last, idx);
            auto next = get<1>(subs);
            auto ts   = get<2>(subs);
            auto tail = get<3>(subs);
            try {
                if (next) {
                    auto newn  = node_t::copy_inner_n(idx + 1, pos.node(), idx);
                    newn->inner()[idx] = next;
                    return { pos.shift(), newn, ts, tail };
                } else if (idx == 0) {
                    return { pos.shift(), nullptr, ts, tail };
                } else if (Collapse && idx == 1 && pos.shift() > BL) {
                    auto newn = pos.node()->inner()[0];
                    return { pos.shift() - B, newn->inc(), ts, tail };
                } else {
                    auto newn = node_t::copy_inner_n(idx, pos.node(), idx);
                    return { pos.shift(), newn, ts, tail };
                }
            } catch (...) {
                assert(!next || pos.shift() > BL);
                assert(tail);
                if (next) dec_regular(next, pos.shift() - B, last + 1 - ts);
                dec_leaf(tail, ts);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_leaf(PosT&& pos, size_t last)
    {
        auto old_tail_size = pos.count();
        auto new_tail_size = pos.index(last) + 1;
        auto new_tail      = new_tail_size == old_tail_size
            ? pos.node()->inc()
            : node_t::copy_leaf(pos.node(), new_tail_size);
        return { 0, nullptr, new_tail_size, new_tail };
    }
};

struct dec_left_visitor : visitor_base<dec_left_visitor>
{
    using this_t = dec_left_visitor;
    using dec_t  = dec_visitor;

    template <typename Pos>
    static void visit_relaxed(Pos&& p, count_t idx)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each_left(dec_t{}, idx);
            node_t::delete_inner_r(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_regular(Pos&& p, count_t idx)
    {
        using node_t = node_type<Pos>;
        auto node = p.node();
        if (node->dec()) {
            p.each_left(dec_t{}, idx);
            node_t::delete_inner(node, p.count());
        }
    }

    template <typename Pos>
    static void visit_leaf(Pos&& p, count_t idx)
    { IMMER_UNREACHABLE; }
};

template <typename NodeT, bool Collapse=true, bool Mutating=true>
struct slice_left_mut_visitor
    : visitor_base<slice_left_mut_visitor<NodeT, Collapse, Mutating>>
{
    using node_t = NodeT;
    using this_t = slice_left_mut_visitor;
    using edit_t = typename NodeT::edit_t;
    using value_t = typename NodeT::value_t;
    using relaxed_t = typename NodeT::relaxed_t;
    // returns a new shift and new root
    using result_t = std::tuple<shift_t, NodeT*>;

    using no_collapse_t = slice_left_mut_visitor<NodeT, false, true>;
    using no_collapse_no_mut_t = slice_left_mut_visitor<NodeT, false, false>;
    using no_mut_t = slice_left_mut_visitor<NodeT, Collapse, false>;

    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    template <typename PosT>
    static result_t visit_relaxed(PosT&& pos, size_t first, edit_t e)
    {
        auto idx    = pos.subindex(first);
        auto count  = pos.count();
        auto node   = pos.node();
        auto mutate = Mutating && node->can_mutate(e);
        auto left_size  = pos.size_before(idx);
        auto child_size = pos.size_sbh(idx, left_size);
        auto dropped_size = first;
        auto child_dropped_size = dropped_size - left_size;
        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
            auto r = mutate
                ? pos.towards_sub_oh(this_t{}, first, idx, e)
                : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
            if (Mutating) pos.visit(dec_left_visitor{}, idx);
            return r;
        } else {
            using std::get;
            auto newn = mutate
                ? (node->ensure_mutable_relaxed(e), node)
                : node_t::make_inner_r_e(e);
            auto newr = newn->relaxed();
            auto newcount = count - idx;
            auto new_child_size = child_size - child_dropped_size;
            try {
                auto subs  = mutate
                    ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
                    : pos.towards_sub_oh(no_collapse_no_mut_t{}, first, idx, e);
                if (mutate) pos.each_left(dec_visitor{}, idx);
                pos.copy_sizes(idx + 1, newcount - 1,
                               new_child_size, newr->d.sizes + 1);
                std::uninitialized_copy(node->inner() + idx + 1,
                                        node->inner() + count,
                                        newn->inner() + 1);
                newn->inner()[0] = get<1>(subs);
                newr->d.sizes[0] = new_child_size;
                newr->d.count = newcount;
                if (!mutate) {
                    node_t::inc_nodes(newn->inner() + 1, newcount - 1);
                    if (Mutating) pos.visit(dec_visitor{});
                }
                return { pos.shift(), newn };
            } catch (...) {
                if (!mutate) node_t::delete_inner_r_e(newn);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_regular(PosT&& pos, size_t first, edit_t e)
    {
        auto idx    = pos.subindex(first);
        auto count  = pos.count();
        auto node   = pos.node();
        auto mutate = Mutating
            // this is more restrictive than actually needed because
            // it causes the algorithm to also avoid mutating the leaf
            // in place
            && !node_t::embed_relaxed
            && node->can_mutate(e);
        auto left_size  = pos.size_before(idx);
        auto child_size = pos.size_sbh(idx, left_size);
        auto dropped_size = first;
        auto child_dropped_size = dropped_size - left_size;
        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
            auto r = mutate
                ? pos.towards_sub_oh(this_t{}, first, idx, e)
                : pos.towards_sub_oh(no_mut_t{}, first, idx, e);
            if (Mutating) pos.visit(dec_left_visitor{}, idx);
            return r;
        } else {
            using std::get;
            // if possible, we convert the node to a relaxed one
            // simply by allocating a `relaxed_t` size table for
            // it... maybe some of this magic should be moved as a
            // `node<...>` static method...
            auto newcount = count - idx;
            auto newn = mutate
                ? (node->impl.d.data.inner.relaxed = new (
                       node_t::heap::allocate(
                           node_t::max_sizeof_relaxed,
                           norefs_tag{})) relaxed_t,
                   node)
                : node_t::make_inner_r_e(e);
            auto newr = newn->relaxed();
            try {
                auto subs = mutate
                    ? pos.towards_sub_oh(no_collapse_t{}, first, idx, e)
                    : pos.towards_sub_oh(no_collapse_no_mut_t{}, first, idx, e);
                if (mutate) pos.each_left(dec_visitor{}, idx);
                newr->d.sizes[0] = child_size - child_dropped_size;
                pos.copy_sizes(idx + 1, newcount - 1,
                               newr->d.sizes[0], newr->d.sizes + 1);
                newr->d.count = newcount;
                newn->inner()[0] = get<1>(subs);
                std::uninitialized_copy(node->inner() + idx + 1,
                                        node->inner() + count,
                                        newn->inner() + 1);
                if (!mutate) {
                    node_t::inc_nodes(newn->inner() + 1, newcount - 1);
                    if (Mutating) pos.visit(dec_visitor{});
                }
                return { pos.shift(), newn };
            } catch (...) {
                if (!mutate) node_t::delete_inner_r_e(newn);
                else {
                    // restore the regular node that we were
                    // attempting to relax...
                    node_t::heap::deallocate(node_t::max_sizeof_relaxed,
                                             node->impl.d.data.inner.relaxed);
                    node->impl.d.data.inner.relaxed = nullptr;
                }
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_leaf(PosT&& pos, size_t first, edit_t e)
    {
        auto node   = pos.node();
        auto idx    = pos.index(first);
        auto count  = pos.count();
        auto mutate = Mutating
            && std::is_nothrow_move_constructible<value_t>::value
            && node->can_mutate(e);
        if (mutate) {
            auto data = node->leaf();
            auto newcount = count - idx;
            std::move(data + idx, data + count, data);
            destroy_n(data + newcount, idx);
            return { 0, node };
        } else {
            auto newn = node_t::copy_leaf_e(e, node, idx, count);
            if (Mutating) pos.visit(dec_visitor{});
            return { 0, newn };
        }
    }
};

template <typename NodeT, bool Collapse=true>
struct slice_left_visitor : visitor_base<slice_left_visitor<NodeT, Collapse>>
{
    using node_t = NodeT;
    using this_t = slice_left_visitor;

    // returns a new shift and new root
    using result_t = std::tuple<shift_t, NodeT*>;
    using no_collapse_t = slice_left_visitor<NodeT, false>;

    static constexpr auto B  = NodeT::bits;
    static constexpr auto BL = NodeT::bits_leaf;

    template <typename PosT>
    static result_t visit_inner(PosT&& pos, size_t first)
    {
        auto idx    = pos.subindex(first);
        auto count  = pos.count();
        auto left_size  = pos.size_before(idx);
        auto child_size = pos.size_sbh(idx, left_size);
        auto dropped_size = first;
        auto child_dropped_size = dropped_size - left_size;
        if (Collapse && pos.shift() > BL && idx == pos.count() - 1) {
            return pos.towards_sub_oh(this_t{}, first, idx);
        } else {
            using std::get;
            auto n     = pos.node();
            auto newc  = count - idx;
            auto newn  = node_t::make_inner_r_n(newc);
            try {
                auto subs  = pos.towards_sub_oh(no_collapse_t{}, first, idx);
                auto newr  = newn->relaxed();
                newr->d.count = count - idx;
                newr->d.sizes[0] = child_size - child_dropped_size;
                pos.copy_sizes(idx + 1, newr->d.count - 1,
                               newr->d.sizes[0], newr->d.sizes + 1);
                assert(newr->d.sizes[newr->d.count - 1] == pos.size() - dropped_size);
                newn->inner()[0] = get<1>(subs);
                std::uninitialized_copy(n->inner() + idx + 1,
                                        n->inner() + count,
                                        newn->inner() + 1);
                node_t::inc_nodes(newn->inner() + 1, newr->d.count - 1);
                return { pos.shift(), newn };
            } catch (...) {
                node_t::delete_inner_r(newn, newc);
                throw;
            }
        }
    }

    template <typename PosT>
    static result_t visit_leaf(PosT&& pos, size_t first)
    {
        auto n = node_t::copy_leaf(pos.node(), pos.index(first), pos.count());
        return { 0, n };
    }
};

template <typename Node>
struct concat_center_pos
{
    static constexpr auto B  = Node::bits;
    static constexpr auto BL = Node::bits_leaf;

    static constexpr count_t max_children = 3;

    using node_t = Node;
    using edit_t = typename Node::edit_t;

    shift_t shift_ = 0u;
    count_t count_ = 0u;
    node_t* nodes_[max_children];
    size_t  sizes_[max_children];

    auto shift() const { return shift_; }

    concat_center_pos(shift_t s,
                      Node* n0, size_t s0)
        : shift_{s}, count_{1}, nodes_{n0}, sizes_{s0} {}

    concat_center_pos(shift_t s,
                      Node* n0, size_t s0,
                      Node* n1, size_t s1)
        : shift_{s}, count_{2}, nodes_{n0, n1}, sizes_{s0, s1}  {}

    concat_center_pos(shift_t s,
                      Node* n0, size_t s0,
                      Node* n1, size_t s1,
                      Node* n2, size_t s2)
        : shift_{s}, count_{3}, nodes_{n0, n1, n2}, sizes_{s0, s1, s2} {}

    template <typename Visitor, typename... Args>
    void each_sub(Visitor v, Args&& ...args)
    {
        if (shift_ == BL) {
            for (auto i = count_t{0}; i < count_; ++i)
                make_leaf_sub_pos(nodes_[i], sizes_[i]).visit(v, args...);
        } else {
            for (auto i = count_t{0}; i < count_; ++i)
                make_relaxed_pos(nodes_[i], shift_ - B, nodes_[i]->relaxed()).visit(v, args...);
        }
    }

    relaxed_pos<Node> realize() &&
    {
        if (count_ > 1) {
            try {
                auto result = node_t::make_inner_r_n(count_);
                auto r      = result->relaxed();
                r->d.count    = count_;
                std::copy(nodes_, nodes_ + count_, result->inner());
                std::copy(sizes_, sizes_ + count_, r->d.sizes);
                return { result, shift_, r };
            } catch (...) {
                each_sub(dec_visitor{});
                throw;
            }
        } else {
            assert(shift_ >= B + BL);
            return { nodes_[0], shift_ - B, nodes_[0]->relaxed() };
        }
    }

    relaxed_pos<Node> realize_e(edit_t e)
    {
        if (count_ > 1) {
            auto result = node_t::make_inner_r_e(e);
            auto r      = result->relaxed();
            r->d.count    = count_;
            std::copy(nodes_, nodes_ + count_, result->inner());
            std::copy(sizes_, sizes_ + count_, r->d.sizes);
            return { result, shift_, r };
        } else {
            assert(shift_ >= B + BL);
            return { nodes_[0], shift_ - B, nodes_[0]->relaxed() };
        }
    }
};

template <typename Node>
struct concat_merger
{
    using node_t = Node;
    static constexpr auto B  = Node::bits;
    static constexpr auto BL = Node::bits_leaf;

    using result_t = concat_center_pos<Node>;

    count_t* curr_;
    count_t  n_;
    result_t result_;

    concat_merger(shift_t shift, count_t* counts, count_t n)
        : curr_{counts}
        , n_{n}
        , result_{shift + B, node_t::make_inner_r_n(std::min(n_, branches<B>)), 0}
    {}

    node_t*  to_        = {};
    count_t  to_offset_ = {};
    size_t   to_size_   = {};

    void add_child(node_t* p, size_t size)
    {
        ++curr_;
        auto parent  = result_.nodes_[result_.count_ - 1];
        auto relaxed = parent->relaxed();
        if (relaxed->d.count == branches<B>) {
            assert(result_.count_ < result_t::max_children);
            n_ -= branches<B>;
            parent  = node_t::make_inner_r_n(std::min(n_, branches<B>));
            relaxed = parent->relaxed();
            result_.nodes_[result_.count_] = parent;
            result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
            ++result_.count_;
        }
        auto idx = relaxed->d.count++;
        result_.sizes_[result_.count_ - 1] += size;
        relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
        parent->inner() [idx] = p;
    };

    template <typename Pos>
    void merge_leaf(Pos&& p)
    {
        auto from       = p.node();
        auto from_size  = p.size();
        auto from_count = p.count();
        assert(from_size);
        if (!to_ && *curr_ == from_count) {
            add_child(from, from_size);
            from->inc();
        } else {
            auto from_offset = count_t{};
            auto from_data   = from->leaf();
            do {
                if (!to_) {
                    to_ = node_t::make_leaf_n(*curr_);
                    to_offset_ = 0;
                }
                auto data = to_->leaf();
                auto to_copy = std::min(from_count - from_offset,
                                        *curr_ - to_offset_);
                std::uninitialized_copy(from_data + from_offset,
                                        from_data + from_offset + to_copy,
                                        data + to_offset_);
                to_offset_  += to_copy;
                from_offset += to_copy;
                if (*curr_ == to_offset_) {
                    add_child(to_, to_offset_);
                    to_ = nullptr;
                }
            } while (from_offset != from_count);
        }
    }

    template <typename Pos>
    void merge_inner(Pos&& p)
    {
        auto from       = p.node();
        auto from_size  = p.size();
        auto from_count = p.count();
        assert(from_size);
        if (!to_ && *curr_ == from_count) {
            add_child(from, from_size);
            from->inc();
        } else {
            auto from_offset = count_t{};
            auto from_data  = from->inner();
            do {
                if (!to_) {
                    to_ = node_t::make_inner_r_n(*curr_);
                    to_offset_ = 0;
                    to_size_   = 0;
                }
                auto data    = to_->inner();
                auto to_copy = std::min(from_count - from_offset,
                                        *curr_ - to_offset_);
                std::uninitialized_copy(from_data + from_offset,
                                        from_data + from_offset + to_copy,
                                        data + to_offset_);
                node_t::inc_nodes(from_data + from_offset, to_copy);
                auto sizes   = to_->relaxed()->d.sizes;
                p.copy_sizes(from_offset, to_copy,
                             to_size_, sizes + to_offset_);
                to_offset_  += to_copy;
                from_offset += to_copy;
                to_size_     = sizes[to_offset_ - 1];
                if (*curr_ == to_offset_) {
                    to_->relaxed()->d.count = to_offset_;
                    add_child(to_, to_size_);
                    to_ = nullptr;
                }
            } while (from_offset != from_count);
        }
    }

    concat_center_pos<Node> finish() const
    {
        assert(!to_);
        return result_;
    }

    void abort()
    {
        auto shift = result_.shift_ - B;
        if (to_) {
            if (shift == BL)
                node_t::delete_leaf(to_, to_offset_);
            else {
                to_->relaxed()->d.count = to_offset_;
                dec_relaxed(to_, shift - B);
            }
        }
        result_.each_sub(dec_visitor());
    }
};

struct concat_merger_visitor : visitor_base<concat_merger_visitor>
{
    using this_t = concat_merger_visitor;

    template <typename Pos, typename Merger>
    static void visit_inner(Pos&& p, Merger& merger)
    { merger.merge_inner(p); }

    template <typename Pos, typename Merger>
    static void visit_leaf(Pos&& p, Merger& merger)
    { merger.merge_leaf(p); }
};

struct concat_rebalance_plan_fill_visitor
    : visitor_base<concat_rebalance_plan_fill_visitor>
{
    using this_t = concat_rebalance_plan_fill_visitor;

    template <typename Pos, typename Plan>
    static void visit_node(Pos&& p, Plan& plan)
    {
        auto count = p.count();
        assert(plan.n < Plan::max_children);
        plan.counts[plan.n++] = count;
        plan.total += count;
    }
};

template <bits_t B, bits_t BL>
struct concat_rebalance_plan
{
    static constexpr auto max_children = 2 * branches<B> + 1;

    count_t counts [max_children];
    count_t n = 0u;
    count_t total = 0u;

    template <typename LPos, typename CPos, typename RPos>
    void fill(LPos&& lpos, CPos&& cpos, RPos&& rpos)
    {
        assert(n == 0u);
        assert(total == 0u);
        using visitor_t = concat_rebalance_plan_fill_visitor;
        lpos.each_left_sub(visitor_t{}, *this);
        cpos.each_sub(visitor_t{}, *this);
        rpos.each_right_sub(visitor_t{}, *this);
    }

    void shuffle(shift_t shift)
    {
        // gcc seems to not really understand this code... :(
#if !defined(_MSC_VER)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Warray-bounds"
#endif
        constexpr count_t rrb_extras    = 2;
        constexpr count_t rrb_invariant = 1;
        const auto bits     = shift == BL ? BL : B;
        const auto branches = count_t{1} << bits;
        const auto optimal  = ((total - 1) >> bits) + 1;
        count_t i = 0;
        while (n >= optimal + rrb_extras) {
            // skip ok nodes
            while (counts[i] > branches - rrb_invariant) i++;
            // short node, redistribute
            auto remaining = counts[i];
            do {
                auto count = std::min(remaining + counts[i+1], branches);
                counts[i] = count;
                remaining +=  counts[i + 1] - count;
                ++i;
            } while (remaining > 0);
            // remove node
            std::move(counts + i + 1, counts + n, counts + i);
            --n;
            --i;
        }
#if !defined(_MSC_VER)
#pragma GCC diagnostic pop
#endif
    }

    template <typename LPos, typename CPos, typename RPos>
    concat_center_pos<node_type<CPos>>
    merge(LPos&& lpos, CPos&& cpos, RPos&& rpos)
    {
        using node_t    = node_type<CPos>;
        using merger_t  = concat_merger<node_t>;
        using visitor_t = concat_merger_visitor;
        auto merger = merger_t{cpos.shift(), counts, n};
        try {
            lpos.each_left_sub(visitor_t{}, merger);
            cpos.each_sub(visitor_t{}, merger);
            rpos.each_right_sub(visitor_t{}, merger);
            cpos.each_sub(dec_visitor{});
            return merger.finish();
        } catch (...) {
            merger.abort();
            throw;
        }
    }
};

template <typename Node, typename LPos, typename CPos, typename RPos>
concat_center_pos<Node>
concat_rebalance(LPos&& lpos, CPos&& cpos, RPos&& rpos)
{
    auto plan = concat_rebalance_plan<Node::bits, Node::bits_leaf>{};
    plan.fill(lpos, cpos, rpos);
    plan.shuffle(cpos.shift());
    try {
        return plan.merge(lpos, cpos, rpos);
    } catch (...) {
        cpos.each_sub(dec_visitor{});
        throw;
    }
}

template <typename Node, typename LPos, typename TPos, typename RPos>
concat_center_pos<Node>
concat_leafs(LPos&& lpos, TPos&& tpos, RPos&& rpos)
{
    static_assert(Node::bits >= 2, "");
    assert(lpos.shift() == tpos.shift());
    assert(lpos.shift() == rpos.shift());
    assert(lpos.shift() == 0);
    if (tpos.count() > 0)
        return {
            Node::bits_leaf,
            lpos.node()->inc(), lpos.count(),
            tpos.node()->inc(), tpos.count(),
            rpos.node()->inc(), rpos.count(),
        };
    else
        return {
            Node::bits_leaf,
            lpos.node()->inc(), lpos.count(),
            rpos.node()->inc(), rpos.count(),
        };
}

template <typename Node>
struct concat_left_visitor;
template <typename Node>
struct concat_right_visitor;
template <typename Node>
struct concat_both_visitor;

template <typename Node, typename LPos, typename TPos, typename RPos>
concat_center_pos<Node>
concat_inners(LPos&& lpos, TPos&& tpos, RPos&& rpos)
{
    auto lshift = lpos.shift();
    auto rshift = rpos.shift();
    if (lshift > rshift) {
        auto cpos = lpos.last_sub(concat_left_visitor<Node>{}, tpos, rpos);
        return concat_rebalance<Node>(lpos, cpos, null_sub_pos{});
    } else if (lshift < rshift) {
        auto cpos = rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos);
        return concat_rebalance<Node>(null_sub_pos{}, cpos, rpos);
    } else {
        assert(lshift == rshift);
        assert(Node::bits_leaf == 0u || lshift > 0);
        auto cpos = lpos.last_sub(concat_both_visitor<Node>{}, tpos, rpos);
        return concat_rebalance<Node>(lpos, cpos, rpos);
    }
}

template <typename Node>
struct concat_left_visitor : visitor_base<concat_left_visitor<Node>>
{
    using this_t = concat_left_visitor;

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_pos<Node>
    visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
    { return concat_inners<Node>(lpos, tpos, rpos); }

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_pos<Node>
    visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
    { IMMER_UNREACHABLE; }
};

template <typename Node>
struct concat_right_visitor : visitor_base<concat_right_visitor<Node>>
{
    using this_t = concat_right_visitor;

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_pos<Node>
    visit_inner(RPos&& rpos, LPos&& lpos, TPos&& tpos)
    { return concat_inners<Node>(lpos, tpos, rpos); }

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_pos<Node>
    visit_leaf(RPos&& rpos, LPos&& lpos, TPos&& tpos)
    { return concat_leafs<Node>(lpos, tpos, rpos); }
};

template <typename Node>
struct concat_both_visitor
    : visitor_base<concat_both_visitor<Node>>
{
    using this_t = concat_both_visitor;

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_pos<Node>
    visit_inner(LPos&& lpos, TPos&& tpos, RPos&& rpos)
    { return rpos.first_sub(concat_right_visitor<Node>{}, lpos, tpos); }

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_pos<Node>
    visit_leaf(LPos&& lpos, TPos&& tpos, RPos&& rpos)
    { return rpos.first_sub_leaf(concat_right_visitor<Node>{}, lpos, tpos); }
};

template <typename Node>
struct concat_trees_right_visitor
    : visitor_base<concat_trees_right_visitor<Node>>
{
    using this_t = concat_trees_right_visitor;

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_pos<Node>
    visit_node(RPos&& rpos, LPos&& lpos, TPos&& tpos)
    { return concat_inners<Node>(lpos, tpos, rpos); }
};

template <typename Node>
struct concat_trees_left_visitor
    : visitor_base<concat_trees_left_visitor<Node>>
{
    using this_t = concat_trees_left_visitor;

    template <typename LPos, typename TPos, typename... Args>
    static concat_center_pos<Node>
    visit_node(LPos&& lpos, TPos&& tpos, Args&& ...args)
    { return visit_maybe_relaxed_sub(
            args...,
            concat_trees_right_visitor<Node>{},
            lpos, tpos); }
};

template <typename Node>
relaxed_pos<Node>
concat_trees(Node* lroot, shift_t lshift, size_t lsize,
             Node* ltail, count_t ltcount,
             Node* rroot, shift_t rshift, size_t rsize)
{
    return visit_maybe_relaxed_sub(
        lroot, lshift, lsize,
        concat_trees_left_visitor<Node>{},
        make_leaf_pos(ltail, ltcount),
        rroot, rshift, rsize)
        .realize();
}

template <typename Node>
relaxed_pos<Node>
concat_trees(Node* ltail, count_t ltcount,
             Node* rroot, shift_t rshift, size_t rsize)
{
    return make_singleton_regular_sub_pos(ltail, ltcount).visit(
        concat_trees_left_visitor<Node>{},
        empty_leaf_pos<Node>{},
        rroot, rshift, rsize)
        .realize();
}

template <typename Node>
using concat_center_mut_pos = concat_center_pos<Node>;

template <typename Node>
struct concat_merger_mut
{
    using node_t = Node;
    using edit_t = typename Node::edit_t;

    static constexpr auto B  = Node::bits;
    static constexpr auto BL = Node::bits_leaf;

    using result_t = concat_center_pos<Node>;

    edit_t ec_  = {};

    count_t* curr_;
    count_t  n_;
    result_t result_;
    count_t  count_ = 0;
    node_t*  candidate_ = nullptr;
    edit_t   candidate_e_ = Node::memory::transience_t::noone;

    concat_merger_mut(edit_t ec, shift_t shift,
                      count_t* counts, count_t n,
                      edit_t candidate_e, node_t* candidate)
        : ec_{ec}
        , curr_{counts}
        , n_{n}
        , result_{shift + B, nullptr, 0}
    {
        if (candidate) {
            candidate->ensure_mutable_relaxed_e(candidate_e, ec);
            result_.nodes_[0] = candidate;
        } else {
            result_.nodes_[0] = node_t::make_inner_r_e(ec);
        }
    }

    node_t*  to_        = {};
    count_t  to_offset_ = {};
    size_t   to_size_   = {};

    void set_candidate(edit_t candidate_e, node_t* candidate)
    { candidate_ = candidate; candidate_e_ = candidate_e; }

    void add_child(node_t* p, size_t size)
    {
        ++curr_;
        auto parent  = result_.nodes_[result_.count_ - 1];
        auto relaxed = parent->relaxed();
        if (count_ == branches<B>) {
            parent->relaxed()->d.count = count_;
            assert(result_.count_ < result_t::max_children);
            n_ -= branches<B>;
            if (candidate_) {
                parent = candidate_;
                parent->ensure_mutable_relaxed_e(candidate_e_, ec_);
                candidate_ = nullptr;
            } else
                parent  = node_t::make_inner_r_e(ec_);
            count_ = 0;
            relaxed = parent->relaxed();
            result_.nodes_[result_.count_] = parent;
            result_.sizes_[result_.count_] = result_.sizes_[result_.count_ - 1];
            ++result_.count_;
        }
        auto idx = count_++;
        result_.sizes_[result_.count_ - 1] += size;
        relaxed->d.sizes[idx] = size + (idx ? relaxed->d.sizes[idx - 1] : 0);
        parent->inner() [idx] = p;
    };

    template <typename Pos>
    void merge_leaf(Pos&& p, edit_t e)
    {
        auto from       = p.node();
        auto from_size  = p.size();
        auto from_count = p.count();
        assert(from_size);
        if (!to_ && *curr_ == from_count) {
            add_child(from, from_size);
        } else {
            auto from_offset  = count_t{};
            auto from_data    = from->leaf();
            auto from_mutate  = from->can_mutate(e);
            do {
                if (!to_) {
                    if (from_mutate) {
                        node_t::ownee(from) = ec_;
                        to_ = from->inc();
                        assert(from_count);
                    } else {
                        to_ = node_t::make_leaf_e(ec_);
                    }
                    to_offset_ = 0;
                }
                auto data = to_->leaf();
                auto to_copy = std::min(from_count - from_offset,
                                        *curr_ - to_offset_);
                if (from == to_) {
                    if (from_offset != to_offset_)
                        std::move(from_data + from_offset,
                                  from_data + from_offset + to_copy,
                                  data + to_offset_);
                } else {
                    if (!from_mutate)
                        std::uninitialized_copy(from_data + from_offset,
                                                from_data + from_offset + to_copy,
                                                data + to_offset_);
                    else
                        detail::uninitialized_move(from_data + from_offset,
                                                  from_data + from_offset + to_copy,
                                                  data + to_offset_);
                }
                to_offset_  += to_copy;
                from_offset += to_copy;
                if (*curr_ == to_offset_) {
                    add_child(to_, to_offset_);
                    to_ = nullptr;
                }
            } while (from_offset != from_count);
        }
    }

    template <typename Pos>
    void merge_inner(Pos&& p, edit_t e)
    {
        auto from       = p.node();
        auto from_size  = p.size();
        auto from_count = p.count();
        assert(from_size);
        if (!to_ && *curr_ == from_count) {
            add_child(from, from_size);
        } else {
            auto from_offset  = count_t{};
            auto from_data    = from->inner();
            auto from_mutate = from->can_relax() && from->can_mutate(e);
            do {
                if (!to_) {
                    if (from_mutate) {
                        node_t::ownee(from) = ec_;
                        from->ensure_mutable_relaxed_e(e, ec_);
                        to_ = from;
                    } else {
                        to_ = node_t::make_inner_r_e(ec_);
                    }
                    to_offset_ = 0;
                    to_size_   = 0;
                }
                auto data    = to_->inner();
                auto to_copy = std::min(from_count - from_offset,
                                        *curr_ - to_offset_);
                auto sizes   = to_->relaxed()->d.sizes;
                if (from != to_ || from_offset != to_offset_) {
                    std::copy(from_data + from_offset,
                              from_data + from_offset + to_copy,
                              data + to_offset_);
                    p.copy_sizes(from_offset, to_copy,
                                 to_size_, sizes + to_offset_);
                }
                to_offset_  += to_copy;
                from_offset += to_copy;
                to_size_     = sizes[to_offset_ - 1];
                if (*curr_ == to_offset_) {
                    to_->relaxed()->d.count = to_offset_;
                    add_child(to_, to_size_);
                    to_ = nullptr;
                }
            } while (from_offset != from_count);
        }
    }

    concat_center_pos<Node> finish() const
    {
        assert(!to_);
        result_.nodes_[result_.count_ - 1]->relaxed()->d.count = count_;
        return result_;
    }

    void abort()
    {
        // We may have mutated stuff the tree in place, leaving
        // everything in a corrupted state...  It should be possible
        // to define cleanup properly, but that is a task for some
        // other day... ;)
        std::terminate();
    }
};

struct concat_merger_mut_visitor : visitor_base<concat_merger_mut_visitor>
{
    using this_t = concat_merger_mut_visitor;

    template <typename Pos, typename Merger>
    static void visit_inner(Pos&& p,
                            Merger& merger, edit_type<Pos> e)
    { merger.merge_inner(p, e); }

    template <typename Pos, typename Merger>
    static void visit_leaf(Pos&& p,
                           Merger& merger, edit_type<Pos> e)
    { merger.merge_leaf(p, e); }
};

template <bits_t B, bits_t BL>
struct concat_rebalance_plan_mut : concat_rebalance_plan<B, BL>
{
    using this_t = concat_rebalance_plan_mut;

    template <typename LPos, typename CPos, typename RPos>
    concat_center_mut_pos<node_type<CPos>>
    merge(edit_type<CPos> ec,
          edit_type<CPos> el, LPos&& lpos, CPos&& cpos,
          edit_type<CPos> er, RPos&& rpos)
    {
        using node_t    = node_type<CPos>;
        using merger_t  = concat_merger_mut<node_t>;
        using visitor_t = concat_merger_mut_visitor;
        auto lnode = ((node_t*)lpos.node());
        auto rnode = ((node_t*)rpos.node());
        auto lmut2 = lnode && lnode->can_relax() && lnode->can_mutate(el);
        auto rmut2 = rnode && rnode->can_relax() && rnode->can_mutate(er);
        auto merger = merger_t{
            ec, cpos.shift(), this->counts, this->n,
            el, lmut2 ? lnode : nullptr
        };
        try {
            lpos.each_left_sub(visitor_t{}, merger, el);
            cpos.each_sub(visitor_t{}, merger, ec);
            if (rmut2) merger.set_candidate(er, rnode);
            rpos.each_right_sub(visitor_t{}, merger, er);
            return merger.finish();
        } catch (...) {
            merger.abort();
            throw;
        }
    }
};

template <typename Node, typename LPos, typename CPos, typename RPos>
concat_center_pos<Node>
concat_rebalance_mut(edit_type<Node> ec,
                     edit_type<Node> el, LPos&& lpos, CPos&& cpos,
                     edit_type<Node> er, RPos&& rpos)
{
    auto plan = concat_rebalance_plan_mut<Node::bits, Node::bits_leaf>{};
    plan.fill(lpos, cpos, rpos);
    plan.shuffle(cpos.shift());
    return plan.merge(ec, el, lpos, cpos, er, rpos);
}

template <typename Node, typename LPos, typename TPos, typename RPos>
concat_center_mut_pos<Node>
concat_leafs_mut(edit_type<Node> ec,
                 edit_type<Node> el, LPos&& lpos, TPos&& tpos,
                 edit_type<Node> er, RPos&& rpos)
{
    static_assert(Node::bits >= 2, "");
    assert(lpos.shift() == tpos.shift());
    assert(lpos.shift() == rpos.shift());
    assert(lpos.shift() == 0);
    if (tpos.count() > 0)
        return {
            Node::bits_leaf,
            lpos.node(), lpos.count(),
            tpos.node(), tpos.count(),
            rpos.node(), rpos.count(),
        };
    else
        return {
            Node::bits_leaf,
            lpos.node(), lpos.count(),
            rpos.node(), rpos.count(),
        };
}

template <typename Node>
struct concat_left_mut_visitor;
template <typename Node>
struct concat_right_mut_visitor;
template <typename Node>
struct concat_both_mut_visitor;

template <typename Node, typename LPos, typename TPos, typename RPos>
concat_center_mut_pos<Node>
concat_inners_mut(edit_type<Node> ec,
                  edit_type<Node> el, LPos&& lpos, TPos&& tpos,
                  edit_type<Node> er, RPos&& rpos)
{
    auto lshift = lpos.shift();
    auto rshift = rpos.shift();
    // lpos.node() can be null it is a singleton_regular_sub_pos<...>,
    // this is, when the tree is just a tail...
    if (lshift > rshift) {
        auto cpos = lpos.last_sub(concat_left_mut_visitor<Node>{},
                                  ec, el, tpos, er, rpos);
        return concat_rebalance_mut<Node>(ec,
                                          el, lpos, cpos,
                                          er, null_sub_pos{});
    } else if (lshift < rshift) {
        auto cpos = rpos.first_sub(concat_right_mut_visitor<Node>{},
                                   ec, el, lpos, tpos, er);
        return concat_rebalance_mut<Node>(ec,
                                          el, null_sub_pos{}, cpos,
                                          er, rpos);
    } else {
        assert(lshift == rshift);
        assert(Node::bits_leaf == 0u || lshift > 0);
        auto cpos = lpos.last_sub(concat_both_mut_visitor<Node>{},
                                  ec, el, tpos, er, rpos);
        return concat_rebalance_mut<Node>(ec,
                                          el, lpos, cpos,
                                          er, rpos);
    }
}

template <typename Node>
struct concat_left_mut_visitor : visitor_base<concat_left_mut_visitor<Node>>
{
    using this_t = concat_left_mut_visitor;
    using edit_t = typename Node::edit_t;

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_mut_pos<Node>
    visit_inner(LPos&& lpos, edit_t ec,
                edit_t el, TPos&& tpos,
                edit_t er, RPos&& rpos)
    { return concat_inners_mut<Node>(
            ec, el, lpos, tpos, er, rpos); }

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_mut_pos<Node>
    visit_leaf(LPos&& lpos, edit_t ec,
               edit_t el, TPos&& tpos,
               edit_t er, RPos&& rpos)
    { IMMER_UNREACHABLE; }
};

template <typename Node>
struct concat_right_mut_visitor
    : visitor_base<concat_right_mut_visitor<Node>>
{
    using this_t = concat_right_mut_visitor;
    using edit_t = typename Node::edit_t;

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_mut_pos<Node>
    visit_inner(RPos&& rpos, edit_t ec,
                edit_t el, LPos&& lpos, TPos&& tpos,
                edit_t er)
    { return concat_inners_mut<Node>(
            ec, el, lpos, tpos, er, rpos); }

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_mut_pos<Node>
    visit_leaf(RPos&& rpos, edit_t ec,
               edit_t el, LPos&& lpos, TPos&& tpos,
               edit_t er)
    { return concat_leafs_mut<Node>(
            ec, el, lpos, tpos, er, rpos); }
};

template <typename Node>
struct concat_both_mut_visitor
    : visitor_base<concat_both_mut_visitor<Node>>
{
    using this_t = concat_both_mut_visitor;
    using edit_t = typename Node::edit_t;

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_mut_pos<Node>
    visit_inner(LPos&& lpos, edit_t ec,
                edit_t el, TPos&& tpos,
                edit_t er, RPos&& rpos)
    { return rpos.first_sub(concat_right_mut_visitor<Node>{},
                            ec, el, lpos, tpos, er); }

    template <typename LPos, typename TPos, typename RPos>
    static concat_center_mut_pos<Node>
    visit_leaf(LPos&& lpos, edit_t ec,
               edit_t el, TPos&& tpos,
               edit_t er, RPos&& rpos)
    { return rpos.first_sub_leaf(concat_right_mut_visitor<Node>{},
                                 ec, el, lpos, tpos, er); }
};

template <typename Node>
struct concat_trees_right_mut_visitor
    : visitor_base<concat_trees_right_mut_visitor<Node>>
{
    using this_t = concat_trees_right_mut_visitor;
    using edit_t = typename Node::edit_t;

    template <typename RPos, typename LPos, typename TPos>
    static concat_center_mut_pos<Node>
    visit_node(RPos&& rpos, edit_t ec,
               edit_t el, LPos&& lpos, TPos&& tpos,
               edit_t er)
    { return concat_inners_mut<Node>(
            ec, el, lpos, tpos, er, rpos); }
};

template <typename Node>
struct concat_trees_left_mut_visitor
    : visitor_base<concat_trees_left_mut_visitor<Node>>
{
    using this_t = concat_trees_left_mut_visitor;
    using edit_t = typename Node::edit_t;

    template <typename LPos, typename TPos, typename... Args>
    static concat_center_mut_pos<Node>
    visit_node(LPos&& lpos, edit_t ec,
               edit_t el, TPos&& tpos,
               edit_t er, Args&& ...args)
    { return visit_maybe_relaxed_sub(
            args...,
            concat_trees_right_mut_visitor<Node>{},
            ec, el, lpos, tpos, er); }
};

template <typename Node>
relaxed_pos<Node>
concat_trees_mut(edit_type<Node> ec,
                 edit_type<Node> el,
                 Node* lroot, shift_t lshift, size_t lsize,
                 Node* ltail, count_t ltcount,
                 edit_type<Node> er,
                 Node* rroot, shift_t rshift, size_t rsize)
{
    return visit_maybe_relaxed_sub(
        lroot, lshift, lsize,
        concat_trees_left_mut_visitor<Node>{},
        ec,
        el, make_leaf_pos(ltail, ltcount),
        er, rroot, rshift, rsize)
        .realize_e(ec);
}

template <typename Node>
relaxed_pos<Node>
concat_trees_mut(edit_type<Node> ec,
                 edit_type<Node> el,
                 Node* ltail, count_t ltcount,
                 edit_type<Node> er,
                 Node* rroot, shift_t rshift, size_t rsize)
{
    return make_singleton_regular_sub_pos(ltail, ltcount).visit(
        concat_trees_left_mut_visitor<Node>{},
        ec,
        el, empty_leaf_pos<Node>{},
        er, rroot, rshift, rsize)
        .realize_e(ec);
}

} // namespace rbts
} // namespace detail
} // namespace immer