tpl_rope.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef TPL_ROPE_H
#define TPL_ROPE_H
 
#include <algorithm>
#include <bit>
#include <limits>
#include <memory>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
 
#include <ah-errors.H>
#include <tpl_array.H>
#include <tpl_small_vector.H>
 
namespace Aleph {
 
template <class T>
concept RopeCharTraitsCompatible = std::is_same_v<T, char> or std::is_same_v<T, wchar_t> or
  std::is_same_v<T, char8_t> or std::is_same_v<T, char16_t> or std::is_same_v<T, char32_t>;
 
template <typename Char = char, size_t LeafSize = 256>
class Rope
{
  static_assert(LeafSize > 0, "Rope requires a positive LeafSize");
 
public:
  using View = std::basic_string_view<Char>;
 
private:
  struct Node
  {
    size_t length = 0;
    size_t depth = 0;  // 0 for a leaf; 1 + max(child depths) for internal.
    // Heap-indirected rather than embedded: `SmallVector<Char, LeafSize>`
    // carries an inline buffer of `LeafSize * sizeof(Char)` bytes as part
    // of its own size (see tpl_small_vector.H), so embedding it directly
    // here would make *every* node -- including internal ones, which
    // never hold character data -- pay that cost (e.g. 280 bytes at the
    // default `LeafSize=256`, roughly 5x the size of everything else this
    // struct needs). A null pointer costs 8 bytes regardless of
    // `LeafSize`; only leaves pay for an actual buffer, and only once.
    std::unique_ptr<const SmallVector<Char, LeafSize>> leaf_data;
    std::shared_ptr<const Node> left;   // null iff this is a leaf.
    std::shared_ptr<const Node> right;  // null iff this is a leaf.
 
    [[nodiscard]] bool is_leaf() const noexcept
    {
      // Both children null iff leaf: every construction path sets
      // `left`/`right` together (never just one), so this is equivalent
      // in practice to checking only `left` -- but checking both means a
      // hypothetically corrupted "one child null" node is *not*
      // misclassified as a leaf, and instead falls through to
      // `verify_rec`'s existing `left == nullptr or right == nullptr`
      // rejection for internal nodes.
      return left == nullptr and right == nullptr;
    }
  };
 
  using NodePtr = std::shared_ptr<const Node>;
 
  NodePtr root_;  // null means the empty rope (length 0).
 
  [[nodiscard]] static NodePtr make_leaf(SmallVector<Char, LeafSize> data)
  {
    auto node = std::make_shared<Node>();
    node->length = data.size();
    node->depth = 0;
    node->leaf_data =
        std::make_unique<const SmallVector<Char, LeafSize>>(std::move(data));
    return node;
  }
 
  [[nodiscard]] static NodePtr make_internal_node(NodePtr left, NodePtr right)
  {
    // Checked *before* adding, not after: structural sharing means a
    // logical length near SIZE_MAX is reachable with very little real
    // memory (e.g. ~64 self-concats of `r = r.concat(r)`, each O(1) since
    // both sides already share the same subtree). Left unchecked, a
    // wrapped `length` can desynchronize from the real `depth` and make
    // `is_balanced()` wrongly decide to rebalance -- and `collect_leaves`
    // does not deduplicate shared nodes, so rebalancing a "wide" shared
    // structure like that visits it once per (possibly exponential)
    // root-to-leaf path instead of once per distinct node.
    ah_overflow_error_if(left->length > std::numeric_limits<size_t>::max() - right->length)
      << "Rope: concatenated length would overflow size_t";
    auto node = std::make_shared<Node>();
    node->length = left->length + right->length;
    node->depth = 1 + std::max(left->depth, right->depth);
    node->left = std::move(left);
    node->right = std::move(right);
    return node;
  }
 
  [[nodiscard]] static NodePtr make_internal(NodePtr left, NodePtr right)
  {
    return maybe_rebalance(make_internal_node(std::move(left), std::move(right)));
  }
 
  [[nodiscard]] static NodePtr try_absorb_right(const NodePtr &node,
                                                const SmallVector<Char, LeafSize> &extra)
  {
    if (node == nullptr)
      return nullptr;
    if (node->is_leaf())
      {
        if (node->length + extra.size() > LeafSize)
          return nullptr;
        // No `reserve()`: the capacity check above already guarantees the
        // merged result fits within `SmallVector`'s inline capacity
        // (`LeafSize`), so this can never reallocate. `append_range`
        // (rather than the copy constructor plus a per-character loop)
        // lets a trivially copyable `Char` (the only kind `Rope` accepts,
        // see the class's own `@tparam` note) copy both pieces via
        // `memcpy` instead of one placement-new call per character.
        SmallVector<Char, LeafSize> merged;
        merged.append_range(node->leaf_data->data(), node->leaf_data->size());
        merged.append_range(extra.data(), extra.size());
        return make_leaf(std::move(merged));
      }
    NodePtr new_right = try_absorb_right(node->right, extra);
    if (new_right == nullptr)
      return nullptr;
    // See the matching check/comment in `make_internal_node`: `node` here
    // can be an arbitrarily large shared subtree, so this addition needs
    // the same overflow guard.
    ah_overflow_error_if(node->length > std::numeric_limits<size_t>::max() - extra.size())
      << "Rope: concatenated length would overflow size_t";
    auto result = std::make_shared<Node>();
    result->length = node->length + extra.size();
    result->depth = node->depth;
    result->left = node->left;
    result->right = std::move(new_right);
    return result;
  }
 
  [[nodiscard]] static NodePtr try_absorb_left(const NodePtr &node,
                                               const SmallVector<Char, LeafSize> &extra)
  {
    if (node == nullptr)
      return nullptr;
    if (node->is_leaf())
      {
        if (node->length + extra.size() > LeafSize)
          return nullptr;
        // No `reserve()`: see the matching note in `try_absorb_right`.
        SmallVector<Char, LeafSize> merged;
        merged.append_range(extra.data(), extra.size());
        merged.append_range(node->leaf_data->data(), node->leaf_data->size());
        return make_leaf(std::move(merged));
      }
    NodePtr new_left = try_absorb_left(node->left, extra);
    if (new_left == nullptr)
      return nullptr;
    // See the matching check/comment in `make_internal_node`.
    ah_overflow_error_if(node->length > std::numeric_limits<size_t>::max() - extra.size())
      << "Rope: concatenated length would overflow size_t";
    auto result = std::make_shared<Node>();
    result->length = node->length + extra.size();
    result->depth = node->depth;
    result->left = std::move(new_left);
    result->right = node->right;
    return result;
  }
 
  [[nodiscard]] static NodePtr concat_nodes(NodePtr left, NodePtr right)
  {
    if (left == nullptr)
      return right;
    if (right == nullptr)
      return left;
 
    // Fast path for the common "append/prepend one small piece at a
    // time" pattern (e.g. one character per loop iteration): if one side
    // is a single leaf, try to absorb it into the adjacent leaf on the
    // other side instead of growing the tree by one level. This touches
    // only the O(depth) nodes on that spine, shares everything else, and
    // -- because it never changes any depth -- never triggers a
    // rebalance. Falls through to the general case if there is no spare
    // room (or neither side is a lone leaf).
    if (right->is_leaf())
      if (NodePtr absorbed = try_absorb_right(left, *right->leaf_data))
        return absorbed;
    if (left->is_leaf())
      if (NodePtr absorbed = try_absorb_left(right, *left->leaf_data))
        return absorbed;
 
    return make_internal(std::move(left), std::move(right));
  }
 
  [[nodiscard]] static bool is_balanced(const Node *node) noexcept
  {
    // No separate `depth <= 2` early return: the formula below already
    // evaluates to `true` for any `depth` up to at least 8 (its minimum
    // possible value, at `length == 0`), so it subsumes that case.
    const unsigned bits = std::bit_width(node->length);
    return node->depth <= 2 * static_cast<size_t>(bits) + 8;
  }
 
  static void collect_leaves(const NodePtr &node, Array<NodePtr> &out)
  {
    if (node->is_leaf())
      {
        out.append(node);
        return;
      }
    collect_leaves(node->left, out);
    collect_leaves(node->right, out);
  }
 
  static void collect_leaf_pointers(const Node *node, Array<const Node *> &out)
  {
    if (node->is_leaf())
      {
        out.append(node);
        return;
      }
    collect_leaf_pointers(node->left.get(), out);
    collect_leaf_pointers(node->right.get(), out);
  }
 
  [[nodiscard]] static NodePtr build_balanced_from_leaves(const Array<NodePtr> &leaves,
                                                          const size_t lo, const size_t hi)
  {
    if (hi - lo == 1)
      return leaves[lo];
    const size_t mid = lo + (hi - lo) / 2;
    NodePtr left = build_balanced_from_leaves(leaves, lo, mid);
    NodePtr right = build_balanced_from_leaves(leaves, mid, hi);
    return make_internal_node(std::move(left), std::move(right));
  }
 
  [[nodiscard]] static NodePtr maybe_rebalance(NodePtr node)
  {
    if (is_balanced(node.get()))
      return node;
    Array<NodePtr> leaves;
    // Estimated leaf count, computed in O(1): `length / LeafSize` is
    // exact when every leaf is full, which is the common case (the
    // leaf-absorption fast path keeps leaves packed). Reserving this
    // avoids Array's geometric-growth reallocations in that common case
    // without over-allocating -- an earlier version of this reservation
    // used `length` itself as the bound (technically valid: no leaf is
    // ever empty, so leaf count can't exceed it), but that is loose by
    // up to a factor of `LeafSize` whenever leaves are reasonably full,
    // and measurably regressed performance (over-reserving dominated the
    // reallocations it was meant to avoid). For a pathologically
    // fragmented tree (many near-empty leaves) this estimate undercounts
    // and `Array` still grows geometrically from here -- no worse than
    // not reserving at all.
    // The `+ 1` below can only overflow `size_t` if `node->length /
    // LeafSize` is already `SIZE_MAX` -- reachable only with the
    // degenerate `LeafSize == 1` and a `length` at or near `SIZE_MAX`
    // (see `make_internal_node`'s overflow guard for how a rope reaches
    // such a length cheaply via structural sharing). Guarded rather than
    // left to wrap: a wrapped-to-0 reserve would silently defeat the
    // estimate instead of just being loose, though either way `Array`
    // still grows correctly from there (see the comment above).
    const size_t estimated_leaf_count = node->length / LeafSize;
    leaves.reserve(estimated_leaf_count == std::numeric_limits<size_t>::max()
                    ? estimated_leaf_count : estimated_leaf_count + 1);
    collect_leaves(node, leaves);
    return build_balanced_from_leaves(leaves, 0, leaves.size());
  }
 
  [[nodiscard]] static NodePtr build_from_view(const View v)
  {
    if (v.size() <= LeafSize)
      {
        // No `reserve()` here: `v.size() <= LeafSize` is exactly
        // `SmallVector<Char, LeafSize>`'s inline capacity, so it can never
        // reallocate regardless. `View` (`basic_string_view<Char>`) is
        // contiguous, so `append_range` can copy it in one `memcpy`
        // instead of one placement-new call per character.
        SmallVector<Char, LeafSize> data;
        data.append_range(v.data(), v.size());
        return make_leaf(std::move(data));
      }
    const size_t mid = v.size() / 2;
    NodePtr left = build_from_view(v.substr(0, mid));
    NodePtr right = build_from_view(v.substr(mid));
    return make_internal_node(std::move(left), std::move(right));
  }
 
  [[nodiscard]] static const Char &char_at(const Node *node, size_t pos) noexcept
  {
    while (not node->is_leaf())
      if (const size_t left_len = node->left->length; pos < left_len)
        node = node->left.get();
      else
        {
          pos -= left_len;
          node = node->right.get();
        }
    // Unchecked access: `pos` is guaranteed in range by the descent above
    // (and, transitively, by `at()`'s own bounds check before calling
    // here). Using the checked `operator[]` would make this `noexcept`
    // function capable of calling `std::terminate()` on `std::out_of_range`
    // instead of safely returning -- and would repeat a bounds check that
    // can never fail.
    return (*node->leaf_data)(pos);
  }
 
  [[nodiscard]] static NodePtr slice(const NodePtr &node, size_t pos, size_t len)
  {
    if (len == 0)
      return nullptr;
 
    // Whole-node request: share `node` itself, regardless of whether it is
    // a leaf or an internal node. Without this check here, an internal
    // node's own "whole subtree" case fell through to the straddle branch
    // below, which slices both children (trivially, via the same
    // fast path) and then *rejoins* them with `concat_nodes` -- producing
    // a freshly-built node with identical content instead of sharing
    // `node`. That defeated the O(1) sharing `substr(0, size())` is
    // documented to provide for internal-rooted ropes.
    if (pos == 0 and len == node->length)
      return node;
 
    if (node->is_leaf())
      {
        // No `reserve()`: `len < node->length <= LeafSize` here (the
        // `len == node->length` case already returned above), so this
        // always stays within `SmallVector`'s inline capacity.
        // `append_range` copies the `[pos, pos+len)` subrange via one
        // `memcpy` instead of one placement-new call per character.
        SmallVector<Char, LeafSize> data;
        data.append_range(node->leaf_data->data() + pos, len);
        return make_leaf(std::move(data));
      }
 
    const size_t left_len = node->left->length;
 
    if (pos + len <= left_len)
      {
        if (pos == 0 and len == left_len)
          return node->left;
        return slice(node->left, pos, len);
      }
 
    if (pos >= left_len)
      {
        const size_t right_pos = pos - left_len;
        if (right_pos == 0 and len == node->right->length)
          return node->right;
        return slice(node->right, right_pos, len);
      }
 
    // Straddles both children: take the tail of `left` and the head of
    // `right`, then rejoin (may trigger a rebalance).
    const size_t left_part_len = left_len - pos;
    NodePtr left_part = slice(node->left, pos, left_part_len);
    NodePtr right_part = slice(node->right, 0, len - left_part_len);
    return concat_nodes(std::move(left_part), std::move(right_part));
  }
 
  static void flatten_into(const Node *node, Array<Char> &out)
  {
    if (node == nullptr)
      return;
    if (node->is_leaf())
      {
        for (const Char &c : *node->leaf_data)
          out.append(c);
        return;
      }
    flatten_into(node->left.get(), out);
    flatten_into(node->right.get(), out);
  }
 
  static void string_append_into(const Node *node, std::basic_string<Char> &out)
    requires RopeCharTraitsCompatible<Char>
  {
    if (node == nullptr)
      return;
    if (node->is_leaf())
      {
        out.append(node->leaf_data->data(), node->leaf_data->size());
        return;
      }
    string_append_into(node->left.get(), out);
    string_append_into(node->right.get(), out);
  }
 
  [[nodiscard]] static bool verify_rec(const Node *node) noexcept
  {
    if (node == nullptr)
      return true;
    if (node->is_leaf())
      return node->leaf_data != nullptr and node->leaf_data->size() == node->length and
        node->length >= 1 and node->length <= LeafSize and node->depth == 0;
    if (node->leaf_data != nullptr)
      return false;
    if (node->left == nullptr or node->right == nullptr)
      return false;
    if (node->length != node->left->length + node->right->length)
      return false;
    if (node->depth != 1 + std::max(node->left->depth, node->right->depth))
      return false;
    return verify_rec(node->left.get()) and verify_rec(node->right.get());
  }
 
  explicit Rope(NodePtr root) noexcept : root_(std::move(root)) {}
 
public:
  Rope() noexcept = default;
 
  explicit Rope(const View v) : root_(v.empty() ? nullptr : build_from_view(v)) {}
 
  Rope(const Rope &other) = default;
  Rope &operator = (const Rope &other) = default;
  Rope(Rope &&other) noexcept = default;
  Rope &operator = (Rope &&other) noexcept = default;
  ~Rope() = default;
 
  [[nodiscard]] size_t size() const noexcept
  {
    return root_ == nullptr ? 0 : root_->length;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return root_ == nullptr;
  }
 
  [[nodiscard]] Char at(const size_t pos) const
  {
    ah_out_of_range_error_if(pos >= size()) << "Rope::at(): index out of range";
    return char_at(root_.get(), pos);
  }
 
  [[nodiscard]] Rope concat(const Rope &other) const
  {
    return Rope(concat_nodes(root_, other.root_));
  }
 
  [[nodiscard]] Rope substr(const size_t pos, const size_t len) const
  {
    ah_out_of_range_error_if(pos > size() or len > size() - pos)
      << "Rope::substr(): range out of bounds";
    return Rope(slice(root_, pos, len));
  }
 
  [[nodiscard]] Rope insert(const size_t pos, const Rope &other) const
  {
    ah_out_of_range_error_if(pos > size()) << "Rope::insert(): index out of range";
    if (other.is_empty())
      return *this;
    return substr(0, pos).concat(other).concat(substr(pos, size() - pos));
  }
 
  [[nodiscard]] Rope erase(const size_t pos, const size_t len) const
  {
    ah_out_of_range_error_if(pos > size() or len > size() - pos)
      << "Rope::erase(): range out of bounds";
    if (len == 0)
      return *this;
    return substr(0, pos).concat(substr(pos + len, size() - pos - len));
  }
 
  [[nodiscard]] Array<Char> flatten() const
  {
    Array<Char> result;
    result.reserve(size());
    flatten_into(root_.get(), result);
    return result;
  }
 
  [[nodiscard]] std::basic_string<Char> to_string() const
    requires RopeCharTraitsCompatible<Char>
  {
    std::basic_string<Char> result;
    ah_length_error_if(size() > result.max_size())
      << "Rope::to_string(): result exceeds std::basic_string<Char>::max_size()";
    result.reserve(size());
    string_append_into(root_.get(), result);
    return result;
  }
 
  [[nodiscard]] bool operator == (const Rope &other) const
  {
    if (size() != other.size())
      return false;
    if (root_ == other.root_)
      return true;  // same shared tree (or both empty): trivially equal.
 
    Array<const Node *> mine, theirs;
    // Same reserve rationale (and same `+ 1` overflow guard) as
    // maybe_rebalance(): `length / LeafSize` is exact when leaves are
    // packed (the common case), avoiding Array's geometric-growth
    // reallocations without over-allocating.
    const size_t estimated_leaf_count = size() / LeafSize;
    const size_t leaf_reserve = estimated_leaf_count == std::numeric_limits<size_t>::max()
                                 ? estimated_leaf_count : estimated_leaf_count + 1;
    mine.reserve(leaf_reserve);
    theirs.reserve(leaf_reserve);
    collect_leaf_pointers(root_.get(), mine);
    collect_leaf_pointers(other.root_.get(), theirs);
 
    size_t i = 0, j = 0, i_off = 0, j_off = 0;
    while (i < mine.size())
      {
        if (i_off == 0 and j_off == 0 and mine[i] == theirs[j])
          {
            // Same shared leaf node on both sides: identical by
            // construction (Rope never mutates a leaf in place), skip
            // straight to the next pair without comparing characters.
            ++i;
            ++j;
            continue;
          }
        const Node &a = *mine[i];
        const Node &b = *theirs[j];
        const size_t n = std::min(a.length - i_off, b.length - j_off);
        // std::equal over a raw pointer range (rather than a hand-rolled
        // per-index loop) gives the compiler a standard, recognizable
        // pattern -- for `Char` types where equality is the built-in
        // one, this is commonly folded into a single memcmp-style bulk
        // comparison instead of one function-call-per-character.
        const Char *pa = a.leaf_data->data() + i_off;
        const Char *pb = b.leaf_data->data() + j_off;
        if (not std::equal(pa, pa + n, pb))
          return false;
        i_off += n;
        j_off += n;
        if (i_off == a.length)
          {
            ++i;
            i_off = 0;
          }
        if (j_off == b.length)
          {
            ++j;
            j_off = 0;
          }
      }
    return true;
  }
 
  [[nodiscard]] bool verify() const noexcept
  {
    return verify_rec(root_.get());
  }
};
 
}  // namespace Aleph
 
#endif  // TPL_ROPE_H