HashMapTests.cpp 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317
  1. #include "tests/HashMapTests.h"
  2. #include "tests/Test.h"
  3. #include "utils/HashMap.h"
  4. #include "utils/StringBuffer.h"
  5. typedef HashMap<int, int> IntMap;
  6. typedef StringBuffer<50> String;
  7. static void testAdd(Test& test) {
  8. (void)test;
  9. IntMap map;
  10. map.add(5, 4);
  11. int* value = map.search(5);
  12. test.checkEqual(true, value != nullptr, "contains added value");
  13. if(value != nullptr) {
  14. test.checkEqual(4, *value, "search finds added value");
  15. }
  16. }
  17. static void testMultipleAdd(Test& test) {
  18. IntMap map;
  19. map.add(5, 4).add(10, 3).add(15, 2);
  20. test.checkEqual(true, map.contains(5), "contains added value 1");
  21. test.checkEqual(true, map.contains(10), "contains added value 2");
  22. test.checkEqual(true, map.contains(15), "contains added value 3");
  23. int* a = map.search(5);
  24. int* b = map.search(10);
  25. int* c = map.search(15);
  26. test.checkEqual(true, a != nullptr, "contains added value 1");
  27. test.checkEqual(true, b != nullptr, "contains added value 2");
  28. test.checkEqual(true, c != nullptr, "contains added value 3");
  29. if(a != nullptr && b != nullptr && c != nullptr) {
  30. test.checkEqual(4, *a, "search finds added value 1");
  31. test.checkEqual(3, *b, "search finds added value 2");
  32. test.checkEqual(2, *c, "search finds added value 3");
  33. }
  34. }
  35. static void testSearch(Test& test) {
  36. IntMap map;
  37. test.checkEqual(true, nullptr == map.search(6),
  38. "search does not find missing key");
  39. }
  40. static void testAddReplace(Test& test) {
  41. IntMap map;
  42. map.add(5, 4).add(5, 10);
  43. test.checkEqual(true, map.contains(5), "contains replaced value");
  44. int* a = map.search(5);
  45. test.checkEqual(true, a != nullptr, "contains replaced value");
  46. if(a != nullptr) {
  47. test.checkEqual(10, *a, "search finds replaced value");
  48. }
  49. }
  50. static void testClear(Test& test) {
  51. IntMap map;
  52. map.add(5, 4).add(4, 10).clear();
  53. test.checkEqual(false, map.contains(5),
  54. "does not contain cleared values 1");
  55. test.checkEqual(false, map.contains(4),
  56. "does not contain cleared values 2");
  57. }
  58. static void testOverflow(Test& test) {
  59. IntMap map;
  60. for(int i = 0; i < 1000000; i++) {
  61. map.add(i, i);
  62. }
  63. for(int i = 0; i < 1000000; i++) {
  64. test.checkEqual(true, map.contains(i),
  65. "still contains values after overflow");
  66. }
  67. test.checkEqual(true, true, "survives overflow");
  68. }
  69. struct A {
  70. int a;
  71. int b;
  72. A(int a, int b) : a(a), b(b) {
  73. }
  74. bool operator==(const A& other) const {
  75. return a == other.a && b == other.b;
  76. }
  77. template<int L>
  78. void toString(StringBuffer<L>& s) const {
  79. s.append("A(").append(a).append(", ").append(b).append(")");
  80. }
  81. };
  82. static void testEmplace(Test& test) {
  83. HashMap<int, A> map;
  84. bool r1 = map.tryEmplace(0, 3, 4);
  85. bool r2 = map.tryEmplace(3, 4, 5);
  86. bool r3 = map.tryEmplace(20, 5, 6);
  87. bool r4 = map.tryEmplace(3, 6, 7);
  88. bool r5 = map.tryEmplace(20, 7, 8);
  89. A* a = map.search(0);
  90. A* b = map.search(3);
  91. A* c = map.search(20);
  92. test.checkEqual(true, a != nullptr, "contains emplaced value 1");
  93. test.checkEqual(true, b != nullptr, "contains emplaced value 2");
  94. test.checkEqual(true, c != nullptr, "contains emplaced value 3");
  95. if(a != nullptr && b != nullptr && c != nullptr) {
  96. test.checkEqual(A(3, 4), *a, "contains emplaced value 1");
  97. test.checkEqual(A(4, 5), *b, "contains emplaced value 2");
  98. test.checkEqual(A(5, 6), *c, "contains emplaced value 3");
  99. }
  100. test.checkEqual(false, r1, "emplacing returns correct value 1");
  101. test.checkEqual(false, r2, "emplacing returns correct value 2");
  102. test.checkEqual(false, r3, "emplacing returns correct value 3");
  103. test.checkEqual(true, r4, "emplacing returns correct value 4");
  104. test.checkEqual(true, r5, "emplacing returns correct value 5");
  105. }
  106. static void testToString1(Test& test) {
  107. IntMap map;
  108. map.add(1, 3).add(2, 4).add(3, 5);
  109. test.checkEqual(String("[1 = 3, 2 = 4, 3 = 5]"), String(map),
  110. "to string 1");
  111. }
  112. static void testToString2(Test& test) {
  113. IntMap map;
  114. map.add(1, 3);
  115. test.checkEqual(String("[1 = 3]"), String(map), "to string 2");
  116. }
  117. static void testToString3(Test& test) {
  118. IntMap map;
  119. test.checkEqual(String("[]"), String(map), "to string 3");
  120. }
  121. static void testCopy(Test& test) {
  122. IntMap map;
  123. map.add(1, 3).add(2, 4).add(3, 5);
  124. IntMap copy(map);
  125. int* a[6] = {map.search(1), map.search(2), map.search(3),
  126. copy.search(1), copy.search(2), copy.search(3)};
  127. for(int i = 0; i < 3; i++) {
  128. test.checkEqual(true, a[i] != nullptr && a[i + 3] != nullptr,
  129. "copy has same values");
  130. if(a[i] != nullptr && a[i + 3] != nullptr) {
  131. test.checkEqual(*(a[i]), *(a[i + 3]), "copy has same values");
  132. }
  133. }
  134. }
  135. static void testCopyAssignment(Test& test) {
  136. IntMap map;
  137. map.add(1, 3).add(2, 4).add(3, 5);
  138. IntMap copy;
  139. copy = map;
  140. int* a[6] = {map.search(1), map.search(2), map.search(3),
  141. copy.search(1), copy.search(2), copy.search(3)};
  142. for(int i = 0; i < 3; i++) {
  143. test.checkEqual(true, a[i] != nullptr && a[i + 3] != nullptr,
  144. "copy assignment has same values");
  145. if(a[i] != nullptr && a[i + 3] != nullptr) {
  146. test.checkEqual(*(a[i]), *(a[i + 3]),
  147. "copy assignment has same values");
  148. }
  149. }
  150. }
  151. static void testMove(Test& test) {
  152. IntMap map;
  153. map.add(1, 3).add(2, 4).add(3, 5);
  154. IntMap move(std::move(map));
  155. int* a = move.search(1);
  156. int* b = move.search(2);
  157. int* c = move.search(3);
  158. test.checkEqual(true, a != nullptr, "move moves values 1");
  159. test.checkEqual(true, b != nullptr, "move moves values 2");
  160. test.checkEqual(true, c != nullptr, "move moves values 3");
  161. if(a != nullptr && b != nullptr && c != nullptr) {
  162. test.checkEqual(3, *a, "move moves values 1");
  163. test.checkEqual(4, *b, "move moves values 2");
  164. test.checkEqual(5, *c, "move moves values 3");
  165. }
  166. }
  167. static void testMoveAssignment(Test& test) {
  168. IntMap map;
  169. map.add(1, 3).add(2, 4).add(3, 5);
  170. IntMap move;
  171. move = std::move(map);
  172. int* a = move.search(1);
  173. int* b = move.search(2);
  174. int* c = move.search(3);
  175. test.checkEqual(true, a != nullptr, "move moves values 1");
  176. test.checkEqual(true, b != nullptr, "move moves values 2");
  177. test.checkEqual(true, c != nullptr, "move moves values 3");
  178. if(a != nullptr && b != nullptr && c != nullptr) {
  179. test.checkEqual(3, *a, "move moves values 1");
  180. test.checkEqual(4, *b, "move moves values 2");
  181. test.checkEqual(5, *c, "move moves values 3");
  182. }
  183. }
  184. static void testRemove(Test& test) {
  185. IntMap map;
  186. map.add(1, 3).add(2, 4).add(3, 5);
  187. bool remove1 = map.remove(2);
  188. bool remove2 = map.remove(7);
  189. int* a = map.search(1);
  190. int* b = map.search(2);
  191. int* c = map.search(3);
  192. test.checkEqual(true, a != nullptr, "move moves values 1");
  193. test.checkEqual(true, b == nullptr, "move moves values 2");
  194. test.checkEqual(true, c != nullptr, "move moves values 3");
  195. test.checkEqual(true, remove1, "remove returns true");
  196. test.checkEqual(false, remove2, "remove returns false");
  197. if(a != nullptr && c != nullptr) {
  198. test.checkEqual(3, *a, "move moves values 1");
  199. test.checkEqual(5, *c, "move moves values 3");
  200. }
  201. }
  202. static void testEntryForEach(Test& test) {
  203. IntMap map;
  204. map.add(5, 4).add(10, 3).add(15, 2);
  205. int counter = 0;
  206. for(auto& entry : map.entries()) {
  207. counter += entry.getKey() + entry.value;
  208. }
  209. test.checkEqual(39, counter, "entry iterator");
  210. const IntMap& cmap = map;
  211. counter = 0;
  212. for(const auto& entry : cmap.entries()) {
  213. counter += entry.getKey() + entry.value;
  214. }
  215. test.checkEqual(39, counter, "const entry iterator");
  216. }
  217. static void testKeyForEach(Test& test) {
  218. IntMap map;
  219. map.add(5, 4).add(10, 3).add(15, 2);
  220. int counter = 0;
  221. for(const int& key : map.keys()) {
  222. counter += key;
  223. }
  224. test.checkEqual(30, counter, "key iterator");
  225. const IntMap& cmap = map;
  226. counter = 0;
  227. for(const int& key : cmap.keys()) {
  228. counter += key;
  229. }
  230. test.checkEqual(30, counter, "const key iterator");
  231. }
  232. static void testValueForEach(Test& test) {
  233. IntMap map;
  234. map.add(5, 4).add(10, 3).add(15, 2);
  235. int counter = 0;
  236. for(int& value : map.values()) {
  237. counter += value;
  238. }
  239. test.checkEqual(9, counter, "value iterator");
  240. const IntMap& cmap = map;
  241. counter = 0;
  242. for(const int& value : cmap.values()) {
  243. counter += value;
  244. }
  245. test.checkEqual(9, counter, "const value iterator");
  246. }
  247. void HashMapTests::test() {
  248. Test test("HashMap");
  249. testAdd(test);
  250. testMultipleAdd(test);
  251. testSearch(test);
  252. testAddReplace(test);
  253. testClear(test);
  254. testOverflow(test);
  255. testEmplace(test);
  256. testToString1(test);
  257. testToString2(test);
  258. testToString3(test);
  259. testCopy(test);
  260. testCopyAssignment(test);
  261. testMove(test);
  262. testMoveAssignment(test);
  263. testRemove(test);
  264. testEntryForEach(test);
  265. testKeyForEach(test);
  266. testValueForEach(test);
  267. test.finalize();
  268. }