26struct HashMapTest :
public UnitTest
29 :
UnitTest (
"HashMap", UnitTestCategories::containers)
32 void runTest()
override
34 doTest<AddElementsTest> (
"AddElementsTest");
35 doTest<AccessTest> (
"AccessTest");
36 doTest<RemoveTest> (
"RemoveTest");
37 doTest<PersistantMemoryLocationOfValues> (
"PersistantMemoryLocationOfValues");
41 struct AddElementsTest
43 template <
typename KeyType>
44 static void run (UnitTest& u)
46 AssociativeMap<KeyType, int> groundTruth;
47 HashMap<KeyType, int> hashMap;
49 RandomKeys<KeyType> keyOracle (300, 3827829);
50 Random valueOracle (48735);
53 for (
int i = 0; i < 10000; ++i)
55 auto key = keyOracle.next();
56 auto value = valueOracle.nextInt();
58 bool contains = (groundTruth.find (key) !=
nullptr);
59 u.expectEquals ((
int) contains, (int) hashMap.contains (key));
61 groundTruth.add (key, value);
62 hashMap.set (key, value);
64 if (! contains) totalValues++;
66 u.expectEquals (hashMap.size(), totalValues);
73 template <
typename KeyType>
74 static void run (UnitTest& u)
76 AssociativeMap<KeyType, int> groundTruth;
77 HashMap<KeyType, int> hashMap;
79 fillWithRandomValues (hashMap, groundTruth);
81 for (
auto pair : groundTruth.pairs)
88 template <
typename KeyType>
89 static void run (UnitTest& u)
91 AssociativeMap<KeyType, int> groundTruth;
92 HashMap<KeyType, int> hashMap;
94 fillWithRandomValues (hashMap, groundTruth);
95 auto n = groundTruth.size();
99 for (
int i = 0; i < 100; ++i)
101 auto idx = r.nextInt (n-- - 1);
102 auto key = groundTruth.pairs.getReference (idx).key;
104 groundTruth.pairs.remove (idx);
105 hashMap.remove (key);
107 u.expect (! hashMap.contains (key));
109 for (
auto pair : groundTruth.pairs)
116 struct PersistantMemoryLocationOfValues
118 struct AddressAndValue {
int value;
const int* valueAddress; };
120 template <
typename KeyType>
121 static void run (UnitTest& u)
123 AssociativeMap<KeyType, AddressAndValue> groundTruth;
124 HashMap<KeyType, int> hashMap;
126 RandomKeys<KeyType> keyOracle (300, 3827829);
127 Random valueOracle (48735);
129 for (
int i = 0; i < 1000; ++i)
131 auto key = keyOracle.next();
132 auto value = valueOracle.nextInt();
134 hashMap.set (key, value);
136 if (
auto* existing = groundTruth.find (key))
139 existing->value = value;
143 groundTruth.add (key, { value, &hashMap.getReference (key) });
146 for (
auto pair : groundTruth.pairs)
148 const auto& hashMapValue = hashMap.getReference (pair.key);
150 u.expectEquals (hashMapValue, pair.value.value);
151 u.expect (&hashMapValue == pair.value.valueAddress);
155 auto n = groundTruth.size();
158 for (
int i = 0; i < 100; ++i)
160 auto idx = r.nextInt (n-- - 1);
161 auto key = groundTruth.pairs.getReference (idx).key;
163 groundTruth.pairs.remove (idx);
164 hashMap.remove (key);
166 for (
auto pair : groundTruth.pairs)
168 const auto& hashMapValue = hashMap.getReference (pair.key);
170 u.expectEquals (hashMapValue, pair.value.value);
171 u.expect (&hashMapValue == pair.value.valueAddress);
178 template <
class Test>
179 void doTest (
const String& testName)
183 Test::template run<int> (*
this);
184 Test::template run<void*> (*
this);
185 Test::template run<String> (*
this);
189 template <
typename KeyType,
typename ValueType>
190 struct AssociativeMap
192 struct KeyValuePair { KeyType key; ValueType value; };
194 ValueType* find (KeyType key)
196 auto n = pairs.size();
198 for (
int i = 0; i < n; ++i)
200 auto& pair = pairs.getReference (i);
209 void add (KeyType key, ValueType value)
211 if (ValueType* v = find (key))
214 pairs.add ({key, value});
217 int size()
const {
return pairs.size(); }
219 Array<KeyValuePair> pairs;
222 template <
typename KeyType,
typename ValueType>
223 static void fillWithRandomValues (HashMap<KeyType, int>& hashMap, AssociativeMap<KeyType, ValueType>& groundTruth)
225 RandomKeys<KeyType> keyOracle (300, 3827829);
226 Random valueOracle (48735);
228 for (
int i = 0; i < 10000; ++i)
230 auto key = keyOracle.next();
231 auto value = valueOracle.nextInt();
233 groundTruth.add (key, value);
234 hashMap.set (key, value);
239 template <
typename KeyType>
243 RandomKeys (
int maxUniqueKeys,
int seed) : r (seed)
245 for (
int i = 0; i < maxUniqueKeys; ++i)
246 keys.add (generateRandomKey (r));
249 const KeyType& next()
251 int i = r.nextInt (keys.size() - 1);
252 return keys.getReference (i);
255 static KeyType generateRandomKey (Random&);
262template <>
int HashMapTest::RandomKeys<int> ::generateRandomKey (Random& rnd) {
return rnd.nextInt(); }
263template <>
void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) {
return reinterpret_cast<void*
> (rnd.nextInt64()); }
265template <> String HashMapTest::RandomKeys<String>::generateRandomKey (Random& rnd)
269 int len = rnd.nextInt (8)+1;
270 for (
int i = 0; i < len; ++i)
271 str +=
static_cast<char> (rnd.nextInt (95) + 32);
276static HashMapTest hashMapTest;
void expectEquals(ValueType actual, ValueType expected, String failureMessage=String())
UnitTest(const String &name, const String &category=String())
void beginTest(const String &testName)