Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

TLBTree< T, _OP >::Node Struct Reference

Iternally used tree node type. More...

#include <tlbtree.h>

Collaboration diagram for TLBTree< T, _OP >::Node:

Collaboration graph
[legend]
List of all members.

Public Member Functions

T & elem (int idx, TLBTree *bt)
 Use this to access the elements:.

T * elemP (int idx, TLBTree *bt)
 Pointer version of elem():.

template<typename K> bool _LBI (const K &e, int *idx, TLBTree *bt)
 Implements binary search for child branch.

void _INSLeafNS (int idx, const T &e, TLBTree *bt)
 Insert element before the passed index.

void _INS_NS (int idx, const T &e, Node *chld, TLBTree *bt)
 Insert element and associated branch pointer before the passed index.

void _DELLeaf (int idx, TLBTree *bt)
void _DEL_L (int idx, TLBTree *bt)
 Remove entry with passed index and its _left_ down pointer from non-leaf node.

void _DEL_R (int idx, TLBTree *bt)
 Remove entry with passed index and its _right_ down pointer from non-leaf node.

 Node ()
 ~Node ()

Public Attributes

int nelem
 Number of elements stored.

Node ** down
 Children nodes [2*m+1] or NULL if leaf.

char _elem []
 Array of 2*m elements.

Detailed Description

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
struct TLBTree< T, _OP >::Node

Iternally used tree node type.

For internal use only.

Definition at line 82 of file tlbtree.h.

Constructor & Destructor Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
TLBTree< T, _OP >::Node::Node (   )  [inline]
 

Definition at line 204 of file tlbtree.h.

References TLBTree< T, _OP >::Node::down, and TLBTree< T, _OP >::Node::nelem.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
TLBTree< T, _OP >::Node::~Node (   )  [inline]
 

Definition at line 205 of file tlbtree.h.

Member Function Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLBTree< T, _OP >::Node::_DEL_L (  int  idx,
TLBTree *  bt
)  [inline]
 

Remove entry with passed index and its _left_ down pointer from non-leaf node.

For internal use only.

Definition at line 181 of file tlbtree.h.

References TLBTree< T, _OP >::Node::down, TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLBTree< T, _OP >::Node::_DEL_R (  int  idx,
TLBTree *  bt
)  [inline]
 

Remove entry with passed index and its _right_ down pointer from non-leaf node.

For internal use only.

Definition at line 193 of file tlbtree.h.

References TLBTree< T, _OP >::Node::down, TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLBTree< T, _OP >::Node::_DELLeaf (  int  idx,
TLBTree *  bt
)  [inline]
 

For internal use only.

Remove entry with passed index from leaf node.

Definition at line 171 of file tlbtree.h.

References TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLBTree< T, _OP >::Node::_INS_NS (  int  idx,
const T &  e,
Node *  chld,
TLBTree *  bt
)  [inline]
 

Insert element and associated branch pointer before the passed index.

For internal use only.

Must NOT be a leaf node, i.e. down!=NULL. Relies on nelem>=1. idx=0 -> insert as first element; idx=nelem<2*m -> insert as last element; May NOT be called if splitting the node will be necessary, i.e. do not call if nelem==2*m.

Definition at line 158 of file tlbtree.h.

References TLBTree< T, _OP >::Node::down, TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
void TLBTree< T, _OP >::Node::_INSLeafNS (  int  idx,
const T &  e,
TLBTree *  bt
)  [inline]
 

Insert element before the passed index.

For internal use only.

Must be a leaf node, i.e. down=NULL. Relies on nelem>=1. idx=0 -> insert as first element; idx=nelem<2*m -> insert as last element; May NOT be called if splitting the node will be necessary, i.e. do not call if nelem==2*m.

Definition at line 140 of file tlbtree.h.

References TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::elemP(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
template<typename K>
bool TLBTree< T, _OP >::Node::_LBI (  const K &  e,
int *  idx,
TLBTree *  bt
)  [inline]
 

Implements binary search for child branch.

For internal use only.

Lookup (branch) index in this node: range 0..nelem (inclusive). Does binary search O(log(m)). If the node is found (exact match), return value is 1 (match), otherwise it is 0. The index in question is stored in *idx.

Definition at line 104 of file tlbtree.h.

References TLBTree< T, _OP >::Node::elem(), TLBTree< T, _OP >::Node::nelem, and TLBTree< T, _OP >::OP.

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T& TLBTree< T, _OP >::Node::elem (  int  idx,
TLBTree *  bt
)  [inline]
 

Use this to access the elements:.

Definition at line 90 of file tlbtree.h.

References TLBTree< T, _OP >::Node::_elem, and TLBTree< T, _OP >::OP.

Referenced by TLBTree< T, _OP >::Node::_DEL_L(), TLBTree< T, _OP >::Node::_DEL_R(), TLBTree< T, _OP >::Node::_DELLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindSmallest(), TLBTree< T, _OP >::Node::_INS_NS(), TLBTree< T, _OP >::Node::_INSLeafNS(), TLBTree< T, _OP >::Node::_LBI(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::store().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
T* TLBTree< T, _OP >::Node::elemP (  int  idx,
TLBTree *  bt
)  [inline]
 

Pointer version of elem():.

Definition at line 93 of file tlbtree.h.

References TLBTree< T, _OP >::Node::_elem, and TLBTree< T, _OP >::OP.

Referenced by TLBTree< T, _OP >::Node::_DEL_L(), TLBTree< T, _OP >::Node::_DEL_R(), TLBTree< T, _OP >::Node::_DELLeaf(), TLBTree< T, _OP >::Node::_INS_NS(), and TLBTree< T, _OP >::Node::_INSLeafNS().

Member Data Documentation

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
char TLBTree< T, _OP >::Node::_elem[]
 

Array of 2*m elements.

Definition at line 86 of file tlbtree.h.

Referenced by TLBTree< T, _OP >::Node::elem(), and TLBTree< T, _OP >::Node::elemP().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
Node** TLBTree< T, _OP >::Node::down
 

Children nodes [2*m+1] or NULL if leaf.

Definition at line 85 of file tlbtree.h.

Referenced by TLBTree< T, _OP >::Node::_DEL_L(), TLBTree< T, _OP >::Node::_DEL_R(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindLargestLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindSmallestLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_HandleRootUnderflow(), TLBTree< T, _OP >::Node::_INS_NS(), and TLBTree< T, _OP >::Node::Node().

template<typename T, typename _OP = TLDefaultOperators_CDT<T>>
int TLBTree< T, _OP >::Node::nelem
 

Number of elements stored.

Definition at line 84 of file tlbtree.h.

Referenced by TLBTree< T, _OP >::Node::_DEL_L(), TLBTree< T, _OP >::Node::_DEL_R(), TLBTree< T, _OP >::Node::_DELLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_FindLargestLeaf(), TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::_HandleRootUnderflow(), TLBTree< T, _OP >::Node::_INS_NS(), TLBTree< T, _OP >::Node::_INSLeafNS(), TLBTree< T, _OP >::Node::_LBI(), TLBTree< T, _OP >::Node::Node(), and TLBTree< NamespaceInfo *, PtrListOperators< NamespaceInfo > >::store().

The documentation for this struct was generated from the following file:
Generated on Sat Feb 19 22:35:47 2005 for Ray by doxygen 1.3.5