structure/bbst/persistent-lazy-red-black-tree.hpp

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "structure/bbst/persistent-lazy-red-black-tree.hpp"

Code

template <typename Monoid, typename OperatorMonoid, typename F, typename G,
          typename H, size_t FULL = 1000>
struct PersistentLazyRedBlackTree
    : LazyRedBlackTree<Monoid, OperatorMonoid, F, G, H> {
  using RBT = LazyRedBlackTree<Monoid, OperatorMonoid, F, G, H>;
  using RBT::LazyRedBlackTree;
  using Node = typename RBT::Node;

 private:
  Node *clone(Node *t) override { return &(*RBT::pool.alloc() = *t); }

 public:
  Node *rebuild(Node *r) {
    auto ret = RBT::dump(r);
    RBT::pool.clear();
    return RBT::build(ret);
  }

  bool almost_full() const { return this->pool.ptr < FULL; }
};

#line 1 "structure/bbst/persistent-lazy-red-black-tree.hpp"
template <typename Monoid, typename OperatorMonoid, typename F, typename G,
          typename H, size_t FULL = 1000>
struct PersistentLazyRedBlackTree
    : LazyRedBlackTree<Monoid, OperatorMonoid, F, G, H> {
  using RBT = LazyRedBlackTree<Monoid, OperatorMonoid, F, G, H>;
  using RBT::LazyRedBlackTree;
  using Node = typename RBT::Node;

 private:
  Node *clone(Node *t) override { return &(*RBT::pool.alloc() = *t); }

 public:
  Node *rebuild(Node *r) {
    auto ret = RBT::dump(r);
    RBT::pool.clear();
    return RBT::build(ret);
  }

  bool almost_full() const { return this->pool.ptr < FULL; }
};

Back to top page