The Zip Tree. More...
#include <ziptree.hpp>
Public Types | |
using | NB = ZTreeNodeBase< Node, Options, Tag > |
using | TB = bst::BinarySearchTree< Node, Options, Tag, Compare > |
using | MyClass = ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter > |
template<bool reverse> | |
using | iterator = typename TB::template iterator< reverse > |
template<bool reverse> | |
using | const_iterator = typename TB::template const_iterator< reverse > |
Public Member Functions | |
ZTree () noexcept | |
Construct a new empty Zip Tree. | |
ZTree (MyClass &&other) noexcept | |
Create a new Zip Tree from a different Zip Tree. More... | |
MyClass & | operator= (MyClass &&other) noexcept |
Move-assign an other Zip Tree to this one. More... | |
void | insert (Node &node) noexcept |
Inserts <node> into the tree. More... | |
void | insert (Node &node, Node &hint) noexcept |
void | remove (Node &node) CMP_NOEXCEPT(node) |
Removes <node> from the tree. More... | |
template<class Comparable > | |
utilities::select_type_t< size_t, Node *, Options::stl_erase > | erase (const Comparable &c) CMP_NOEXCEPT(c) |
Deletes a node that compares equally to from the tree. More... | |
template<bool reverse> | |
utilities::select_type_t< const iterator< reverse >, Node *, Options::stl_erase > | erase (const iterator< reverse > &it) CMP_NOEXCEPT(*it) |
Deletes a node by iterator. More... | |
void | dbg_verify () const |
void | dbg_print_rank_stats () const |
void | dump_to_dot (const std::string &filename) const |
Debugging Method: Draw the Tree as a .dot file. More... | |
const_iterator< false > | find (const Comparable &query) const CMP_NOEXCEPT(query) |
Finds an element in the tree. More... | |
iterator< false > | find (const Comparable &query) CMP_NOEXCEPT(query) |
iterator< false > | find (const Comparable &query, Callbacks *cbs) |
const_iterator< false > | upper_bound (const Comparable &query) const CMP_NOEXCEPT(query) |
Upper-bounds an element. More... | |
iterator< false > | upper_bound (const Comparable &query) CMP_NOEXCEPT(query) |
const_iterator< false > | lower_bound (const Comparable &query) const CMP_NOEXCEPT(query) |
Lower-bounds an element. More... | |
iterator< false > | lower_bound (const Comparable &query) CMP_NOEXCEPT(query) |
const_iterator< false > | cbegin () const noexcept |
const_iterator< false > | cend () const noexcept |
const_iterator< false > | begin () const noexcept |
iterator< false > | begin () noexcept |
const_iterator< false > | end () const noexcept |
iterator< false > | end () noexcept |
const_iterator< true > | crbegin () const noexcept |
const_iterator< true > | crend () const noexcept |
const_iterator< true > | rbegin () const noexcept |
iterator< true > | rbegin () noexcept |
const_iterator< true > | rend () const noexcept |
iterator< true > | rend () noexcept |
const_iterator< false > | iterator_to (const Node &node) const noexcept |
iterator< false > | iterator_to (Node &node) noexcept |
size_t | size () const noexcept |
void | clear () noexcept |
Removes all elements from the tree. More... | |
bool | empty () const noexcept |
Returns whether the tree is empty. More... | |
Node * | get_root () const noexcept |
Static Public Member Functions | |
static Node * | get_parent (Node *n) noexcept |
static Node * | get_left_child (Node *n) noexcept |
static Node * | get_right_child (Node *n) noexcept |
Protected Member Functions | |
Node * | get_first_equal (Node *n) noexcept |
Node * | get_smallest () const noexcept |
Node * | get_largest () const noexcept |
Node * | get_uncle (Node *node) const noexcept |
Protected Attributes | |
Node * | root |
Compare | cmp |
SizeHolder< Options::constant_time_size > | s |
The Zip Tree.
This is the main Zip Tree class.
Node | The node class for this tree. It must be derived from ZTreeNodeBase. |
NodeTraits | A class implementing various hooks and functions on your node class. See DOCTODO for details. |
Options | The TreeOptions class specifying the parameters of this ZTree. See the TreeOptions and TreeFlags classes for details. |
Tag | An class tag that identifies this tree. Can be used to insert the same nodes into multiple trees. See DOCTODO for details. Can be any class, the class can be empty. |
Compare | A compare class. The Zip Tree follows STL semantics for 'Compare'. Defaults to ygg::utilities::flexible_less. Implement operator<(const Node & lhs, const Node & rhs) if you want to use it. |
RankGetter | A class that must implement a static size_t get_rank(const Node &) function that returns the rank of a node. If you implement this yourself (instead of using the provided default), you are responsible of making sure that the ranks uphold the assumptions that zip trees make regarding the ranks. |
|
noexcept |
Create a new Zip Tree from a different Zip Tree.
The other Zip Tree is moved into this one, i.e., using it afterwards is undefined behavior.
other | The Zip Tree that this one is constructed from |
|
noexceptinherited |
Returns an iterator pointing to the smallest element in the tree.
|
noexceptinherited |
Returns an iterator pointing to the smallest element in the tree.
|
noexceptinherited |
Returns an iterator pointing after the largest element in the tree.
|
noexceptinherited |
Removes all elements from the tree.
Removes all elements from the tree.
|
noexceptinherited |
Returns an reverse iterator pointing to the largest element in the tree.
|
noexceptinherited |
Returns an reverse iterator pointing before the smallest element in the tree.
void ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::dump_to_dot | ( | const std::string & | filename | ) | const |
Debugging Method: Draw the Tree as a .dot file.
Outputs the current tree as a .dot file which can be drawn using graphviz.
filename | The file path where to write the .dot file. |
|
noexceptinherited |
Returns whether the tree is empty.
This method runs in O(1).
|
noexceptinherited |
Returns an iterator pointing after the largest element in the tree.
utilities::select_type_t<size_t, Node *, Options::stl_erase> ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::erase | ( | const Comparable & | c | ) |
Deletes a node that compares equally to from the tree.
Removes a node that compares equally to from the tree.
If STL_ERASE is set, this method removes all nodes that compare equally to c from the tree and returns the number of nodes removed.
If STL_ERASE is not set, it removes only one node and returns a pointer to the removed node.
Parameters
c Anything comparable to a node. A node (resp. all nodes, see above) that compares equally will be removed
- Returns
- If STL_ERASE is unset: A pointer to the node that has been removed, or nullptr if no node was removed. If STL_ERASE is set: The number of erased nodes.
utilities::select_type_t<const iterator<reverse>, Node *, Options::stl_erase> ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::erase | ( | const iterator< reverse > & | it | ) |
Deletes a node by iterator.
Removes a node that is pointed to by an iterator.
c | Anything comparable to a node. A node (resp. all nodes, see above) that compares equally will be removed |
|
inherited |
Finds an element in the tree.
Returns an iterator to the first element that compares equally to <query>. Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.
query | An object comparing equally to the element that should be found. |
|
noexcept |
Inserts <node> into the tree.
Inserts <node> into the tree.
Warning: Please note that after calling insert() on a node (and before removing that node again), that node may not move in memory. A common pitfall is to store nodes in a std::vector (or other STL container), which reallocates (and thereby moves objecs around).
For zip trees, the hinted version is equivalent to the unhinted insertion.
Node | The node to be inserted. |
|
noexceptinherited |
Returns an iterator pointing to the entry held in node.
node | The node the iterator should point to. |
|
inherited |
Lower-bounds an element.
Returns an iterator to the first element that is not less that <query>, i.e., that does not have to go before <query>.
Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.
query | An object comparable to Node that should be lower-bounded |
|
noexcept |
Move-assign an other Zip Tree to this one.
The other Zip Tree is moved into this one, i.e., using it afterwards is undefined behavior.
other | The Zip Tree that this one is constructed from |
|
noexceptinherited |
Returns an reverse iterator pointing to the largest element in the tree.
void ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::remove | ( | Node & | node | ) |
Removes <node> from the tree.
Removes <node> from the tree.
Node | The node to be removed. |
|
noexceptinherited |
Returns an reverse iterator pointing before the smallest element in the tree.
|
noexceptinherited |
Return the number of elements in the tree.
This method runs in O(1).
|
inherited |
Upper-bounds an element.
Returns an iterator to the smallest element to which <query> compares as "less", i.e. the smallest element that is considered go strictly after <query>.
Note that <query> does not have to be a Node, but can be anything that can be compared to a Node, i.e., for which Compare()(const Node &, const Comparable &) and Compare()(const Comparable &, const Node &) are defined and implemented. In the case of using the default ygg::utilities::flexible_less as Compare, that means you have to implement operator<() for both types.
query | An object comparable to Node that should be upper-bounded |