Trie.h 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284
  1. #pragma once
  2. #include "CharMap.h"
  3. namespace Framework
  4. {
  5. template<class T, class M> struct TrieIteratorData
  6. {
  7. M* map;
  8. TrieIteratorData* parent;
  9. TrieIteratorData()
  10. {
  11. map = 0;
  12. parent = 0;
  13. }
  14. TrieIteratorData(M* zMap, TrieIteratorData parent)
  15. {
  16. map = zMap;
  17. this->parent = new TrieIteratorData(parent);
  18. }
  19. TrieIteratorData(const TrieIteratorData& data)
  20. {
  21. map = data.map;
  22. if (data.parent)
  23. parent = new TrieIteratorData(*data.parent);
  24. else
  25. parent = 0;
  26. }
  27. ~TrieIteratorData()
  28. {
  29. delete parent;
  30. }
  31. TrieIteratorData& operator=(const TrieIteratorData& data)
  32. {
  33. map = data.map;
  34. TrieIteratorData* tmp = parent;
  35. if (data.parent)
  36. parent = new TrieIteratorData(*data.parent);
  37. else
  38. parent = 0;
  39. delete tmp;
  40. return *this;
  41. }
  42. void set(M* zMap, TrieIteratorData parent)
  43. {
  44. map = zMap;
  45. parent = new TrieIteratorData(parent);
  46. }
  47. };
  48. template<class T, class M> class TrieIterator
  49. {
  50. private:
  51. TrieIteratorData<T, M> data;
  52. public:
  53. TrieIterator(TrieIteratorData<T, M> data)
  54. {
  55. this->data = data;
  56. }
  57. TrieIterator next()
  58. {
  59. for (unsigned char i = 0; true; i++)
  60. {
  61. if (data.map->z(i))
  62. return TrieIterator(
  63. TrieIteratorData<T, M>(data.map->z(i)->map, data));
  64. if (i == 255) break;
  65. }
  66. if (!data.parent || !data.parent->map)
  67. return TrieIterator(
  68. TrieIteratorData<T, M>(0, TrieIteratorData<T, M>()));
  69. TrieIteratorData<T, M> d = data;
  70. do
  71. {
  72. for (unsigned char i = 0; true; i++)
  73. {
  74. if (d.parent->map->z(i)
  75. && d.parent->map->z(i)->map == d.map)
  76. {
  77. if (i < 256)
  78. {
  79. for (unsigned char j = (unsigned char)(i + 1); true;
  80. j++)
  81. {
  82. if (d.parent->map->z(j))
  83. return TrieIterator(TrieIteratorData<T, M>(
  84. d.parent->map->z(j)->map, *d.parent));
  85. if (j == 255) break;
  86. }
  87. }
  88. d = *d.parent;
  89. break;
  90. }
  91. if (i == 255) break;
  92. }
  93. } while (d.parent && d.parent->map);
  94. return TrieIterator(TrieIteratorData<T, M>(0, TrieIteratorData<T, M>()));
  95. }
  96. TrieIterator& operator++() //! prefix
  97. {
  98. data = next().data;
  99. return *this;
  100. }
  101. TrieIterator operator++(int) //! postfix
  102. {
  103. TrieIterator temp(*this);
  104. data = next().data;
  105. return temp;
  106. }
  107. operator bool()
  108. {
  109. return data.map != 0;
  110. }
  111. operator T*()
  112. {
  113. return data.map->zValue();
  114. }
  115. T* operator->()
  116. {
  117. return data.map->zValue();
  118. }
  119. T* val()
  120. {
  121. return data.map->zValue();
  122. }
  123. };
  124. template<class T> class Trie : public virtual ReferenceCounter
  125. {
  126. private:
  127. CharMap<Trie<T>, T>* map;
  128. public:
  129. Trie()
  130. : ReferenceCounter()
  131. {
  132. map = new CharMap<Trie<T>, T>();
  133. }
  134. ~Trie()
  135. {
  136. map->release();
  137. }
  138. void set(const char* addr, int addrLen, T value)
  139. {
  140. if (!addrLen)
  141. map->setValue(value);
  142. else
  143. {
  144. if (!map->z(*addr)) map->set(*addr, new Trie<T>());
  145. map->z(*addr)->set(addr + 1, addrLen - 1, value);
  146. }
  147. }
  148. void remove(const char* addr, int addrLen)
  149. {
  150. if (!addrLen)
  151. map->setValue(0);
  152. else
  153. {
  154. if (!map->z(*addr)) return;
  155. map->z(*addr)->remove(addr + 1, addrLen - 1);
  156. }
  157. }
  158. T get(const char* addr, int addrLen) const
  159. {
  160. if (!addrLen)
  161. return map->getValue();
  162. else
  163. {
  164. if (!map->z(*addr)) return 0;
  165. return map->z(*addr)->get(addr + 1, addrLen - 1);
  166. }
  167. }
  168. void leeren()
  169. {
  170. map->release();
  171. map = new CharMap<Trie<T>, T>();
  172. }
  173. TrieIterator<T, CharMap<Trie<T>, T>> getIterator()
  174. {
  175. return TrieIterator<T, CharMap<Trie<T>, T>>(
  176. TrieIteratorData<T, CharMap<Trie<T>, T>>(
  177. map, TrieIteratorData<T, CharMap<Trie<T>, T>>()));
  178. }
  179. friend TrieIterator<T, CharMap<Trie<T>, T>>;
  180. };
  181. template<class T> class RCTrie : public virtual ReferenceCounter
  182. {
  183. private:
  184. RCCharMap<RCTrie<T>, T>* map;
  185. public:
  186. RCTrie()
  187. : ReferenceCounter()
  188. {
  189. map = new RCCharMap<RCTrie<T>, T>();
  190. }
  191. ~RCTrie()
  192. {
  193. map->release();
  194. }
  195. void set(const char* addr, int addrLen, T* value)
  196. {
  197. if (!addrLen)
  198. map->setValue(value);
  199. else
  200. {
  201. if (!map->z(*addr)) map->set(*addr, new RCTrie<T>());
  202. map->z(*addr)->set(addr + 1, addrLen - 1, value);
  203. }
  204. }
  205. void remove(const char* addr, int addrLen)
  206. {
  207. if (!addrLen)
  208. map->setValue(0);
  209. else
  210. {
  211. if (!map->z(*addr)) return;
  212. map->z(*addr)->remove(addr + 1, addrLen - 1);
  213. }
  214. }
  215. T* get(const char* addr, int addrLen)
  216. {
  217. if (!addrLen)
  218. return map->getValue();
  219. else
  220. {
  221. if (!map->z(*addr)) return 0;
  222. return map->z(*addr)->get(addr + 1, addrLen - 1);
  223. }
  224. }
  225. T* z(const char* addr, int addrLen) const
  226. {
  227. if (!addrLen)
  228. return map->zValue();
  229. else
  230. {
  231. if (!map->z(*addr)) return 0;
  232. return map->z(*addr)->z(addr + 1, addrLen - 1);
  233. }
  234. }
  235. void leeren()
  236. {
  237. map->release();
  238. map = new RCCharMap<RCTrie<T>, T>();
  239. }
  240. TrieIterator<T, RCCharMap<RCTrie<T>, T>> getIterator()
  241. {
  242. return TrieIterator<T, RCCharMap<RCTrie<T>, T>>(
  243. TrieIteratorData<T, RCCharMap<RCTrie<T>, T>>(
  244. map, TrieIteratorData<T, RCCharMap<RCTrie<T>, T>>()));
  245. }
  246. friend TrieIterator<T, RCCharMap<RCTrie<T>, T>>;
  247. };
  248. } // namespace Framework