tpl_cartesian_tree.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  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_CARTESIAN_TREE_H
# define TPL_CARTESIAN_TREE_H
 
# include <cassert>
# include <cstddef>
# include <concepts>
# include <initializer_list>
# include <type_traits>
# include <utility>
# include <vector>
# include <tpl_array.H>
# include <tpl_dynList.H>
# include <tpl_sparse_table.H>
# include <ahFunction.H>
# include <ah-errors.H>
# include <ah-concepts.H>
 
namespace Aleph
{
  template <typename T, class Comp>
    requires StrictWeakOrder<Comp, T>
  class Gen_Cartesian_Tree
  {
  public:
    static constexpr size_t NONE = static_cast<size_t>(-1);
 
  private:
    Array<T> data_; // original values
    Array<size_t> parent_; // parent[i] = parent of node i
    Array<size_t> left_; // left[i]  = left child of node i
    Array<size_t> right_; // right[i] = right child of node i
    size_t root_; // index of the root node
    size_t n_; // number of elements
 
    Comp comp_;
 
    void build()
    {
      if (n_ == 0)
        {
          root_ = NONE;
          return;
        }
 
      // Stack stored in a plain array — at most n elements
      auto stk = Array<size_t>::create(n_);
      size_t top = 0; // stack size (top points to next free slot)
 
      for (size_t i = 0; i < n_; ++i)
        {
          size_t last_popped = NONE;
 
          // Pop while i is strictly better than stack top (stable on ties)
          while (top > 0 and comp_(data_(i), data_(stk(top - 1))))
            {
              last_popped = stk(top - 1);
              --top;
            }
 
          // The last popped node becomes the left child of i
          left_(i) = last_popped;
          if (last_popped != NONE)
            parent_(last_popped) = i;
 
          // i becomes right child of the current stack top
          if (top > 0)
            {
              right_(stk(top - 1)) = i;
              parent_(i) = stk(top - 1);
            }
          else
            parent_(i) = NONE;
 
          stk(top++) = i;
        }
 
      root_ = stk(0); // the bottom of the stack is the root
    }
 
    void init_and_build()
    {
      parent_ = Array<size_t>::create(n_);
      left_ = Array<size_t>::create(n_);
      right_ = Array<size_t>::create(n_);
      for (size_t i = 0; i < n_; ++i)
        {
          parent_(i) = NONE;
          left_(i) = NONE;
          right_(i) = NONE;
        }
      build();
    }
 
  public:
    using Item_Type = T;
 
    Gen_Cartesian_Tree(const Array<T> & values, Comp c = Comp())
      : data_(values), root_(NONE), n_(values.size()), comp_(c)
    {
      init_and_build();
    }
 
    Gen_Cartesian_Tree(const std::vector<T> & values, Comp c = Comp())
      : data_(Array<T>::create(values.size())), root_(NONE),
        n_(values.size()), comp_(c)
    {
      for (size_t i = 0; i < n_; ++i)
        data_(i) = values[i];
      init_and_build();
    }
 
    Gen_Cartesian_Tree(std::initializer_list<T> il, Comp c = Comp())
      : data_(Array<T>::create(il.size())), root_(NONE),
        n_(il.size()), comp_(c)
    {
      size_t i = 0;
      for (auto it = il.begin(); it != il.end(); ++it)
        data_(i++) = *it;
      init_and_build();
    }
 
    Gen_Cartesian_Tree(const DynList<T> & values, Comp c = Comp())
      : data_(Array<T>::create(values.size())), root_(NONE),
        n_(values.size()), comp_(c)
    {
      size_t i = 0;
      for (auto it = values.get_it(); it.has_curr(); it.next_ne())
        data_(i++) = it.get_curr();
      init_and_build();
    }
 
    Gen_Cartesian_Tree(const size_t num, const T & init, Comp c = Comp())
      : data_(Array<T>::create(num)), root_(NONE), n_(num), comp_(c)
    {
      for (size_t i = 0; i < n_; ++i)
        data_(i) = init;
      init_and_build();
    }
 
    Gen_Cartesian_Tree(const Gen_Cartesian_Tree &) = default;
 
    Gen_Cartesian_Tree &operator=(const Gen_Cartesian_Tree &) = default;
 
    Gen_Cartesian_Tree(Gen_Cartesian_Tree &&) noexcept(
      std::is_nothrow_move_constructible_v<Array<T>> and
      std::is_nothrow_move_constructible_v<Comp>) = default;
 
    Gen_Cartesian_Tree &operator=(Gen_Cartesian_Tree &&) noexcept(
      std::is_nothrow_move_assignable_v<Array<T>> and
      std::is_nothrow_move_assignable_v<Comp>) = default;
 
    [[nodiscard]] constexpr size_t root() const noexcept { return root_; }
 
    size_t left_child(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::left_child: i=" << i << " >= n=" << n_;
      return left_(i);
    }
 
    size_t right_child(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::right_child: i=" << i << " >= n=" << n_;
      return right_(i);
    }
 
    size_t parent_of(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::parent_of: i=" << i << " >= n=" << n_;
      return parent_(i);
    }
 
    const T &data_at(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::data_at: i=" << i << " >= n=" << n_;
      return data_(i);
    }
 
    [[nodiscard]] constexpr size_t size() const noexcept { return n_; }
 
    [[nodiscard]] constexpr bool is_empty() const noexcept { return n_ == 0; }
 
    bool is_leaf(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::is_leaf: i=" << i << " >= n=" << n_;
      return left_(i) == NONE and right_(i) == NONE;
    }
 
    bool is_root(const size_t i) const
    {
      ah_out_of_range_error_if(i >= n_)
        << "Gen_Cartesian_Tree::is_root: i=" << i << " >= n=" << n_;
      return i == root_;
    }
 
    [[nodiscard]] size_t height() const
    {
      if (n_ == 0)
        return 0;
 
      size_t max_depth = 0;
 
      // DFS with explicit stack: (node, depth)
      struct Entry
      {
        size_t node;
        size_t depth;
      };
      auto stk = Array<Entry>::create(n_);
      size_t top = 0;
      stk(top++) = {root_, 1};
 
      while (top > 0)
        {
          auto [node, depth] = stk(--top);
          if (depth > max_depth)
            max_depth = depth;
          if (right_(node) != NONE)
            stk(top++) = {right_(node), depth + 1};
          if (left_(node) != NONE)
            stk(top++) = {left_(node), depth + 1};
        }
 
      return max_depth;
    }
 
    [[nodiscard]] Array<size_t> inorder() const
    {
      if (n_ == 0)
        return {};
 
      auto result = Array<size_t>::create(n_);
      size_t idx = 0;
 
      // Iterative inorder with explicit stack
      auto stk = Array<size_t>::create(n_);
      size_t top = 0;
      size_t curr = root_;
 
      while (curr != NONE or top > 0)
        {
          while (curr != NONE)
            {
              stk(top++) = curr;
              curr = left_(curr);
            }
          curr = stk(--top);
          result(idx++) = curr;
          curr = right_(curr);
        }
 
      return result;
    }
 
    [[nodiscard]] Array<T> values() const
    {
      auto ret = Array<T>::create(n_);
      for (size_t i = 0; i < n_; ++i)
        ret(i) = data_(i);
      return ret;
    }
 
    void swap(Gen_Cartesian_Tree & other)
      noexcept(noexcept(data_.swap(other.data_)) &&
               noexcept(parent_.swap(other.parent_)) &&
               noexcept(left_.swap(other.left_)) &&
               noexcept(right_.swap(other.right_)) &&
               noexcept(std::swap(root_, other.root_)) &&
               noexcept(std::swap(n_, other.n_)) &&
               std::is_nothrow_swappable_v<Comp>)
    {
      data_.swap(other.data_);
      parent_.swap(other.parent_);
      left_.swap(other.left_);
      right_.swap(other.right_);
      std::swap(root_, other.root_);
      std::swap(n_, other.n_);
      std::swap(comp_, other.comp_);
    }
  };
 
  template <std::totally_ordered T>
  struct Cartesian_Tree
      : public Gen_Cartesian_Tree<T, Aleph::less<T>>
  {
    using Base = Gen_Cartesian_Tree<T, Aleph::less<T>>;
    using Base::Base;
  };
 
  template <std::totally_ordered T>
  struct Max_Cartesian_Tree
      : public Gen_Cartesian_Tree<T, Aleph::greater<T>>
  {
    using Base = Gen_Cartesian_Tree<T, Aleph::greater<T>>;
    using Base::Base;
  };
 
 
  // ================================================================
  // Gen_Euler_Tour_LCA — LCA in O(1) via Euler Tour + Sparse Table
  // ================================================================
 
  template <typename T, class Comp>
    requires StrictWeakOrder<Comp, T>
  class Gen_Euler_Tour_LCA
  {
    struct DepthEntry
    {
      size_t depth;
      size_t node;
    };
 
    struct DepthMinOp
    {
      constexpr DepthEntry operator()(const DepthEntry & a,
                                      const DepthEntry & b) const noexcept
      {
        return a.depth <= b.depth ? a : b;
      }
    };
 
    Gen_Cartesian_Tree<T, Comp> tree_;
    Array<size_t> euler_; // euler tour: 2n-1 node indices
    Array<size_t> depth_arr_; // depth at each euler tour position
    Array<size_t> first_; // first_[node] = first position in euler
    Array<size_t> node_depth_; // depth of each node in the tree
    Gen_Sparse_Table<DepthEntry, DepthMinOp> sparse_;
    size_t euler_size_;
 
    void build_euler_tour()
    {
      const size_t n = tree_.size();
      if (n == 0)
        return;
 
      constexpr size_t NONE = Gen_Cartesian_Tree<T, Comp>::NONE;
 
      euler_size_ = 2 * n - 1;
      euler_ = Array<size_t>::create(euler_size_);
      depth_arr_ = Array<size_t>::create(euler_size_);
      first_ = Array<size_t>::create(n);
      node_depth_ = Array<size_t>::create(n);
 
      for (size_t i = 0; i < n; ++i)
        first_(i) = NONE;
 
      // Stack entries: (node, phase, depth, cached children)
      // phase 0: first visit — record euler, push left child
      // phase 1: back from left — if left existed, record euler;
      //          push right child
      // phase 2: back from right — if right existed, record euler;
      //          pop
      struct Frame
      {
        size_t node;
        int phase;
        size_t depth;
        size_t left;
        size_t right;
      };
      auto make_frame = [this](const size_t node, const size_t depth) -> Frame
      {
        return {node, 0, depth, tree_.left_child(node), tree_.right_child(node)};
      };
      auto stk = Array<Frame>::create(n);
      size_t top = 0;
      size_t eidx = 0;
 
      stk(top++) = make_frame(tree_.root(), 0);
 
      while (top > 0)
        {
          if (auto & frame = stk(top - 1); frame.phase == 0)
            {
              // First visit — always record
              euler_(eidx) = frame.node;
              depth_arr_(eidx) = frame.depth;
              node_depth_(frame.node) = frame.depth;
              first_(frame.node) = eidx;
              ++eidx;
              frame.phase = 1;
 
              if (frame.left != NONE)
                stk(top++) = make_frame(frame.left, frame.depth + 1);
            }
          else if (frame.phase == 1)
            {
              // Back from left subtree
              if (frame.left != NONE)
                {
                  // We actually returned from left child — record again
                  euler_(eidx) = frame.node;
                  depth_arr_(eidx) = frame.depth;
                  ++eidx;
                }
              frame.phase = 2;
 
              if (frame.right != NONE)
                stk(top++) = make_frame(frame.right, frame.depth + 1);
            }
          else
            {
              // Back from right subtree
              if (frame.right != NONE)
                {
                  // We actually returned from right child — record again
                  euler_(eidx) = frame.node;
                  depth_arr_(eidx) = frame.depth;
                  ++eidx;
                }
              --top;
            }
        }
 
      // Euler tour length is exactly 2*n-1 for any non-empty binary tree.
      assert(eidx == euler_size_);
    }
 
    void build_sparse_table()
    {
      if (euler_size_ == 0)
        return;
 
      auto entries = Array<DepthEntry>::create(euler_size_);
      for (size_t i = 0; i < euler_size_; ++i)
        entries(i) = {depth_arr_(i), euler_(i)};
 
      sparse_ = Gen_Sparse_Table<DepthEntry, DepthMinOp>(entries);
    }
 
  public:
    Gen_Euler_Tour_LCA(const Array<T> & values, Comp c = Comp())
      : tree_(values, c), sparse_(0, DepthEntry{0, 0}), euler_size_(0)
    {
      build_euler_tour();
      build_sparse_table();
    }
 
    Gen_Euler_Tour_LCA(const std::vector<T> & values, Comp c = Comp())
      : tree_(values, c), sparse_(0, DepthEntry{0, 0}), euler_size_(0)
    {
      build_euler_tour();
      build_sparse_table();
    }
 
    Gen_Euler_Tour_LCA(std::initializer_list<T> il, Comp c = Comp())
      : tree_(il, c), sparse_(0, DepthEntry{0, 0}), euler_size_(0)
    {
      build_euler_tour();
      build_sparse_table();
    }
 
    Gen_Euler_Tour_LCA(const DynList<T> & values, Comp c = Comp())
      : tree_(values, c), sparse_(0, DepthEntry{0, 0}), euler_size_(0)
    {
      build_euler_tour();
      build_sparse_table();
    }
 
    Gen_Euler_Tour_LCA(const size_t num, const T & init, Comp c = Comp())
      : tree_(num, init, c), sparse_(0, DepthEntry{0, 0}), euler_size_(0)
    {
      build_euler_tour();
      build_sparse_table();
    }
 
    size_t lca(const size_t u, const size_t v) const
    {
      const size_t n = tree_.size();
      ah_out_of_range_error_if(u >= n)
        << "Gen_Euler_Tour_LCA::lca: u=" << u << " >= n=" << n;
      ah_out_of_range_error_if(v >= n)
        << "Gen_Euler_Tour_LCA::lca: v=" << v << " >= n=" << n;
 
      size_t l = first_(u);
      size_t r = first_(v);
      if (l > r)
        std::swap(l, r);
 
      return sparse_.query(l, r).node;
    }
 
    size_t depth_of(const size_t u) const
    {
      ah_out_of_range_error_if(u >= tree_.size())
        << "Gen_Euler_Tour_LCA::depth_of: u=" << u << " >= n=" << tree_.size();
      return node_depth_(u);
    }
 
    size_t distance(const size_t u, const size_t v) const
    {
      const size_t ancestor = lca(u, v);
      return node_depth_(u) + node_depth_(v) - 2 * node_depth_(ancestor);
    }
 
    [[nodiscard]] constexpr size_t size() const noexcept
    {
      return tree_.size();
    }
 
    [[nodiscard]] constexpr bool is_empty() const noexcept
    {
      return tree_.is_empty();
    }
 
    const Gen_Cartesian_Tree<T, Comp> &tree() const noexcept
    {
      return tree_;
    }
 
    [[nodiscard]] Array<size_t> euler_tour() const
    {
      auto ret = Array<size_t>::create(euler_size_);
      for (size_t i = 0; i < euler_size_; ++i)
        ret(i) = euler_(i);
      return ret;
    }
 
    [[nodiscard]] size_t euler_tour_size() const noexcept
    {
      return euler_size_;
    }
  };
 
  template <std::totally_ordered T>
  struct Euler_Tour_LCA
      : public Gen_Euler_Tour_LCA<T, Aleph::less<T>>
  {
    using Base = Gen_Euler_Tour_LCA<T, Aleph::less<T>>;
    using Base::Base;
  };
 
  template <std::totally_ordered T>
  struct Max_Euler_Tour_LCA
      : public Gen_Euler_Tour_LCA<T, Aleph::greater<T>>
  {
    using Base = Gen_Euler_Tour_LCA<T, Aleph::greater<T>>;
    using Base::Base;
  };
 
 
  // ================================================================
  // Gen_Cartesian_Tree_RMQ — O(1) RMQ via Cartesian Tree + LCA
  // ================================================================
 
  template <typename T, class Comp>
    requires StrictWeakOrder<Comp, T>
  class Gen_Cartesian_Tree_RMQ
  {
    Gen_Euler_Tour_LCA<T, Comp> lca_;
 
  public:
    using Item_Type = T;
 
    Gen_Cartesian_Tree_RMQ(const Array<T> & values, Comp c = Comp())
      : lca_(values, c) {}
 
    Gen_Cartesian_Tree_RMQ(const std::vector<T> & values, Comp c = Comp())
      : lca_(values, c) {}
 
    Gen_Cartesian_Tree_RMQ(std::initializer_list<T> il, Comp c = Comp())
      : lca_(il, c) {}
 
    Gen_Cartesian_Tree_RMQ(const DynList<T> & values, Comp c = Comp())
      : lca_(values, c) {}
 
    Gen_Cartesian_Tree_RMQ(const size_t num, const T & init,
                           Comp c = Comp())
      : lca_(num, init, c) {}
 
    T query(const size_t l, const size_t r) const
    {
      ah_out_of_range_error_if(l > r)
        << "Gen_Cartesian_Tree_RMQ::query: l=" << l << " > r=" << r;
      ah_out_of_range_error_if(r >= lca_.size())
        << "Gen_Cartesian_Tree_RMQ::query: r=" << r << " >= n=" << lca_.size();
 
      return lca_.tree().data_at(lca_.lca(l, r));
    }
 
    size_t query_idx(const size_t l, const size_t r) const
    {
      ah_out_of_range_error_if(l > r)
        << "Gen_Cartesian_Tree_RMQ::query_idx: l=" << l << " > r=" << r;
      ah_out_of_range_error_if(r >= lca_.size())
        << "Gen_Cartesian_Tree_RMQ::query_idx: r=" << r << " >= n=" << lca_.size();
 
      return lca_.lca(l, r);
    }
 
    T get(const size_t i) const
    {
      return lca_.tree().data_at(i);
    }
 
    [[nodiscard]] constexpr size_t size() const noexcept
    {
      return lca_.size();
    }
 
    [[nodiscard]] constexpr bool is_empty() const noexcept
    {
      return lca_.is_empty();
    }
 
    [[nodiscard]] Array<T> values() const
    {
      return lca_.tree().values();
    }
 
    const Gen_Euler_Tour_LCA<T, Comp> &lca_engine() const noexcept
    {
      return lca_;
    }
  };
 
  template <std::totally_ordered T>
  struct Cartesian_Tree_RMQ
      : public Gen_Cartesian_Tree_RMQ<T, Aleph::less<T>>
  {
    using Base = Gen_Cartesian_Tree_RMQ<T, Aleph::less<T>>;
    using Base::Base;
  };
 
  template <std::totally_ordered T>
  struct Cartesian_Tree_RMaxQ
      : public Gen_Cartesian_Tree_RMQ<T, Aleph::greater<T>>
  {
    using Base = Gen_Cartesian_Tree_RMQ<T, Aleph::greater<T>>;
    using Base::Base;
  };
} // end namespace Aleph
 
# endif /* TPL_CARTESIAN_TREE_H */