BTree_t< T, K > Class Template Reference
Template binary tree class.
More...
#include <UTLists.h>
List of all members.
Detailed Description
template<class T, class K>
class BTree_t< T, K >
Template binary tree class. The template type T must inherit from BTreeNode_t <class T, class K> where T is the node type and K is the node comparison key.
class T must implement a Compare(K key) const function which returns a signed integer. If this comes before key, T::Compare should return a negative number. If this comes after key, T::Compare should return a positive number. If this equals key, T::Compare should return 0. The compare function can be inline. If it would be more efficient (if the key type is not a] basic type or pointer), the Compare function can and probably should be implemented as Compare(const K& key) const instead.
class T must implement a const operator K or const operator const K& (depending on which is more efficient for the node type). That operator can, and usually should, be inline. The declaration would typically be of one of these forms:
inline operator K() const;
inline operator const K&() const;
If a list of items is constructed once then searched by key, a SortedList_t should be used instead due to its better memory usage and search efficiency.
Definition at line 322 of file UTLists.h.
Constructor & Destructor Documentation
template<class T , class K >
Constructor for an empty tree.
Definition at line 1988 of file UTLists.h.
Member Function Documentation
template<class T , class K>
| T * BTree_t< T, K >::FindItem |
( |
K |
key |
) |
const [inline] |
Searches the tree for an item with a matching key, returning it if it is found, or NULL if it is not. If multiple items have the same key, the matching item closest to the head will be returned.
Definition at line 1997 of file UTLists.h.
template<class T , class K>
| T * BTree_t< T, K >::FindItemAtOrBefore |
( |
K |
key |
) |
const [inline] |
Searches the tree for an item with a matching key, returning it if it is found, the item immediately before key if an exact match was not found, or NULL if no such item exists. If multiple items have the same key, the matching item closest to the tail will be returned.
Definition at line 2029 of file UTLists.h.
template<class T , class K>
| T * BTree_t< T, K >::FindItemAtOrAfter |
( |
K |
key |
) |
const [inline] |
Searches the tree for an item with a matching key, returning it if it is found, the item immediately after key if an exact match was not found, or NULL if no such item exists. If multiple items have the same key, the matching item closest to the head will be returned.
Definition at line 2065 of file UTLists.h.
template<class T, class K >
| T * BTree_t< T, K >::IsInTree |
( |
T * |
item |
) |
const [inline] |
Searches the tree for the specified item, returning a pointer to it if it is found or NULL if it is not.
Definition at line 2424 of file UTLists.h.
template<class T, class K >
| void BTree_t< T, K >::AddItem |
( |
T * |
new_item, |
|
|
bool |
balance_tree = true | |
|
) |
| | [inline] |
Searches for the appropriate position in the tree, and adds new_item at that location. If one or more items in the tree already have the same key, the new item will be added closest to the tail.
Definition at line 2101 of file UTLists.h.
template<class T , class K >
| T * BTree_t< T, K >::RemoveHead |
( |
bool |
balance_tree = true |
) |
[inline] |
Removes and returns the item at the head of the tree.
Definition at line 2338 of file UTLists.h.
template<class T , class K >
| T * BTree_t< T, K >::RemoveTail |
( |
bool |
balance_tree = true |
) |
[inline] |
Removes and returns the item at the end of the tree.
Definition at line 2381 of file UTLists.h.
template<class T, class K >
| T * BTree_t< T, K >::RemoveItem |
( |
T * |
item, |
|
|
bool |
balance_tree = true | |
|
) |
| | [inline] |
Removes and returns the specified item.
Definition at line 2437 of file UTLists.h.
template<class T , class K >
| int BTree_t< T, K >::CountItems |
( |
|
) |
const [inline] |
Returns the number of items in the tree.
Definition at line 2571 of file UTLists.h.
template<class T , class K >
| T * BTree_t< T, K >::Head |
( |
|
) |
const [inline] |
Returns the item at the head of the tree. Use BTreeNode_t <class T, class K>Next to walk the tree.
Definition at line 2579 of file UTLists.h.
template<class T , class K >
| T * BTree_t< T, K >::Tail |
( |
|
) |
const [inline] |
Returns the item at the end of the tree. Use BTreeNode_t <class T, class K>Prev to walk the tree.
Definition at line 2592 of file UTLists.h.
template<class T , class K >
| T * BTree_t< T, K >::Root |
( |
|
) |
const [inline] |
Returns the item at the root of the tree. Use BTreeNode_t <class T, class K>Next or BTreeNode_t <class T, class K>Prev to walk the tree.
Definition at line 2605 of file UTLists.h.
template<class T, class K >
| void BTree_t< T, K >::operator+= |
( |
T * |
new_item |
) |
[inline] |
Searches for the appropriate position in the tree, and adds new_item at that location. If one or more items in the tree already have the same key, the new item will be added closest to the tail.
Definition at line 2613 of file UTLists.h.
template<class T, class K >
| void BTree_t< T, K >::operator-= |
( |
T * |
item |
) |
[inline] |
Removes the specified item from the tree.
Definition at line 2621 of file UTLists.h.
The documentation for this class was generated from the following file:
- D:/develop/svn/utlib/utlib/trunk/UT/src_UT/UTLists.h
