#include <bintree.hpp>

Inheritance diagram for BF::BinTree< T, S >:

Collaboration diagram for BF::BinTree< T, S >:

Classes
class	BinNode

class	Iterator

Public Member Functions
	BinTree ()

virtual	~BinTree ()

virtual const BinNode *	root () const

void	setCompareCallback (int(*cb)(T a, T b))

int	insert (T obj)

S	count () const

bool	contains (T obj)

virtual void	print ()

T	max () const

T	min () const

virtual const BinNode *	minNode () const

virtual const BinNode *	maxNode () const

virtual int	remove (T obj)

virtual int	deleteNode (BinNode *node)

int	removeAll ()

int	leafValues (List< T > *list)

virtual int	createIterator (Iterator **itr)

virtual const BinNode *	getNodeForObject (T obj)

int	runCompare (T a, T b) const

Public Member Functions inherited from BF::Object
	Object ()

	Object (Object &obj)

virtual	~Object ()

Protected Member Functions
BinNode *	getNodeForObject (T obj, BinNode *node)

BinNode **	rootAddr ()
	Root accessors.

void	setRoot (BinNode *node)

virtual BinNode *	root ()

virtual void *	createNode ()

BinNode **	getNodeLocation (const BinNode *node)

void	setNodeLocation (BinNode node, BinNode *location)

BinNode *	getNodeParent (const BinNode *node)

void	setNodeParent (BinNode node, BinNode parent)

virtual int	insert (BinNode newNode, BinNode parent)

virtual bool	canNewNodeTakeNewLocation (BinNode **newLocation)

virtual int	replaceNodeWithTheOnlyChild (BinNode *node)

virtual int	replaceNodeWithNode (BinNode node, BinNode replacement)

int	removeNode (BinNode *node)

virtual void	print (BinNode *node)

virtual const BinNode *	maxNode (const BinNode *node) const
	Returns the leaf node

virtual const BinNode *	minNode (const BinNode *node) const
	Returns the leaf node

Protected Attributes
S	_count

Additional Inherited Members
Static Public Member Functions inherited from BF::Object
static void	retain (Object *obj)

static void	release (Object *obj)

static int	retainCount (Object *obj)

static int	retainCount (Object &obj)

Detailed Description

template<typename T, typename S = int>
class BF::BinTree< T, S >

Standard Binary Tree

Left most node is the least value comparison

Constructor & Destructor Documentation

◆ BinTree()

template<typename T , typename S = int>

BF::BinTree< T, S >::BinTree ( )

inline

◆ ~BinTree()

template<typename T , typename S = int>

virtual BF::BinTree< T, S >::~BinTree ( )

inlinevirtual

Here is the call graph for this function:

Member Function Documentation

◆ canNewNodeTakeNewLocation()

template<typename T , typename S = int>

virtual bool BF::BinTree< T, S >::canNewNodeTakeNewLocation ( BinNode ** newLocation )

inlineprotectedvirtual

Tests newLocation for a BinNode. We want to make sure a new node can live in this memory location.

Created this function to allow base classes to override functionality and possibly prepare the newLocation for the BinNode

◆ contains()

template<typename T , typename S = int>

bool BF::BinTree< T, S >::contains ( T obj )

inline

Sees if obj is inside our tree start from root

Here is the call graph for this function:

◆ count()

template<typename T , typename S = int>

S BF::BinTree< T, S >::count ( ) const

inline

◆ createIterator()

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::createIterator ( Iterator ** itr )

inlinevirtual

Caller owns memory to the iterator

After you have traversed through all nodes, the iterator becomes stale. To reiterate, you must ask us to create one again

Here is the call graph for this function:

◆ createNode()

template<typename T , typename S = int>

virtual void * BF::BinTree< T, S >::createNode ( )

inlineprotectedvirtual

Creates BinNode

Derived classes must override to submit their own node

◆ deleteNode()

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::deleteNode ( BinNode * node )

inlinevirtual

Removes node from tree and deletes it from memory

Here is the call graph for this function:

◆ getNodeForObject() [1/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::getNodeForObject ( T obj )

inlinevirtual

Returns nonnull pointer to BinNode

Returns NULL if node with obj could not be found

Caller does not own node

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

Here is the call graph for this function:

◆ getNodeForObject() [2/2]

template<typename T , typename S = int>

BinNode * BF::BinTree< T, S >::getNodeForObject	(	T	obj,
		BinNode *	node )

inlineprotected

Returns nonnull pointer to BinNode

Returns NULL if node with obj could not be found

TODO: remove recursion

Here is the call graph for this function:

◆ getNodeLocation()

template<typename T , typename S = int>

BinNode ** BF::BinTree< T, S >::getNodeLocation ( const BinNode * node )

inlineprotected

◆ getNodeParent()

template<typename T , typename S = int>

BinNode * BF::BinTree< T, S >::getNodeParent ( const BinNode * node )

inlineprotected

◆ insert() [1/2]

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::insert	(	BinNode *	newNode,
		BinNode *	parent )

inlineprotectedvirtual

Inserts newNode into parent's children

newNode should already have an obj set. Otherwise there will be undefined behavior

Sets newNode's location field

Here is the call graph for this function:

◆ insert() [2/2]

template<typename T , typename S = int>

int BF::BinTree< T, S >::insert ( T obj )

inline

Inserts object into tree

Here is the call graph for this function:

◆ leafValues()

template<typename T , typename S = int>

int BF::BinTree< T, S >::leafValues ( List< T > * list )

inline

Makes a list of all leaf node values

Returns nonzero upon error

Here is the call graph for this function:

◆ max()

template<typename T , typename S = int>

T BF::BinTree< T, S >::max ( ) const

inline

Here is the call graph for this function:

◆ maxNode() [1/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::maxNode ( ) const

inlinevirtual

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

Here is the call graph for this function:

◆ maxNode() [2/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::maxNode ( const BinNode * node ) const

inlineprotectedvirtual

Returns the leaf node

Here is the call graph for this function:

◆ min()

template<typename T , typename S = int>

T BF::BinTree< T, S >::min ( ) const

inline

Here is the call graph for this function:

◆ minNode() [1/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::minNode ( ) const

inlinevirtual

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

Here is the call graph for this function:

◆ minNode() [2/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::minNode ( const BinNode * node ) const

inlineprotectedvirtual

Returns the leaf node

Here is the call graph for this function:

◆ print() [1/2]

template<typename T , typename S = int>

virtual void BF::BinTree< T, S >::print ( )

inlinevirtual

Prints tree with root at the left most positions and the leafs at the right most, start from the top the right leaves

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

Here is the call graph for this function:

◆ print() [2/2]

template<typename T , typename S = int>

virtual void BF::BinTree< T, S >::print ( BinNode * node )

inlineprotectedvirtual

Here is the call graph for this function:

◆ remove()

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::remove ( T obj )

inlinevirtual

Removes the node that has the object

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

Here is the call graph for this function:

◆ removeAll()

template<typename T , typename S = int>

int BF::BinTree< T, S >::removeAll ( )

inline

Deletes everything in the tree

Here is the call graph for this function:

◆ removeNode()

template<typename T , typename S = int>

int BF::BinTree< T, S >::removeNode ( BinNode * node )

inlineprotected

Performs standard BST Deletion

Here is the call graph for this function:

◆ replaceNodeWithNode()

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::replaceNodeWithNode	(	BinNode *	node,
		BinNode *	replacement )

inlineprotectedvirtual

This node's children will not be exchanged. The replacement's children will be retained. Additionally, the replacement's parent will no longer have any reference to node

Use insert logic to place the children in correctly

Here is the call graph for this function:

◆ replaceNodeWithTheOnlyChild()

template<typename T , typename S = int>

virtual int BF::BinTree< T, S >::replaceNodeWithTheOnlyChild ( BinNode * node )

inlineprotectedvirtual

Replaces node with its child

We assume node only has one kid

Here is the call graph for this function:

◆ root() [1/2]

template<typename T , typename S = int>

virtual BinNode * BF::BinTree< T, S >::root ( )

inlineprotectedvirtual

◆ root() [2/2]

template<typename T , typename S = int>

virtual const BinNode * BF::BinTree< T, S >::root ( ) const

inlinevirtual

Reimplemented in BF::RBTree< T, S >, BF::RBTree< BF::Dictionary::Entry *, int >, and BF::RBTree< BF::Dictionary::Entry *, S >.

◆ rootAddr()

template<typename T , typename S = int>

BinNode ** BF::BinTree< T, S >::rootAddr ( )

inlineprotected

Root accessors.

◆ runCompare()

template<typename T , typename S = int>

int BF::BinTree< T, S >::runCompare	(	T	a,
		T	b ) const

inline

If the _compare function pointer was not set, then we will default by comparing its literal value

0xFFFFFFFF returned if comparison errored

a == b -> 0 a < b -> ret < 0 a > b -> ret > 0

◆ setCompareCallback()

template<typename T , typename S = int>

void BF::BinTree< T, S >::setCompareCallback ( int(* cb )(T a, T b) )

inline

Optional but will help with sorting tree

if not set, we will compare a and b literally

Please set your own comparison if a and b are some other object

◆ setNodeLocation()

template<typename T , typename S = int>

void BF::BinTree< T, S >::setNodeLocation	(	BinNode *	node,
		BinNode **	location )

inlineprotected

◆ setNodeParent()

template<typename T , typename S = int>

void BF::BinTree< T, S >::setNodeParent	(	BinNode *	node,
		BinNode *	parent )

inlineprotected

◆ setRoot()

template<typename T , typename S = int>

void BF::BinTree< T, S >::setRoot ( BinNode * node )

inlineprotected

Member Data Documentation

◆ _count

template<typename T , typename S = int>

S BF::BinTree< T, S >::_count

protected

Holds size of tree

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

bintree.hpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BinTree()

◆ ~BinTree()

Member Function Documentation

◆ canNewNodeTakeNewLocation()

◆ contains()

◆ count()

◆ createIterator()

◆ createNode()

◆ deleteNode()

◆ getNodeForObject() [1/2]

◆ getNodeForObject() [2/2]

◆ getNodeLocation()

◆ getNodeParent()

◆ insert() [1/2]

◆ insert() [2/2]

◆ leafValues()

◆ max()

◆ maxNode() [1/2]

◆ maxNode() [2/2]

◆ min()

◆ minNode() [1/2]

◆ minNode() [2/2]

◆ print() [1/2]

◆ print() [2/2]

◆ remove()

◆ removeAll()

◆ removeNode()

◆ replaceNodeWithNode()

◆ replaceNodeWithTheOnlyChild()

◆ root() [1/2]

◆ root() [2/2]

◆ rootAddr()

◆ runCompare()

◆ setCompareCallback()

◆ setNodeLocation()

◆ setNodeParent()

◆ setRoot()

Member Data Documentation

◆ _count