root/tests/test_wtree.cc

Revision 1324:2f96f62f6ce8, 26.7 kB (checked in by Daniel Burrows <dburrows@…>, 2 years ago)

Add support for checking whether one imm::map is a "superset" of another.
Line 
1// test_wtree.cc
2//
3//   Copyright (C) 2005, 2008 Daniel Burrows
4//
5//   This program is free software; you can redistribute it and/or
6//   modify it under the terms of the GNU General Public License as
7//   published by the Free Software Foundation; either version 2 of
8//   the License, or (at your option) any later version.
9//
10//   This program is distributed in the hope that it will be useful,
11//   but WITHOUT ANY WARRANTY; without even the implied warranty of
12//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13//   General Public License for more details.
14//
15//   You should have received a copy of the GNU General Public License
16//   along with this program; see the file COPYING.  If not, write to
17//   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18//   Boston, MA 02111-1307, USA.
19
20#include <cppunit/extensions/HelperMacros.h>
21
22#include <generic/util/immset.h>
23
24using imm::map;
25using imm::set;
26using imm::wtree_node;
27
28template<typename T>
29std::ostream &operator<<(std::ostream &out, const imm::set<T> &t)
30{
31  out << "{";
32  for(typename imm::set<T>::const_iterator i = t.begin();
33      i != t.end(); ++i)
34    {
35      if(i != t.begin())
36        out << ", ";
37      out << *i;
38    }
39  out << "}";
40
41  return out;
42}
43
44template<typename T1, typename T2>
45std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p)
46{
47  out << "(" << p.first << ", " << p.second << ")";
48  return out;
49}
50
51template<typename Key, typename Val>
52std::ostream &operator<<(std::ostream &out, const imm::map<Key, Val> &m)
53{
54  out << "{";
55  for(typename imm::map<Key, Val>::const_iterator i = m.begin();
56      i != m.end(); ++i)
57    {
58      if(i != m.begin())
59        out << ", ";
60      out << i->first << " |-> " << i->second;
61    }
62  out << "}";
63  return out;
64}
65
66#define CPPUNIT_ASSERT_LEAF(n) \
67  do { \
68    CPPUNIT_ASSERT(!n.getLeft().isValid()); \
69    CPPUNIT_ASSERT(!n.getRight().isValid()); \
70  } while(0)
71
72class WTreeTest : public CppUnit::TestFixture
73{
74  CPPUNIT_TEST_SUITE(WTreeTest);
75
76  CPPUNIT_TEST(testRotateLeft);
77  CPPUNIT_TEST(testRotateRight);
78  CPPUNIT_TEST(testDoubleRotateLeft);
79  CPPUNIT_TEST(testDoubleRotateRight);
80  CPPUNIT_TEST(testEquality);
81  CPPUNIT_TEST(testLessThan);
82  CPPUNIT_TEST(testIntersects);
83  CPPUNIT_TEST(testContains);
84  CPPUNIT_TEST(generalWTreeTest);
85  CPPUNIT_TEST(mapTest);
86  CPPUNIT_TEST(mapIntersectTest);
87
88  CPPUNIT_TEST_SUITE_END();
89public:
90  typedef wtree_node<int> int_node;
91
92  // Simple test of the rotate facilities.
93  void testRotateLeft()
94  {
95    int_node a(5,
96               int_node(3, int_node(2), int_node(4)),
97               int_node(7, int_node(6), int_node(8)));
98
99    int_node a_left = a.getLeft();
100    int_node a_right = a.getRight();
101
102    CPPUNIT_ASSERT(a_left.isValid());
103    CPPUNIT_ASSERT(a_right.isValid());
104
105    int_node a_left_left = a_left.getLeft();
106    int_node a_left_right = a_left.getRight();
107    int_node a_right_left = a_right.getLeft();
108    int_node a_right_right = a_right.getRight();
109
110    CPPUNIT_ASSERT(a_left_left.isValid());
111    CPPUNIT_ASSERT(a_left_right.isValid());
112    CPPUNIT_ASSERT(a_right_left.isValid());
113    CPPUNIT_ASSERT(a_right_right.isValid());
114
115    CPPUNIT_ASSERT_LEAF(a_left_left);
116    CPPUNIT_ASSERT_LEAF(a_left_right);
117    CPPUNIT_ASSERT_LEAF(a_right_left);
118    CPPUNIT_ASSERT_LEAF(a_right_right);
119
120
121    CPPUNIT_ASSERT_EQUAL(2, a_left_left.getVal());
122    CPPUNIT_ASSERT_EQUAL(3, a_left.getVal());
123    CPPUNIT_ASSERT_EQUAL(4, a_left_right.getVal());
124    CPPUNIT_ASSERT_EQUAL(5, a.getVal());
125    CPPUNIT_ASSERT_EQUAL(6, a_right_left.getVal());
126    CPPUNIT_ASSERT_EQUAL(7, a_right.getVal());
127    CPPUNIT_ASSERT_EQUAL(8, a_right_right.getVal());
128
129
130
131    int_node b = a.left_rotate_single();
132
133    CPPUNIT_ASSERT_EQUAL(a.size(), b.size());
134
135    CPPUNIT_ASSERT(b.isValid());
136
137    int_node b_left = b.getLeft();
138    int_node b_right = b.getRight();
139
140    CPPUNIT_ASSERT(b_left.isValid());
141    CPPUNIT_ASSERT(b_right.isValid());
142    CPPUNIT_ASSERT_LEAF(b_right);
143
144    int_node b_left_left = b_left.getLeft();
145    int_node b_left_right = b_left.getRight();
146
147    CPPUNIT_ASSERT(b_left_left.isValid());
148    CPPUNIT_ASSERT(b_left_right.isValid());
149    CPPUNIT_ASSERT_LEAF(b_left_right);
150
151    int_node b_left_left_left = b_left_left.getLeft();
152    int_node b_left_left_right = b_left_left.getRight();
153
154    CPPUNIT_ASSERT(b_left_left_left.isValid());
155    CPPUNIT_ASSERT(b_left_left_right.isValid());
156
157    CPPUNIT_ASSERT_LEAF(b_left_left_left);
158    CPPUNIT_ASSERT_LEAF(b_left_left_right);
159
160
161
162    CPPUNIT_ASSERT_EQUAL(2, b_left_left_left.getVal());
163    CPPUNIT_ASSERT_EQUAL(3, b_left_left.getVal());
164    CPPUNIT_ASSERT_EQUAL(4, b_left_left_right.getVal());
165    CPPUNIT_ASSERT_EQUAL(5, b_left.getVal());
166    CPPUNIT_ASSERT_EQUAL(6, b_left_right.getVal());
167    CPPUNIT_ASSERT_EQUAL(7, b.getVal());
168    CPPUNIT_ASSERT_EQUAL(8, b_right.getVal());
169  }
170
171  void testRotateRight()
172  {
173    int_node a(5,
174               int_node(3, int_node(2), int_node(4)),
175               int_node(7, int_node(6), int_node(8)));
176
177    int_node a_left = a.getLeft();
178    int_node a_right = a.getRight();
179
180    CPPUNIT_ASSERT(a_left.isValid());
181    CPPUNIT_ASSERT(a_right.isValid());
182
183    int_node a_left_left = a_left.getLeft();
184    int_node a_left_right = a_left.getRight();
185    int_node a_right_left = a_right.getLeft();
186    int_node a_right_right = a_right.getRight();
187
188    CPPUNIT_ASSERT(a_left_left.isValid());
189    CPPUNIT_ASSERT(a_left_right.isValid());
190    CPPUNIT_ASSERT(a_right_left.isValid());
191    CPPUNIT_ASSERT(a_right_right.isValid());
192
193    CPPUNIT_ASSERT_LEAF(a_left_left);
194    CPPUNIT_ASSERT_LEAF(a_left_right);
195    CPPUNIT_ASSERT_LEAF(a_right_left);
196    CPPUNIT_ASSERT_LEAF(a_right_right);
197
198
199    CPPUNIT_ASSERT_EQUAL(2, a_left_left.getVal());
200    CPPUNIT_ASSERT_EQUAL(3, a_left.getVal());
201    CPPUNIT_ASSERT_EQUAL(4, a_left_right.getVal());
202    CPPUNIT_ASSERT_EQUAL(5, a.getVal());
203    CPPUNIT_ASSERT_EQUAL(6, a_right_left.getVal());
204    CPPUNIT_ASSERT_EQUAL(7, a_right.getVal());
205    CPPUNIT_ASSERT_EQUAL(8, a_right_right.getVal());
206
207
208
209    int_node c = a.right_rotate_single();
210
211    CPPUNIT_ASSERT_EQUAL(a.size(), c.size());
212    CPPUNIT_ASSERT(c.isValid());
213
214    int_node c_left = c.getLeft(), c_right = c.getRight();
215
216    CPPUNIT_ASSERT(c_left.isValid());
217    CPPUNIT_ASSERT(c_right.isValid());
218    CPPUNIT_ASSERT_LEAF(c_left);
219
220    int_node c_right_left = c_right.getLeft(), c_right_right = c_right.getRight();
221
222    CPPUNIT_ASSERT(c_right_left.isValid());
223    CPPUNIT_ASSERT(c_right_right.isValid());
224    CPPUNIT_ASSERT_LEAF(c_right_left);
225
226    int_node c_right_right_left  = c_right_right.getLeft();
227    int_node c_right_right_right = c_right_right.getRight();
228
229    CPPUNIT_ASSERT(c_right_right_left.isValid());
230    CPPUNIT_ASSERT(c_right_right_right.isValid());
231    CPPUNIT_ASSERT_LEAF(c_right_right_left);
232    CPPUNIT_ASSERT_LEAF(c_right_right_right);
233
234    CPPUNIT_ASSERT_EQUAL(2, c_left.getVal());
235    CPPUNIT_ASSERT_EQUAL(3, c.getVal());
236    CPPUNIT_ASSERT_EQUAL(4, c_right_left.getVal());
237    CPPUNIT_ASSERT_EQUAL(5, c_right.getVal());
238    CPPUNIT_ASSERT_EQUAL(6, c_right_right_left.getVal());
239    CPPUNIT_ASSERT_EQUAL(7, c_right_right.getVal());
240    CPPUNIT_ASSERT_EQUAL(8, c_right_right_right.getVal());
241  }
242
243  void testDoubleRotateLeft()
244  {
245    int_node a = int_node(3, 2,
246                          int_node(7,
247                                   int_node(5, 4, 6),
248                                   8));
249
250    int_node a_left = a.getLeft(), a_right = a.getRight();
251
252    CPPUNIT_ASSERT(a_left.isValid());
253    CPPUNIT_ASSERT(a_right.isValid());
254    CPPUNIT_ASSERT_LEAF(a_left);
255
256    int_node a_right_left = a_right.getLeft(), a_right_right = a_right.getRight();
257
258    CPPUNIT_ASSERT(a_right_left.isValid());
259    CPPUNIT_ASSERT(a_right_right.isValid());
260    CPPUNIT_ASSERT_LEAF(a_right_right);
261
262    int_node a_right_left_left = a_right_left.getLeft();
263    int_node a_right_left_right = a_right_left.getRight();
264
265    CPPUNIT_ASSERT(a_right_left_left.isValid());
266    CPPUNIT_ASSERT(a_right_left_right.isValid());
267    CPPUNIT_ASSERT_LEAF(a_right_left_left);
268    CPPUNIT_ASSERT_LEAF(a_right_left_right);
269
270
271    CPPUNIT_ASSERT_EQUAL(2, a_left.getVal());
272    CPPUNIT_ASSERT_EQUAL(3, a.getVal());
273    CPPUNIT_ASSERT_EQUAL(4, a_right_left_left.getVal());
274    CPPUNIT_ASSERT_EQUAL(5, a_right_left.getVal());
275    CPPUNIT_ASSERT_EQUAL(6, a_right_left_right.getVal());
276    CPPUNIT_ASSERT_EQUAL(7, a_right.getVal());
277    CPPUNIT_ASSERT_EQUAL(8, a_right_right.getVal());
278
279
280    int_node b = a.left_rotate_double();
281
282    CPPUNIT_ASSERT(b.isValid());
283
284    int_node b_left = b.getLeft();
285    int_node b_right = b.getRight();
286
287    CPPUNIT_ASSERT(b_left.isValid());
288    CPPUNIT_ASSERT(b_right.isValid());
289
290    int_node b_left_left = b_left.getLeft(), b_left_right = b_left.getRight();
291
292    CPPUNIT_ASSERT(b_left_left.isValid());
293    CPPUNIT_ASSERT(b_left_right.isValid());
294
295    CPPUNIT_ASSERT_LEAF(b_left_left);
296    CPPUNIT_ASSERT_LEAF(b_left_right);
297
298    int_node b_right_left = b_right.getLeft(), b_right_right = b_right.getRight();
299
300    CPPUNIT_ASSERT(b_right_left.isValid());
301    CPPUNIT_ASSERT(b_right_right.isValid());
302
303    CPPUNIT_ASSERT_LEAF(b_right_left);
304    CPPUNIT_ASSERT_LEAF(b_right_right);
305
306
307    CPPUNIT_ASSERT_EQUAL(2, b_left_left.getVal());
308    CPPUNIT_ASSERT_EQUAL(3, b_left.getVal());
309    CPPUNIT_ASSERT_EQUAL(4, b_left_right.getVal());
310    CPPUNIT_ASSERT_EQUAL(5, b.getVal());
311    CPPUNIT_ASSERT_EQUAL(6, b_right_left.getVal());
312    CPPUNIT_ASSERT_EQUAL(7, b_right.getVal());
313    CPPUNIT_ASSERT_EQUAL(8, b_right_right.getVal());
314  }
315
316  void testDoubleRotateRight()
317  {
318    int_node a = int_node(7,
319                          int_node(3, 2, int_node(5, 4, 6)),
320                          8);
321
322    CPPUNIT_ASSERT(a.isValid());
323
324    int_node a_left = a.getLeft(), a_right = a.getRight();
325
326    CPPUNIT_ASSERT(a_left.isValid());
327    CPPUNIT_ASSERT(a_right.isValid());
328    CPPUNIT_ASSERT_LEAF(a_right);
329
330    int_node a_left_left = a_left.getLeft(), a_left_right = a_left.getRight();
331
332    CPPUNIT_ASSERT(a_left_left.isValid());
333    CPPUNIT_ASSERT(a_left_right.isValid());
334    CPPUNIT_ASSERT_LEAF(a_left_left);
335
336    int_node a_left_right_left = a_left_right.getLeft();
337    int_node a_left_right_right = a_left_right.getRight();
338
339    CPPUNIT_ASSERT(a_left_right_left.isValid());
340    CPPUNIT_ASSERT(a_left_right_right.isValid());
341    CPPUNIT_ASSERT_LEAF(a_left_right_left);
342    CPPUNIT_ASSERT_LEAF(a_left_right_right);
343
344    CPPUNIT_ASSERT_EQUAL(2, a_left_left.getVal());
345    CPPUNIT_ASSERT_EQUAL(3, a_left.getVal());
346    CPPUNIT_ASSERT_EQUAL(4, a_left_right_left.getVal());
347    CPPUNIT_ASSERT_EQUAL(5, a_left_right.getVal());
348    CPPUNIT_ASSERT_EQUAL(6, a_left_right_right.getVal());
349    CPPUNIT_ASSERT_EQUAL(7, a.getVal());
350    CPPUNIT_ASSERT_EQUAL(8, a_right.getVal());
351
352
353
354    int_node b = a.right_rotate_double();
355
356    CPPUNIT_ASSERT(b.isValid());
357
358    int_node b_left = b.getLeft(), b_right = b.getRight();
359    CPPUNIT_ASSERT(b_left.isValid());
360    CPPUNIT_ASSERT(b_right.isValid());
361
362    int_node b_left_left = b_left.getLeft(), b_left_right = b_left.getRight();
363    CPPUNIT_ASSERT(b_left_left.isValid());
364    CPPUNIT_ASSERT(b_left_right.isValid());
365    CPPUNIT_ASSERT_LEAF(b_left_left);
366    CPPUNIT_ASSERT_LEAF(b_left_right);
367
368    int_node b_right_left = b_right.getLeft(), b_right_right = b_right.getRight();
369    CPPUNIT_ASSERT(b_right_left.isValid());
370    CPPUNIT_ASSERT(b_right_right.isValid());
371    CPPUNIT_ASSERT_LEAF(b_right_left);
372    CPPUNIT_ASSERT_LEAF(b_right_right);
373
374
375    CPPUNIT_ASSERT_EQUAL(2, b_left_left.getVal());
376    CPPUNIT_ASSERT_EQUAL(3, b_left.getVal());
377    CPPUNIT_ASSERT_EQUAL(4, b_left_right.getVal());
378    CPPUNIT_ASSERT_EQUAL(5, b.getVal());
379    CPPUNIT_ASSERT_EQUAL(6, b_right_left.getVal());
380    CPPUNIT_ASSERT_EQUAL(7, b_right.getVal());
381    CPPUNIT_ASSERT_EQUAL(8, b_right_right.getVal());
382  }
383
384  static bool WTreeValuesMatch(const set<int> &t,
385                               const int *values, int count)
386  {
387    if(count == 0)
388      return t.empty();
389    else
390      {
391        set<int>::const_iterator i = t.begin();
392
393        while(i != t.end() && count > 0)
394          {
395            if(*values != *i)
396              return false;
397
398            ++i;
399            ++values;
400            --count;
401          }
402
403        return i == t.end() && count == 0;
404      }
405  }
406
407  static void dumpMatchFailure(std::ostream &out,
408                               const set<int> &t,
409                               const int *values,
410                               int count)
411  {
412    out << "Expected {";
413    while(count > 0)
414      {
415        out << *values;
416        if(count > 1)
417          out << ", ";
418
419        ++values;
420        --count;
421      }
422
423    out << "}; got {";
424
425    for(set<int>::const_iterator i = t.begin(); i != t.end(); ++i)
426      {
427        if(i != t.begin())
428          out << ", ";
429
430        out << *i;
431      }
432
433    out << "}";
434  }
435
436  /** A macro to assert that a given wtree has exactly the listed
437   *  contents.  A macro is used instead of a procedure so that line
438   *  numbers in test failures are useful.
439   */
440#define assertWTreeValues(t, values, count) \
441do  { \
442  if(!WTreeValuesMatch(t, values, count)) \
443    { \
444      std::ostringstream out; \
445      dumpMatchFailure(out, t, values, count); \
446      CPPUNIT_FAIL(out.str()); \
447    } } while(0)
448
449  void testEquality()
450  {
451    set<int> a;
452    set<int> b;
453
454    CPPUNIT_ASSERT(a == b);
455
456    a.insert(1);
457
458    CPPUNIT_ASSERT(!(a == b));
459
460    a.insert(6);
461    a.insert(4);
462    a.insert(5);
463    a.insert(2);
464    a.insert(3);
465
466    CPPUNIT_ASSERT(!(a == b));
467
468    b.insert(1);
469    b.insert(2);
470    b.insert(3);
471    b.insert(4);
472    b.insert(5);
473    b.insert(6);
474
475    int tmp[] = {1, 2, 3, 4, 5, 6};
476    assertWTreeValues(a, tmp, 6);
477    assertWTreeValues(b, tmp, 6);
478
479    CPPUNIT_ASSERT(a == b);
480
481    a.erase(4);
482
483    CPPUNIT_ASSERT(!(a == b));
484
485    a.insert(4);
486
487    CPPUNIT_ASSERT(a == b);
488
489    b.insert(10);
490
491    CPPUNIT_ASSERT(!(a == b));
492
493    b.erase(5);
494
495    CPPUNIT_ASSERT(!(a == b));
496
497    a.erase(5);
498
499    CPPUNIT_ASSERT(!(a == b));
500
501    a.insert(10);
502
503    CPPUNIT_ASSERT(a == b);
504  }
505
506  void testLessThan()
507  {
508    set<int> a;
509    set<int> b;
510
511    a.insert(1);
512    a.insert(2);
513    a.insert(3);
514    a.insert(4);
515    a.insert(5);
516    a.insert(6);
517
518    b.insert(2);
519    b.insert(3);
520    b.insert(4);
521    b.insert(5);
522    b.insert(6);
523
524    CPPUNIT_ASSERT(a < b);
525    CPPUNIT_ASSERT(!(b < a));
526
527    b.insert(1);
528
529    CPPUNIT_ASSERT(!(a < b));
530    CPPUNIT_ASSERT(!(b < a));
531
532    a.erase(1);
533
534    CPPUNIT_ASSERT(!(a < b));
535    CPPUNIT_ASSERT(b < a);
536  }
537
538#define assertNoIntersect(a, b) \
539  do { \
540    if(a.intersects(b)) \
541      { \
542        std::ostringstream out; \
543        out << "Sets " << a << " and " << b << " unexpectedly intersect:"\
544            << std::endl; \
545        a.dump(out); \
546        b.dump(out); \
547        CPPUNIT_FAIL(out.str()); \
548      } \
549     } while(0)
550
551#define assertIntersect(a, b) \
552  do { \
553    if(!a.intersects(b)) \
554      { \
555        std::ostringstream out; \
556        out << "Sets " << a << " and " << b << " unexpectedly fail to intersect:"\
557            << std::endl; \
558        a.dump(out); \
559        b.dump(out); \
560        CPPUNIT_FAIL(out.str()); \
561      } \
562     } while(0)
563
564  void testIntersects()
565  {
566    set<int> a;
567    set<int> b;
568
569    a.insert(1);
570    assertNoIntersect(a, b);
571    assertNoIntersect(b, a);
572    a.insert(3);
573    assertNoIntersect(a, b);
574    assertNoIntersect(b, a);
575    a.insert(5);
576    assertNoIntersect(a, b);
577    assertNoIntersect(b, a);
578    a.insert(7);
579    assertNoIntersect(a, b);
580    assertNoIntersect(b, a);
581
582    b.insert(0);
583    assertNoIntersect(a, b);
584    assertNoIntersect(b, a);
585    b.insert(2);
586    assertNoIntersect(a, b);
587    assertNoIntersect(b, a);
588    b.insert(4);
589    assertNoIntersect(a, b);
590    assertNoIntersect(b, a);
591    b.insert(6);
592    assertNoIntersect(a, b);
593    assertNoIntersect(b, a);
594    b.insert(8);
595    assertNoIntersect(a, b);
596    assertNoIntersect(b, a);
597    b.insert(5);
598    assertIntersect(a, b);
599    assertIntersect(b, a);
600    b.erase(6);
601    assertIntersect(a, b);
602    assertIntersect(b, a);
603    a.erase(1);
604    assertIntersect(a, b);
605    assertIntersect(b, a);
606    a.erase(3);
607    assertIntersect(a, b);
608    assertIntersect(b, a);
609    b.erase(8);
610    assertIntersect(a, b);
611    assertIntersect(b, a);
612    b.erase(0);
613    assertIntersect(a, b);
614    assertIntersect(b, a);
615    a.erase(5);
616    assertNoIntersect(a, b);
617    assertNoIntersect(b, a);
618    b.erase(4);
619    assertNoIntersect(a, b);
620    assertNoIntersect(b, a);
621    b.erase(5);
622    assertNoIntersect(a, b);
623    assertNoIntersect(b, a);
624    b.erase(2);
625    assertNoIntersect(a, b);
626    assertNoIntersect(b, a);
627  }
628
629#define assertNotContains(a, b) \
630  do { \
631    if(a.contains(b)) \
632      { \
633        std::ostringstream out; \
634        out << a << " unexpectedly contains " << b << ":"\
635            << std::endl; \
636        a.dump(out); \
637        b.dump(out); \
638        CPPUNIT_FAIL(out.str()); \
639      } \
640     } while(0)
641
642#define assertContains(a, b) \
643  do { \
644    if(!a.contains(b)) \
645      { \
646        std::ostringstream out; \
647        out << a << " unexpectedly does not contain " << b << ":"\
648            << std::endl; \
649        a.dump(out); \
650        b.dump(out); \
651        CPPUNIT_FAIL(out.str()); \
652      } \
653     } while(0)
654
655  void testContains()
656  {
657    set<int> s1;
658    set<int> s2;
659    set<int> s3;
660
661    s1.insert(5);
662
663    s2.insert(6);
664    s2.insert(8);
665
666    s3.insert(10);
667    s3.insert(5);
668
669    set<int> t;
670
671    assertContains(s1, t);
672    assertContains(s2, t);
673    assertContains(s3, t);
674    assertNotContains(t, s1);
675    assertNotContains(t, s2);
676    assertNotContains(t, s3);
677
678
679
680    t.insert(5);
681
682    assertContains(s1, t);
683    assertNotContains(s2, t);
684    assertContains(s3, t);
685    assertContains(t, s1);
686    assertNotContains(t, s2);
687    assertNotContains(t, s3);
688
689
690    t.insert(10);
691
692    assertNotContains(s1, t);
693    assertNotContains(s2, t);
694    assertContains(s3, t);
695    assertContains(t, s1);
696    assertNotContains(t, s2);
697    assertContains(t, s3);
698
699    t.insert(6);
700
701
702    assertNotContains(s1, t);
703    assertNotContains(s2, t);
704    assertNotContains(s3, t);
705    assertContains(t, s1);
706    assertNotContains(t, s2);
707    assertContains(t, s3);
708
709    t.erase(5);
710
711    assertNotContains(s1, t);
712    assertNotContains(s2, t);
713    assertNotContains(s3, t);
714    assertNotContains(t, s1);
715    assertNotContains(t, s2);
716    assertNotContains(t, s3);
717
718
719    t.insert(9);
720
721
722    assertNotContains(s1, t);
723    assertNotContains(s2, t);
724    assertNotContains(s3, t);
725    assertNotContains(t, s1);
726    assertNotContains(t, s2);
727    assertNotContains(t, s3);
728
729
730    t.insert(8);
731
732    assertNotContains(s1, t);
733    assertNotContains(s2, t);
734    assertNotContains(s3, t);
735    assertNotContains(t, s1);
736    assertContains(t, s2);
737    assertNotContains(t, s3);
738
739
740    t.erase(9);
741
742
743    assertNotContains(s1, t);
744    assertNotContains(s2, t);
745    assertNotContains(s3, t);
746    assertNotContains(t, s1);
747    assertContains(t, s2);
748    assertNotContains(t, s3);
749  }
750
751#define assertNotSupermap(a, b) \
752  do { \
753    if(a.is_supermap_of(b)) \
754      { \
755        std::ostringstream out; \
756        out << a << " unexpectedly is a supermap of " << b << ":"\
757            << std::endl; \
758        a.dump(out); \
759        b.dump(out); \
760        CPPUNIT_FAIL(out.str()); \
761      } \
762     } while(0)
763
764#define assertSupermap(a, b) \
765  do { \
766    if(!a.is_supermap_of(b)) \
767      { \
768        std::ostringstream out; \
769        out << a << " unexpectedly is not a supermap of " << b << ":"\
770            << std::endl; \
771        a.dump(out); \
772        b.dump(out); \
773        CPPUNIT_FAIL(out.str()); \
774      } \
775     } while(0)
776
777  void testSupermap()
778  {
779    map<int, int> s1;
780    map<int, int> s2;
781    map<int, int> s3;
782
783    s1.put(5, 6);
784
785    s2.put(6, 2);
786    s2.put(8, 10);
787
788    s3.put(10, 3);
789    s3.put(5, 7);
790
791    map<int, int> t;
792
793    assertSupermap(s1, t);
794    assertSupermap(s2, t);
795    assertSupermap(s3, t);
796    assertNotSupermap(t, s1);
797    assertNotSupermap(t, s2);
798    assertNotSupermap(t, s3);
799
800
801
802    t.put(5, 2);
803
804    assertNotSupermap(s1, t);
805    assertNotSupermap(s2, t);
806    assertNotSupermap(s3, t);
807    assertNotSupermap(t, s1);
808    assertNotSupermap(t, s2);
809    assertNotSupermap(t, s3);
810
811
812    t.put(5, 6);
813
814    assertSupermap(s1, t);
815    assertNotSupermap(s2, t);
816    assertNotSupermap(s3, t);
817    assertSupermap(t, s1);
818    assertNotSupermap(t, s2);
819    assertNotSupermap(t, s3);
820
821
822    t.put(5, 7);
823
824    assertNotSupermap(s1, t);
825    assertNotSupermap(s2, t);
826    assertSupermap(s3, t);
827    assertNotSupermap(t, s1);
828    assertNotSupermap(t, s2);
829    assertNotSupermap(t, s3);
830
831
832    t.put(10, 3);
833    t.put(5, 6);
834
835    assertNotSupermap(s1, t);
836    assertNotSupermap(s2, t);
837    assertNotSupermap(s3, t);
838    assertNotSupermap(t, s1);
839    assertNotSupermap(t, s2);
840    assertNotSupermap(t, s3);
841
842    t.put(5, 7);
843    t.put(10, 3);
844
845    assertNotSupermap(s1, t);
846    assertNotSupermap(s2, t);
847    assertSupermap(s3, t);
848    assertSupermap(t, s1);
849    assertNotSupermap(t, s2);
850    assertSupermap(t, s3);
851
852    t.put(6, 2);
853
854
855    assertNotSupermap(s1, t);
856    assertNotSupermap(s2, t);
857    assertNotSupermap(s3, t);
858    assertSupermap(t, s1);
859    assertNotSupermap(t, s2);
860    assertSupermap(t, s3);
861
862    t.erase(5);
863
864    assertNotSupermap(s1, t);
865    assertNotSupermap(s2, t);
866    assertNotSupermap(s3, t);
867    assertNotSupermap(t, s1);
868    assertNotSupermap(t, s2);
869    assertNotSupermap(t, s3);
870
871
872    t.put(9, 100);
873
874
875    assertNotSupermap(s1, t);
876    assertNotSupermap(s2, t);
877    assertNotSupermap(s3, t);
878    assertNotSupermap(t, s1);
879    assertNotSupermap(t, s2);
880    assertNotSupermap(t, s3);
881
882
883    t.put(8, 10);
884
885    assertNotSupermap(s1, t);
886    assertNotSupermap(s2, t);
887    assertNotSupermap(s3, t);
888    assertNotSupermap(t, s1);
889    assertSupermap(t, s2);
890    assertNotSupermap(t, s3);
891
892
893    t.erase(9);
894
895
896    assertNotSupermap(s1, t);
897    assertNotSupermap(s2, t);
898    assertNotSupermap(s3, t);
899    assertNotSupermap(t, s1);
900    assertSupermap(t, s2);
901    assertNotSupermap(t, s3);
902  }
903
904  void generalWTreeTest()
905  {
906    set<int> t;
907
908    assertWTreeValues(t, NULL, 0);
909
910    {
911      t.insert(5);
912      int vals[] = {5};
913      assertWTreeValues(t, vals, 1);
914    }
915
916    CPPUNIT_ASSERT(!t.find_node(3).isValid());
917
918    {
919      wtree_node<int> found = t.find_node(5);
920      CPPUNIT_ASSERT(found.isValid());
921      CPPUNIT_ASSERT_EQUAL(5, found.getVal());
922    }
923
924
925    {
926      t.insert(3);
927      int vals[] = {3, 5};
928      assertWTreeValues(t, vals, 2);
929    }
930
931    {
932      t.insert(8);
933      int vals[] = {3, 5, 8};
934      assertWTreeValues(t, vals, 3);
935    }
936
937
938    {
939      t.insert(7);
940      int vals[] = {3, 5, 7, 8};
941      assertWTreeValues(t, vals, 4);
942    }
943
944
945    CPPUNIT_ASSERT(!t.find_node(9).isValid());
946
947    {
948      wtree_node<int> found = t.find_node(5);
949
950      CPPUNIT_ASSERT(found.isValid());
951      CPPUNIT_ASSERT_EQUAL(5, found.getVal());
952    }
953
954    {
955      t.insert(4);
956      int vals[] = {3, 4, 5, 7, 8};
957      assertWTreeValues(t, vals, 5);
958    }
959
960
961    {
962      t.insert(3);
963      int vals[] = {3, 4, 5, 7, 8};
964      assertWTreeValues(t, vals, 5);
965    }
966
967
968    {
969      t.insertUpdate(3);
970      int vals[] = {3, 4, 5, 7, 8};
971      assertWTreeValues(t, vals, 5);
972    }
973
974
975    {
976      t.insertUpdate(6);
977      int vals[] = {3, 4, 5, 6, 7, 8};
978      assertWTreeValues(t, vals, 6);
979    }
980
981
982    {
983      t.erase(5);
984      int vals[] = {3, 4, 6, 7, 8};
985      assertWTreeValues(t, vals, 5);
986    }
987
988
989    {
990      t.erase(7);
991      int vals[] = {3, 4, 6, 8};
992      assertWTreeValues(t, vals, 4);
993    }
994
995    {
996      t.erase(7);
997      int vals[] = {3, 4, 6, 8};
998      assertWTreeValues(t, vals, 4);
999    }
1000
1001    {
1002      t.erase(10);
1003      int vals[] = {3, 4, 6, 8};
1004      assertWTreeValues(t, vals, 4);
1005    }
1006
1007
1008    {
1009      t.erase(-1);
1010      int vals[] = {3, 4, 6, 8};
1011      assertWTreeValues(t, vals, 4);
1012    }
1013
1014
1015    {
1016      t.erase(4);
1017      int vals[] = {3, 6, 8};
1018      assertWTreeValues(t, vals, 3);
1019    }
1020
1021
1022    {
1023      t.erase(8);
1024      int vals[] = {3, 6};
1025      assertWTreeValues(t, vals, 2);
1026    }
1027
1028
1029
1030    {
1031      t.erase(3);
1032      int vals[] = {6};
1033      assertWTreeValues(t, vals, 1);
1034    }
1035
1036
1037
1038    {
1039      t.erase(6);
1040      int *vals = NULL;
1041      assertWTreeValues(t, vals, 0);
1042    }
1043
1044    // Test for a specific error that occurs when deleting a node for
1045    // which the smallest element of the right child has its own right
1046    // child.
1047    //
1048    // \todo this is tuned for a specific balancing implementation and
1049    // might not detect an equivalent error in another implementation.
1050    {
1051      t = imm::set<int>();
1052      t.insert(50);
1053      t.insert(75);
1054      t.insert(25);
1055      t.insert(62);
1056      t.insert(87);
1057      t.insert(68);
1058      t.erase(50);
1059
1060      int vals[] = {25, 62, 68, 75, 87};
1061      assertWTreeValues(t, vals, 5);
1062    }
1063  }
1064
1065  void mapTest()
1066  {
1067    map<int, int> m;
1068
1069    CPPUNIT_ASSERT(m.empty());
1070    CPPUNIT_ASSERT_EQUAL(0U, m.size());
1071
1072    m.put(5, 2);
1073    CPPUNIT_ASSERT(!m.empty());
1074    CPPUNIT_ASSERT_EQUAL(1U, m.size());
1075
1076    m.put(3, 10);
1077    CPPUNIT_ASSERT(!m.empty());
1078    CPPUNIT_ASSERT_EQUAL(2U, m.size());
1079
1080    m.put(4, 10);
1081    CPPUNIT_ASSERT(!m.empty());
1082    CPPUNIT_ASSERT_EQUAL(3U, m.size());
1083
1084    m.put(1, 3);
1085    CPPUNIT_ASSERT(!m.empty());
1086    CPPUNIT_ASSERT_EQUAL(4U, m.size());
1087
1088    m.put(2, 8);
1089    CPPUNIT_ASSERT(!m.empty());
1090    CPPUNIT_ASSERT_EQUAL(5U, m.size());
1091
1092    m.put(6, 11);
1093    CPPUNIT_ASSERT(!m.empty());
1094    CPPUNIT_ASSERT_EQUAL(6U, m.size());
1095
1096    m.put(1, 0);
1097    CPPUNIT_ASSERT(!m.empty());
1098    CPPUNIT_ASSERT_EQUAL(6U, m.size());
1099
1100
1101    CPPUNIT_ASSERT_EQUAL(-1, m.get(0, -1));
1102    CPPUNIT_ASSERT_EQUAL(0, m.get(1, -1));
1103    CPPUNIT_ASSERT_EQUAL(8, m.get(2, -1));
1104    CPPUNIT_ASSERT_EQUAL(10, m.get(3, -1));
1105    CPPUNIT_ASSERT_EQUAL(10, m.get(4, -1));
1106    CPPUNIT_ASSERT_EQUAL(2, m.get(5, -1));
1107    CPPUNIT_ASSERT_EQUAL(11, m.get(6, -1));
1108
1109    m.put(6, 12);
1110    CPPUNIT_ASSERT_EQUAL(12, m.get(6, -1));
1111  }
1112
1113  template<typename T1, typename T2>
1114  struct second_less
1115  {
1116    typedef std::pair<T1, T2> X;
1117
1118    bool operator()(const X &x1, const X &x2) const
1119    {
1120      return x1.second < x2.second;
1121    }
1122  };
1123
1124  template<typename T1, typename T2>
1125  struct second_greater
1126  {
1127    typedef std::pair<T1, T2> X;
1128
1129    bool operator()(const X &x1, const X &x2) const
1130    {
1131      return x1.second > x2.second;
1132    }
1133  };
1134
1135  typedef second_less<int, int> int_mapping_less;
1136  typedef second_greater<int, int> int_mapping_greater;
1137
1138  void mapIntersectTest()
1139  {
1140    imm::map<int, int> m1, m2;
1141
1142    m1.put(3, 5);
1143    m1.put(6, 1);
1144    m1.put(2, 8);
1145    m1.put(10, 7);
1146    m1.put(0, 3);
1147    m1.put(30, 5);
1148    m1.put(20, 7);
1149
1150    m2.put(1, 4);
1151    m2.put(7, 9);
1152    m2.put(-10, 5);
1153    m2.put(-5, 1);
1154    m2.put(-7, 50);
1155    m2.put(-100, -8);
1156
1157    CPPUNIT_ASSERT(!m1.shares_value(m2));
1158    CPPUNIT_ASSERT(!m1.domain_intersects(m2));
1159
1160    m2.put(6, 1);
1161    CPPUNIT_ASSERT(m1.shares_value(m2));
1162    CPPUNIT_ASSERT(m1.domain_intersects(m2));
1163
1164    m2.put(6, 5);
1165
1166
1167    CPPUNIT_ASSERT(!m1.shares_value(m2));
1168    CPPUNIT_ASSERT(m1.domain_intersects(m2));
1169    CPPUNIT_ASSERT(m1.has_related_mapping(m2, std::less<std::pair<int, int> >()));
1170    CPPUNIT_ASSERT(m2.has_related_mapping(m1, std::greater<std::pair<int, int> >()));
1171
1172    m2.put(6, 0);
1173
1174    CPPUNIT_ASSERT(!m1.shares_value(m2));
1175    CPPUNIT_ASSERT(m1.domain_intersects(m2));
1176    CPPUNIT_ASSERT(!m1.has_related_mapping(m2, std::less<std::pair<int, int> >()));
1177    CPPUNIT_ASSERT(m1.has_related_mapping(m2, std::greater<std::pair<int, int> >()));
1178    CPPUNIT_ASSERT(!m2.has_related_mapping(m1, std::greater<std::pair<int, int> >()));
1179    CPPUNIT_ASSERT(m2.has_related_mapping(m1, std::less<std::pair<int, int> >()));
1180  }
1181};
1182
1183CPPUNIT_TEST_SUITE_REGISTRATION(WTreeTest);
Note: See TracBrowser for help on using the browser.