1 /*
2 * unittests/core/Map.cc
3 * Apto
4 *
5 * Created by David on 2/14/11.
6 * Copyright 2011 David Michael Bryson. All rights reserved.
7 * http://programerror.com/software/apto
8 *
9 * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the
10 * following conditions are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the
13 * following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the
15 * following disclaimer in the documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of David Michael Bryson, nor the names of contributors may be used to endorse or promote
17 * products derived from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY DAVID MICHAEL BRYSON AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
21 * DISCLAIMED. IN NO EVENT SHALL DAVID MICHAEL BRYSON OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
25 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 *
27 * Authors: David M. Bryson <david@programerror.com>
28 *
29 */
30
31 #include "apto/core/Array.h"
32 #include "apto/core/ArrayUtils.h"
33 #include "apto/core/Map.h"
34
35 #include "gtest/gtest.h"
36
37
38 // Map<int, int, HashBTree>
39 // --------------------------------------------------------------------------------------------------------------
40
TEST(CoreHashBTreeMap,Construction)41 TEST(CoreHashBTreeMap, Construction) {
42 Apto::Map<int, int, Apto::DefaultHashBTree> map;
43 EXPECT_EQ(0, map.GetSize());
44 }
45
46
TEST(CoreHashBTreeMap,Indexing)47 TEST(CoreHashBTreeMap, Indexing) {
48 Apto::Map<int, int, Apto::DefaultHashBTree> map;
49 map[1] = 1;
50 map.Set(2, 2);
51 map.Get(3) = 3;
52
53 int val;
54
55 EXPECT_EQ(3, map.GetSize());
56 EXPECT_EQ(1, map[1]);
57 EXPECT_EQ(1, map.Get(1));
58 EXPECT_EQ(1, map.GetWithDefault(1, -1));
59 val = -1;
60 EXPECT_TRUE(map.Get(1, val));
61 EXPECT_EQ(1, val);
62
63 EXPECT_EQ(2, map[2]);
64 EXPECT_EQ(2, map.Get(2));
65 EXPECT_EQ(2, map.GetWithDefault(2, -1));
66 val = -1;
67 EXPECT_TRUE(map.Get(2, val));
68 EXPECT_EQ(2, val);
69
70 EXPECT_EQ(3, map[3]);
71 EXPECT_EQ(3, map.Get(3));
72 EXPECT_EQ(3, map.GetWithDefault(3, -1));
73 val = -1;
74 EXPECT_TRUE(map.Get(3, val));
75 EXPECT_EQ(3, val);
76
77 EXPECT_EQ(4, map.GetWithDefault(4, 4));
78 EXPECT_EQ(4, map.GetSize());
79 }
80
81
TEST(CoreHashBTreeMap,Assignment)82 TEST(CoreHashBTreeMap, Assignment) {
83 Apto::Map<int, int, Apto::DefaultHashBTree> map1;
84 for (int i = 0; i < 4; i++) map1[i] = i;
85 for (int i = 0; i < 4; i++) EXPECT_EQ(i, map1[i]);
86
87 Apto::Map<int, int, Apto::DefaultHashBTree> map2;
88 for (int i = 0; i < 4; i++) map2[i] = i + 2;
89 for (int i = 0; i < 4; i++) EXPECT_EQ(i + 2, map2[i]);
90
91 map2 = map1;
92 for (int i = 0; i < 4; i++) EXPECT_EQ(i, map2[i]);
93
94 Apto::Map<int, int, Apto::DefaultHashBTree> map3(map1);
95 for (int i = 0; i < 4; i++) EXPECT_EQ(i, map3[i]);
96 }
97
98 template <class K, class V> class HashBTreeSize1 : public Apto::HashBTree<K, V, 1> { ; };
99
TEST(CoreHashBTreeMap,Removal)100 TEST(CoreHashBTreeMap, Removal) {
101 // Set HashFactor to 1 to really test the tree removal
102 Apto::Map<int, int, HashBTreeSize1> map;
103 EXPECT_FALSE(map.Remove(8));
104 EXPECT_EQ(0, map.GetSize());
105
106 // Build fully balanced tree
107 map[4] = 4;
108 map[2] = 2;
109 map[6] = 6;
110 map[1] = 1;
111 map[3] = 3;
112 map[5] = 5;
113 map[7] = 7;
114
115 // Check full tree
116 EXPECT_EQ(7, map.GetSize());
117 for (int i = 1; i <= 7; i++) EXPECT_EQ(i, map[i]);
118
119 // Remove left leaf node
120 EXPECT_TRUE(map.Remove(1));
121 EXPECT_EQ(6, map.GetSize());
122 for (int i = 2; i <= 7; i++) EXPECT_EQ(i, map[i]);
123
124 // Remove right leaf node
125 EXPECT_TRUE(map.Remove(7));
126 EXPECT_EQ(5, map.GetSize());
127 for (int i = 2; i <= 6; i++) EXPECT_EQ(i, map[i]);
128
129 // Remove internal node with right only subtree
130 EXPECT_TRUE(map.Remove(2));
131 EXPECT_EQ(4, map.GetSize());
132 for (int i = 3; i <= 6; i++) EXPECT_EQ(i, map[i]);
133
134 // Remove internal node with left only subtree
135 EXPECT_TRUE(map.Remove(6));
136 EXPECT_EQ(3, map.GetSize());
137 for (int i = 3; i <= 5; i++) EXPECT_EQ(i, map[i]);
138
139 // Remove internal node with two subtrees (also the root node)
140 EXPECT_TRUE(map.Remove(4));
141 EXPECT_EQ(2, map.GetSize());
142 EXPECT_EQ(3, map[3]);
143 EXPECT_EQ(5, map[5]);
144
145 // Make sure that remove works properly when node does not exist
146 EXPECT_FALSE(map.Remove(8));
147 EXPECT_EQ(2, map.GetSize());
148
149 // Make sure we can still add into the map
150 map[4] = 4;
151 EXPECT_EQ(3, map.GetSize());
152 }
153
154
TEST(CoreHashBTreeMap,Comparison)155 TEST(CoreHashBTreeMap, Comparison) {
156 Apto::Map<int, int, Apto::DefaultHashBTree> map1;
157 for (int i = 0; i < 4; i++) map1[i] = i;
158 EXPECT_TRUE(map1 == map1);
159 EXPECT_FALSE(map1 != map1);
160
161 Apto::Map<int, int, Apto::DefaultHashBTree> map2;
162 for (int i = 0; i < 4; i++) map2[i] = i + 2;
163 EXPECT_TRUE(map2 == map2);
164 EXPECT_FALSE(map2 != map2);
165
166 EXPECT_FALSE(map1 == map2);
167 EXPECT_TRUE(map1 != map2);
168 EXPECT_FALSE(map2 == map1);
169 EXPECT_TRUE(map2 != map1);
170
171 map2 = map1;
172 EXPECT_FALSE(map1 != map2);
173 EXPECT_TRUE(map1 == map2);
174 EXPECT_FALSE(map2 != map1);
175 EXPECT_TRUE(map2 == map1);
176
177 Apto::Map<int, int, Apto::DefaultHashBTree> map3(map1);
178 EXPECT_FALSE(map1 != map3);
179 EXPECT_TRUE(map1 == map3);
180 EXPECT_FALSE(map3 != map1);
181 EXPECT_TRUE(map3 == map1);
182
183 map3[5] = 5;
184 EXPECT_FALSE(map1 == map3);
185 EXPECT_TRUE(map1 != map3);
186 EXPECT_FALSE(map3 == map1);
187 EXPECT_TRUE(map3 != map1);
188 }
189
190
TEST(CoreHashBTreeMap,Iteration)191 TEST(CoreHashBTreeMap, Iteration) {
192 Apto::Map<int, int, Apto::DefaultHashBTree> map1;
193 for (int i = 0; i < 4; i++) map1[i] = i;
194
195 Apto::Array<int> key_array(map1.GetSize());
196 Apto::Array<int> value_array(map1.GetSize());
197 Apto::Map<int, int, Apto::DefaultHashBTree>::Iterator it = map1.Begin();
198 for (int i = 0; it.Next(); i++) {
199 key_array[i] = it.Get()->Value1();
200 value_array[i] = *it.Get()->Value2();
201 }
202 QSort(key_array);
203 QSort(value_array);
204 for (int i = 0; i < map1.GetSize(); i++) {
205 EXPECT_EQ(i, key_array[i]);
206 EXPECT_EQ(i, value_array[i]);
207 }
208
209 int new_entry = map1.GetSize();
210 map1[new_entry] = new_entry;
211 EXPECT_EQ(map1.GetSize() - 1, map1[map1.GetSize() - 1]);
212
213 key_array.Resize(map1.GetSize());
214 Apto::Map<int, int, Apto::DefaultHashBTree>::KeyIterator kit = map1.Keys();
215 for (int i = 0; kit.Next(); i++) key_array[i] = *kit.Get();
216 QSort(key_array);
217 for (int i = 0; i < map1.GetSize(); i++) EXPECT_EQ(i, key_array[i]);
218
219 value_array.Resize(map1.GetSize());
220 Apto::Map<int, int, Apto::DefaultHashBTree>::ValueIterator vit = map1.Values();
221 for (int i = 0; vit.Next(); i++) value_array[i] = *vit.Get();
222 QSort(value_array);
223 for (int i = 0; i < map1.GetSize(); i++) EXPECT_EQ(i, value_array[i]);
224 }
225