1/** \file
2 * \brief Tests for ogdf::Skiplist and skiplist-based ogdf::SortedSequence.
3 *
4 * \author Tilo Wiedera
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <ogdf/basic/geometry.h>
33#include <ogdf/basic/Math.h>
34#include <ogdf/basic/Skiplist.h>
35#include <ogdf/basic/SortedSequence.h>
36
37#include <testing.h>
38
39constexpr int MAX_ELEMENTS = 100;
40
41template<typename T>
42void describeSkiplist(const string& typeName, std::function<T()> randomValue) {
43 describe("Skiplist<" + typeName + ">", [&] {
44 Skiplist<T*> list;
45
46 after_each([&] {
47 list.clear(true);
48 });
49
50 it("recognizes empty lists", [&] {
51 AssertThat(list.empty(), IsTrue());
52
53 list.add(new T);
54 AssertThat(list.empty(), IsFalse());
55
56 list.clear(true);
57 AssertThat(list.empty(), IsTrue());
58 });
59
60 it("returns its size", [&] {
61 for (int i = 0; i < MAX_ELEMENTS; i++) {
62 AssertThat(list.size(), Equals(i));
63 list.add(new T(randomValue()));
64 }
65 });
66
67 it("sorts inserted values", [&] {
68 std::map<T,int> counter;
69
70 for (int i = 0; i < MAX_ELEMENTS; i++) {
71 T j = randomValue();
72
73 if(counter.find(j) == counter.end()) {
74 counter[j] = 1;
75 } else {
76 counter[j]++;
77 }
78
79 list.add(new T(j));
80 }
81
82 T prev = std::numeric_limits<T>::lowest();
83 for(T* p : list) {
84 T j = *p;
85 counter[j]--;
86
87 if(counter[j] == 0) {
88 counter.erase(j);
89 }
90
91 if(j != prev) {
92 AssertThat(prev, IsLessThan(j));
93 prev = j;
94 }
95 }
96
97 AssertThat(counter.empty(), IsTrue());
98 });
99
100 it("works with many duplicate values", [&] {
101 T small = randomValue();
102 T big;
103 do {
104 big = randomValue();
105 } while (big == small);
106
107 if(big < small) {
108 std::swap(big, small);
109 }
110
111 for(int i = 0; i < MAX_ELEMENTS; i++) {
112 list.add(&big);
113 }
114
115 list.add(&small);
116 list.add(&big);
117 list.add(&small);
118
119 AssertThat(list.size(), Equals(MAX_ELEMENTS+3));
120
121 int counter = 0;
122 for(auto p : list) {
123 counter++;
124
125 if(counter < 3) {
126 AssertThat(p, Equals(&small));
127 } else {
128 AssertThat(p, Equals(&big));
129 }
130 }
131
132 AssertThat(counter, Equals(list.size()));
133
134 list.clear();
135 });
136 });
137}
138
139template<typename T>
140void describeSortedSequence(const string& typeName) {
141 class MyInfoObject {
142 public:
143 T x;
144 MyInfoObject(T p) : x(p) {}
145 MyInfoObject() : MyInfoObject(0) {}
146 };
147
148 SortedSequence<int, MyInfoObject> sequence;
149
150 auto toInfo = [](T i) {
151 i = std::abs(i);
152 return (i+1)*(i+2);
153 };
154
155 auto insert = [&](T i) {
156 MyInfoObject info = MyInfoObject(toInfo(i));
157 sequence.insert(i, info);
158 };
159
160 List<T> perm;
161
162 for(T i = 0; i < MAX_ELEMENTS; i++) {
163 perm.pushBack(i);
164 }
165
166 describe("SortedSequence<" + typeName + ">", [&] {
167 before_each([&] {
168 perm.permute();
169 });
170
171 after_each([&] {
172 sequence.clear();
173 });
174
175 it("recognizes empty sequences", [&] {
176 AssertThat(sequence.empty(), IsTrue());
177
178 insert(1);
179 AssertThat(sequence.empty(), IsFalse());
180
181 sequence.clear();
182 AssertThat(sequence.empty(), IsTrue());
183 });
184
185 it("returns its size", [&] {
186 int counter = 0;
187
188 for(T i : perm) {
189 AssertThat(sequence.size(), Equals(counter));
190 insert(i);
191 counter++;
192 }
193 });
194
195 it("returns its info object", [&] {
196 for (T i : perm) {
197 insert(i);
198 }
199
200 for (auto it = sequence.begin(); it.valid(); it++) {
201 AssertThat(it.info().x, Equals(toInfo(it.key())));
202 }
203 });
204
205 it("sorts inserted values", [&] {
206 for(T i : perm) {
207 AssertThat(sequence.lookup(i).valid(), IsFalse());
208 insert(i);
209 AssertThat(sequence.lookup(i).valid(), IsTrue());
210 }
211
212 AssertThat(sequence.size(), Equals(perm.size()));
213
214 T prev{};
215 for (auto it = sequence.begin(); it.valid(); it++) {
216 T k = it.key();
217
218 AssertThat(sequence.lookup(k).valid(), IsTrue());
219 if(it != sequence.begin()) {
220 AssertThat(k, IsGreaterThan(prev));
221 }
222
223 prev = k;
224 }
225 });
226
227 it("deletes values", [&] {
228 insert(42);
229 insert(17);
230 sequence.del(42);
231 insert(2017);
232
233 AssertThat(sequence.lookup(42).valid(), IsFalse());
234 AssertThat(sequence.size(), Equals(2));
235
236 sequence.delItem(sequence.lookup(2017));
237
238 AssertThat(sequence.lookup(2017).valid(), IsFalse());
239 AssertThat(sequence.size(), Equals(1));
240 });
241
242 it("identifies min and max values", [&] {
243 AssertThat(sequence.minItem().valid(), IsFalse());
244 AssertThat(sequence.maxItem().valid(), IsFalse());
245
246 for(int i : perm) {
247 insert(i);
248 }
249
250 AssertThat(sequence.minItem().key(), Equals(0));
251 AssertThat(sequence.maxItem().key(), Equals(MAX_ELEMENTS-1));
252 });
253
254 it("locates the smallest feasible value", [&] {
255 AssertThat(sequence.locate(0).valid(), IsFalse());
256
257 int max = 0;
258 bool firstIteration = true;
259
260 for(int i : perm) {
261 Math::updateMax(max, i);
262 insert(i);
263
264 if(!firstIteration) {
265 AssertThat(sequence.locate(0).key(), !Equals(max));
266 }
267
268 AssertThat(sequence.locate(max).key(), Equals(max));
269 AssertThat(sequence.locate(max + 1).valid(), IsFalse());
270
271 firstIteration = false;
272 }
273 });
274 });
275}
276
277go_bandit([] {
278 auto ranD = [] { return randomDouble(0, MAX_ELEMENTS); };
279
280 describeSkiplist<int>("int", [] { return randomNumber(0, (MAX_ELEMENTS*5)/6); });
281 describeSkiplist<double>("double", ranD);
282 describeSkiplist<DPoint>("DPoint", [&] { return DPoint(ranD(), ranD()); });
283
284 describeSortedSequence<int>("int");
285 describeSortedSequence<double>("double");
286});
287