OpenShot Library | OpenShotAudio  0.2.1
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 
23 namespace juce
24 {
25 
26 struct 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  //==============================================================================
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
117  {
118  struct AddressAndValue { int value; const int* valueAddress; };
119 
120  template <typename KeyType>
121  static void run (UnitTest& u)
122  {
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>
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>
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 
262 template <> int HashMapTest::RandomKeys<int> ::generateRandomKey (Random& rnd) { return rnd.nextInt(); }
263 template <> void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) { return reinterpret_cast<void*> (rnd.nextInt64()); }
264 
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 
276 static HashMapTest hashMapTest;
277 
278 } // namespace juce
Holds a set of mappings between some key/value pairs.
Definition: juce_HashMap.h:107
void remove(KeyTypeParameter keyToRemove)
Removes an item with the given key.
Definition: juce_HashMap.h:239
int nextInt() noexcept
Returns the next random 32 bit integer.
Definition: juce_Random.cpp:78
int size() const noexcept
Returns the current number of items in the map.
Definition: juce_HashMap.h:165
UnitTest(const String &name, const String &category=String())
Creates a test with the given name and optionally places it in a category.
The JUCE String class!
Definition: juce_String.h:42
void expectEquals(ValueType actual, ValueType expected, String failureMessage=String())
Compares a value to an expected value.
int64 nextInt64() noexcept
Returns the next 64-bit random number.
Definition: juce_Random.cpp:96
This is a base class for classes that perform a unit test.
Definition: juce_UnitTest.h:73
void set(KeyTypeParameter newKey, ValueTypeParameter newValue)
Adds or replaces an element in the hash-map.
Definition: juce_HashMap.h:236
void beginTest(const String &testName)
Tells the system that a new subsection of tests is beginning.
void runTest() override
Implement this method in your subclass to actually run your tests.
Holds a resizable array of primitive or copy-by-value objects.
Definition: juce_Array.h:59
void expect(bool testResult, const String &failureMessage=String())
Checks that the result of a test is true, and logs this result.
A random number generator.
Definition: juce_Random.h:38
bool contains(KeyTypeParameter keyToLookFor) const
Returns true if the map contains an item with the specified key.
Definition: juce_HashMap.h:211
ValueType & getReference(KeyTypeParameter keyToLookFor)
Returns a reference to the value corresponding to a given key.
Definition: juce_HashMap.h:189