base class for both map and set – should not be used directly More...

#include <orbtree_base.h>

Inheritance diagram for orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >:

[legend]

Collaboration diagram for orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >:

Public Types
typedef NodeAllocator::NVType	NVType
	Type the function NVFunc returns.

Public Member Functions
void	clear ()
	erase all nodes

template<class K >
void	get_sum_fv (const K &k, NVType *res) const
	get the generalized rank for a key, i.e. the sum of NVFunc for all nodes with node.key < k

void	get_sum_fv_node (NodeHandle x, NVType *res) const
	get the generalized rank for a given node, i.e. the sum of NVFunv for all nodes before it in order

void	get_norm_fv (NVType *res) const
	get the normalization factor, i.e. the sum of all keys

void	check_tree (double epsilon=-1.0) const
	check that the tree is valid More...

template<class... T>
auto	emplace (T &&... t) -> std::pair< NodeHandle, bool >

template<class... T>
auto	emplace_hint (NodeHandle hint, T &&... t) -> NodeHandle

Protected Types
typedef NodeAllocator::Node	Node
	node objects

typedef NodeAllocator::KeyValue	KeyValue

typedef NodeAllocator::KeyValue::KeyType	KeyType

typedef NodeAllocator::KeyValue::ValueType	ValueType

typedef NodeAllocator::NodeHandle	NodeHandle
	handle to refer nodes to (pointer or integer)

Protected Member Functions
void	NVAdd (NVType x, const NVType y) const
	function to add NVType values; checks for overflow and throws exception in the case of integral types

void	NVSubtract (NVType x, const NVType y) const
	function to subtract NVType values; checks for overflow and throws exception in the case of integral types

void	create_sentinels ()

Node &	get_node (NodeHandle n)
	convenience function that returns node object for a node handle

const Node &	get_node (NodeHandle n) const
	convenience function that returns node object for a node handle

NodeHandle	root () const
	handle of root sentinel

NodeHandle	nil () const
	handle of nil sentinel

	orbtree_base (const NVFunc &f_, const Compare &c_)

	orbtree_base (NVFunc &&f_, const Compare &c_)

template<class T >
	orbtree_base (const T &t, const Compare &c_)

std::pair< NodeHandle, bool >	insert (ValueType &&kv)
	Insert new element. More...

std::pair< NodeHandle, bool >	insert (const ValueType &kv)
	Insert new element. More...

NodeHandle	insert (NodeHandle hint, ValueType &&kv)
	Insert new element with hint. More...

NodeHandle	insert (NodeHandle hint, const ValueType &kv)
	Insert new element with hint. More...

template<class... T>
std::pair< NodeHandle, bool >	emplace (T &&... t)
	Construct new element in place. More...

template<class... T>
NodeHandle	emplace_hint (NodeHandle hint, T &&... t)
	Construct new element in place with hint. More...

bool	insert_search (const KeyType &k, NodeHandle &n, bool &insert_left) const
	helper for insert – find the location where to insert More...

bool	insert_search_hint (NodeHandle hint, const KeyType &k, NodeHandle &n, bool &insert_left) const
	helper for insert – find the location where to insert More...

void	insert_helper (NodeHandle n, NodeHandle n1, bool insert_left)
	helper function to do the real work for insert More...

template<class K >
auto	find (const K &key) const -> NodeHandle
	find any node with the given key More...

template<class K >
auto	lower_bound (const K &key) const -> NodeHandle
	find the first node not less than the given key – returns nil if none found

template<class K >
auto	upper_bound (const K &key) const -> NodeHandle
	find the first node larger than the given key – returns nil if none found

const KeyType &	get_node_key (NodeHandle n) const
	convenience function to get the key of a node

bool	compare_key_equals (NodeHandle n, const KeyType &k) const
	helper for erase to compare elements

void	get_node_grvalue (NodeHandle n, NVType *res) const
	get the value of NVFunc for the given node More...

NodeHandle	first () const
	get first node (or nil)

NodeHandle	last () const
	get last node (or nil)

NodeHandle	next (NodeHandle n) const
	get node after n (or nil) – note: next(nil) == nil

NodeHandle	previous (NodeHandle n) const
	get node before n (or nil) – note: previous(nil) == last() to make it easier to implement end() iterator

NodeHandle	erase (NodeHandle n)
	remove the given node – return the next node (i.e. next(n) before deleting n)

Node &	get_left (NodeHandle n)
	convenience helper to get node object that is the left child of the given node handle

const Node &	get_left (NodeHandle n) const
	convenience helper to get node object that is the left child of the given node handle

Node &	get_right (NodeHandle n)
	convenience helper to get node object that is the right child of the given node handle

const Node &	get_right (NodeHandle n) const
	convenience helper to get node object that is the right child of the given node handle

Node &	get_parent (NodeHandle n)
	convenience helper to get node object that is the parent of the given node handle

const Node &	get_parent (NodeHandle n) const
	convenience helper to get node object that is the parent of the given node handle

NodeHandle	get_sibling_handle (NodeHandle n) const
	convenience helper to get the handle of a node's sibling (i.e. parent's other child)

Node &	get_sibling (NodeHandle n)
	convenience helper to get the node object of a node's sibling (i.e. parent's other child)

const Node &	get_sibling (NodeHandle n) const
	convenience helper to get the node object of a node's sibling (i.e. parent's other child)

bool	is_left_side (NodeHandle n) const
	check which side child is n (i.e. returns true if n is the left child of its parent) – requires that n != root

void	update_sum (NodeHandle n)
	update the sum only inside n

void	update_sum_r (NodeHandle n)
	update the sum recursively up the tree

template<class KeyValue_ = KeyValue>
void	update_value (NodeHandle n, typename KeyValue_::MappedType const &v)
	update value in a node – only if this is a map; update sum recursively based on it as well

template<class KeyValue_ = KeyValue>
void	update_value (NodeHandle n, typename KeyValue_::MappedType &&v)
	update value in a node – only if this is a map; update sum recursively based on it as well

void	rotate_left (NodeHandle x)
	left rotate More...

void	rotate_right (NodeHandle x)
	right rotate More...

void	rotate_parent (NodeHandle x)
	rotate by parent of x (x takes parent's place), this calls either rotate_left() or rotate_right() with the parent of x

void	check_tree_r (double epsilon, NodeHandle x, size_t black_count, size_t &previous_black_count) const
	recursive helper for check_tree(double)

Protected Member Functions inherited from orbtree::NVFunc_wrapper< NVFunc >
	NVFunc_wrapper (const NVFunc &f_)

	NVFunc_wrapper (NVFunc &&f_)

template<class T >
	NVFunc_wrapper (const T &t)

Protected Attributes
size_t	size1
	keep track of the number of inserted elements

NVFunc &	f

Compare	c

Protected Attributes inherited from orbtree::NVFunc_wrapper< NVFunc >
NVFunc	f

Detailed Description

template<class NodeAllocator, class Compare, class NVFunc, bool multi>
class orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >

base class for both map and set – should not be used directly

Template Parameters

NodeAllocator	Class taking care of allocating and freeing nodes, should be NodeAllocatorPtr or NodeAllocatorCompact from orbtree_node.h
Compare	Comparison functor
NVFunc	Function that calculates each node's "value" – it is assumed to be a vector-valued function, so these values are stored and manipulated in arrays. It should have a function get_nr() that return the number of values to use. See NVFunc_Adapter_Simple and NVFunc_Adapter_Vec for examples.
multi	Whether multiple nodes with the same key are allowed.

Member Function Documentation

◆ check_tree()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

void orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::check_tree ( double epsilon = -1.0 ) const

check that the tree is valid

Checks that binary tree and red-black tree properties are OK, throws exception on error. Also checks that rank function values (partial sums) are consistent as well if epsilon >= 0 (epsilon is the tolerance for rounding errors if NVType is not integral)

◆ emplace()

template<class NodeAllocator, class Compare, class NVFunc, bool multi>

template<class... T>

std::pair<NodeHandle,bool> orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::emplace ( T &&... t )

protected

Construct new element in place.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

◆ emplace_hint()

template<class NodeAllocator, class Compare, class NVFunc, bool multi>

template<class... T>

NodeHandle orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::emplace_hint	(	NodeHandle	hint,
		T &&...	t
	)

protected

Construct new element in place with hint.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

Caller suggests a position which is before the element pointed to by the supplied iterator.

For non-multi tree (map/set; i.e. duplicates are not allowed):

if the hint points to the correct position (i.e. the new element should go before the element referenced by the hint iterator), then a search is not performed, so the insertion cost is amortized constant
in all other cases, the hint is ignored

For multi tree (duplicate keys are allowed):

if the key is equal to the key of element referenced by the hint iterator, then the new element is inserted before it
otherwise, the new element is inserted as close as possible

◆ find()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

template<class K >

auto orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::find ( const K & key ) const -> NodeHandle

protected

find any node with the given key

K should be comparable to KeyType

returns nil if not found (to make it easier with iterators)

◆ get_node_grvalue()

template<class NodeAllocator, class Compare, class NVFunc, bool multi>

void orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::get_node_grvalue	(	NodeHandle	n,
		NVType *	res
	)		const

inlineprotected

get the value of NVFunc for the given node

should not be called with nil, root or Invalid

note that rank function can depend on a node's value as well; care need to be taken to update rank if a node's value changes!

◆ insert() [1/4]

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

auto orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert ( ValueType && kv )

protected

Insert new element.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

◆ insert() [2/4]

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

auto orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert ( const ValueType & kv )

protected

Insert new element.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

◆ insert() [3/4]

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

auto orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert	(	NodeHandle	hint,
		ValueType &&	kv
	)

protected

Insert new element with hint.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

Caller suggests a position which is before the element pointed to by the supplied iterator.

For non-multi tree (map/set; i.e. duplicates are not allowed):

if the hint points to the correct position (i.e. the new element should go before the element referenced by the hint iterator), then a search is not performed, so the insertion cost is amortized constant
in all other cases, the hint is ignored

For multi tree (duplicate keys are allowed):

if the key is equal to the key of element referenced by the hint iterator, then the new element is inserted before it
otherwise, the new element is inserted as close as possible

◆ insert() [4/4]

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

auto orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert	(	NodeHandle	hint,
		const ValueType &	kv
	)

protected

Insert new element with hint.

Return type is always std::pair<iterator,bool>, where the first element is a handle to the newly inserted node and the second element indicates if insert was successful.

For multi map/set, insert always succeeds, to the second element is always true. In this case, a new element is always inserted after any existing elements with the same key.

For a non-multi map/set, insert fails if an element with the same key already exists. In this case, a handle to the element with the same key is returned along with false in the second element.

Caller suggests a position which is before the element pointed to by the supplied iterator.

For non-multi tree (map/set; i.e. duplicates are not allowed):

if the hint points to the correct position (i.e. the new element should go before the element referenced by the hint iterator), then a search is not performed, so the insertion cost is amortized constant
in all other cases, the hint is ignored

For multi tree (duplicate keys are allowed):

if the key is equal to the key of element referenced by the hint iterator, then the new element is inserted before it
otherwise, the new element is inserted as close as possible

◆ insert_helper()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

void orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert_helper	(	NodeHandle	n,
		NodeHandle	n1,
		bool	insert_left
	)

protected

helper function to do the real work for insert

insert n1 as the left / right child of n

n1 must already contain the proper key / value, but can be uninitialized otherwise

note: this function does not check for the correct relationship between the keys of n and n1, that is the caller's responsibility

◆ insert_search()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

bool orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert_search	(	const KeyType &	k,
		NodeHandle &	n,
		bool &	insert_left
	)		const

protected

helper for insert – find the location where to insert

note: in a multi map/set, the inserted element will come after any already existing elements with the same key

Return true if insert is possible, false if element already exists and this is a non-multi map/set.

◆ insert_search_hint()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

bool orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::insert_search_hint	(	NodeHandle	hint,
		const KeyType &	k,
		NodeHandle &	n,
		bool &	insert_left
	)		const

protected

helper for insert – find the location where to insert

note: in a multi map/set, the inserted element will come after any already existing elements with the same key

Return true if insert is possible, false if element already exists and this is a non-multi map/set.

Try to insert as close to hint as possible. Note: if hint is bad, it is ignored.

◆ rotate_left()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

void orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::rotate_left ( NodeHandle x )

protected

left rotate

right child of x takes its place, x becomes its left child left child of x's original right child becomes x's right child

◆ rotate_right()

template<class NodeAllocator , class Compare , class NVFunc , bool multi>

void orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >::rotate_right ( NodeHandle x )

protected

right rotate

left child of x takes its place, y becomes its right child right child of x's original left child becomes x's left child

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

orbtree_base.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class NodeAllocator, class Compare, class NVFunc, bool multi> class orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >

Member Function Documentation

◆ check_tree()

◆ emplace()

◆ emplace_hint()

◆ find()

◆ get_node_grvalue()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ insert_helper()

◆ insert_search()

◆ insert_search_hint()

◆ rotate_left()

◆ rotate_right()

template<class NodeAllocator, class Compare, class NVFunc, bool multi>
class orbtree::orbtree_base< NodeAllocator, Compare, NVFunc, multi >