OpenShot Library | libopenshot-audio 0.2.0
juce_HashMap_test.cpp
1/*
2 ==============================================================================
3
4 This file is part of the JUCE library.
5 Copyright (c) 2017 - ROLI Ltd.
6
7 JUCE is an open source library subject to commercial or open-source
8 licensing.
9
10 The code included in this file is provided under the terms of the ISC license
11 http://www.isc.org/downloads/software-support-policy/isc-license. Permission
12 To use, copy, modify, and/or distribute this software for any purpose with or
13 without fee is hereby granted provided that the above copyright notice and
14 this permission notice appear in all copies.
15
16 JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
17 EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
18 DISCLAIMED.
19
20 ==============================================================================
21*/
22
23namespace juce
24{
25
26struct HashMapTest : public UnitTest
27{
28 HashMapTest() : UnitTest ("HashMap", "Containers") {}
29
30 void runTest() override
31 {
32 doTest<AddElementsTest> ("AddElementsTest");
33 doTest<AccessTest> ("AccessTest");
34 doTest<RemoveTest> ("RemoveTest");
35 doTest<PersistantMemoryLocationOfValues> ("PersistantMemoryLocationOfValues");
36 }
37
38 //==============================================================================
40 {
41 template <typename KeyType>
42 static void run (UnitTest& u)
43 {
46
47 RandomKeys<KeyType> keyOracle (300, 3827829);
48 Random valueOracle (48735);
49
50 int totalValues = 0;
51 for (int i = 0; i < 10000; ++i)
52 {
53 auto key = keyOracle.next();
54 auto value = valueOracle.nextInt();
55
56 bool contains = (groundTruth.find (key) != nullptr);
57 u.expectEquals ((int) contains, (int) hashMap.contains (key));
58
59 groundTruth.add (key, value);
60 hashMap.set (key, value);
61
62 if (! contains) totalValues++;
63
64 u.expectEquals (hashMap.size(), totalValues);
65 }
66 }
67 };
68
70 {
71 template <typename KeyType>
72 static void run (UnitTest& u)
73 {
76
77 fillWithRandomValues (hashMap, groundTruth);
78
79 for (auto pair : groundTruth.pairs)
80 u.expectEquals (hashMap[pair.key], pair.value);
81 }
82 };
83
85 {
86 template <typename KeyType>
87 static void run (UnitTest& u)
88 {
91
92 fillWithRandomValues (hashMap, groundTruth);
93 auto n = groundTruth.size();
94
95 Random r (3827387);
96
97 for (int i = 0; i < 100; ++i)
98 {
99 auto idx = r.nextInt (n-- - 1);
100 auto key = groundTruth.pairs.getReference (idx).key;
101
102 groundTruth.pairs.remove (idx);
103 hashMap.remove (key);
104
105 u.expect (! hashMap.contains (key));
106
107 for (auto pair : groundTruth.pairs)
108 u.expectEquals (hashMap[pair.key], pair.value);
109 }
110 }
111 };
112
113 // ensure that the addresses of object references don't change
115 {
116 struct AddressAndValue { int value; const int* valueAddress; };
117
118 template <typename KeyType>
119 static void run (UnitTest& u)
120 {
122 HashMap<KeyType, int> hashMap;
123
124 RandomKeys<KeyType> keyOracle (300, 3827829);
125 Random valueOracle (48735);
126
127 for (int i = 0; i < 1000; ++i)
128 {
129 auto key = keyOracle.next();
130 auto value = valueOracle.nextInt();
131
132 hashMap.set (key, value);
133
134 if (auto* existing = groundTruth.find (key))
135 {
136 // don't change the address: only the value
137 existing->value = value;
138 }
139 else
140 {
141 groundTruth.add (key, { value, &hashMap.getReference (key) });
142 }
143
144 for (auto pair : groundTruth.pairs)
145 {
146 const auto& hashMapValue = hashMap.getReference (pair.key);
147
148 u.expectEquals (hashMapValue, pair.value.value);
149 u.expect (&hashMapValue == pair.value.valueAddress);
150 }
151 }
152
153 auto n = groundTruth.size();
154 Random r (3827387);
155
156 for (int i = 0; i < 100; ++i)
157 {
158 auto idx = r.nextInt (n-- - 1);
159 auto key = groundTruth.pairs.getReference (idx).key;
160
161 groundTruth.pairs.remove (idx);
162 hashMap.remove (key);
163
164 for (auto pair : groundTruth.pairs)
165 {
166 const auto& hashMapValue = hashMap.getReference (pair.key);
167
168 u.expectEquals (hashMapValue, pair.value.value);
169 u.expect (&hashMapValue == pair.value.valueAddress);
170 }
171 }
172 }
173 };
174
175 //==============================================================================
176 template <class Test>
177 void doTest (const String& testName)
178 {
179 beginTest (testName);
180
181 Test::template run<int> (*this);
182 Test::template run<void*> (*this);
183 Test::template run<String> (*this);
184 }
185
186 //==============================================================================
187 template <typename KeyType, typename ValueType>
189 {
190 struct KeyValuePair { KeyType key; ValueType value; };
191
192 ValueType* find (KeyType key)
193 {
194 auto n = pairs.size();
195
196 for (int i = 0; i < n; ++i)
197 {
198 auto& pair = pairs.getReference (i);
199
200 if (pair.key == key)
201 return &pair.value;
202 }
203
204 return nullptr;
205 }
206
207 void add (KeyType key, ValueType value)
208 {
209 if (ValueType* v = find (key))
210 *v = value;
211 else
212 pairs.add ({key, value});
213 }
214
215 int size() const { return pairs.size(); }
216
217 Array<KeyValuePair> pairs;
218 };
219
220 template <typename KeyType, typename ValueType>
221 static void fillWithRandomValues (HashMap<KeyType, int>& hashMap, AssociativeMap<KeyType, ValueType>& groundTruth)
222 {
223 RandomKeys<KeyType> keyOracle (300, 3827829);
224 Random valueOracle (48735);
225
226 for (int i = 0; i < 10000; ++i)
227 {
228 auto key = keyOracle.next();
229 auto value = valueOracle.nextInt();
230
231 groundTruth.add (key, value);
232 hashMap.set (key, value);
233 }
234 }
235
236 //==============================================================================
237 template <typename KeyType>
239 {
240 public:
241 RandomKeys (int maxUniqueKeys, int seed) : r (seed)
242 {
243 for (int i = 0; i < maxUniqueKeys; ++i)
244 keys.add (generateRandomKey (r));
245 }
246
247 const KeyType& next()
248 {
249 int i = r.nextInt (keys.size() - 1);
250 return keys.getReference (i);
251 }
252 private:
253 static KeyType generateRandomKey (Random&);
254
255 Random r;
256 Array<KeyType> keys;
257 };
258};
259
260template <> int HashMapTest::RandomKeys<int> ::generateRandomKey (Random& rnd) { return rnd.nextInt(); }
261template <> void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) { return reinterpret_cast<void*> (rnd.nextInt64()); }
262
263template <> String HashMapTest::RandomKeys<String>::generateRandomKey (Random& rnd)
264{
265 String str;
266
267 int len = rnd.nextInt (8)+1;
268 for (int i = 0; i < len; ++i)
269 str += static_cast<char> (rnd.nextInt (95) + 32);
270
271 return str;
272}
273
274static HashMapTest hashMapTest;
275
276} // namespace juce
Holds a resizable array of primitive or copy-by-value objects.
Definition juce_Array.h:60
int size() const noexcept
Returns the current number of elements in the array.
Definition juce_Array.h:219
void remove(int indexToRemove)
Removes an element from the array.
Definition juce_Array.h:724
void add(const ElementType &newElement)
Appends a new element at the end of the array.
Definition juce_Array.h:375
ElementType & getReference(int index) const noexcept
Returns a direct reference to one of the elements in the array, without checking the index passed in.
Definition juce_Array.h:271
void set(int indexToChange, ParameterType newValue)
Replaces an element with a new value.
Definition juce_Array.h:499
bool contains(ParameterType elementToLookFor) const
Returns true if the array contains at least one occurrence of an object.
Definition juce_Array.h:357
A random number generator.
Definition juce_Random.h:39
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.
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.