HashMapTests.cpp 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284
  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. };
  78. std::ostream& operator<<(std::ostream& os, const A& a) {
  79. return os << "A(" << a.a << ", " << a.b << ")";
  80. }
  81. static void testEmplace(Test& test) {
  82. HashMap<int, A> map;
  83. bool r1 = map.tryEmplace(0, 3, 4);
  84. bool r2 = map.tryEmplace(3, 4, 5);
  85. bool r3 = map.tryEmplace(20, 5, 6);
  86. bool r4 = map.tryEmplace(3, 6, 7);
  87. bool r5 = map.tryEmplace(20, 7, 8);
  88. A* a = map.search(0);
  89. A* b = map.search(3);
  90. A* c = map.search(20);
  91. test.checkEqual(true, a != nullptr, "contains emplaced value 1");
  92. test.checkEqual(true, b != nullptr, "contains emplaced value 2");
  93. test.checkEqual(true, c != nullptr, "contains emplaced value 3");
  94. if(a != nullptr && b != nullptr && c != nullptr) {
  95. test.checkEqual(A(3, 4), *a, "contains emplaced value 1");
  96. test.checkEqual(A(4, 5), *b, "contains emplaced value 2");
  97. test.checkEqual(A(5, 6), *c, "contains emplaced value 3");
  98. }
  99. test.checkEqual(false, r1, "emplacing returns correct value 1");
  100. test.checkEqual(false, r2, "emplacing returns correct value 2");
  101. test.checkEqual(false, r3, "emplacing returns correct value 3");
  102. test.checkEqual(true, r4, "emplacing returns correct value 4");
  103. test.checkEqual(true, r5, "emplacing returns correct value 5");
  104. }
  105. static void testToString1(Test& test) {
  106. IntMap map;
  107. map.add(1, 3).add(2, 4).add(3, 5);
  108. test.checkEqual(String("[1 = 3, 2 = 4, 3 = 5]"), String(map),
  109. "to string 1");
  110. }
  111. static void testToString2(Test& test) {
  112. IntMap map;
  113. map.add(1, 3);
  114. test.checkEqual(String("[1 = 3]"), String(map), "to string 2");
  115. }
  116. static void testToString3(Test& test) {
  117. IntMap map;
  118. test.checkEqual(String("[]"), String(map), "to string 3");
  119. }
  120. static void testCopy(Test& test) {
  121. IntMap map;
  122. map.add(1, 3).add(2, 4).add(3, 5);
  123. IntMap copy(map);
  124. int* a[6] = {map.search(1), map.search(2), map.search(3),
  125. copy.search(1), copy.search(2), copy.search(3)};
  126. for(int i = 0; i < 3; i++) {
  127. test.checkEqual(true, a[i] != nullptr && a[i + 3] != nullptr,
  128. "copy has same values");
  129. if(a[i] != nullptr && a[i + 3] != nullptr) {
  130. test.checkEqual(*(a[i]), *(a[i + 3]), "copy has same values");
  131. }
  132. }
  133. }
  134. static void testCopyAssignment(Test& test) {
  135. IntMap map;
  136. map.add(1, 3).add(2, 4).add(3, 5);
  137. IntMap copy;
  138. copy = map;
  139. int* a[6] = {map.search(1), map.search(2), map.search(3),
  140. copy.search(1), copy.search(2), copy.search(3)};
  141. for(int i = 0; i < 3; i++) {
  142. test.checkEqual(true, a[i] != nullptr && a[i + 3] != nullptr,
  143. "copy assignment has same values");
  144. if(a[i] != nullptr && a[i + 3] != nullptr) {
  145. test.checkEqual(*(a[i]), *(a[i + 3]),
  146. "copy assignment has same values");
  147. }
  148. }
  149. }
  150. static void testMove(Test& test) {
  151. IntMap map;
  152. map.add(1, 3).add(2, 4).add(3, 5);
  153. IntMap move(std::move(map));
  154. int* a = move.search(1);
  155. int* b = move.search(2);
  156. int* c = move.search(3);
  157. test.checkEqual(true, a != nullptr, "move moves values 1");
  158. test.checkEqual(true, b != nullptr, "move moves values 2");
  159. test.checkEqual(true, c != nullptr, "move moves values 3");
  160. if(a != nullptr && b != nullptr && c != nullptr) {
  161. test.checkEqual(3, *a, "move moves values 1");
  162. test.checkEqual(4, *b, "move moves values 2");
  163. test.checkEqual(5, *c, "move moves values 3");
  164. }
  165. }
  166. static void testMoveAssignment(Test& test) {
  167. IntMap map;
  168. map.add(1, 3).add(2, 4).add(3, 5);
  169. IntMap move;
  170. move = std::move(map);
  171. int* a = move.search(1);
  172. int* b = move.search(2);
  173. int* c = move.search(3);
  174. test.checkEqual(true, a != nullptr, "move moves values 1");
  175. test.checkEqual(true, b != nullptr, "move moves values 2");
  176. test.checkEqual(true, c != nullptr, "move moves values 3");
  177. if(a != nullptr && b != nullptr && c != nullptr) {
  178. test.checkEqual(3, *a, "move moves values 1");
  179. test.checkEqual(4, *b, "move moves values 2");
  180. test.checkEqual(5, *c, "move moves values 3");
  181. }
  182. }
  183. static void testRemove(Test& test) {
  184. IntMap map;
  185. map.add(1, 3).add(2, 4).add(3, 5);
  186. bool remove1 = map.remove(2);
  187. bool remove2 = map.remove(7);
  188. int* a = map.search(1);
  189. int* b = map.search(2);
  190. int* c = map.search(3);
  191. test.checkEqual(true, a != nullptr, "move moves values 1");
  192. test.checkEqual(true, b == nullptr, "move moves values 2");
  193. test.checkEqual(true, c != nullptr, "move moves values 3");
  194. test.checkEqual(true, remove1, "remove returns true");
  195. test.checkEqual(false, remove2, "remove returns false");
  196. if(a != nullptr && c != nullptr) {
  197. test.checkEqual(3, *a, "move moves values 1");
  198. test.checkEqual(5, *c, "move moves values 3");
  199. }
  200. }
  201. static void testForEach(Test& test) {
  202. IntMap map;
  203. map.add(5, 4).add(10, 3).add(15, 2);
  204. auto iter = map.begin();
  205. test.checkEqual(true, iter != map.end(), "not at end 1");
  206. ++iter;
  207. test.checkEqual(true, iter != map.end(), "not at end 2");
  208. ++iter;
  209. test.checkEqual(true, iter != map.end(), "not at end 3");
  210. ++iter;
  211. test.checkEqual(false, iter != map.end(), "at end");
  212. const IntMap& cmap = map;
  213. auto citer = cmap.begin();
  214. test.checkEqual(true, citer != cmap.end(), "not at end 1");
  215. ++citer;
  216. test.checkEqual(true, citer != cmap.end(), "not at end 2");
  217. ++citer;
  218. test.checkEqual(true, citer != cmap.end(), "not at end 3");
  219. ++citer;
  220. test.checkEqual(false, citer != cmap.end(), "at end");
  221. }
  222. void HashMapTests::test() {
  223. Test test("HashMap");
  224. testAdd(test);
  225. testMultipleAdd(test);
  226. testSearch(test);
  227. testAddReplace(test);
  228. testClear(test);
  229. testOverflow(test);
  230. testEmplace(test);
  231. testToString1(test);
  232. testToString2(test);
  233. testToString3(test);
  234. testCopy(test);
  235. testCopyAssignment(test);
  236. testMove(test);
  237. testMoveAssignment(test);
  238. testRemove(test);
  239. testForEach(test);
  240. test.finalize();
  241. }