home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / BTree.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  15KB  |  497 lines
  1.  
  2. #ifndef __BTREE_H__
  3. #define __BTREE_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Balanced Search Tree
  9.  
  10. ===============================================================================
  11. */
  12.  
  13. //#define BTREE_CHECK
  14.  
  15. template< class objType, class keyType >
  16. class idBTreeNode {
  17. public:
  18.     keyType                            key;            // key used for sorting
  19.     objType *                        object;            // if != NULL pointer to object stored in leaf node
  20.     idBTreeNode *                    parent;            // parent node
  21.     idBTreeNode *                    next;            // next sibling
  22.     idBTreeNode *                    prev;            // prev sibling
  23.     int                                numChildren;    // number of children
  24.     idBTreeNode *                    firstChild;        // first child
  25.     idBTreeNode *                    lastChild;        // last child
  26. };
  27.  
  28.  
  29. template< class objType, class keyType, int maxChildrenPerNode >
  30. class idBTree {
  31. public:
  32.                                     idBTree( void );
  33.                                     ~idBTree( void );
  34.  
  35.     void                            Init( void );
  36.     void                            Shutdown( void );
  37.  
  38.     idBTreeNode<objType,keyType> *    Add( objType *object, keyType key );                        // add an object to the tree
  39.     void                            Remove( idBTreeNode<objType,keyType> *node );                // remove an object node from the tree
  40.  
  41.     objType *                        Find( keyType key ) const;                                    // find an object using the given key
  42.     objType *                        FindSmallestLargerEqual( keyType key ) const;                // find an object with the smallest key larger equal the given key
  43.     objType *                        FindLargestSmallerEqual( keyType key ) const;                // find an object with the largest key smaller equal the given key
  44.  
  45.     idBTreeNode<objType,keyType> *    GetRoot( void ) const;                                        // returns the root node of the tree
  46.     int                                GetNodeCount( void ) const;                                    // returns the total number of nodes in the tree
  47.     idBTreeNode<objType,keyType> *    GetNext( idBTreeNode<objType,keyType> *node ) const;        // goes through all nodes of the tree
  48.     idBTreeNode<objType,keyType> *    GetNextLeaf( idBTreeNode<objType,keyType> *node ) const;    // goes through all leaf nodes of the tree
  49.  
  50. private:
  51.     idBTreeNode<objType,keyType> *    root;
  52. // RAVEN BEGIN
  53. // jnewquist: Mark memory tags for idBlockAlloc
  54.     idBlockAlloc<idBTreeNode<objType,keyType>,128,MA_DEFAULT>    nodeAllocator;
  55. // RAVEN END
  56.  
  57.     idBTreeNode<objType,keyType> *    AllocNode( void );
  58.     void                            FreeNode( idBTreeNode<objType,keyType> *node );
  59.     void                            SplitNode( idBTreeNode<objType,keyType> *node );
  60.     idBTreeNode<objType,keyType> *    MergeNodes( idBTreeNode<objType,keyType> *node1, idBTreeNode<objType,keyType> *node2 );
  61.  
  62.     void                            CheckTree_r( idBTreeNode<objType,keyType> *node, int &numNodes ) const;
  63.     void                            CheckTree( void ) const;
  64. };
  65.  
  66.  
  67. template< class objType, class keyType, int maxChildrenPerNode >
  68. ID_INLINE idBTree<objType,keyType,maxChildrenPerNode>::idBTree( void ) {
  69.     assert( maxChildrenPerNode >= 4 );
  70.     root = NULL;
  71. }
  72.  
  73. template< class objType, class keyType, int maxChildrenPerNode >
  74. ID_INLINE idBTree<objType,keyType,maxChildrenPerNode>::~idBTree( void ) {
  75.     Shutdown();
  76. }
  77.  
  78. template< class objType, class keyType, int maxChildrenPerNode >
  79. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::Init( void ) {
  80.     root = AllocNode();
  81. }
  82.  
  83. template< class objType, class keyType, int maxChildrenPerNode >
  84. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::Shutdown( void ) {
  85.     nodeAllocator.Shutdown();
  86.     root = NULL;
  87. }
  88.  
  89. template< class objType, class keyType, int maxChildrenPerNode >
  90. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::Add( objType *object, keyType key ) {
  91.     idBTreeNode<objType,keyType> *node, *child, *newNode;
  92.  
  93.     if ( root->numChildren >= maxChildrenPerNode ) {
  94.         newNode = AllocNode();
  95.         newNode->key = root->key;
  96.         newNode->firstChild = root;
  97.         newNode->lastChild = root;
  98.         newNode->numChildren = 1;
  99.         root->parent = newNode;
  100.         SplitNode( root );
  101.         root = newNode;
  102.     }
  103.  
  104.     newNode = AllocNode();
  105.     newNode->key = key;
  106.     newNode->object = object;
  107.  
  108.     for ( node = root; node->firstChild != NULL; node = child ) {
  109.  
  110.         if ( key > node->key ) {
  111.             node->key = key;
  112.         }
  113.  
  114.         // find the first child with a key larger equal to the key of the new node
  115.         for( child = node->firstChild; child->next; child = child->next ) {
  116.             if ( key <= child->key ) {
  117.                 break;
  118.             }
  119.         }
  120.  
  121.         if ( child->object ) {
  122.  
  123.             if ( key <= child->key ) {
  124.                 // insert new node before child
  125.                 if ( child->prev ) {
  126.                     child->prev->next = newNode;
  127.                 } else {
  128.                     node->firstChild = newNode;
  129.                 }
  130.                 newNode->prev = child->prev;
  131.                 newNode->next = child;
  132.                 child->prev = newNode;
  133.             } else {
  134.                 // insert new node after child
  135.                 if ( child->next ) {
  136.                     child->next->prev = newNode;
  137.                 } else {
  138.                     node->lastChild = newNode;
  139.                 }
  140.                 newNode->prev = child;
  141.                 newNode->next = child->next;
  142.                 child->next = newNode;
  143.             }
  144.  
  145.             newNode->parent = node;
  146.             node->numChildren++;
  147.  
  148. #ifdef BTREE_CHECK
  149.             CheckTree();
  150. #endif
  151.  
  152.             return newNode;
  153.         }
  154.  
  155.         // make sure the child has room to store another node
  156.         if ( child->numChildren >= maxChildrenPerNode ) {
  157.             SplitNode( child );
  158.             if ( key <= child->prev->key ) {
  159.                 child = child->prev;
  160.             }
  161.         }
  162.     }
  163.  
  164.     // we only end up here if the root node is empty
  165.     newNode->parent = root;
  166.     root->key = key;
  167.     root->firstChild = newNode;
  168.     root->lastChild = newNode;
  169.     root->numChildren++;
  170.  
  171. #ifdef BTREE_CHECK
  172.     CheckTree();
  173. #endif
  174.  
  175.     return newNode;
  176. }
  177.  
  178. template< class objType, class keyType, int maxChildrenPerNode >
  179. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::Remove( idBTreeNode<objType,keyType> *node ) {
  180.     idBTreeNode<objType,keyType> *parent;
  181.  
  182.     assert( node->object != NULL );
  183.  
  184.     // unlink the node from it's parent
  185.     if ( node->prev ) {
  186.         node->prev->next = node->next;
  187.     } else {
  188.         node->parent->firstChild = node->next;
  189.     }
  190.     if ( node->next ) {
  191.         node->next->prev = node->prev;
  192.     } else {
  193.         node->parent->lastChild = node->prev;
  194.     }
  195.     node->parent->numChildren--;
  196.  
  197.     // make sure there are no parent nodes with a single child
  198.     for ( parent = node->parent; parent != root && parent->numChildren <= 1; parent = parent->parent ) {
  199.  
  200.         if ( parent->next ) {
  201.             parent = MergeNodes( parent, parent->next );
  202.         } else if ( parent->prev ) {
  203.             parent = MergeNodes( parent->prev, parent );
  204.         }
  205.  
  206.         // a parent may not use a key higher than the key of it's last child
  207.         if ( parent->key > parent->lastChild->key ) {
  208.             parent->key = parent->lastChild->key;
  209.         }
  210.  
  211.         if ( parent->numChildren > maxChildrenPerNode ) {
  212.             SplitNode( parent );
  213.             break;
  214.         }
  215.     }
  216.     for ( ; parent != NULL && parent->lastChild != NULL; parent = parent->parent ) {
  217.         // a parent may not use a key higher than the key of it's last child
  218.         if ( parent->key > parent->lastChild->key ) {
  219.             parent->key = parent->lastChild->key;
  220.         }
  221.     }
  222.  
  223.     // free the node
  224.     FreeNode( node );
  225.  
  226.     // remove the root node if it has a single internal node as child
  227.     if ( root->numChildren == 1 && root->firstChild->object == NULL ) {
  228.         idBTreeNode<objType,keyType> *oldRoot = root;
  229.         root->firstChild->parent = NULL;
  230.         root = root->firstChild;
  231.         FreeNode( oldRoot );
  232.     }
  233.  
  234. #ifdef BTREE_CHECK
  235.     CheckTree();
  236. #endif
  237. }
  238.  
  239. template< class objType, class keyType, int maxChildrenPerNode >
  240. ID_INLINE objType *idBTree<objType,keyType,maxChildrenPerNode>::Find( keyType key ) const {
  241.     idBTreeNode<objType,keyType> *node;
  242.  
  243.     for ( node = root->firstChild; node != NULL; node = node->firstChild ) {
  244.         while( node->next ) {
  245.             if ( node->key >= key ) {
  246.                 break;
  247.             }
  248.             node = node->next;
  249.         }
  250.         if ( node->object ) {
  251.             if ( node->key == key ) {
  252.                 return node->object;
  253.             } else {
  254.                 return NULL;
  255.             }
  256.         }
  257.     }
  258.     return NULL;
  259. }
  260.  
  261. template< class objType, class keyType, int maxChildrenPerNode >
  262. ID_INLINE objType *idBTree<objType,keyType,maxChildrenPerNode>::FindSmallestLargerEqual( keyType key ) const {
  263.     idBTreeNode<objType,keyType> *node;
  264.  
  265.     for ( node = root->firstChild; node != NULL; node = node->firstChild ) {
  266.         while( node->next ) {
  267.             if ( node->key >= key ) {
  268.                 break;
  269.             }
  270.             node = node->next;
  271.         }
  272.         if ( node->object ) {
  273.             if ( node->key >= key ) {
  274.                 return node->object;
  275.             } else {
  276.                 return NULL;
  277.             }
  278.         }
  279.     }
  280.     return NULL;
  281. }
  282.  
  283. template< class objType, class keyType, int maxChildrenPerNode >
  284. ID_INLINE objType *idBTree<objType,keyType,maxChildrenPerNode>::FindLargestSmallerEqual( keyType key ) const {
  285.     idBTreeNode<objType,keyType> *node;
  286.  
  287.     for ( node = root->lastChild; node != NULL; node = node->lastChild ) {
  288.         while( node->prev ) {
  289.             if ( node->key <= key ) {
  290.                 break;
  291.             }
  292.             node = node->prev;
  293.         }
  294.         if ( node->object ) {
  295.             if ( node->key <= key ) {
  296.                 return node->object;
  297.             } else {
  298.                 return NULL;
  299.             }
  300.         }
  301.     }
  302.     return NULL;
  303. }
  304.  
  305. template< class objType, class keyType, int maxChildrenPerNode >
  306. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::GetRoot( void ) const {
  307.     return root;
  308. }
  309.  
  310. template< class objType, class keyType, int maxChildrenPerNode >
  311. ID_INLINE int idBTree<objType,keyType,maxChildrenPerNode>::GetNodeCount( void ) const {
  312.     return nodeAllocator.GetAllocCount();
  313. }
  314.  
  315. template< class objType, class keyType, int maxChildrenPerNode >
  316. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::GetNext( idBTreeNode<objType,keyType> *node ) const {
  317.     if ( node->firstChild ) {
  318.         return node->firstChild;
  319.     } else {
  320.         while( node && node->next == NULL ) {
  321.             node = node->parent;
  322.         }
  323.         return node;
  324.     }
  325. }
  326.  
  327. template< class objType, class keyType, int maxChildrenPerNode >
  328. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::GetNextLeaf( idBTreeNode<objType,keyType> *node ) const {
  329.     if ( node->firstChild ) {
  330.         while ( node->firstChild ) {
  331.             node = node->firstChild;
  332.         }
  333.         return node;
  334.     } else {
  335.         while( node && node->next == NULL ) {
  336.             node = node->parent;
  337.         }
  338.         if ( node ) {
  339.             node = node->next;
  340.             while ( node->firstChild ) {
  341.                 node = node->firstChild;
  342.             }
  343.             return node;
  344.         } else {
  345.             return NULL;
  346.         }
  347.     }
  348. }
  349.  
  350. template< class objType, class keyType, int maxChildrenPerNode >
  351. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::AllocNode( void ) {
  352.     idBTreeNode<objType,keyType> *node = nodeAllocator.Alloc();
  353.     node->key = 0;
  354.     node->parent = NULL;
  355.     node->next = NULL;
  356.     node->prev = NULL;
  357.     node->numChildren = 0;
  358.     node->firstChild = NULL;
  359.     node->lastChild = NULL;
  360.     node->object = NULL;
  361.     return node;
  362. }
  363.  
  364. template< class objType, class keyType, int maxChildrenPerNode >
  365. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::FreeNode( idBTreeNode<objType,keyType> *node ) {
  366.     nodeAllocator.Free( node );
  367. }
  368.  
  369. template< class objType, class keyType, int maxChildrenPerNode >
  370. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::SplitNode( idBTreeNode<objType,keyType> *node ) {
  371.     int i;
  372.     idBTreeNode<objType,keyType> *child, *newNode;
  373.  
  374.     // allocate a new node
  375.     newNode = AllocNode();
  376.     newNode->parent = node->parent;
  377.  
  378.     // divide the children over the two nodes
  379.     child = node->firstChild;
  380.     child->parent = newNode;
  381.     for ( i = 3; i < node->numChildren; i += 2 ) {
  382.         child = child->next;
  383.         child->parent = newNode;
  384.     }
  385.  
  386.     newNode->key = child->key;
  387.     newNode->numChildren = node->numChildren / 2;
  388.     newNode->firstChild = node->firstChild;
  389.     newNode->lastChild = child;
  390.  
  391.     node->numChildren -= newNode->numChildren;
  392.     node->firstChild = child->next;
  393.  
  394.     child->next->prev = NULL;
  395.     child->next = NULL;
  396.  
  397.     // add the new child to the parent before the split node
  398.     assert( node->parent->numChildren < maxChildrenPerNode );
  399.  
  400.     if ( node->prev ) {
  401.         node->prev->next = newNode;
  402.     } else {
  403.         node->parent->firstChild = newNode;
  404.     }
  405.     newNode->prev = node->prev;
  406.     newNode->next = node;
  407.     node->prev = newNode;
  408.  
  409.     node->parent->numChildren++;
  410. }
  411.  
  412. template< class objType, class keyType, int maxChildrenPerNode >
  413. ID_INLINE idBTreeNode<objType,keyType> *idBTree<objType,keyType,maxChildrenPerNode>::MergeNodes( idBTreeNode<objType,keyType> *node1, idBTreeNode<objType,keyType> *node2 ) {
  414.     idBTreeNode<objType,keyType> *child;
  415.  
  416.     assert( node1->parent == node2->parent );
  417.     assert( node1->next == node2 && node2->prev == node1 );
  418.     assert( node1->object == NULL && node2->object == NULL );
  419.     assert( node1->numChildren >= 1 && node2->numChildren >= 1 );
  420.  
  421.     for ( child = node1->firstChild; child->next; child = child->next ) {
  422.         child->parent = node2;
  423.     }
  424.     child->parent = node2;
  425.     child->next = node2->firstChild;
  426.     node2->firstChild->prev = child;
  427.     node2->firstChild = node1->firstChild;
  428.     node2->numChildren += node1->numChildren;
  429.  
  430.     // unlink the first node from the parent
  431.     if ( node1->prev ) {
  432.         node1->prev->next = node2;
  433.     } else {
  434.         node1->parent->firstChild = node2;
  435.     }
  436.     node2->prev = node1->prev;
  437.     node2->parent->numChildren--;
  438.  
  439.     FreeNode( node1 );
  440.  
  441.     return node2;
  442. }
  443.  
  444. template< class objType, class keyType, int maxChildrenPerNode >
  445. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::CheckTree_r( idBTreeNode<objType,keyType> *node, int &numNodes ) const {
  446.     int numChildren;
  447.     idBTreeNode<objType,keyType> *child;
  448.  
  449.     numNodes++;
  450.  
  451.     // the root node may have zero children and leaf nodes always have zero children, all other nodes should have at least 2 and at most maxChildrenPerNode children
  452.     assert( ( node == root ) || ( node->object != NULL && node->numChildren == 0 ) || ( node->numChildren >= 2 && node->numChildren <= maxChildrenPerNode ) );
  453.     // the key of a node may never be larger than the key of it's last child
  454.     assert( ( node->lastChild == NULL ) || ( node->key <= node->lastChild->key ) );
  455.  
  456.     numChildren = 0;
  457.     for ( child = node->firstChild; child; child = child->next ) {
  458.         numChildren++;
  459.         // make sure the children are properly linked
  460.         if ( child->prev == NULL ) {
  461.             assert( node->firstChild == child );
  462.         } else {
  463.             assert( child->prev->next == child );
  464.         }
  465.         if ( child->next == NULL ) {
  466.             assert( node->lastChild == child );
  467.         } else {
  468.             assert( child->next->prev == child );
  469.         }
  470.         // recurse down the tree
  471.         CheckTree_r( child, numNodes );
  472.     }
  473.     // the number of children should equal the number of linked children
  474.     assert( numChildren == node->numChildren );
  475. }
  476.  
  477. template< class objType, class keyType, int maxChildrenPerNode >
  478. ID_INLINE void idBTree<objType,keyType,maxChildrenPerNode>::CheckTree( void ) const {
  479.     int numNodes = 0;
  480.     idBTreeNode<objType,keyType> *node, *lastNode;
  481.  
  482.     CheckTree_r( root, numNodes );
  483.  
  484.     // the number of nodes in the tree should equal the number of allocated nodes
  485.     assert( numNodes == nodeAllocator.GetAllocCount() );
  486.  
  487.     // all the leaf nodes should be ordered
  488.     lastNode = GetNextLeaf( GetRoot() );
  489.     if ( lastNode ) {
  490.         for ( node = GetNextLeaf( lastNode ); node; lastNode = node, node = GetNextLeaf( node ) ) {
  491.             assert( lastNode->key <= node->key );
  492.         }
  493.     }
  494. }
  495.  
  496. #endif /* !__BTREE_H__ */
  497.