Ordered binary tree. More...

#include <base/collection/OrderedBinaryTree.h>

Classes
class	Iterator

class	ReadIterator

Public Types
typedef TYPE	Value

typedef KEY	Key

typedef BinaryTree< TYPE >::Node	Node

typedef InfixOrderEnumerator< EnumeratorTraits< Node > >	Enumerator

typedef InfixOrderEnumerator< ReadEnumeratorTraits< Node > >	ReadEnumerator

typedef PrefixOrderIterator< IteratorTraits< Node > >	NodePrefixIterator

typedef PrefixOrderIterator< ReadIteratorTraits< Node > >	NodeReadPrefixIterator

typedef InfixOrderIterator< IteratorTraits< Node > >	NodeInfixIterator

typedef InfixOrderIterator< ReadIteratorTraits< Node > >	NodeReadInfixIterator

typedef PostfixOrderIterator< IteratorTraits< Node > >	NodePostfixIterator

typedef PostfixOrderIterator< ReadIteratorTraits< Node > >	NodeReadPostfixIterator

typedef InfixOrderIterator< IteratorTraits< Node > >	NodeIterator

typedef InfixOrderIterator< ReadIteratorTraits< Node > >	NodeReadIterator

Public Member Functions
	OrderedBinaryTree () noexcept

	OrderedBinaryTree (const OrderedBinaryTree &copy)

OrderedBinaryTree &	operator= (const OrderedBinaryTree &copy)

Enumerator	getEnumerator () noexcept

ReadEnumerator	getReadEnumerator () const noexcept

ReadIterator	begin () const noexcept

ReadIterator	end () const noexcept

Node *	find (const Key &value) noexcept

const Node *	find (const Key &value) const noexcept

Node *	getFirst () noexcept

Node *	getLast () noexcept

Node *	rebalance (Node *node) noexcept

void	rebalance ()

bool	rebalance (Node *node, bool right) noexcept

Pair< Node *, bool >	add (const Value &value)

Value *	add2 (const Value &value)

Pair< Node *, bool >	add (Value &&value)

Value *	add2 (Value &&value)

void	remove (Node *node)

template<class PREDICATE >
MemorySize	removeImpl (Node *node, PREDICATE predicate)

template<class PREDICATE >
MemorySize	removeByPredicate (PREDICATE predicate)

Iterator	remove (const Iterator &it)

void	removeAll ()

Static Public Member Functions
static bool	invariant (const Node a, const Node b)

Additional Inherited Members
Protected Types inherited from BinaryTree< TYPE >
typedef TYPE	Value

typedef BinaryNode< TYPE >	Node

typedef PrefixOrderEnumerator< EnumeratorTraits< Node > >	Enumerator

typedef PrefixOrderEnumerator< ReadEnumeratorTraits< Node > >	ReadEnumerator

typedef PrefixOrderIterator< ReadIteratorTraits< Node > >	ReadIterator

Protected Member Functions inherited from BinaryTree< TYPE >
	BinaryTree ()

	BinaryTree (const BinaryTree &copy) noexcept

BinaryTree &	operator= (const BinaryTree &copy) noexcept

bool	isEmpty () const noexcept

Node *	getRoot ()

const Node *	getRoot () const noexcept

Enumerator	getEnumerator () noexcept

ReadEnumerator	getReadEnumerator () const noexcept

void	setRoot (Node *node)

void	removeAll ()

Protected Attributes inherited from BinaryTree< TYPE >
Reference< BinaryTreeImpl >	elements

Detailed Description

template<class TYPE, class KEY = TYPE>
class OrderedBinaryTree< TYPE, KEY >

Ordered binary tree.

Binary tree with the nodes ordered. All the values of the left and right subtrees are respectively less than and greater than the value for any node.

Version: 1.0

Member Typedef Documentation

◆ Enumerator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderEnumerator<EnumeratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::Enumerator

Modifying enumerator.

◆ Key

template<class TYPE , class KEY = TYPE>

typedef KEY OrderedBinaryTree< TYPE, KEY >::Key

The type of the key.

◆ Node

template<class TYPE , class KEY = TYPE>

typedef BinaryTree<TYPE>::Node OrderedBinaryTree< TYPE, KEY >::Node

The type of the node.

◆ NodeInfixIterator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderIterator<IteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeInfixIterator

Modifying iterator.

◆ NodeIterator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderIterator<IteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeIterator

Modifying iterator.

◆ NodePostfixIterator

template<class TYPE , class KEY = TYPE>

typedef PostfixOrderIterator<IteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodePostfixIterator

Modifying iterator.

◆ NodePrefixIterator

template<class TYPE , class KEY = TYPE>

typedef PrefixOrderIterator<IteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodePrefixIterator

Modifying iterator.

◆ NodeReadInfixIterator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderIterator<ReadIteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeReadInfixIterator

Non-modifying iterator.

◆ NodeReadIterator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderIterator<ReadIteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeReadIterator

Non-modifying iterator.

◆ NodeReadPostfixIterator

template<class TYPE , class KEY = TYPE>

typedef PostfixOrderIterator<ReadIteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeReadPostfixIterator

Non-modifying iterator.

◆ NodeReadPrefixIterator

template<class TYPE , class KEY = TYPE>

typedef PrefixOrderIterator<ReadIteratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::NodeReadPrefixIterator

Non-modifying iterator.

◆ ReadEnumerator

template<class TYPE , class KEY = TYPE>

typedef InfixOrderEnumerator<ReadEnumeratorTraits<Node> > OrderedBinaryTree< TYPE, KEY >::ReadEnumerator

Non-modifying enumerator.

◆ Value

template<class TYPE , class KEY = TYPE>

typedef TYPE OrderedBinaryTree< TYPE, KEY >::Value

The type of the value.

Constructor & Destructor Documentation

◆ OrderedBinaryTree() [1/2]

template<class TYPE , class KEY = TYPE>

OrderedBinaryTree< TYPE, KEY >::OrderedBinaryTree ( )

inlinenoexcept

Initializes an empty ordered binary tree.

◆ OrderedBinaryTree() [2/2]

template<class TYPE , class KEY = TYPE>

OrderedBinaryTree< TYPE, KEY >::OrderedBinaryTree ( const OrderedBinaryTree< TYPE, KEY > & copy )

inline

Initializes binary tree from other binary tree.

Member Function Documentation

◆ add() [1/2]

template<class TYPE , class KEY = TYPE>

Pair<Node*, bool> OrderedBinaryTree< TYPE, KEY >::add ( const Value & value )

inline

Adds a value to the binary tree.

Parameters

value The value to be added.

Returns: The node and boolean which is true if node was added.

◆ add() [2/2]

template<class TYPE , class KEY = TYPE>

Pair<Node*, bool> OrderedBinaryTree< TYPE, KEY >::add ( Value && value )

inline

Adds a value to the binary tree.

Parameters

value The value to be added.

Returns: The node and boolean which is true if node was added.

◆ add2() [1/2]

template<class TYPE , class KEY = TYPE>

Value* OrderedBinaryTree< TYPE, KEY >::add2 ( const Value & value )

inline

Adds a value to the binary tree.

Parameters

value The value to be added.

Returns: The value if it already exists. nullptr if the value was not found in the tree.

◆ add2() [2/2]

template<class TYPE , class KEY = TYPE>

Value* OrderedBinaryTree< TYPE, KEY >::add2 ( Value && value )

inline

Adds a value to the binary tree.

Parameters

value The value to be added.

Returns: The value if it already exists. nullptr if the value was not found in the tree.

◆ begin()

template<class TYPE , class KEY = TYPE>

ReadIterator OrderedBinaryTree< TYPE, KEY >::begin ( ) const

inlinenoexcept

Returns a non-modifying iterator of the ordered binary tree.

◆ end()

template<class TYPE , class KEY = TYPE>

ReadIterator OrderedBinaryTree< TYPE, KEY >::end ( ) const

inlinenoexcept

Returns a non-modifying iterator of the ordered binary tree.

◆ find() [1/2]

template<class TYPE , class KEY = TYPE>

const Node* OrderedBinaryTree< TYPE, KEY >::find ( const Key & value ) const

inlinenoexcept

Searches for the specified value in this tree.

Parameters

value The value to look for.

Returns: The node with the matching value. nullptr if not found.

◆ find() [2/2]

template<class TYPE , class KEY = TYPE>

Node* OrderedBinaryTree< TYPE, KEY >::find ( const Key & value )

inlinenoexcept

Searches for the specified value in this tree.

Parameters

value The value to look for.

Returns: The node with the matching value. nullptr if not found.

◆ getEnumerator()

template<class TYPE , class KEY = TYPE>

Enumerator OrderedBinaryTree< TYPE, KEY >::getEnumerator ( )

inlinenoexcept

Returns a modifying enumerator of the ordered binary tree.

◆ getFirst()

template<class TYPE , class KEY = TYPE>

Node* OrderedBinaryTree< TYPE, KEY >::getFirst ( )

inlinenoexcept

Returns the first/smallest value of this tree.

Returns: nullptr if the tree is empty.

◆ getLast()

template<class TYPE , class KEY = TYPE>

Node* OrderedBinaryTree< TYPE, KEY >::getLast ( )

inlinenoexcept

Returns the last/highest value of this tree.

Returns: nullptr if the tree is empty.

◆ getReadEnumerator()

template<class TYPE , class KEY = TYPE>

ReadEnumerator OrderedBinaryTree< TYPE, KEY >::getReadEnumerator ( ) const

inlinenoexcept

Returns a non-modifying enumerator of the ordered binary tree.

◆ operator=()

template<class TYPE , class KEY = TYPE>

OrderedBinaryTree& OrderedBinaryTree< TYPE, KEY >::operator= ( const OrderedBinaryTree< TYPE, KEY > & copy )

inline

Assignment of ordered binary tree to ordered binary tree.

◆ rebalance()

template<class TYPE , class KEY = TYPE>

bool OrderedBinaryTree< TYPE, KEY >::rebalance	(	Node *	node,
		bool	right
	)

inlinenoexcept

Rebalances the given subtree.

◆ remove() [1/2]

template<class TYPE , class KEY = TYPE>

Iterator OrderedBinaryTree< TYPE, KEY >::remove ( const Iterator & it )

inline

Removes the given item and returns the next iterator.

◆ remove() [2/2]

template<class TYPE , class KEY = TYPE>

void OrderedBinaryTree< TYPE, KEY >::remove ( Node * node )

inline

Removes the specified node from the binary tree. Raises InvalidNode if the node is invalid.

Parameters

node	The node to be removed.

◆ removeAll()

template<class TYPE , class KEY = TYPE>

void OrderedBinaryTree< TYPE, KEY >::removeAll ( )

inline

Removes all the nodes from the tree.

◆ removeByPredicate()

template<class TYPE , class KEY = TYPE>

template<class PREDICATE >

MemorySize OrderedBinaryTree< TYPE, KEY >::removeByPredicate ( PREDICATE predicate )

inline

Removes all elements matching the given predicate.

Classes

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

template<class TYPE, class KEY = TYPE> class OrderedBinaryTree< TYPE, KEY >

Member Typedef Documentation

◆ Enumerator

◆ Key

◆ Node

◆ NodeInfixIterator

◆ NodeIterator

◆ NodePostfixIterator

◆ NodePrefixIterator

◆ NodeReadInfixIterator

◆ NodeReadIterator

◆ NodeReadPostfixIterator

◆ NodeReadPrefixIterator

◆ ReadEnumerator

◆ Value

Constructor & Destructor Documentation

◆ OrderedBinaryTree() [1/2]

◆ OrderedBinaryTree() [2/2]

Member Function Documentation

◆ add() [1/2]

◆ add() [2/2]

◆ add2() [1/2]

◆ add2() [2/2]

◆ begin()

◆ end()

◆ find() [1/2]

◆ find() [2/2]

◆ getEnumerator()

◆ getFirst()

◆ getLast()

◆ getReadEnumerator()

◆ operator=()

◆ rebalance()

◆ remove() [1/2]

◆ remove() [2/2]

◆ removeAll()

◆ removeByPredicate()

template<class TYPE, class KEY = TYPE>
class OrderedBinaryTree< TYPE, KEY >