1/*
2 * Copyright © 2013 Intel Corporation
3 *
4 * This library is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License as published by
6 * the Free Software Foundation, either version 2.1 of the License, or
7 * (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public License
15 * along with this library.  If not, see <http://www.gnu.org/licenses/>.
16 *
17 * Authors:
18 *      Simon McVittie <simon.mcvittie@collabora.co.uk>
19 */
20
21using Gee;
22using Folks;
23
24/* An object with no equality pseudo-operator. */
25public class DirectEq : Object
26{
27  public uint u;
28
29  public DirectEq (uint u)
30    {
31      this.u = u;
32    }
33}
34
35/* An object with an equality pseudo-operator. */
36public class UInt : Object
37{
38  public uint u;
39
40  public UInt (uint u)
41    {
42      this.u = u;
43    }
44
45  public static uint hash_static (UInt that)
46    {
47      return that.u;
48    }
49
50  public static bool equals_static (UInt left, UInt right)
51    {
52      return left.u == right.u;
53    }
54}
55
56public class SmallSetTests : Folks.TestCase
57{
58  public SmallSetTests ()
59    {
60      base ("SmallSet");
61      this.add_test ("objects_hash", () => this.test_objects (true));
62      this.add_test ("objects", () => this.test_objects (false));
63      this.add_test ("iter_hash", () => this.test_iter (true));
64      this.add_test ("iter", () => this.test_iter (false));
65      this.add_test ("readonly_hash", () => this.test_readonly (true));
66      this.add_test ("readonly", () => this.test_readonly (false));
67      this.add_test ("direct_hash", () => this.test_direct (true));
68      this.add_test ("direct", () => this.test_direct (false));
69      this.add_test ("string_hash", () => this.test_strings (true));
70      this.add_test ("string", () => this.test_strings (false));
71      this.add_test ("cheating", this.test_cheating);
72    }
73
74  public void test_objects (bool use_hash)
75    {
76      var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
77      var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
78
79      Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
80
81      assert (objects != null);
82      assert (!objects.read_only);
83      assert (objects.size == 0);
84      assert (objects.is_empty);
85
86      objects.add (new UInt (10000));
87      objects.add (new UInt (1));
88      objects.add (new UInt (10));
89      objects.add (new UInt (100));
90      objects.add (new UInt (1000));
91
92      assert (objects != null);
93      assert (!objects.read_only);
94      assert (!objects.is_empty);
95      assert (objects.size == 5);
96
97      uint sum = 0;
98      bool res = objects.foreach ((obj) =>
99        {
100          sum += obj.u;
101          return true;
102        });
103
104      /* FIXME: this used to be wrong in HashSet (GNOME #696710).
105       * Do this unconditionally when we depend on a Gee with that fixed */
106      if (!use_hash)
107        assert (res == true);
108
109      assert (sum == 11111);
110
111      sum = 0;
112      res = objects.foreach ((obj) =>
113        {
114          sum += obj.u;
115          return false;
116        });
117      assert (res == false);
118      assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 ||
119        sum == 10000);
120
121      var ten = new UInt (10);
122
123      objects.foreach ((obj) =>
124        {
125          /* It is not the same object as the one in the set... */
126          assert (ten != obj);
127          return true;
128        });
129
130      /* ... but it is equal, and that'll do */
131      assert (objects.contains (ten));
132      /* Vala syntactic sugar */
133      assert (ten in objects);
134      /* It's a set. Attempts to add a duplicate are ignored. */
135      res = objects.add (ten);
136      assert (res == false);
137      assert (objects.size == 5);
138      objects.foreach ((obj) =>
139        {
140          assert (ten != obj);
141          return true;
142        });
143
144      objects.remove (ten);
145
146      /* Vala syntactic sugar: behind the scenes, this uses an iterator */
147      sum = 0;
148      foreach (var obj in objects)
149        sum += obj.u;
150      assert (sum == 11101);
151
152      /* Put it back. */
153      res = objects.add (ten);
154      assert (res == true);
155
156      sum = 0;
157      foreach (var obj in objects)
158        sum += obj.u;
159      assert (sum == 11111);
160
161      objects.clear ();
162      assert (objects.size == 0);
163      assert (objects.is_empty);
164      foreach (var obj in objects)
165        assert_not_reached ();
166    }
167
168  public void test_iter (bool use_hash)
169    {
170      var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
171      var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
172
173      Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
174
175      var iter = objects.iterator ();   /* points before 0 - invalid */
176      assert (!iter.valid);
177      assert (!iter.read_only);
178      assert (!iter.has_next ());
179      bool res = iter.next ();          /* fails, remains pointing before 0 */
180      assert (!res);
181      assert (!iter.valid);
182      assert (!iter.has_next ());
183
184      objects.add (new UInt (1));
185      objects.add (new UInt (10));
186      objects.add (new UInt (100));
187      objects.add (new UInt (1000));
188      objects.add (new UInt (10000));
189      assert (objects.size == 5);
190
191      iter = objects.iterator ();       /* points before 0 - invalid */
192
193      assert (!iter.valid);
194      assert (!iter.read_only);
195
196      assert (iter.has_next ());
197      res = iter.next ();               /* points to 0 */
198      assert (res);
199      assert (iter.valid);
200      assert (iter.has_next ());
201
202      iter.next ();                     /* points to 1 */
203      iter.next ();                     /* points to 2 */
204      iter.next ();                     /* points to 3 */
205      assert (iter.valid);
206      assert (iter.has_next ());
207      iter.next ();                     /* points to 4 */
208      assert (iter.valid);
209      assert (!iter.has_next ());
210      res = iter.next ();               /* fails, remains pointing to 4 */
211      assert (!res);
212      assert (iter.valid);              /* still valid */
213      assert (!iter.has_next ());
214
215      iter = objects.iterator ();
216      uint sum = 0;
217      /* If the iterator has not been started then iter.foreach starts from
218       * the beginning, skipping any prior items. */
219      iter.foreach ((obj) =>
220        {
221          sum += obj.u;
222          return true;
223        });
224      assert (sum == 11111);
225
226      sum = 0;
227      iter = objects.iterator ();
228      res = iter.foreach ((obj) =>
229        {
230          sum += obj.u;
231          return false;
232        });
233      assert (res == false);
234      assert (sum == 1 || sum == 10 || sum == 100 || sum == 1000 ||
235        sum == 10000);
236
237      sum = 0;
238      iter = objects.iterator ();
239      iter.next ();
240      sum += iter.get ().u;
241      iter.next ();
242      sum += iter.get ().u;
243      iter.next ();
244      /* If iter.valid then iter.foreach starts from the current item,
245       * skipping any prior items. We already added the ones we expect to
246       * have skipped. */
247      iter.foreach ((obj) =>
248        {
249          sum += obj.u;
250          return true;
251        });
252      assert (sum == 11111);
253
254      sum = 0;
255      iter = objects.iterator ();
256      iter.next ();
257      iter.next ();
258      iter.next ();
259      iter.next ();
260      iter.next ();
261      iter.foreach ((obj) =>
262        {
263          /* only run for the current == last item */
264          sum += 1;
265          return true;
266        });
267      assert (sum == 1);
268
269      /* Remove the first element. */
270      sum = 0;
271      iter = objects.iterator ();
272      iter.next ();
273      assert (iter.valid);
274      var removed = iter.get ();
275      iter.remove ();
276      sum += removed.u;
277      assert (!iter.valid);
278      while (iter.next ())
279        sum += iter.get ().u;
280      assert (sum == 11111);
281      /* Put it back. */
282      objects.add (removed);
283
284      /* Remove a middle element. */
285      sum = 0;
286      iter = objects.iterator ();
287      iter.next ();
288      sum += iter.get ().u;
289      iter.next ();
290      sum += iter.get ().u;
291      iter.next ();
292      assert (iter.valid);
293      removed = iter.get ();
294      iter.remove ();
295      sum += removed.u;
296      assert (!iter.valid);
297      while (iter.next ())
298        sum += iter.get ().u;
299      assert (sum == 11111);
300      /* Put it back. */
301      objects.add (removed);
302
303      /* Remove the last element. */
304      sum = 0;
305      iter = objects.iterator ();
306      iter.next ();
307      iter.next ();
308      iter.next ();
309      iter.next ();
310      iter.next ();
311      assert (iter.valid);
312      assert (!iter.has_next ());
313      removed = iter.get ();
314      iter.remove ();
315      sum += removed.u;
316      assert (!iter.valid);
317      assert (!iter.has_next ());
318      foreach (var obj in objects)
319        sum += obj.u;
320      assert (sum == 11111);
321      /* Put it back. */
322      objects.add (removed);
323    }
324
325  public void test_readonly (bool use_hash)
326    {
327      var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
328      var hash = new HashSet<UInt> (UInt.hash_static, UInt.equals_static);
329
330      Set<UInt> objects = (use_hash ? hash as Set<UInt> : small as Set<UInt>);
331
332      var ro = objects.read_only_view;
333      assert (ro != null);
334      assert (ro != objects);
335      assert (ro.read_only);
336      assert (ro.size == 0);
337
338      objects.add (new UInt (23));
339      assert (objects.size == 1);
340      assert (ro.size == 1);
341
342      uint u = 0;
343      ro.foreach ((obj) =>
344        {
345          assert (u == 0);
346          u = obj.u;
347          return true;
348        });
349      assert (u == 23);
350
351      var iter = ro.iterator ();
352      assert (iter.read_only);
353      u = 0;
354      iter.foreach ((obj) =>
355        {
356          assert (u == 0);
357          u = obj.u;
358          return true;
359        });
360      assert (u == 23);
361
362      /* These are implementation details */
363      if (!use_hash)
364        {
365          /* A new read-only view of an object is not the same thing yet */
366          var ro2 = objects.read_only_view;
367          assert (ro != ro2);
368
369          /* The read-only view of a read-only view is itself */
370          ro2 = ro.read_only_view;
371          assert (ro == ro2);
372        }
373    }
374
375  public void test_direct (bool use_hash)
376    {
377      var small = new SmallSet<DirectEq> ();
378      var hash = new HashSet<DirectEq> ();
379
380      Set<DirectEq> objects = (use_hash ?
381          hash as Set<DirectEq> : small as Set<DirectEq>);
382
383      objects.add (new DirectEq (23));
384      objects.add (new DirectEq (23));
385      var fortytwo = new DirectEq (42);
386      objects.add (fortytwo);
387      objects.add (fortytwo);
388      assert (objects.size == 3);
389
390      uint sum = 0;
391      foreach (var obj in objects)
392        sum += obj.u;
393      assert (sum == 23 + 23 + 42);
394    }
395
396  public void test_strings (bool use_hash)
397    {
398      var small = new SmallSet<string> ();
399      var hash = new HashSet<string> ((Gee.HashDataFunc) str_hash,
400          (Gee.EqualDataFunc) str_equal);
401
402      Set<string> strings = (use_hash ?
403          hash as Set<string> : small as Set<string>);
404
405      strings.add ("cheese");
406      strings.add ("cheese");
407      strings.add ("ham");
408      assert (strings.size == 2);
409    }
410
411  public void test_cheating ()
412    {
413      var small = new SmallSet<UInt> (UInt.hash_static, UInt.equals_static);
414      var set_ = (!) (small as Set<UInt>);
415
416      small.add (new UInt (1));
417      small.add (new UInt (10));
418      small.add (new UInt (100));
419      small.add (new UInt (1000));
420      small.add (new UInt (10000));
421
422      int i = 0;
423      set_.iterator ().foreach ((obj) =>
424        {
425          /* Fast-path: get() provides indexed access */
426          assert (small[i] == obj);
427          i++;
428          return true;
429        });
430      assert (i == 5);
431
432      /* Slow iteration: we don't know, syntactically, that set_ is a
433       * SmallSet, so we'll use the iterator */
434      uint sum = 0;
435      foreach (var obj in set_)
436        sum += obj.u;
437      assert (sum == 11111);
438
439      /* Fast iteration: we do know, syntactically, that small is a
440       * SmallSet, so we'll use indexed access */
441      sum = 0;
442      foreach (unowned UInt obj in small)
443        sum += obj.u;
444      assert (sum == 11111);
445    }
446}
447
448public int main (string[] args)
449{
450  Test.init (ref args);
451
452  var tests = new SmallSetTests ();
453  tests.register ();
454  Test.run ();
455  tests.final_tear_down ();
456
457  return 0;
458}
459