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 
23 namespace juce
24 {
25 
26 struct 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  {
44  AssociativeMap<KeyType, int> groundTruth;
45  HashMap<KeyType, int> hashMap;
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 
69  struct AccessTest
70  {
71  template <typename KeyType>
72  static void run (UnitTest& u)
73  {
74  AssociativeMap<KeyType, int> groundTruth;
75  HashMap<KeyType, int> hashMap;
76 
77  fillWithRandomValues (hashMap, groundTruth);
78 
79  for (auto pair : groundTruth.pairs)
80  u.expectEquals (hashMap[pair.key], pair.value);
81  }
82  };
83 
84  struct RemoveTest
85  {
86  template <typename KeyType>
87  static void run (UnitTest& u)
88  {
89  AssociativeMap<KeyType, int> groundTruth;
90  HashMap<KeyType, int> hashMap;
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 
260 template <> int HashMapTest::RandomKeys<int> ::generateRandomKey (Random& rnd) { return rnd.nextInt(); }
261 template <> void* HashMapTest::RandomKeys<void*>::generateRandomKey (Random& rnd) { return reinterpret_cast<void*> (rnd.nextInt64()); }
262 
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 
274 static HashMapTest hashMapTest;
275 
276 } // 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 specied 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