Tree.h 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207
  1. #pragma once
  2. #include "Array.h"
  3. namespace Framework
  4. {
  5. template< class T >
  6. class TreeIterator;
  7. template< class T >
  8. class Tree : public virtual ReferenceCounter
  9. {
  10. private:
  11. T *value;
  12. RCArray< Tree > *subtrees;
  13. Tree *zParent;
  14. public:
  15. Tree()
  16. : ReferenceCounter()
  17. {
  18. value = 0;
  19. zParent = 0;
  20. subtrees = new RCArray< Tree >();
  21. }
  22. Tree( T *value )
  23. : ReferenceCounter()
  24. {
  25. zParent = 0;
  26. this->value = value;
  27. subtrees = new RCArray< Tree >();
  28. }
  29. ~Tree()
  30. {
  31. if( value )
  32. value->release();
  33. subtrees->release();
  34. }
  35. TreeIterator<T> getIterator()
  36. {
  37. return TreeIterator( this );
  38. }
  39. void leeren()
  40. {
  41. if( value )
  42. value->release();
  43. value = 0;
  44. subtrees->leeren();
  45. }
  46. void addSubtree( Tree *t )
  47. {
  48. t->zParent = this;
  49. subtrees->add( t );
  50. }
  51. void setValue( T *v )
  52. {
  53. if( value )
  54. value->release();
  55. value = v;
  56. }
  57. T *getValue()
  58. {
  59. return value ? dynamic_cast<T *>( value->getThis() ) : 0;
  60. }
  61. T *zValue()
  62. {
  63. return value;
  64. }
  65. Tree *getParent()
  66. {
  67. return zParent ? dynamic_cast<Tree *>( zParent->getThis() ) : 0;
  68. }
  69. Tree *zParent()
  70. {
  71. return zParent;
  72. }
  73. friend TreeIterator;
  74. };
  75. template< class T >
  76. class TreeIterator
  77. {
  78. private:
  79. Tree *current;
  80. int nextSub;
  81. public:
  82. TreeIterator( Tree *tree )
  83. {
  84. current = tree;
  85. nextSub = 0;
  86. }
  87. TreeIterator( const TreeIterator &it )
  88. {
  89. current = it.current;
  90. nextSub = it.nextSub;
  91. }
  92. TreeIterator< T > &operator=( TreeIterator< T > &r )
  93. {
  94. current = r.current;
  95. nextSub = it.nextSub;
  96. return *this;
  97. }
  98. bool hasNext()
  99. {
  100. if( current->subtrees->getEintragAnzahl() >= nextSub )
  101. return 1;
  102. Tree<T> *c = current;
  103. while( true )
  104. {
  105. Tree<T> *p = c->zParent();
  106. if( !p )
  107. {
  108. return 0;
  109. }
  110. for( auto i = p->subtrees->getIterator(); i; i++ )
  111. {
  112. if( i._ == c )
  113. {
  114. i++;
  115. if( i )
  116. return 1;
  117. else
  118. {
  119. c = p;
  120. break;
  121. }
  122. }
  123. }
  124. }
  125. }
  126. TreeIterator< T > next()
  127. {
  128. if( current->subtrees->getEintragAnzahl() >= nextSub )
  129. return TreeIterator( current->subtrees->z( nextSub++ ) );
  130. Tree<T> *c = current;
  131. while( true )
  132. {
  133. Tree<T> *p = c->zParent();
  134. if( !p )
  135. return TreeIterator<T>( 0 );
  136. for( auto i = p->subtrees->getIterator(); i; i++ )
  137. {
  138. if( i._ == c )
  139. {
  140. i++;
  141. if( i )
  142. return TreeIterator<T>( i._ );
  143. else
  144. {
  145. c = p;
  146. break;
  147. }
  148. }
  149. }
  150. }
  151. }
  152. operator bool()
  153. {
  154. return current != 0;
  155. }
  156. operator T *( )
  157. {
  158. return current->zValue();
  159. }
  160. TreeIterator< T > &operator++() //! prefix
  161. {
  162. TreeIterator< T > temp( *this );
  163. *this = next();
  164. return temp;
  165. }
  166. TreeIterator< T > &operator++( int ) //! postfix
  167. {
  168. *this = next();
  169. return *this;
  170. }
  171. T *operator->()
  172. {
  173. return current->zValue();
  174. }
  175. T val()
  176. {
  177. return current->zValue();
  178. }
  179. };
  180. }