RedBlackTree.hpp

Vá para a documentação deste arquivo.

#ifndef PERSISTENCE_REDBLACKTREE_HPP_
#define PERSISTENCE_REDBLACKTREE_HPP_

#include <vector>

namespace persistence {

namespace red_black_tree {

template<class T> class Node {
    public:


    Node *child[2];

    bool red;

    const T value;


    int timestamp;

    Node *copy;

    Node *parent;


    Node *extra;

    bool extraSide;

    int extraTimestamp;


    Node(const T& val, int version);
};

template<class T> class RedBlackTree {
    public:


    const T* Find(const T& x, int version);

     void Insert(const T& value);

     const T* Remove(const T& value);

    inline int current();


    std::vector<Node<T>*> roots;
    

    RedBlackTree();
    ~RedBlackTree();

    Node<T>* Child(Node<T> *u, bool side, int version) const;


    Node<T>* Active(Node<T> *u);

    Node<T>* Child(Node<T> *u, bool side);

    void Modify(Node<T> *u, bool side, Node<T> *v);

    Node<T> *Copy(Node<T> *u);

    void Rotate(Node<T> *u, bool side);

    void Transplant(Node<T> *u, Node<T> *x);

    Node<T>* MinElement(Node<T> *u);

    void AddBlack(Node<T> *y, bool side);


};

} // namespace red_black_tree

} // namespace persistence

#include "RedBlackTree.tpp"

#endif // PERSISTENCE_REDBLACKTREE_HPP_