Cpl::Container::AvlTree_ Class Reference

This concrete class implements the core functionality of for AVL Binary tree (i.e. More...

Detailed Description

This concrete class implements the core functionality of for AVL Binary tree (i.e.

a sorted list with fast searches, inserts, and deletes). Tree does not allow duplicate keys. Clients should NOT USE THIS CLASS DIRECTLY, but via a Map. The Map class is a wrapper that makes the AVL tree type safe.

This class was adapted from Jonathan Bertoni C code snippet: 'non-recursive non-allocating avl tree code'

The original code is in the public domain and is available at: https://sourceforge.net/snippet/detail.php?type=snippet&id=100933

#include <AvlTree_.h>

Public Member Functions
	AvlTree_ ()
	Constructor.
	AvlTree_ (const char *ignoreThisParameter_usedToCreateAUniqueConstructor)
	This is a special constructor for when the list is statically declared (i.e.
bool	insert (MapItem &node)
	Inserts an item into the tree.
MapItem *	removeItem (MapItem &node)
	Deletes the specified item from the tree.
MapItem *	find (const Key &keyToFind) const
	Searches for a item with a matching key. Returns 0 if not found.
MapItem *	first () const
	Returns the first item in the tree. Returns 0 if tree is empty.
MapItem *	last () const
	Returns the last item in the tree. Returns 0 if tree is empty.

Static Public Member Functions
static MapItem *	next (MapItem &current)
	Returns the next item in the tree. Returns 0 if at the end-of-tree.
static MapItem *	previous (MapItem &current)
	Returns the previous item in the tree. Returns 0 if at the start-of-tree.

Constructor & Destructor Documentation

AvlTree_() [1/2]

Cpl::Container::AvlTree_::AvlTree_

(

)

Constructor.

AvlTree_() [2/2]

Cpl::Container::AvlTree_::AvlTree_

(

const char *

ignoreThisParameter_usedToCreateAUniqueConstructor

)

This is a special constructor for when the list is statically declared (i.e.

it is initialized as part of C++ startup BEFORE main() is executed. C/C++ guarantees that all statically declared data will be initialized to zero by default (see r.8.4 in C++ Programming Language, Second Edition). Since the head & tail pointers are initialized to zero - then the C/C++ default is OK. Why do I care about all this? Because if you attempt to build static list(s), then the order of when the list is constructed vs. when the static elements are added to the list is a problem! To avoid this problem, a alternate constructor that does NOT initialize the head & tail pointers is provided. It assumes that the pointers are already set zero because the list is "static". Whew!

Member Function Documentation

find()

MapItem * Cpl::Container::AvlTree_::find

(

const Key &

keyToFind

)

const

Searches for a item with a matching key. Returns 0 if not found.

first()

MapItem * Cpl::Container::AvlTree_::first

(

)

const

Returns the first item in the tree. Returns 0 if tree is empty.

insert()

bool Cpl::Container::AvlTree_::insert

(

MapItem &

node

)

Inserts an item into the tree.

If the node is successfully inserted, then the method return true. If the tree already contains a node with the same key, then the method returns false.

last()

MapItem * Cpl::Container::AvlTree_::last

(

)

const

Returns the last item in the tree. Returns 0 if tree is empty.

next()

static MapItem * Cpl::Container::AvlTree_::next ( MapItem &  current )

static

Returns the next item in the tree. Returns 0 if at the end-of-tree.

previous()

static MapItem * Cpl::Container::AvlTree_::previous ( MapItem &  current )

static

Returns the previous item in the tree. Returns 0 if at the start-of-tree.

removeItem()

MapItem * Cpl::Container::AvlTree_::removeItem

(

MapItem &

node

)

Deletes the specified item from the tree.

Returns the node deleted. If the delete fails (i.e. node does not exist in the tree), then 0 is returned.

---

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

• Cpl/Container/AvlTree_.h