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

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "structure/bbst/persistent-red-black-tree.hpp"

Code

template< typename Monoid, typename F, size_t FULL = 1000 >
struct PersistentRedBlackTree : RedBlackTree< Monoid, F > {
  using RBT = RedBlackTree< Monoid, F >;
  using RBT::RedBlackTree;
  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-red-black-tree.hpp"
template< typename Monoid, typename F, size_t FULL = 1000 >
struct PersistentRedBlackTree : RedBlackTree< Monoid, F > {
  using RBT = RedBlackTree< Monoid, F >;
  using RBT::RedBlackTree;
  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