JASS::binary_tree< KEY, ELEMENT > Class Template Reference

Thread-safe unballanced binary tree that uses an allocator, and consequently never calls delete on elements or keys. More...

#include <binary_tree.h>

Collaboration diagram for JASS::binary_tree< KEY, ELEMENT >:

Classes
class	iterator
	Iterate over the binary tree. More...
class	node
	A node within the binary tree. More...

Public Member Functions
	binary_tree (allocator &pool)
	Constructor. More...
iterator	begin () const
	Return an iterator pointing to left-most (smallest) node in the tree. More...
iterator	end () const
	Return an iterator pointing past the end of the tree. More...
ELEMENT &	operator[] (const KEY &key)
	Return a reference to the element stored for the given key. If no element is stored for the key then a new empty element is made. More...

Static Public Member Functions
static void	unittest (void)
	Unit test this class.

Protected Member Functions
ELEMENT &	find_and_add (const KEY &key, node *parent, std::atomic< node *> &current, node *new_node=nullptr)
	If the key exists in the tree then return the data associated with it, else create empty data for the key. More...
void	text_render (std::ostream &stream) const
	Write the contents of this object to the output steam. More...
void	text_render (std::ostream &stream, const std::atomic< node *> &current, size_t depth=0) const
	Helper function for writing to output streams. More...

Protected Attributes
allocator &	pool
	The pool allocator.
std::atomic< node * >	root
	The root of the binary tree.

Related Functions
(Note that these are not member functions.)
template<typename A , typename B >
std::ostream &	operator<< (std::ostream &stream, const binary_tree< A, B > &tree)
	Output a human readable serialisation to an ostream.

Detailed Description

template<typename KEY, typename ELEMENT>
class JASS::binary_tree< KEY, ELEMENT >

Thread-safe unballanced binary tree that uses an allocator, and consequently never calls delete on elements or keys.

Data is kept in nodes and in-order with low on the left and high on the right. Elements are addressed using the operator[key] syntax seen with a std::map. Note that this syntax makes it impossible to have duplicate keys. There is no way to remove an element from the binary tree once added. Note that KEY and ELEMENT must take the allocator in their constructors.

Template Parameters

KEY	The type used as the key to the element (must include KEY(allocator, KEY) copy constructor)
ELEMENT	The element data returned given the key (must include ELEMENT(allocator) constructur)

Constructor & Destructor Documentation

binary_tree()

template<typename KEY, typename ELEMENT>

JASS::binary_tree< KEY, ELEMENT >::binary_tree ( allocator &  pool )

inline

Constructor.

Parameters

pool	[in] The allocator used for all storage within this tree.

Member Function Documentation

begin()

template<typename KEY, typename ELEMENT>

iterator JASS::binary_tree< KEY, ELEMENT >::begin ( ) const

inline

Return an iterator pointing to left-most (smallest) node in the tree.

Returns

Iterator pointing to smallest member of the tree.

end()

template<typename KEY, typename ELEMENT>

iterator JASS::binary_tree< KEY, ELEMENT >::end ( ) const

inline

Return an iterator pointing past the end of the tree.

Returns

Iterator pointing past the end of the tree.

find_and_add()

template<typename KEY, typename ELEMENT>

ELEMENT& JASS::binary_tree< KEY, ELEMENT >::find_and_add ( const KEY &  key, node *  parent, std::atomic< node *> &  current, node *  new_node = nullptr  )

inlineprotected

If the key exists in the tree then return the data associated with it, else create empty data for the key.

Parameters

key	[in] The key to search for.
parent	[in] A pointer to the parent node (used as the "up" pointer for a new node).
current	[in] A reference to the current node pointer.
new_node	[in] A pointer to the node to add to the tree (do not use, this is used internally to avoid memory wastage).

Returns

The element associated with the key, or an empty element if a new node for the key was created.

operator[]()

template<typename KEY, typename ELEMENT>

ELEMENT& JASS::binary_tree< KEY, ELEMENT >::operator[] ( const KEY &  key )

inline

Return a reference to the element stored for the given key. If no element is stored for the key then a new empty element is made.

Parameters

key	[in] They key to find the data for.

Returns

The element associated with the key - or an empty element if no key previously existed.

text_render() [1/2]

template<typename KEY, typename ELEMENT>

void JASS::binary_tree< KEY, ELEMENT >::text_render ( std::ostream &  stream ) const

inlineprotected

Write the contents of this object to the output steam.

Parameters

stream

[in] The stream to write to.

text_render() [2/2]

template<typename KEY, typename ELEMENT>

void JASS::binary_tree< KEY, ELEMENT >::text_render ( std::ostream &  stream, const std::atomic< node *> &  current, size_t  depth = 0  ) const

inlineprotected

Helper function for writing to output streams.

Parameters

stream	[in] The stream to write to.
current	[in] A reference to the node to write.
depth	[in] The level of recursion (used for spacing).

---

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

• source/binary_tree.h