HashMap.h 9.1 KB

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