home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / Hierarchy.h < prev    next >
C/C++ Source or Header  |  2005-11-14  |  6KB  |  336 lines
  1.  
  2. #ifndef __HIERARCHY_H__
  3. #define __HIERARCHY_H__
  4.  
  5. /*
  6. ==============================================================================
  7.  
  8.     idHierarchy
  9.  
  10. ==============================================================================
  11. */
  12.  
  13. template< class type >
  14. class idHierarchy {
  15. public:
  16.  
  17.                         idHierarchy();
  18.                         ~idHierarchy();
  19.     
  20.     void                SetOwner( type *object );
  21.     type *                Owner( void ) const;
  22.     void                ParentTo( idHierarchy &node );
  23.     void                MakeSiblingAfter( idHierarchy &node );
  24.     bool                ParentedBy( const idHierarchy &node ) const;
  25.     void                RemoveFromParent( void );
  26.     void                RemoveFromHierarchy( void );
  27.  
  28.     type *                GetParent( void ) const;        // parent of this node
  29.     type *                GetChild( void ) const;            // first child of this node
  30.     type *                GetSibling( void ) const;        // next node with the same parent
  31.     type *                GetPriorSibling( void ) const;    // previous node with the same parent
  32.     type *                GetNext( void ) const;            // goes through all nodes of the hierarchy
  33.     type *                GetNextLeaf( void ) const;        // goes through all leaf nodes of the hierarchy
  34.  
  35. private:
  36.     idHierarchy *        parent;
  37.     idHierarchy *        sibling;
  38.     idHierarchy *        child;
  39.     type *                owner;
  40.  
  41.     idHierarchy<type>    *GetPriorSiblingNode( void ) const;    // previous node with the same parent
  42. };
  43.  
  44. /*
  45. ================
  46. idHierarchy<type>::idHierarchy
  47. ================
  48. */
  49. template< class type >
  50. idHierarchy<type>::idHierarchy() {
  51.     owner    = NULL;
  52.     parent    = NULL;    
  53.     sibling    = NULL;
  54.     child    = NULL;
  55. }
  56.  
  57. /*
  58. ================
  59. idHierarchy<type>::~idHierarchy
  60. ================
  61. */
  62. template< class type >
  63. idHierarchy<type>::~idHierarchy() {
  64.     RemoveFromHierarchy();
  65. }
  66.  
  67. /*
  68. ================
  69. idHierarchy<type>::Owner
  70.  
  71. Gets the object that is associated with this node.
  72. ================
  73. */
  74. template< class type >
  75. type *idHierarchy<type>::Owner( void ) const {
  76.     return owner;
  77. }
  78.  
  79. /*
  80. ================
  81. idHierarchy<type>::SetOwner
  82.  
  83. Sets the object that this node is associated with.
  84. ================
  85. */
  86. template< class type >
  87. void idHierarchy<type>::SetOwner( type *object ) {
  88.     owner = object;
  89. }
  90.  
  91. /*
  92. ================
  93. idHierarchy<type>::ParentedBy
  94. ================
  95. */
  96. template< class type >
  97. bool idHierarchy<type>::ParentedBy( const idHierarchy &node ) const {
  98.     if ( parent == &node ) {
  99.         return true;
  100.     } else if ( parent ) {
  101.         return parent->ParentedBy( node );
  102.     }
  103.     return false;
  104. }
  105.  
  106. /*
  107. ================
  108. idHierarchy<type>::ParentTo
  109.  
  110. Makes the given node the parent.
  111. ================
  112. */
  113. template< class type >
  114. void idHierarchy<type>::ParentTo( idHierarchy &node ) {
  115.     RemoveFromParent();
  116.  
  117.     parent        = &node;
  118.     sibling        = node.child;
  119.     node.child    = this;
  120. }
  121.  
  122. /*
  123. ================
  124. idHierarchy<type>::MakeSiblingAfter
  125.  
  126. Makes the given node a sibling after the passed in node.
  127. ================
  128. */
  129. template< class type >
  130. void idHierarchy<type>::MakeSiblingAfter( idHierarchy &node ) {
  131.     RemoveFromParent();
  132.     parent    = node.parent;
  133.     sibling = node.sibling;
  134.     node.sibling = this;
  135. }
  136.  
  137. /*
  138. ================
  139. idHierarchy<type>::RemoveFromParent
  140. ================
  141. */
  142. template< class type >
  143. void idHierarchy<type>::RemoveFromParent( void ) {
  144.     idHierarchy<type> *prev;
  145.  
  146.     if ( parent ) {
  147.         prev = GetPriorSiblingNode();
  148.         if ( prev ) {
  149.             prev->sibling = sibling;
  150.         } else {
  151.             parent->child = sibling;
  152.         }
  153.     }
  154.  
  155.     parent = NULL;
  156.     sibling = NULL;
  157. }
  158.  
  159. /*
  160. ================
  161. idHierarchy<type>::RemoveFromHierarchy
  162.  
  163. Removes the node from the hierarchy and adds it's children to the parent.
  164. ================
  165. */
  166. template< class type >
  167. void idHierarchy<type>::RemoveFromHierarchy( void ) {
  168.     idHierarchy<type> *parentNode;
  169.     idHierarchy<type> *node;
  170.  
  171.     parentNode = parent;
  172.     RemoveFromParent();
  173.  
  174.     if ( parentNode ) {
  175.         while( child ) {
  176.             node = child;
  177.             node->RemoveFromParent();
  178.             node->ParentTo( *parentNode );
  179.         }
  180.     } else {
  181.         while( child ) {
  182.             child->RemoveFromParent();
  183.         }
  184.     }
  185. }
  186.  
  187. /*
  188. ================
  189. idHierarchy<type>::GetParent
  190. ================
  191. */
  192. template< class type >
  193. type *idHierarchy<type>::GetParent( void ) const {
  194.     if ( parent ) {
  195.         return parent->owner;
  196.     }
  197.     return NULL;
  198. }
  199.  
  200. /*
  201. ================
  202. idHierarchy<type>::GetChild
  203. ================
  204. */
  205. template< class type >
  206. type *idHierarchy<type>::GetChild( void ) const {
  207.     if ( child ) {
  208.         return child->owner;
  209.     }
  210.     return NULL;
  211. }
  212.  
  213. /*
  214. ================
  215. idHierarchy<type>::GetSibling
  216. ================
  217. */
  218. template< class type >
  219. type *idHierarchy<type>::GetSibling( void ) const {
  220.     if ( sibling ) {
  221.         return sibling->owner;
  222.     }
  223.     return NULL;
  224. }
  225.  
  226. /*
  227. ================
  228. idHierarchy<type>::GetPriorSiblingNode
  229.  
  230. Returns NULL if no parent, or if it is the first child.
  231. ================
  232. */
  233. template< class type >
  234. idHierarchy<type> *idHierarchy<type>::GetPriorSiblingNode( void ) const {
  235.     if ( !parent || ( parent->child == this ) ) {
  236.         return NULL;
  237.     }
  238.  
  239.     idHierarchy<type> *prev;
  240.     idHierarchy<type> *node;
  241.  
  242.     node = parent->child;
  243.     prev = NULL;
  244.     while( ( node != this ) && ( node != NULL ) ) {
  245.         prev = node;
  246.         node = node->sibling;
  247.     }
  248.  
  249.     if ( node != this ) {
  250.         idLib::common->Error( "idHierarchy::GetPriorSibling: could not find node in parent's list of children" );
  251.     }
  252.  
  253.     return prev;
  254. }
  255.  
  256. /*
  257. ================
  258. idHierarchy<type>::GetPriorSibling
  259.  
  260. Returns NULL if no parent, or if it is the first child.
  261. ================
  262. */
  263. template< class type >
  264. type *idHierarchy<type>::GetPriorSibling( void ) const {
  265.     idHierarchy<type> *prior;
  266.  
  267.     prior = GetPriorSiblingNode();
  268.     if ( prior ) {
  269.         return prior->owner;
  270.     }
  271.  
  272.     return NULL;
  273. }
  274.  
  275. /*
  276. ================
  277. idHierarchy<type>::GetNext
  278.  
  279. Goes through all nodes of the hierarchy.
  280. ================
  281. */
  282. template< class type >
  283. type *idHierarchy<type>::GetNext( void ) const {
  284.     const idHierarchy<type> *node;
  285.  
  286.     if ( child ) {
  287.         return child->owner;
  288.     } else {
  289.         node = this;
  290.         while( node && node->sibling == NULL ) {
  291.             node = node->parent;
  292.         }
  293.         if ( node ) {
  294.             return node->sibling->owner;
  295.         } else {
  296.             return NULL;
  297.         }
  298.     }
  299. }
  300.  
  301. /*
  302. ================
  303. idHierarchy<type>::GetNextLeaf
  304.  
  305. Goes through all leaf nodes of the hierarchy.
  306. ================
  307. */
  308. template< class type >
  309. type *idHierarchy<type>::GetNextLeaf( void ) const {
  310.     const idHierarchy<type> *node;
  311.  
  312.     if ( child ) {
  313.         node = child;
  314.         while ( node->child ) {
  315.             node = node->child;
  316.         }
  317.         return node->owner;
  318.     } else {
  319.         node = this;
  320.         while( node && node->sibling == NULL ) {
  321.             node = node->parent;
  322.         }
  323.         if ( node ) {
  324.             node = node->sibling;
  325.             while ( node->child ) {
  326.                 node = node->child;
  327.             }
  328.             return node->owner;
  329.         } else {
  330.             return NULL;
  331.         }
  332.     }
  333. }
  334.  
  335. #endif /* !__HIERARCHY_H__ */
  336.