Trie.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219
  1. #pragma once
  2. #include "CharMap.h"
  3. namespace Framework
  4. {
  5. template<class T>
  6. class Trie;
  7. template< class T >
  8. struct TrieIteratorData
  9. {
  10. CharMap< Trie< T >, T > *map;
  11. TrieIteratorData<T> *parent;
  12. TrieIteratorData()
  13. {
  14. map = 0;
  15. parent = 0;
  16. }
  17. TrieIteratorData( CharMap< Trie< T >, T > *zMap, TrieIteratorData<T> parent )
  18. {
  19. map = zMap;
  20. this->parent = new TrieIteratorData<T>( parent );
  21. }
  22. TrieIteratorData( const TrieIteratorData &data )
  23. {
  24. map = data.map;
  25. if( data.parent )
  26. parent = new TrieIteratorData( *data.parent );
  27. else
  28. parent = 0;
  29. }
  30. ~TrieIteratorData()
  31. {
  32. delete parent;
  33. }
  34. TrieIteratorData &operator=( TrieIteratorData &data )
  35. {
  36. map = data.map;
  37. TrieIteratorData *tmp = parent;
  38. if( data.parent )
  39. parent = new TrieIteratorData( *data.parent );
  40. else
  41. parent = 0;
  42. delete tmp;
  43. return *this;
  44. }
  45. void set( CharMap< Trie< T >, T > *zMap, TrieIteratorData parent )
  46. {
  47. map = zMap;
  48. parent = new TrieIteratorData( parent );
  49. }
  50. };
  51. template< class T >
  52. class TrieIterator
  53. {
  54. private:
  55. TrieIteratorData<T> data;
  56. public:
  57. TrieIterator( TrieIteratorData<T> data )
  58. {
  59. this->data = data;
  60. }
  61. TrieIterator next()
  62. {
  63. Trie<T> *n = 0;
  64. for( int i = 0; i < 256; i++ )
  65. {
  66. if( data.map->z( i ) )
  67. return TrieIterator( TrieIteratorData<T>( data.map->z( i )->map, data ) );
  68. }
  69. if( !data.parent || !data.parent->map )
  70. return TrieIterator( TrieIteratorData<T>( 0, TrieIteratorData<T>() ) );
  71. TrieIteratorData<T> d = data;
  72. do
  73. {
  74. for( int i = 0; i < 256; i++ )
  75. {
  76. if( d.parent->map->z( i ) && d.parent->map->z( i )->map == d.map )
  77. {
  78. for( int j = i + 1; j < 256; j++ )
  79. {
  80. if( d.parent->map->z( j ) )
  81. return TrieIterator( TrieIteratorData<T>( d.parent->map->z( j )->map, *d.parent ) );
  82. }
  83. d = *d.parent;
  84. break;
  85. }
  86. }
  87. } while( d.parent && d.parent->map );
  88. return TrieIterator( TrieIteratorData<T>( 0, TrieIteratorData<T>() ) );
  89. }
  90. TrieIterator< T > &operator++() // prefix
  91. {
  92. TrieIterator< T > temp( *this );
  93. *this = next();
  94. return temp;
  95. }
  96. TrieIterator< T > &operator++( int ) // postfix
  97. {
  98. *this = next();
  99. return *this;
  100. }
  101. operator bool()
  102. {
  103. return data.map != 0;
  104. }
  105. operator T*( )
  106. {
  107. return data.map->zValue();
  108. }
  109. T *operator->()
  110. {
  111. return data.map->zValue();
  112. }
  113. T *val()
  114. {
  115. return data.map->zValue();
  116. }
  117. };
  118. template<class T>
  119. class Trie
  120. {
  121. private:
  122. CharMap< Trie< T >, T > *map;
  123. int ref;
  124. public:
  125. Trie()
  126. {
  127. map = new CharMap< Trie< T >, T >();
  128. ref = 1;
  129. }
  130. ~Trie()
  131. {
  132. map->release();
  133. }
  134. void set( const char *addr, T *value )
  135. {
  136. if( !*addr )
  137. map->setValue( value );
  138. else
  139. {
  140. if( !map->z( *addr ) )
  141. map->set( *addr, new Trie< T >() );
  142. map->z( *addr )->set( addr + 1, value );
  143. }
  144. }
  145. T *get( const char *addr )
  146. {
  147. if( !*addr )
  148. return map->getValue();
  149. else
  150. {
  151. if( !map->z( *addr ) )
  152. return 0;
  153. return map->z( *addr )->get( addr + 1 );
  154. }
  155. }
  156. T *z( const char *addr )
  157. {
  158. if( !*addr )
  159. return map->zValue();
  160. else
  161. {
  162. if( !map->z( *addr ) )
  163. return 0;
  164. return map->z( *addr )->z( addr + 1 );
  165. }
  166. }
  167. void leeren()
  168. {
  169. map->release();
  170. map = new CharMap< Trie< T >, T >();
  171. }
  172. TrieIterator< T > getIterator()
  173. {
  174. return TrieIterator< T >( TrieIteratorData<T>( map, TrieIteratorData<T>() ) );
  175. }
  176. Trie *getThis()
  177. {
  178. ref++;
  179. return this;
  180. }
  181. Trie *release()
  182. {
  183. if( !--ref )
  184. delete this;
  185. return 0;
  186. }
  187. friend TrieIterator<T>;
  188. };
  189. }