OpenShot Audio Library | OpenShotAudio 0.3.2
Loading...
Searching...
No Matches
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()
29 : UnitTest ("HashMap", UnitTestCategories::containers)
30 {}
31
32 void runTest() override
33 {
34 doTest<AddElementsTest> ("AddElementsTest");
35 doTest<AccessTest> ("AccessTest");
36 doTest<RemoveTest> ("RemoveTest");
37 doTest<PersistantMemoryLocationOfValues> ("PersistantMemoryLocationOfValues");
38 }
39
40 //==============================================================================
41 struct AddElementsTest
42 {
43 template <typename KeyType>
44 static void run (UnitTest& u)
45 {
46 AssociativeMap<KeyType, int> groundTruth;
47 HashMap<KeyType, int> hashMap;
48
49 RandomKeys<KeyType> keyOracle (300, 3827829);
50 Random valueOracle (48735);
51
52 int totalValues = 0;
53 for (int i = 0; i < 10000; ++i)
54 {
55 auto key = keyOracle.next();
56 auto value = valueOracle.nextInt();
57
58 bool contains = (groundTruth.find (key) != nullptr);
59 u.expectEquals ((int) contains, (int) hashMap.contains (key));
60
61 groundTruth.add (key, value);
62 hashMap.set (key, value);
63
64 if (! contains) totalValues++;
65
66 u.expectEquals (hashMap.size(), totalValues);
67 }
68 }
69 };
70
71 struct AccessTest
72 {
73 template <typename KeyType>
74 static void run (UnitTest& u)
75 {
76 AssociativeMap<KeyType, int> groundTruth;
77 HashMap<KeyType, int> hashMap;
78
79 fillWithRandomValues (hashMap, groundTruth);
80
81 for (auto pair : groundTruth.pairs)
82 u.expectEquals (hashMap[pair.key], pair.value);
83 }
84 };
85
86 struct RemoveTest
87 {
88 template <typename KeyType>
89 static void run (UnitTest& u)
90 {
91 AssociativeMap<KeyType, int> groundTruth;
92 HashMap<KeyType, int> hashMap;
93
94 fillWithRandomValues (hashMap, groundTruth);
95 auto n = groundTruth.size();
96
97 Random r (3827387);
98
99 for (int i = 0; i < 100; ++i)
100 {
101 auto idx = r.nextInt (n-- - 1);
102 auto key = groundTruth.pairs.getReference (idx).key;
103
104 groundTruth.pairs.remove (idx);
105 hashMap.remove (key);
106
107 u.expect (! hashMap.contains (key));
108
109 for (auto pair : groundTruth.pairs)
110 u.expectEquals (hashMap[pair.key], pair.value);
111 }
112 }
113 };
114
115 // ensure that the addresses of object references don't change
116 struct PersistantMemoryLocationOfValues
117 {
118 struct AddressAndValue { int value; const int* valueAddress; };
119
120 template <typename KeyType>
121 static void run (UnitTest& u)
122 {
123 AssociativeMap<KeyType, AddressAndValue> groundTruth;
124 HashMap<KeyType, int> hashMap;
125
126 RandomKeys<KeyType> keyOracle (300, 3827829);
127 Random valueOracle (48735);
128
129 for (int i = 0; i < 1000; ++i)
130 {
131 auto key = keyOracle.next();
132 auto value = valueOracle.nextInt();
133
134 hashMap.set (key, value);
135
136 if (auto* existing = groundTruth.find (key))
137 {
138 // don't change the address: only the value
139 existing->value = value;
140 }
141 else
142 {
143 groundTruth.add (key, { value, &hashMap.getReference (key) });
144 }
145
146 for (auto pair : groundTruth.pairs)
147 {
148 const auto& hashMapValue = hashMap.getReference (pair.key);
149
150 u.expectEquals (hashMapValue, pair.value.value);
151 u.expect (&hashMapValue == pair.value.valueAddress);
152 }
153 }
154
155 auto n = groundTruth.size();
156 Random r (3827387);
157
158 for (int i = 0; i < 100; ++i)
159 {
160 auto idx = r.nextInt (n-- - 1);
161 auto key = groundTruth.pairs.getReference (idx).key;
162
163 groundTruth.pairs.remove (idx);
164 hashMap.remove (key);
165
166 for (auto pair : groundTruth.pairs)
167 {
168 const auto& hashMapValue = hashMap.getReference (pair.key);
169
170 u.expectEquals (hashMapValue, pair.value.value);
171 u.expect (&hashMapValue == pair.value.valueAddress);
172 }
173 }
174 }
175 };
176
177 //==============================================================================
178 template <class Test>
179 void doTest (const String& testName)
180 {
181 beginTest (testName);
182
183 Test::template run<int> (*this);
184 Test::template run<void*> (*this);
185 Test::template run<String> (*this);
186 }
187
188 //==============================================================================
189 template <typename KeyType, typename ValueType>
190 struct AssociativeMap
191 {
192 struct KeyValuePair { KeyType key; ValueType value; };
193
194 ValueType* find (KeyType key)
195 {
196 auto n = pairs.size();
197
198 for (int i = 0; i < n; ++i)
199 {
200 auto& pair = pairs.getReference (i);
201
202 if (pair.key == key)
203 return &pair.value;
204 }
205
206 return nullptr;
207 }
208
209 void add (KeyType key, ValueType value)
210 {
211 if (ValueType* v = find (key))
212 *v = value;
213 else
214 pairs.add ({key, value});
215 }
216
217 int size() const { return pairs.size(); }
218
219 Array<KeyValuePair> pairs;
220 };
221
222 template <typename KeyType, typename ValueType>
223 static void fillWithRandomValues (HashMap<KeyType, int>& hashMap, AssociativeMap<KeyType, ValueType>& groundTruth)
224 {
225 RandomKeys<KeyType> keyOracle (300, 3827829);
226 Random valueOracle (48735);
227
228 for (int i = 0; i < 10000; ++i)
229 {
230 auto key = keyOracle.next();
231 auto value = valueOracle.nextInt();
232
233 groundTruth.add (key, value);
234 hashMap.set (key, value);
235 }
236 }
237
238 //==============================================================================
239 template <typename KeyType>
240 class RandomKeys
241 {
242 public:
243 RandomKeys (int maxUniqueKeys, int seed) : r (seed)
244 {
245 for (int i = 0; i < maxUniqueKeys; ++i)
246 keys.add (generateRandomKey (r));
247 }
248
249 const KeyType& next()
250 {
251 int i = r.nextInt (keys.size() - 1);
252 return keys.getReference (i);
253 }
254 private:
255 static KeyType generateRandomKey (Random&);
256
257 Random r;
258 Array<KeyType> keys;
259 };
260};
261
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()); }
264
265template <> String HashMapTest::RandomKeys<String>::generateRandomKey (Random& rnd)
266{
267 String str;
268
269 int len = rnd.nextInt (8)+1;
270 for (int i = 0; i < len; ++i)
271 str += static_cast<char> (rnd.nextInt (95) + 32);
272
273 return str;
274}
275
276static HashMapTest hashMapTest;
277
278} // namespace juce
void expectEquals(ValueType actual, ValueType expected, String failureMessage=String())
UnitTest(const String &name, const String &category=String())
void beginTest(const String &testName)