29 :
UnitTest (
"HashMap", UnitTestCategories::containers)
34 doTest<AddElementsTest> (
"AddElementsTest");
35 doTest<AccessTest> (
"AccessTest");
36 doTest<RemoveTest> (
"RemoveTest");
37 doTest<PersistantMemoryLocationOfValues> (
"PersistantMemoryLocationOfValues");
43 template <
typename KeyType>
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);
61 groundTruth.add (key, value);
62 hashMap.
set (key, value);
64 if (! contains) totalValues++;
73 template <
typename KeyType>
79 fillWithRandomValues (hashMap, groundTruth);
81 for (
auto pair : groundTruth.pairs)
88 template <
typename KeyType>
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);
109 for (
auto pair : groundTruth.pairs)
120 template <
typename KeyType>
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);
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);
166 for (
auto pair : groundTruth.pairs)
168 const auto& hashMapValue = hashMap.
getReference (pair.key);
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>
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()
255 static KeyType generateRandomKey (
Random&);
263 template <>
void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) {
return reinterpret_cast<void*
> (rnd.nextInt64()); }
265 template <> 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);
276 static HashMapTest hashMapTest;
int size() const noexcept
Returns the current number of elements in the array.
void add(const ElementType &newElement)
Appends a new element at the end of the array.
ElementType & getReference(int index) noexcept
Returns a direct reference to one of the elements in the array, without checking the index passed in.
Holds a set of mappings between some key/value pairs.
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
void remove(KeyTypeParameter keyToRemove)
Removes an item with the given key.
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Adds or replaces an element in the hash-map.
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specified key.
int size() const noexcept
Returns the current number of items in the map.
A random number generator.
int nextInt() noexcept
Returns the next random 32 bit integer.
This is a base class for classes that perform a unit test.
void expectEquals(ValueType actual, ValueType expected, String failureMessage=String())
Compares a value to an expected value.
UnitTest(const String &name, const String &category=String())
Creates a test with the given name and optionally places it in a category.
void beginTest(const String &testName)
Tells the system that a new subsection of tests is beginning.
void expect(bool testResult, const String &failureMessage=String())
Checks that the result of a test is true, and logs this result.
void runTest() override
Implement this method in your subclass to actually run your tests.