HashMap.h 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337
  1. #pragma once
  2. #include <functional>
  3. #include "Array.h"
  4. namespace Framework
  5. {
  6. template<typename K, typename V>
  7. class MapEntry
  8. {
  9. private:
  10. K key;
  11. V value;
  12. public:
  13. MapEntry()
  14. {}
  15. MapEntry( K key, V value )
  16. : key( key ),
  17. value( value )
  18. {}
  19. K getKey()
  20. {
  21. return key;
  22. }
  23. V getValue()
  24. {
  25. return value;
  26. }
  27. template<typename K2, typename V2>
  28. friend class HashMap;
  29. };
  30. template<typename K, typename V>
  31. class MapIterator
  32. {
  33. private:
  34. int bucketIndex;
  35. Iterator< MapEntry<K, V> > iterator;
  36. Array< MapEntry<K, V> >** buckets;
  37. int bucketCount;
  38. public:
  39. MapIterator( Array< MapEntry<K, V> >** buckets, int bucketCount, int bucketIndex, Iterator< MapEntry<K, V> > iterator )
  40. : iterator( iterator )
  41. {
  42. while( bucketIndex < bucketCount && (!buckets[ bucketIndex ] || buckets[ bucketIndex ]->getEintragAnzahl() == 0) )
  43. {
  44. bucketIndex++;
  45. iterator = Iterator< MapEntry<K, V> >( 0 );
  46. }
  47. if( bucketIndex < bucketCount )
  48. {
  49. if( !iterator )
  50. this->iterator = buckets[ bucketIndex ]->begin();
  51. }
  52. else
  53. {
  54. this->iterator = Iterator< MapEntry<K, V> >( 0 );
  55. this->bucketIndex = 0;
  56. this->buckets = 0;
  57. this->bucketCount = 0;
  58. }
  59. this->buckets = buckets;
  60. this->bucketCount = bucketCount;
  61. this->bucketIndex = bucketIndex;
  62. }
  63. MapIterator( const MapIterator< K, V >& it )
  64. : iterator( it.iterator )
  65. {
  66. buckets = it.buckets;
  67. bucketCount = it.bucketCount;
  68. bucketIndex = it.bucketIndex;
  69. }
  70. MapIterator< K, V >& operator=( MapIterator< K, V > r )
  71. {
  72. iterator = r.iterator;
  73. buckets = r.buckets;
  74. bucketCount = r.bucketCount;
  75. bucketIndex = r.bucketIndex;
  76. return *this;
  77. }
  78. bool hasNext()
  79. {
  80. if( iterator && iterator.hasNext() )
  81. return 1;
  82. int ind = bucketIndex + 1;
  83. while( ind < bucketCount && (!buckets[ ind ] || buckets[ ind ]->getEintragAnzahl() == 0) )
  84. ind++;
  85. return ind < bucketCount;
  86. }
  87. MapIterator< K, V > next()
  88. {
  89. if( bucketIndex >= bucketCount )
  90. {
  91. Text err = "Index out of Range Exception File: ";
  92. err += __FILE__;
  93. err += " Line: ";
  94. err += __LINE__;
  95. throw std::out_of_range( (char*)err );
  96. }
  97. if( iterator.hasNext() )
  98. return MapIterator( buckets, bucketCount, bucketIndex, iterator.next() );
  99. else
  100. return MapIterator( buckets, bucketCount, bucketIndex + 1, Iterator< MapEntry<K, V> >( 0 ) );
  101. }
  102. operator bool()
  103. {
  104. return bucketIndex < bucketCount;
  105. }
  106. operator MapEntry<K, V>()
  107. {
  108. if( bucketIndex >= bucketCount )
  109. {
  110. Text err = "Index out of Range Exception File: ";
  111. err += __FILE__;
  112. err += " Line: ";
  113. err += __LINE__;
  114. throw std::out_of_range( (char*)err );
  115. }
  116. return iterator.val();
  117. }
  118. MapIterator< K, V >& operator++() //! prefix
  119. {
  120. ++iterator;
  121. if( !iterator )
  122. {
  123. bucketIndex++;
  124. while( bucketIndex < bucketCount && (!buckets[ bucketIndex ] || buckets[ bucketIndex ]->getEintragAnzahl() == 0) )
  125. bucketIndex++;
  126. if( bucketIndex < bucketCount )
  127. this->iterator = buckets[ bucketIndex ]->begin();
  128. else
  129. {
  130. this->iterator = Iterator< MapEntry<K, V> >( 0 );
  131. this->bucketIndex = 0;
  132. this->buckets = 0;
  133. this->bucketCount = 0;
  134. }
  135. }
  136. return *this;
  137. }
  138. MapIterator< K, V > operator++( int ) //! postfix
  139. {
  140. MapIterator< K, V > temp( *this );
  141. ++(*this);
  142. return temp;
  143. }
  144. MapEntry< K, V > operator*()
  145. {
  146. if( bucketIndex >= bucketCount )
  147. {
  148. Text err = "Index out of Range Exception File: ";
  149. err += __FILE__;
  150. err += " Line: ";
  151. err += __LINE__;
  152. throw std::out_of_range( (char*)err );
  153. }
  154. return iterator.val();
  155. }
  156. MapEntry< K, V > operator->()
  157. {
  158. if( bucketIndex >= bucketCount )
  159. {
  160. Text err = "Index out of Range Exception File: ";
  161. err += __FILE__;
  162. err += " Line: ";
  163. err += __LINE__;
  164. throw std::out_of_range( (char*)err );
  165. }
  166. return iterator.val();
  167. }
  168. void set( MapEntry<K, V> val )
  169. {
  170. if( bucketIndex < bucketCount )
  171. iterator.set( val );
  172. else
  173. {
  174. Text err = "Index out of Range Exception File: ";
  175. err += __FILE__;
  176. err += " Line: ";
  177. err += __LINE__;
  178. throw std::out_of_range( (char*)err );
  179. }
  180. }
  181. bool operator!=( MapIterator< K, V >& r )
  182. {
  183. return buckets != r.buckets || iterator != r.iterator;
  184. }
  185. };
  186. template<typename K, typename V>
  187. class HashMap : public virtual ReferenceCounter
  188. {
  189. private:
  190. Array< MapEntry<K, V> >** buckets;
  191. int bucketCount;
  192. std::function<int( K )> hash;
  193. int size;
  194. public:
  195. HashMap( int bucketCount, std::function<int( K )> hash )
  196. : ReferenceCounter(),
  197. buckets( new Array< MapEntry<K, V> >* [ bucketCount ] ),
  198. bucketCount( bucketCount ),
  199. hash( hash ),
  200. size( 0 )
  201. {
  202. memset( buckets, 0, sizeof( Array< MapEntry<K, V> > * ) * bucketCount );
  203. }
  204. ~HashMap()
  205. {
  206. for( int i = 0; i < bucketCount; i++ )
  207. {
  208. if( buckets[ i ] )
  209. buckets[ i ]->release();
  210. }
  211. delete[] buckets;
  212. }
  213. void put( K key, V value )
  214. {
  215. int index = abs( hash( key ) ) % bucketCount;
  216. if( !buckets[ index ] )
  217. buckets[ index ] = new Array< MapEntry<K, V>>();
  218. for( auto iterator = buckets[ index ]->begin(); iterator; iterator++ )
  219. {
  220. if( iterator._.getKey() == key )
  221. {
  222. iterator.set( MapEntry<K, V>( key, value ) );
  223. return;
  224. }
  225. }
  226. buckets[ index ]->add( MapEntry<K, V>( key, value ) );
  227. size++;
  228. }
  229. void remove( K key )
  230. {
  231. int index = abs( hash( key ) ) % bucketCount;
  232. if( !buckets[ index ] )
  233. return;
  234. int listIndex = 0;
  235. for( auto bucket : *buckets[ index ] )
  236. {
  237. if( bucket.getKey() == key )
  238. {
  239. buckets[ index ]->remove( listIndex );
  240. size--;
  241. return;
  242. }
  243. listIndex++;
  244. }
  245. }
  246. V get( K key ) const
  247. {
  248. int index = abs( hash( key ) ) % bucketCount;
  249. if( !buckets[ index ] )
  250. throw "element not found";
  251. for( auto iterator : *buckets[ index ] )
  252. {
  253. if( iterator.getKey() == key )
  254. return iterator.getValue();
  255. }
  256. throw "element not found";
  257. }
  258. V safeGet( K key, V fallback ) const
  259. {
  260. int index = abs( hash( key ) ) % bucketCount;
  261. if( !buckets[ index ] )
  262. return fallback;
  263. for( auto bucket : *buckets[ index ] )
  264. {
  265. if( bucket.getKey() == key )
  266. return bucket.getValue();
  267. }
  268. return fallback;
  269. }
  270. bool has( K key ) const
  271. {
  272. int index = abs( hash( key ) ) % bucketCount;
  273. if( !buckets[ index ] )
  274. return 0;
  275. for( auto bucket : *buckets[ index ] )
  276. {
  277. if( bucket.getKey() == key )
  278. return 1;
  279. }
  280. return 0;
  281. }
  282. int getSize() const
  283. {
  284. return size;
  285. }
  286. void leeren()
  287. {
  288. for( int i = 0; i < bucketCount; i++ )
  289. {
  290. if( buckets[ i ] )
  291. buckets[ i ]->leeren();
  292. }
  293. }
  294. MapIterator<K, V> begin()
  295. {
  296. return MapIterator<K, V>( buckets, bucketCount, 0, Iterator< MapEntry<K, V> >( 0 ) );
  297. }
  298. MapIterator<K, V> end()
  299. {
  300. return MapIterator<K, V>( 0, 0, 0, Iterator< MapEntry<K, V> >( 0 ) );
  301. }
  302. };
  303. }