Tree.h 4.2 KB

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