Mercurial > dedupe

annotate TestRBTree.cpp @ 18:fcb7a71a22c1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make it possible to turn off asserting for the RBTree template header.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 29 Aug 2012 20:04:05 +0200
parents 06166d6c083b
children 247adcbbaf8b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 #include "RBTree.hpp"
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2 #include "TestFramework.hpp"
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 #include <QtCore/QString>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 BOOST_AUTO_TEST_CASE( TestInsertLeftHeavy )
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8 RBTree<QString> map;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 QString k1 = "9";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 QString k2 = "8";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 QString k3 = "7";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 QString k4 = "6";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 BOOST_REQUIRE(!map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 BOOST_REQUIRE_EQUAL(map.size(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 map.insert(k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 BOOST_REQUIRE_EQUAL(map.size(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 map.insert(k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 BOOST_REQUIRE_EQUAL(map.size(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 map.insert(k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 BOOST_WARN_EQUAL(map.total_depth(), 5u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 BOOST_REQUIRE_EQUAL(map.size(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52 BOOST_REQUIRE(map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 BOOST_REQUIRE(!map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 map.insert(k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 BOOST_WARN_EQUAL(map.total_depth(), 8u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 BOOST_REQUIRE_EQUAL(map.size(), 4u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
60 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 BOOST_REQUIRE(map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 BOOST_AUTO_TEST_CASE( TestInsertRightHeavy )
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 RBTree<QString> map;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 QString k1 = "5";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 QString k2 = "6";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 QString k3 = "7";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 QString k4 = "8";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 BOOST_REQUIRE(!map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 BOOST_REQUIRE_EQUAL(map.size(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 map.insert(k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 BOOST_REQUIRE_EQUAL(map.size(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 map.insert(k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 BOOST_REQUIRE_EQUAL(map.size(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
102 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
103 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
104
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
105 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
106 map.insert(k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
107 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
108 BOOST_WARN_EQUAL(map.total_depth(), 5u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
109 BOOST_REQUIRE_EQUAL(map.size(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
110 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
111 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
112 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
113 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
114 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
115 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
116 BOOST_REQUIRE(map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
117 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
118
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
119 BOOST_REQUIRE(!map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
120 map.insert(k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
121 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
122 BOOST_WARN_EQUAL(map.total_depth(), 8u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
123 BOOST_REQUIRE_EQUAL(map.size(), 4u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
124 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
125 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
126 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
127 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
128 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
129 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
130 BOOST_REQUIRE(map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
131 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
132 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
133
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
134 BOOST_AUTO_TEST_CASE( TestInsertBalanced )
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
135 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
136 RBTree<QString> map;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
137
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
138 QString k1 = "8";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
139 QString k2 = "4";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
140 QString k3 = "12";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
141 QString k4 = "2";
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
142
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
143 BOOST_REQUIRE(!map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
144 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
145 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
146 BOOST_REQUIRE_EQUAL(map.size(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
147 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
148 map.insert(k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
149 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
150 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
151 BOOST_REQUIRE_EQUAL(map.size(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
152 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
153 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
154 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
155 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
156
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
157 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
158 map.insert(k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
159 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
160 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
161 BOOST_REQUIRE_EQUAL(map.size(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
162 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
163 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
164 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
165 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
166 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
167 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
168
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
169 BOOST_REQUIRE(!map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
170 map.insert(k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
171 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
172 BOOST_WARN_EQUAL(map.total_depth(), 5u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
173 BOOST_REQUIRE_EQUAL(map.size(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
174 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
175 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
176 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
177 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
178 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
179 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
180 BOOST_REQUIRE(map.find(k3));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
181 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
182
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
183 BOOST_REQUIRE(!map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
184 map.insert(k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
185 BOOST_WARN_EQUAL(map.depth(), 2u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
186 BOOST_WARN_EQUAL(map.total_depth(), 8u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
187 BOOST_REQUIRE_EQUAL(map.size(), 4u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
188 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
189 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
190 BOOST_REQUIRE(map.find(k1));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
191 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
192 BOOST_REQUIRE(map.find(k2));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
193 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
194 BOOST_REQUIRE(map.find(k4));
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
195 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
196 }