The Zip Tree. More...

#include <ziptree.hpp>

Inheritance diagram for ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >:

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

Detailed Description

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>
class ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >

The Zip Tree.

This is the main Zip Tree class.

Template Parameters

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.

Constructor & Destructor Documentation

◆ ZTree()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::ZTree ( MyClass && other )

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.

Parameters

other The Zip Tree that this one is constructed from

Member Function Documentation

◆ begin()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::begin ( ) const

noexceptinherited

Returns an iterator pointing to the smallest element in the tree.

◆ cbegin()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::cbegin ( ) const

noexceptinherited

Returns an iterator pointing to the smallest element in the tree.

◆ cend()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::cend ( ) const

noexceptinherited

Returns an iterator pointing after the largest element in the tree.

◆ clear()

void ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::clear ( )

noexceptinherited

Removes all elements from the tree.

◆ crbegin()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::crbegin ( ) const

noexceptinherited

Returns an reverse iterator pointing to the largest element in the tree.

◆ crend()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::crend ( ) const

noexceptinherited

Returns an reverse iterator pointing before the smallest element in the tree.

◆ dump_to_dot()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

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.

Parameters

filename The file path where to write the .dot file.

◆ empty()

bool ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::empty ( ) const

noexceptinherited

Returns whether the tree is empty.

This method runs in O(1).

Returns: true if the tree is empty, false otherwise

◆ end()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::end ( ) const

noexceptinherited

Returns an iterator pointing after the largest element in the tree.

◆ erase() [1/2]

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

template<class Comparable >

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.

Warning: The behavior of this method strongly depends on whether the STL_ERASE option is set or not!

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.

◆ erase() [2/2]

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

template<bool reverse>

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.

Warning: The return type of this method depends on whether the STL_ERASE option is set or not!

Removes a node that is pointed to by an iterator.

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. If STL_ERASE is set: An iterator to the node after the removed node (or end()).

◆ find()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::find ( const Comparable & query ) const

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.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparing equally to the element that should be found.

Returns: An iterator to the first element comparing equally to <query>, or end() if no such element exists

◆ insert()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

void ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::insert ( Node & node )

noexcept

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.

Parameters

Node	The node to be inserted.

◆ iterator_to()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::iterator_to ( const Node & node ) const

noexceptinherited

Returns an iterator pointing to the entry held in node.

Parameters

node	The node the iterator should point to.

◆ lower_bound()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::lower_bound ( const Comparable & query ) const

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.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparable to Node that should be lower-bounded

Returns: An iterator to the first element comparing greater-or-equally to <query>, or end() if no such element exists

◆ operator=()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

MyClass& ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::operator= ( MyClass && other )

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.

Parameters

other The Zip Tree that this one is constructed from

◆ rbegin()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::rbegin ( ) const

noexceptinherited

Returns an reverse iterator pointing to the largest element in the tree.

◆ remove()

template<class Node, class NodeTraits, class Options = DefaultOptions, class Tag = int, class Compare = ygg::utilities::flexible_less, class RankGetter = ztree_internal::ZTreeRankGenerator< Node, Options, Options::ztree_use_hash, Options::ztree_store_rank>>

void ygg::ZTree< Node, NodeTraits, Options, Tag, Compare, RankGetter >::remove ( Node & node )

Removes <node> from the tree.

Parameters

Node	The node to be removed.

◆ rend()

const_iterator<true> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::rend ( ) const

noexceptinherited

Returns an reverse iterator pointing before the smallest element in the tree.

◆ size()

size_t ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::size ( ) const

noexceptinherited

Return the number of elements in the tree.

This method runs in O(1).

Warning: This method is only available if CONSTANT_TIME_SIZE is set as option!

Returns: The number of elements in the tree.

◆ upper_bound()

const_iterator<false> ygg::bst::BinarySearchTree< Node, Options, Tag, Compare, DefaultParentContainer<Node> >::upper_bound ( const Comparable & query ) const

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.

Warning: Not available for explicitly ordered trees

Parameters

query An object comparable to Node that should be upper-bounded

Returns: An iterator to the first element comparing "greater" to <query>, or end() if no such element exists

The documentation for this class was generated from the following file:

/home/lukas/src/intervaltree/ygg/src/ziptree.hpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ZTree()

Member Function Documentation

◆ begin()

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ dump_to_dot()

◆ empty()

◆ end()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find()

◆ insert()

◆ iterator_to()

◆ lower_bound()

◆ operator=()

◆ rbegin()

◆ remove()

◆ rend()

◆ size()

◆ upper_bound()