tpl_link_cut_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_LINK_CUT_TREE_H
# define TPL_LINK_CUT_TREE_H
 
# include <concepts>
# include <initializer_list>
# include <limits>
# include <memory>
# include <type_traits>
# include <utility>
# include <tpl_array.H>
# include <tpl_arrayStack.H>
# include <tpl_tree_node.H>
# include <ah-errors.H>
 
namespace Aleph
{
  // ---------------------------------------------------------------
  //  Concepts
  // ---------------------------------------------------------------
 
  template <typename M, typename T>
  concept LCTMonoid =
      requires(const M & m, const T & a, const T & b)
        {
          { M::identity() } -> std::convertible_to<T>;
          { M::combine(a, b) } -> std::convertible_to<T>;
        };
 
  template <typename L, typename T>
  concept LCTLazyTag =
      std::equality_comparable<typename L::tag_type> and
      requires(const typename L::tag_type & t1,
               const typename L::tag_type & t2,
               const T & val, size_t cnt)
        {
          typename L::tag_type;
          { L::tag_identity() } -> std::convertible_to<typename L::tag_type>;
          { L::apply(val, t1, cnt) } -> std::convertible_to<T>;
          { L::compose(t1, t2) } -> std::convertible_to<typename L::tag_type>;
        };
 
  // ---------------------------------------------------------------
  //  Built-in monoids
  // ---------------------------------------------------------------
 
  template <typename T>
  struct DefaultMonoid
  {
    static constexpr T identity() noexcept { return T{}; }
    static constexpr T combine(const T &, const T & b) noexcept { return b; }
  };
 
  template <typename T>
  struct SumMonoid
  {
    using supports_counted_lazy = std::true_type;
 
    static constexpr T identity() noexcept { return T{0}; }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      return a + b;
    }
  };
 
  template <typename T>
  struct MinMonoid
  {
    static constexpr T identity() noexcept
    {
      return std::numeric_limits<T>::max();
    }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      return a < b ? a : b;
    }
  };
 
  template <typename T>
  struct MaxMonoid
  {
    static constexpr T identity() noexcept
    {
      return std::numeric_limits<T>::lowest();
    }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      return a > b ? a : b;
    }
  };
 
  template <typename T>
  struct XorMonoid
  {
    static constexpr T identity() noexcept { return T{0}; }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      return a ^ b;
    }
  };
 
  template <typename T>
  struct GcdMonoid
  {
    static constexpr T identity() noexcept { return T{0}; }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      T x = a < T{0} ? -a : a;
      T y = b < T{0} ? -b : b;
      while (y != T{0})
        {
          T t = y;
          y = x % y;
          x = t;
        }
      return x;
    }
  };
 
  template <typename T>
  struct ProductMonoid
  {
    static constexpr T identity() noexcept { return T{1}; }
 
    static constexpr T combine(const T & a, const T & b) noexcept
    {
      return a * b;
    }
  };
 
  // ---------------------------------------------------------------
  //  Lazy-tag policies
  // ---------------------------------------------------------------
 
  template <typename T>
  struct NoLazyTag
  {
    using tag_type = bool;
    static constexpr bool tag_identity() noexcept { return false; }
    static constexpr T apply(const T & v, bool, size_t) noexcept { return v; }
    static constexpr bool compose(bool, bool) noexcept { return false; }
  };
 
  template <typename T>
  struct AddLazyTag
  {
    using tag_type = T;
    static constexpr T tag_identity() noexcept { return T{0}; }
 
    static constexpr T apply(const T & v, const T & tag, size_t cnt) noexcept
    {
      return v + tag * static_cast<T>(cnt);
    }
 
    static constexpr T compose(const T & a, const T & b) noexcept
    {
      return a + b;
    }
  };
 
  template <typename T>
  struct AssignLazyTag
  {
    struct tag_type
    {
      T val = {};
      bool active = false;
 
      constexpr bool operator==(const tag_type & o) const noexcept
      {
        return active == o.active and (not active or val == o.val);
      }
    };
 
    static constexpr tag_type tag_identity() noexcept { return {}; }
 
    static constexpr T apply(const T & v, const tag_type & tag,
                             size_t cnt) noexcept
    {
      return tag.active ? tag.val * static_cast<T>(cnt) : v;
    }
 
    static constexpr tag_type compose(const tag_type & existing,
                                      const tag_type & newer) noexcept
    {
      return newer.active ? newer : existing;
    }
  };
 
  template <class Monoid, class = void>
  struct monoid_supports_counted_lazy : std::false_type {};
 
  template <class Monoid>
  struct monoid_supports_counted_lazy<Monoid, std::void_t<typename Monoid::supports_counted_lazy>>
      : std::bool_constant<Monoid::supports_counted_lazy::value> {};
 
  template <class LazyTag, typename T>
  struct is_counted_lazy_tag : std::false_type {};
 
  template <typename T>
  struct is_counted_lazy_tag<AddLazyTag<T>, T> : std::true_type {};
 
  template <typename T>
  struct is_counted_lazy_tag<AssignLazyTag<T>, T> : std::true_type {};
 
  // ---------------------------------------------------------------
  //  Gen_Link_Cut_Tree
  // ---------------------------------------------------------------
 
  template <typename T = int,
            class Monoid = DefaultMonoid<T>,
            class LazyTag = NoLazyTag<T>>
    requires LCTMonoid<Monoid, T> and LCTLazyTag<LazyTag, T>
  class Gen_Link_Cut_Tree
  {
    static_assert(not is_counted_lazy_tag<LazyTag, T>::value
                  or monoid_supports_counted_lazy<Monoid>::value,
                  "AddLazyTag::apply and AssignLazyTag::apply require a monoid "
                  "with supports_counted_lazy=true");
 
  public:
    struct Node
    {
      friend class Gen_Link_Cut_Tree;
 
    private:
      Node *left = nullptr;
      Node *right = nullptr;
      Node *parent = nullptr;
      bool rev = false;
      size_t sz = 1;
 
      T val;
      T agg;
 
      using tag_type = typename LazyTag::tag_type;
      tag_type lazy = LazyTag::tag_identity();
 
      [[nodiscard]] const T &get_val() const noexcept { return val; }
 
      Node() : val(T{}), agg(T{}) {}
      explicit Node(const T & v) : val(v), agg(v) {}
      explicit Node(T && v) : val(std::move(v)), agg(val) {}
    };
 
  private:
    Array<Node *> nodes;
    size_t n_components = 0;
 
    // ---- auxiliary predicates ----
 
    static bool is_root(const Node *x) noexcept
    {
      return x->parent == nullptr or
             (x->parent->left != x and x->parent->right != x);
    }
 
    static bool is_left(const Node *x) noexcept
    {
      return x->parent and x->parent->left == x;
    }
 
    // ---- lazy propagation ----
 
    static void push(Node *x) noexcept
    {
      if (not x)
        return;
 
      if (x->rev)
        {
          std::swap(x->left, x->right);
          if (x->left) x->left->rev ^= true;
          if (x->right) x->right->rev ^= true;
          x->rev = false;
        }
 
      if constexpr (not std::is_same_v<LazyTag, NoLazyTag<T>>)
        {
          if (not (x->lazy == LazyTag::tag_identity()))
            {
              auto propagate = [&](Node *c)
                {
                  if (not c)
                    return;
                  c->val = LazyTag::apply(c->val, x->lazy, 1);
                  c->agg = LazyTag::apply(c->agg, x->lazy, c->sz);
                  c->lazy = LazyTag::compose(c->lazy, x->lazy);
                };
              propagate(x->left);
              propagate(x->right);
              x->lazy = LazyTag::tag_identity();
            }
        }
    }
 
    // ---- aggregate recomputation ----
 
    static void pull(Node *x) noexcept
    {
      if (not x)
        return;
 
      x->sz = 1;
      x->agg = x->val;
 
      if (x->left)
        {
          x->sz += x->left->sz;
          x->agg = Monoid::combine(x->left->agg, x->agg);
        }
      if (x->right)
        {
          x->sz += x->right->sz;
          x->agg = Monoid::combine(x->agg, x->right->agg);
        }
    }
 
    // ---- rotations ----
 
    static void rotate(Node *x) noexcept
    {
      Node *p = x->parent;
      Node *g = p->parent;
 
      if (not is_root(p))
        {
          if (g->left == p)
            g->left = x;
          else
            g->right = x;
        }
 
      if (p->left == x)
        {
          p->left = x->right;
          if (x->right)
            x->right->parent = p;
          x->right = p;
        }
      else
        {
          p->right = x->left;
          if (x->left)
            x->left->parent = p;
          x->left = p;
        }
 
      x->parent = g;
      p->parent = x;
 
      pull(p);
      pull(x);
    }
 
    // ---- splay ----
 
    static void splay(Node *x) noexcept
    {
      // collect ancestors within this auxiliary tree
      // and push lazy flags top-down
      {
        Node *u = x;
        ArrayStack<Node *> stk;
        while (not is_root(u))
          {
            stk.push(u->parent);
            u = u->parent;
          }
        push(u); // push the aux-tree root
        while (not stk.is_empty())
          push(stk.pop());
        push(x);
      }
 
      while (not is_root(x))
        {
          Node *p = x->parent;
          if (not is_root(p))
            // zig-zig or zig-zag
            if (Node *g = p->parent; (g->left == p) == (p->left == x))
              rotate(p); // zig-zig: rotate parent first
            else
              rotate(x); // zig-zag: rotate x first
          rotate(x);
        }
    }
 
    // ---- access ----
 
    // Exposes the root-to-x preferred path.  Returns the last
    // node splayed during traversal (the LCA when preceded by
    // a prior access).
    static Node * access(Node *x) noexcept
    {
      Node *last = nullptr;
      for (Node *u = x; u != nullptr; u = u->parent)
        {
          splay(u);
          u->right = last;
          pull(u);
          last = u;
        }
      splay(x);
      return last;
    }
 
    // ---- iterative in-order traversal of a splay subtree ----
 
    template <typename Op>
    static void inorder_traverse(Node *root, Op && op)
    {
      ArrayStack<Node *> stk;
      Node *cur = root;
      while (cur or not stk.is_empty())
        {
          while (cur)
            {
              push(cur);
              stk.push(cur);
              cur = cur->left;
            }
          cur = stk.pop();
          op(cur);
          cur = cur->right;
        }
    }
 
  public:
    Gen_Link_Cut_Tree() = default;
 
    ~Gen_Link_Cut_Tree()
    {
      for (size_t i = 0; i < nodes.size(); ++i)
        delete nodes(i);
    }
 
    Gen_Link_Cut_Tree(const Gen_Link_Cut_Tree &) = delete;
 
    Gen_Link_Cut_Tree &operator=(const Gen_Link_Cut_Tree &) = delete;
 
    Gen_Link_Cut_Tree(Gen_Link_Cut_Tree &&) = delete;
 
    Gen_Link_Cut_Tree &operator=(Gen_Link_Cut_Tree &&) = delete;
 
    Node * make_vertex(const T & val = T{})
    {
      auto *nd = new Node(val);
      nodes.append(nd);
      ++n_components;
      return nd;
    }
 
    Node * make_vertex(T && val)
    {
      auto *nd = new Node(std::move(val));
      nodes.append(nd);
      ++n_components;
      return nd;
    }
 
    void destroy_vertex(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
 
      size_t idx = 0;
      while (idx < nodes.size() and nodes(idx) != x)
        ++idx;
      ah_domain_error_if(idx == nodes.size())
        << "vertex does not belong to this link-cut tree";
 
      access(x);
      ah_domain_error_if(x->left != nullptr or x->right != nullptr or x->parent != nullptr)
        << "vertex must be isolated";
 
      if (idx + 1 < nodes.size())
        nodes(idx) = nodes(nodes.size() - 1);
      nodes.remove_last();
      delete x;
      --n_components;
    }
 
    [[nodiscard]] size_t size() const noexcept { return nodes.size(); }
 
    void make_root(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      x->rev ^= true;
      push(x);
    }
 
    [[nodiscard]] Node * find_root(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      while (true)
        {
          push(x);
          if (x->left == nullptr)
            break;
          x = x->left;
        }
      splay(x);
      return x;
    }
 
    [[nodiscard]] bool connected(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      if (u == v)
        return true;
      find_root(u);
      find_root(v);
      // after find_root(v), if they were connected, u would be
      // an ancestor of v in the aux tree → u->parent != nullptr
      // But the standard check is simpler:
      return find_root(u) == find_root(v);
    }
 
    void link(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      ah_invalid_argument_if(u == v) << "self-loop";
      make_root(u);
      ah_domain_error_if(find_root(v) == u) << "already connected";
      u->parent = v;
      --n_components;
    }
 
    void cut(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      make_root(u);
      access(v);
      ah_domain_error_if(v->left != u or u->parent != v or u->right != nullptr)
        << "edge does not exist";
      v->left = nullptr;
      u->parent = nullptr;
      pull(v);
      ++n_components;
    }
 
    [[nodiscard]] Node * lca(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      if (u == v)
        return u;
      access(u);
      Node *ans = access(v);
      // verify they were connected: after access(v),
      // u should be reachable via parent chain from v
      // (access(u) already exposed the root-to-u path)
      ah_domain_error_if(find_root(u) != find_root(v)) << "not connected";
      return ans;
    }
 
    [[nodiscard]] T path_query(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      make_root(u);
      ah_domain_error_if(find_root(v) != u) << "vertices not connected";
      access(v);
      return v->agg;
    }
 
    [[nodiscard]] size_t path_size(Node *u, Node *v)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      make_root(u);
      ah_domain_error_if(find_root(v) != u) << "vertices not connected";
      access(v);
      return v->sz;
    }
 
    [[nodiscard]] const T &get_val(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      return x->val;
    }
 
    void set_val(Node *x, const T & val)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      x->val = val;
      pull(x);
    }
 
    void path_apply(Node *u, Node *v, const typename LazyTag::tag_type & tag)
      requires (not std::is_same_v<LazyTag, NoLazyTag<T>>)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      make_root(u);
      ah_domain_error_if(find_root(v) != u) << "vertices not connected";
      access(v);
      v->val = LazyTag::apply(v->val, tag, 1);
      v->agg = LazyTag::apply(v->agg, tag, v->sz);
      v->lazy = LazyTag::compose(v->lazy, tag);
    }
 
    // ---- component & tree queries ----
 
    [[nodiscard]] size_t num_components() const noexcept
    {
      return n_components;
    }
 
    [[nodiscard]] size_t tree_size(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      size_t count = 0;
      for (size_t i = 0; i < nodes.size(); ++i)
        if (connected(nodes(i), x))
          ++count;
      return count;
    }
 
    [[nodiscard]] size_t depth(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      return x->left ? x->left->sz : 0;
    }
 
    [[nodiscard]] Node * parent(Node *x)
    {
      ah_invalid_argument_if(x == nullptr) << "null handle";
      access(x);
      if (not x->left)
        return nullptr;
      Node *p = x->left;
      push(p);
      while (p->right)
        {
          p = p->right;
          push(p);
        }
      splay(p);
      return p;
    }
 
    // ---- iteration ----
 
    template <typename Op>
    void for_each_node(Op && op) const
    {
      for (size_t i = 0; i < nodes.size(); ++i)
        op(nodes(i));
    }
 
    template <typename Op>
    void for_each_on_path(Node *u, Node *v, Op && op)
    {
      ah_invalid_argument_if(u == nullptr or v == nullptr) << "null handle";
      make_root(u);
      ah_domain_error_if(find_root(v) != u) << "vertices not connected";
 
      Array<Node *> rev_path;
      for (Node *cur = v; cur != nullptr; cur = parent(cur))
        rev_path.append(cur);
 
      for (size_t i = rev_path.size(); i > 0; --i)
        op(rev_path(i - 1));
    }
 
    // ---- batch construction ----
 
    Array<Node *> make_path(std::initializer_list<T> vals)
    {
      Array<Node *> result;
      Node *prev = nullptr;
      for (const auto & v: vals)
        {
          auto *nd = make_vertex(v);
          if (prev)
            link(prev, nd);
          prev = nd;
          result.append(nd);
        }
      return result;
    }
 
    Array<Node *> make_vertices(std::initializer_list<T> vals)
    {
      Array<Node *> result;
      for (const auto & v: vals)
        result.append(make_vertex(v));
      return result;
    }
 
    template <typename Container>
    void link_edges(const Container & edges)
    {
      for (const auto & [u, v]: edges)
        link(u, v);
    }
 
    // ---- snapshot export ----
 
    [[nodiscard]] Tree_Node<T> * export_to_tree_node(Node * root)
    {
      ah_invalid_argument_if(root == nullptr) << "null handle";
      make_root(root);
 
      // Collect all nodes in root's component and create Tree_Node copies
      Array<Node *> lct_nodes;
      using TN = Tree_Node<T>;
 
      for_each_node([&](Node * nd)
      {
        if (connected(nd, root))
          lct_nodes.append(nd);
      });
 
      Array<TN *> tree_nodes(lct_nodes.size());
      tree_nodes.putn(lct_nodes.size());
      for (size_t i = 0; i < tree_nodes.size(); ++i)
        tree_nodes(i) = nullptr;
 
      auto find_idx = [&](Node * nd) -> size_t
      {
        for (size_t i = 0; i < lct_nodes.size(); ++i)
          if (lct_nodes(i) == nd)
            return i;
        return lct_nodes.size();
      };
 
      size_t root_idx = find_idx(root);
      struct DestroyTreeDeleter
      {
        void operator()(TN * nd) const noexcept
        {
          if (nd != nullptr)
            destroy_tree(nd);
        }
      };
      std::unique_ptr<TN, DestroyTreeDeleter> root_guard(new TN(root->val));
      tree_nodes(root_idx) = root_guard.get();
 
      for (size_t i = 0; i < lct_nodes.size(); ++i)
        {
          if (i == root_idx)
            continue;
          Node * par = parent(lct_nodes(i));
          if (par != nullptr)
            {
              size_t pi = find_idx(par);
              std::unique_ptr<TN> child(new TN(lct_nodes(i)->val));
              tree_nodes(pi)->insert_rightmost_child(child.get());
              tree_nodes(i) = child.release();
            }
        }
 
      return root_guard.release();
    }
  };
 
  using Link_Cut_Tree = Gen_Link_Cut_Tree<int>;
} // namespace Aleph
 
# endif /* TPL_LINK_CUT_TREE_H */