diff options
Diffstat (limited to 'immer/detail/rbts/operations.hpp')
| -rw-r--r-- | immer/detail/rbts/operations.hpp | 2461 |
1 files changed, 2461 insertions, 0 deletions
diff --git a/immer/detail/rbts/operations.hpp b/immer/detail/rbts/operations.hpp new file mode 100644 index 000000000000..ff703e892b42 --- /dev/null +++ b/immer/detail/rbts/operations.hpp @@ -0,0 +1,2461 @@ +// +// 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/detail/rbts/position.hpp> +#include <immer/detail/rbts/visitor.hpp> +#include <immer/detail/util.hpp> +#include <immer/heap/tags.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 std::make_tuple(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 std::make_tuple(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 std::make_tuple(pos.shift(), newn, ts, tail); + } + } else if (idx == 0) { + if (Mutating) + pos.visit(dec_right_visitor{}, count_t{1}); + return std::make_tuple(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 std::make_tuple(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 std::make_tuple(pos.shift(), node, ts, tail); + } else { + auto newn = node_t::copy_inner_r_e(e, node, idx); + if (Mutating) + pos.visit(dec_visitor{}); + return std::make_tuple(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 std::make_tuple(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 std::make_tuple(pos.shift(), newn, ts, tail); + } + } else if (idx == 0) { + if (Mutating) + pos.visit(dec_right_visitor{}, count_t{1}); + return std::make_tuple(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 std::make_tuple(pos.shift() - B, newn, ts, tail); + } else { + if (mutate) { + pos.each_right(dec_visitor{}, idx + 1); + return std::make_tuple(pos.shift(), node, ts, tail); + } else { + auto newn = node_t::copy_inner_e(e, node, idx); + if (Mutating) + pos.visit(dec_visitor{}); + return std::make_tuple(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 std::make_tuple(0, nullptr, new_tail_size, node); + } else if (mutate) { + destroy_n(node->leaf() + new_tail_size, + old_tail_size - new_tail_size); + return std::make_tuple(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 std::make_tuple(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 std::make_tuple(pos.shift(), newn, ts, tail); + } else if (idx == 0) { + return std::make_tuple(pos.shift(), nullptr, ts, tail); + } else if (Collapse && idx == 1 && pos.shift() > BL) { + auto newn = pos.node()->inner()[0]; + return std::make_tuple( + pos.shift() - B, newn->inc(), ts, tail); + } else { + auto newn = node_t::copy_inner_r(pos.node(), idx); + return std::make_tuple(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 std::make_tuple(pos.shift(), newn, ts, tail); + } else if (idx == 0) { + return std::make_tuple(pos.shift(), nullptr, ts, tail); + } else if (Collapse && idx == 1 && pos.shift() > BL) { + auto newn = pos.node()->inner()[0]; + return std::make_tuple( + pos.shift() - B, newn->inc(), ts, tail); + } else { + auto newn = node_t::copy_inner_n(idx, pos.node(), idx); + return std::make_tuple(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 std::make_tuple(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 std::make_tuple(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 std::make_tuple(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 std::make_tuple(0, node); + } else { + auto newn = node_t::copy_leaf_e(e, node, idx, count); + if (Mutating) + pos.visit(dec_visitor{}); + return std::make_tuple(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 std::make_tuple(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 std::make_tuple(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 |