]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2015 Mirantis, Inc. | |
7 | * | |
8 | * Author: Igor Fedotov <ifedotov@mirantis.com> | |
9 | * | |
10 | * This is free software; you can redistribute it and/or | |
11 | * modify it under the terms of the GNU Lesser General Public | |
12 | * License version 2.1, as published by the Free Software | |
13 | * Foundation. See file COPYING. | |
14 | * | |
15 | */ | |
16 | ||
17 | #include <gtest/gtest.h> | |
18 | #include "include/interval_set.h" | |
19 | #include "include/btree_interval_set.h" | |
20 | ||
21 | using namespace ceph; | |
22 | ||
23 | typedef uint64_t IntervalValueType; | |
24 | ||
25 | template<typename T> // tuple<type to test on, test array size> | |
26 | class IntervalSetTest : public ::testing::Test { | |
27 | ||
28 | public: | |
29 | typedef T ISet; | |
30 | }; | |
31 | ||
32 | typedef ::testing::Types< interval_set<IntervalValueType> , btree_interval_set<IntervalValueType> > IntervalSetTypes; | |
33 | ||
34 | TYPED_TEST_CASE(IntervalSetTest, IntervalSetTypes); | |
35 | ||
36 | TYPED_TEST(IntervalSetTest, compare) { | |
37 | typedef typename TestFixture::ISet ISet; | |
38 | ISet iset1, iset2; | |
39 | ASSERT_TRUE(iset1 == iset1); | |
40 | ASSERT_TRUE(iset1 == iset2); | |
41 | ||
42 | iset1.insert(1); | |
43 | ASSERT_FALSE(iset1 == iset2); | |
44 | ||
45 | iset2.insert(1); | |
46 | ASSERT_TRUE(iset1 == iset2); | |
47 | ||
48 | iset1.insert(2, 3); | |
49 | iset2.insert(2, 4); | |
50 | ASSERT_FALSE(iset1 == iset2); | |
51 | ||
52 | iset2.erase(2, 4); | |
53 | iset2.erase(1); | |
54 | iset2.insert(2, 3); | |
55 | iset2.insert(1); | |
56 | ASSERT_TRUE(iset1 == iset2); | |
57 | ||
58 | iset1.insert(100, 10); | |
59 | iset2.insert(100, 5); | |
60 | ASSERT_FALSE(iset1 == iset2); | |
61 | iset2.insert(105, 5); | |
62 | ASSERT_TRUE(iset1 == iset2); | |
63 | ||
64 | iset1.insert(200, 10); | |
65 | iset2.insert(205, 5); | |
66 | ASSERT_FALSE(iset1 == iset2); | |
67 | iset2.insert(200, 1); | |
68 | iset2.insert(202, 3); | |
69 | ASSERT_FALSE(iset1 == iset2); | |
70 | iset2.insert(201, 1); | |
71 | ASSERT_TRUE(iset1 == iset2); | |
72 | ||
73 | iset1.clear(); | |
74 | ASSERT_FALSE(iset1 == iset2); | |
75 | iset2.clear(); | |
76 | ASSERT_TRUE(iset1 == iset2); | |
77 | } | |
78 | ||
79 | TYPED_TEST(IntervalSetTest, contains) { | |
80 | typedef typename TestFixture::ISet ISet; | |
81 | ISet iset1; | |
82 | ASSERT_FALSE(iset1.contains( 1 )); | |
83 | ASSERT_FALSE(iset1.contains( 0, 1 )); | |
84 | ||
85 | iset1.insert(1); | |
86 | ASSERT_TRUE(iset1.contains( 1 )); | |
87 | ASSERT_FALSE(iset1.contains( 0 )); | |
88 | ASSERT_FALSE(iset1.contains( 2 )); | |
89 | ASSERT_FALSE(iset1.contains( 0, 1 )); | |
90 | ASSERT_FALSE(iset1.contains( 0, 2 )); | |
91 | ASSERT_TRUE(iset1.contains( 1, 1 )); | |
92 | ASSERT_FALSE(iset1.contains( 1, 2 )); | |
93 | ||
94 | iset1.insert(2, 3); | |
95 | ASSERT_TRUE(iset1.contains( 1 )); | |
96 | ASSERT_FALSE(iset1.contains( 0 )); | |
97 | ASSERT_TRUE(iset1.contains( 2 )); | |
98 | ASSERT_FALSE(iset1.contains( 0, 1 )); | |
99 | ASSERT_FALSE(iset1.contains( 0, 2 )); | |
100 | ASSERT_TRUE(iset1.contains( 1, 1 )); | |
101 | ASSERT_TRUE(iset1.contains( 1, 2 )); | |
102 | ASSERT_TRUE(iset1.contains( 1, 3 )); | |
103 | ASSERT_TRUE(iset1.contains( 1, 4 )); | |
104 | ASSERT_FALSE(iset1.contains( 1, 5 )); | |
105 | ASSERT_TRUE(iset1.contains( 2, 1 )); | |
106 | ASSERT_TRUE(iset1.contains( 2, 2 )); | |
107 | ASSERT_TRUE(iset1.contains( 2, 3 )); | |
108 | ASSERT_FALSE(iset1.contains( 2, 4 )); | |
109 | ASSERT_TRUE(iset1.contains( 3, 2 )); | |
110 | ASSERT_TRUE(iset1.contains( 4, 1 )); | |
111 | ASSERT_FALSE(iset1.contains( 4, 2 )); | |
112 | ||
113 | iset1.insert(10, 10); | |
114 | ASSERT_TRUE(iset1.contains( 1, 4 )); | |
115 | ASSERT_FALSE(iset1.contains( 1, 5 )); | |
116 | ASSERT_TRUE(iset1.contains( 2, 2 )); | |
117 | ASSERT_FALSE(iset1.contains( 2, 4 )); | |
118 | ||
119 | ASSERT_FALSE(iset1.contains( 1, 10 )); | |
120 | ASSERT_FALSE(iset1.contains( 9, 1 )); | |
121 | ASSERT_FALSE(iset1.contains( 9 )); | |
122 | ASSERT_FALSE(iset1.contains( 9, 11 )); | |
123 | ASSERT_TRUE(iset1.contains( 10, 1 )); | |
124 | ASSERT_TRUE(iset1.contains( 11, 9 )); | |
125 | ASSERT_TRUE(iset1.contains( 11, 2 )); | |
126 | ASSERT_TRUE(iset1.contains( 18, 2 )); | |
127 | ASSERT_TRUE(iset1.contains( 18, 2 )); | |
128 | ASSERT_TRUE(iset1.contains( 10 )); | |
129 | ASSERT_TRUE(iset1.contains( 19 )); | |
130 | ASSERT_FALSE(iset1.contains( 20 )); | |
131 | ASSERT_FALSE(iset1.contains( 21 )); | |
132 | ||
133 | ASSERT_FALSE(iset1.contains( 11, 11 )); | |
134 | ASSERT_FALSE(iset1.contains( 18, 9 )); | |
135 | ||
136 | iset1.clear(); | |
137 | ASSERT_FALSE(iset1.contains( 1 )); | |
138 | ASSERT_FALSE(iset1.contains( 0 )); | |
139 | ASSERT_FALSE(iset1.contains( 2 )); | |
140 | ASSERT_FALSE(iset1.contains( 0, 1 )); | |
141 | ASSERT_FALSE(iset1.contains( 0, 2 )); | |
142 | ASSERT_FALSE(iset1.contains( 1, 1 )); | |
143 | ASSERT_FALSE(iset1.contains( 10, 2 )); | |
144 | } | |
145 | ||
146 | TYPED_TEST(IntervalSetTest, intersects) { | |
147 | typedef typename TestFixture::ISet ISet; | |
148 | ISet iset1; | |
149 | ASSERT_FALSE(iset1.intersects( 1, 1 )); | |
150 | ASSERT_FALSE(iset1.intersects( 0, 1 )); | |
151 | ASSERT_FALSE(iset1.intersects( 0, 10 )); | |
152 | ||
153 | iset1.insert(1); | |
154 | ASSERT_TRUE(iset1.intersects( 1, 1 )); | |
155 | ASSERT_FALSE(iset1.intersects( 0, 1 )); | |
156 | ASSERT_FALSE(iset1.intersects( 2, 1 )); | |
157 | ASSERT_TRUE(iset1.intersects( 0, 2 )); | |
158 | ASSERT_TRUE(iset1.intersects( 0, 20 )); | |
159 | ASSERT_TRUE(iset1.intersects( 1, 2 )); | |
160 | ASSERT_TRUE(iset1.intersects( 1, 20 )); | |
161 | ||
162 | iset1.insert(2, 3); | |
163 | ASSERT_FALSE(iset1.intersects( 0, 1 )); | |
164 | ASSERT_TRUE(iset1.intersects( 0, 2 )); | |
165 | ASSERT_TRUE(iset1.intersects( 0, 200 )); | |
166 | ASSERT_TRUE(iset1.intersects( 1, 1 )); | |
167 | ASSERT_TRUE(iset1.intersects( 1, 4 )); | |
168 | ASSERT_TRUE(iset1.intersects( 1, 5 )); | |
169 | ASSERT_TRUE(iset1.intersects( 2, 1 )); | |
170 | ASSERT_TRUE(iset1.intersects( 2, 2 )); | |
171 | ASSERT_TRUE(iset1.intersects( 2, 3 )); | |
172 | ASSERT_TRUE(iset1.intersects( 2, 4 )); | |
173 | ASSERT_TRUE(iset1.intersects( 3, 2 )); | |
174 | ASSERT_TRUE(iset1.intersects( 4, 1 )); | |
175 | ASSERT_TRUE(iset1.intersects( 4, 2 )); | |
176 | ASSERT_FALSE(iset1.intersects( 5, 2 )); | |
177 | ||
178 | iset1.insert(10, 10); | |
179 | ASSERT_TRUE(iset1.intersects( 1, 4 )); | |
180 | ASSERT_TRUE(iset1.intersects( 1, 5 )); | |
181 | ASSERT_TRUE(iset1.intersects( 1, 10 )); | |
182 | ASSERT_TRUE(iset1.intersects( 2, 2 )); | |
183 | ASSERT_TRUE(iset1.intersects( 2, 4 )); | |
184 | ASSERT_FALSE(iset1.intersects( 5, 1 )); | |
185 | ASSERT_FALSE(iset1.intersects( 5, 2 )); | |
186 | ASSERT_FALSE(iset1.intersects( 5, 5 )); | |
187 | ASSERT_TRUE(iset1.intersects( 5, 12 )); | |
188 | ASSERT_TRUE(iset1.intersects( 5, 20 )); | |
189 | ||
190 | ASSERT_FALSE(iset1.intersects( 9, 1 )); | |
191 | ASSERT_TRUE(iset1.intersects( 9, 2 )); | |
192 | ||
193 | ASSERT_TRUE(iset1.intersects( 9, 11 )); | |
194 | ASSERT_TRUE(iset1.intersects( 10, 1 )); | |
195 | ASSERT_TRUE(iset1.intersects( 11, 9 )); | |
196 | ASSERT_TRUE(iset1.intersects( 11, 2 )); | |
197 | ASSERT_TRUE(iset1.intersects( 11, 11 )); | |
198 | ASSERT_TRUE(iset1.intersects( 18, 2 )); | |
199 | ASSERT_TRUE(iset1.intersects( 18, 9 )); | |
200 | ASSERT_FALSE(iset1.intersects( 20, 1 )); | |
201 | ASSERT_FALSE(iset1.intersects( 21, 12 )); | |
202 | ||
203 | iset1.clear(); | |
204 | ASSERT_FALSE(iset1.intersects( 0, 1 )); | |
205 | ASSERT_FALSE(iset1.intersects( 0, 2 )); | |
206 | ASSERT_FALSE(iset1.intersects( 1, 1 )); | |
207 | ASSERT_FALSE(iset1.intersects( 5, 2 )); | |
208 | ASSERT_FALSE(iset1.intersects( 10, 2 )); | |
209 | } | |
210 | ||
211 | TYPED_TEST(IntervalSetTest, insert_erase) { | |
212 | typedef typename TestFixture::ISet ISet; | |
213 | ISet iset1, iset2; | |
214 | IntervalValueType start, len; | |
215 | ||
216 | iset1.insert(3, 5, &start, &len); | |
217 | ASSERT_TRUE( start == 3 ); | |
218 | ASSERT_TRUE( len == 5 ); | |
219 | ASSERT_TRUE( iset1.num_intervals() == 1 ); | |
220 | ASSERT_TRUE( iset1.size() == 5 ); | |
221 | ||
222 | //adding standalone interval | |
223 | iset1.insert(15, 10, &start, &len); | |
224 | ASSERT_TRUE( start == 15 ); | |
225 | ASSERT_TRUE( len == 10 ); | |
226 | ASSERT_TRUE( iset1.num_intervals() == 2 ); | |
227 | ASSERT_EQ( iset1.size(), 15 ); | |
228 | ||
229 | //adding leftmost standalone interval | |
230 | iset1.insert(1, 1, &start, &len); | |
231 | ASSERT_TRUE( start == 1 ); | |
232 | ASSERT_TRUE( len == 1 ); | |
233 | ASSERT_TRUE( iset1.num_intervals() == 3 ); | |
234 | ASSERT_EQ( iset1.size(), 16 ); | |
235 | ||
236 | //adding leftmost adjusent interval | |
237 | iset1.insert(0, 1, &start, &len); | |
238 | ASSERT_TRUE( start == 0 ); | |
239 | ASSERT_TRUE( len == 2 ); | |
240 | ASSERT_TRUE( iset1.num_intervals() == 3 ); | |
241 | ASSERT_EQ( iset1.size(), 17 ); | |
242 | ||
243 | //adding interim interval that merges leftmost and subseqent intervals | |
244 | iset1.insert(2, 1, &start, &len); | |
245 | ASSERT_TRUE( start == 0 ); | |
246 | ASSERT_TRUE( len == 8 ); | |
247 | ASSERT_TRUE( iset1.num_intervals() == 2); | |
248 | ASSERT_EQ( iset1.size(), 18); | |
249 | ||
250 | //adding rigtmost standalone interval | |
251 | iset1.insert(30, 5, &start, &len); | |
252 | ASSERT_TRUE( start == 30 ); | |
253 | ASSERT_TRUE( len == 5 ); | |
254 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
255 | ASSERT_EQ( iset1.size(), 23 ); | |
256 | ||
257 | //adding rigtmost adjusent interval | |
258 | iset1.insert(35, 10, &start, &len); | |
259 | ASSERT_TRUE( start == 30 ); | |
260 | ASSERT_TRUE( len == 15 ); | |
261 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
262 | ASSERT_EQ( iset1.size(), 33 ); | |
263 | ||
264 | //adding interim interval that merges with the interval preceeding the rightmost | |
265 | iset1.insert(25, 1, &start, &len); | |
266 | ASSERT_TRUE( start == 15 ); | |
267 | ASSERT_TRUE( len == 11 ); | |
268 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
269 | ASSERT_EQ( iset1.size(), 34); | |
270 | ||
271 | //adding interim interval that merges with the rightmost and preceeding intervals | |
272 | iset1.insert(26, 4, &start, &len); | |
273 | ASSERT_TRUE( start == 15 ); | |
274 | ASSERT_TRUE( len == 30 ); | |
275 | ASSERT_TRUE( iset1.num_intervals() == 2); | |
276 | ASSERT_EQ( iset1.size(), 38); | |
277 | ||
278 | //and finally build single interval filling the gap at 8-15 using different interval set | |
279 | iset2.insert( 8, 1 ); | |
280 | iset2.insert( 14, 1 ); | |
281 | iset2.insert( 9, 4 ); | |
282 | iset1.insert( iset2 ); | |
283 | iset1.insert(13, 1, &start, &len); | |
284 | ASSERT_TRUE( start == 0 ); | |
285 | ASSERT_TRUE( len == 45 ); | |
286 | ASSERT_TRUE( iset1.num_intervals() == 1); | |
287 | ASSERT_EQ( iset1.size(), 45); | |
288 | ||
289 | //now reverses the process using subtract & erase | |
290 | iset1.subtract( iset2 ); | |
291 | iset1.erase(13, 1); | |
292 | ASSERT_TRUE( iset1.num_intervals() == 2); | |
293 | ASSERT_EQ( iset1.size(), 38); | |
294 | ASSERT_TRUE( iset1.contains( 7, 1 )); | |
295 | ASSERT_FALSE( iset1.contains( 8, 7 )); | |
296 | ASSERT_TRUE( iset1.contains( 15, 1 )); | |
297 | ASSERT_TRUE( iset1.contains( 26, 4 )); | |
298 | ||
299 | iset1.erase(26, 4); | |
300 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
301 | ASSERT_EQ( iset1.size(), 34); | |
302 | ASSERT_TRUE( iset1.contains( 7, 1 )); | |
303 | ASSERT_FALSE( iset1.intersects( 8, 7 )); | |
304 | ASSERT_TRUE( iset1.contains( 15, 1 )); | |
305 | ASSERT_TRUE( iset1.contains( 25, 1 )); | |
306 | ASSERT_FALSE( iset1.contains( 26, 4 )); | |
307 | ASSERT_TRUE( iset1.contains( 30, 1 )); | |
308 | ||
309 | iset1.erase(25, 1); | |
310 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
311 | ASSERT_EQ( iset1.size(), 33 ); | |
312 | ASSERT_TRUE( iset1.contains( 24, 1 )); | |
313 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
314 | ASSERT_FALSE( iset1.intersects( 26, 4 )); | |
315 | ASSERT_TRUE( iset1.contains( 30, 1 )); | |
316 | ASSERT_TRUE( iset1.contains( 35, 10 )); | |
317 | ||
318 | iset1.erase(35, 10); | |
319 | ASSERT_TRUE( iset1.num_intervals() == 3); | |
320 | ASSERT_EQ( iset1.size(), 23 ); | |
321 | ASSERT_TRUE( iset1.contains( 30, 5 )); | |
322 | ASSERT_TRUE( iset1.contains( 34, 1 )); | |
323 | ASSERT_FALSE( iset1.contains( 35, 10 )); | |
324 | ASSERT_FALSE(iset1.contains( 45, 1 )); | |
325 | ||
326 | iset1.erase(30, 5); | |
327 | ASSERT_TRUE( iset1.num_intervals() == 2); | |
328 | ASSERT_EQ( iset1.size(), 18); | |
329 | ASSERT_TRUE( iset1.contains( 2, 1 )); | |
330 | ASSERT_TRUE( iset1.contains( 24, 1 )); | |
331 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
332 | ASSERT_FALSE( iset1.contains( 29, 1 )); | |
333 | ASSERT_FALSE( iset1.contains( 30, 5 )); | |
334 | ASSERT_FALSE( iset1.contains( 35, 1 )); | |
335 | ||
336 | iset1.erase(2, 1); | |
337 | ASSERT_TRUE( iset1.num_intervals() == 3 ); | |
338 | ASSERT_EQ( iset1.size(), 17 ); | |
339 | ASSERT_TRUE( iset1.contains( 0, 1 )); | |
340 | ASSERT_TRUE( iset1.contains( 1, 1 )); | |
341 | ASSERT_FALSE( iset1.contains( 2, 1 )); | |
342 | ASSERT_TRUE( iset1.contains( 3, 1 )); | |
343 | ASSERT_TRUE( iset1.contains( 15, 1 )); | |
344 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
345 | ||
346 | iset1.erase( 0, 1); | |
347 | ASSERT_TRUE( iset1.num_intervals() == 3 ); | |
348 | ASSERT_EQ( iset1.size(), 16 ); | |
349 | ASSERT_FALSE( iset1.contains( 0, 1 )); | |
350 | ASSERT_TRUE( iset1.contains( 1, 1 )); | |
351 | ASSERT_FALSE( iset1.contains( 2, 1 )); | |
352 | ASSERT_TRUE( iset1.contains( 3, 1 )); | |
353 | ASSERT_TRUE( iset1.contains( 15, 1 )); | |
354 | ||
355 | iset1.erase(1, 1); | |
356 | ASSERT_TRUE( iset1.num_intervals() == 2 ); | |
357 | ASSERT_EQ( iset1.size(), 15 ); | |
358 | ASSERT_FALSE( iset1.contains( 1, 1 )); | |
359 | ASSERT_TRUE( iset1.contains( 15, 10 )); | |
360 | ASSERT_TRUE( iset1.contains( 3, 5 )); | |
361 | ||
362 | iset1.erase(15, 10); | |
363 | ASSERT_TRUE( iset1.num_intervals() == 1 ); | |
364 | ASSERT_TRUE( iset1.size() == 5 ); | |
365 | ASSERT_FALSE( iset1.contains( 1, 1 )); | |
366 | ASSERT_FALSE( iset1.contains( 15, 10 )); | |
367 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
368 | ASSERT_TRUE( iset1.contains( 3, 5 )); | |
369 | ||
370 | iset1.erase( 3, 1); | |
371 | ASSERT_TRUE( iset1.num_intervals() == 1 ); | |
372 | ASSERT_TRUE( iset1.size() == 4 ); | |
373 | ASSERT_FALSE( iset1.contains( 1, 1 )); | |
374 | ASSERT_FALSE( iset1.contains( 15, 10 )); | |
375 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
376 | ASSERT_TRUE( iset1.contains( 4, 4 )); | |
377 | ASSERT_FALSE( iset1.contains( 3, 5 )); | |
378 | ||
379 | iset1.erase( 4, 4); | |
380 | ASSERT_TRUE( iset1.num_intervals() == 0); | |
381 | ASSERT_TRUE( iset1.size() == 0); | |
382 | ASSERT_FALSE( iset1.contains( 1, 1 )); | |
383 | ASSERT_FALSE( iset1.contains( 15, 10 )); | |
384 | ASSERT_FALSE( iset1.contains( 25, 1 )); | |
385 | ASSERT_FALSE( iset1.contains( 3, 4 )); | |
386 | ASSERT_FALSE( iset1.contains( 3, 5 )); | |
387 | ASSERT_FALSE( iset1.contains( 4, 4 )); | |
388 | ||
389 | ||
390 | } | |
391 | ||
392 | TYPED_TEST(IntervalSetTest, intersect_of) { | |
393 | typedef typename TestFixture::ISet ISet; | |
394 | ISet iset1, iset2, iset3; | |
395 | ||
396 | iset1.intersection_of( iset2, iset3 ); | |
397 | ASSERT_TRUE( iset1.num_intervals() == 0); | |
398 | ASSERT_TRUE( iset1.size() == 0); | |
399 | ||
400 | iset2.insert( 0, 1 ); | |
401 | iset2.insert( 5, 10 ); | |
402 | iset2.insert( 30, 10 ); | |
403 | ||
404 | iset3.insert( 0, 2 ); | |
405 | iset3.insert( 15, 1 ); | |
406 | iset3.insert( 20, 5 ); | |
407 | iset3.insert( 29, 3 ); | |
408 | iset3.insert( 35, 3 ); | |
409 | iset3.insert( 39, 3 ); | |
410 | ||
411 | iset1.intersection_of( iset2, iset3 ); | |
412 | ASSERT_TRUE( iset1.num_intervals() == 4); | |
413 | ASSERT_TRUE( iset1.size() == 7); | |
414 | ||
415 | ASSERT_TRUE( iset1.contains( 0, 1 )); | |
416 | ASSERT_FALSE( iset1.contains( 0, 2 )); | |
417 | ||
418 | ASSERT_FALSE( iset1.contains( 5, 11 )); | |
419 | ASSERT_FALSE( iset1.contains( 4, 1 )); | |
420 | ASSERT_FALSE( iset1.contains( 16, 1 )); | |
421 | ||
422 | ASSERT_FALSE( iset1.contains( 20, 5 )); | |
423 | ||
424 | ASSERT_FALSE( iset1.contains( 29, 1 )); | |
425 | ASSERT_FALSE( iset1.contains( 30, 10 )); | |
426 | ||
427 | ASSERT_TRUE( iset1.contains( 30, 2 )); | |
428 | ASSERT_TRUE( iset1.contains( 35, 3 )); | |
429 | ASSERT_FALSE( iset1.contains( 35, 4 )); | |
430 | ||
431 | ASSERT_TRUE( iset1.contains( 39, 1 )); | |
432 | ASSERT_FALSE( iset1.contains( 38, 2 )); | |
433 | ASSERT_FALSE( iset1.contains( 39, 2 )); | |
434 | ||
435 | iset3=iset1; | |
436 | iset1.intersection_of(iset2); | |
437 | ASSERT_TRUE( iset1 == iset3); | |
438 | ||
439 | iset2.clear(); | |
440 | iset2.insert(0,1); | |
441 | iset1.intersection_of(iset2); | |
442 | ASSERT_TRUE( iset1.num_intervals() == 1); | |
443 | ASSERT_TRUE( iset1.size() == 1); | |
444 | ||
445 | iset1 = iset3; | |
446 | iset2.clear(); | |
447 | iset1.intersection_of(iset2); | |
448 | ASSERT_TRUE( iset1.num_intervals() == 0); | |
449 | ASSERT_TRUE( iset1.size() == 0); | |
450 | ||
451 | } | |
452 | ||
453 | TYPED_TEST(IntervalSetTest, union_of) { | |
454 | typedef typename TestFixture::ISet ISet; | |
455 | ISet iset1, iset2, iset3; | |
456 | ||
457 | iset1.union_of( iset2, iset3 ); | |
458 | ASSERT_TRUE( iset1.num_intervals() == 0); | |
459 | ASSERT_TRUE( iset1.size() == 0); | |
460 | ||
461 | iset2.insert( 0, 1 ); | |
462 | iset2.insert( 5, 10 ); | |
463 | iset2.insert( 30, 10 ); | |
464 | ||
465 | iset3.insert( 0, 2 ); | |
466 | iset3.insert( 15, 1 ); | |
467 | iset3.insert( 20, 5 ); | |
468 | iset3.insert( 29, 3 ); | |
469 | iset3.insert( 39, 3 ); | |
470 | ||
471 | iset1.union_of( iset2, iset3 ); | |
472 | ASSERT_TRUE( iset1.num_intervals() == 4); | |
473 | ASSERT_EQ( iset1.size(), 31); | |
474 | ASSERT_TRUE( iset1.contains( 0, 2 )); | |
475 | ASSERT_FALSE( iset1.contains( 0, 3 )); | |
476 | ||
477 | ASSERT_TRUE( iset1.contains( 5, 11 )); | |
478 | ASSERT_FALSE( iset1.contains( 4, 1 )); | |
479 | ASSERT_FALSE( iset1.contains( 16, 1 )); | |
480 | ||
481 | ASSERT_TRUE( iset1.contains( 20, 5 )); | |
482 | ||
483 | ASSERT_TRUE( iset1.contains( 30, 10 )); | |
484 | ASSERT_TRUE( iset1.contains( 29, 13 )); | |
485 | ASSERT_FALSE( iset1.contains( 29, 14 )); | |
486 | ASSERT_FALSE( iset1.contains( 42, 1 )); | |
487 | ||
488 | iset2.clear(); | |
489 | iset1.union_of(iset2); | |
490 | ASSERT_TRUE( iset1.num_intervals() == 4); | |
491 | ASSERT_EQ( iset1.size(), 31); | |
492 | ||
493 | iset3.clear(); | |
494 | iset3.insert( 29, 3 ); | |
495 | iset3.insert( 39, 2 ); | |
496 | iset1.union_of(iset3); | |
497 | ||
498 | ASSERT_TRUE( iset1.num_intervals() == 4); | |
499 | ASSERT_EQ( iset1.size(), 31); //actually we added nothing | |
500 | ASSERT_TRUE( iset1.contains( 29, 13 )); | |
501 | ASSERT_FALSE( iset1.contains( 29, 14 )); | |
502 | ASSERT_FALSE( iset1.contains( 42, 1 )); | |
503 | ||
504 | } | |
505 | ||
506 | TYPED_TEST(IntervalSetTest, subset_of) { | |
507 | typedef typename TestFixture::ISet ISet; | |
508 | ISet iset1, iset2; | |
509 | ||
510 | ASSERT_TRUE(iset1.subset_of(iset2)); | |
511 | ||
512 | iset1.insert(5,10); | |
513 | ASSERT_FALSE(iset1.subset_of(iset2)); | |
514 | ||
515 | iset2.insert(6,8); | |
516 | ASSERT_FALSE(iset1.subset_of(iset2)); | |
517 | ||
518 | iset2.insert(5,1); | |
519 | ASSERT_FALSE(iset1.subset_of(iset2)); | |
520 | ||
521 | iset2.insert(14,10); | |
522 | ASSERT_TRUE(iset1.subset_of(iset2)); | |
523 | ||
524 | iset1.insert( 20, 4); | |
525 | ASSERT_TRUE(iset1.subset_of(iset2)); | |
526 | ||
527 | iset1.insert( 24, 1); | |
528 | ASSERT_FALSE(iset1.subset_of(iset2)); | |
529 | } | |
530 | ||
531 | TYPED_TEST(IntervalSetTest, span_of) { | |
532 | typedef typename TestFixture::ISet ISet; | |
533 | ISet iset1, iset2; | |
534 | ||
535 | iset2.insert(5,5); | |
536 | iset2.insert(20,5); | |
537 | ||
538 | iset1.span_of( iset2, 8, 5 ); | |
539 | ASSERT_EQ( iset1.num_intervals(), 2); | |
540 | ASSERT_EQ( iset1.size(), 5); | |
541 | ASSERT_TRUE( iset1.contains( 8, 2 )); | |
542 | ASSERT_TRUE( iset1.contains( 20, 3 )); | |
543 | ||
544 | iset1.span_of( iset2, 3, 5 ); | |
545 | ASSERT_EQ( iset1.num_intervals(), 1); | |
546 | ASSERT_EQ( iset1.size(), 5); | |
547 | ASSERT_TRUE( iset1.contains( 5, 5 )); | |
548 | ||
549 | iset1.span_of( iset2, 10, 7 ); | |
550 | ASSERT_EQ( iset1.num_intervals(), 1); | |
551 | ASSERT_EQ( iset1.size(), 5); | |
552 | ASSERT_TRUE( iset1.contains( 20, 5 )); | |
553 | ASSERT_FALSE( iset1.contains( 20, 6 )); | |
554 | ||
555 | iset1.span_of( iset2, 5, 10); | |
556 | ASSERT_EQ( iset1.num_intervals(), 2); | |
557 | ASSERT_EQ( iset1.size(), 10); | |
558 | ASSERT_TRUE( iset1.contains( 5, 5 )); | |
559 | ASSERT_TRUE( iset1.contains( 20, 5 )); | |
560 | ||
561 | iset1.span_of( iset2, 100, 5 ); | |
562 | ASSERT_EQ( iset1.num_intervals(), 0); | |
563 | ASSERT_EQ( iset1.size(), 0); | |
564 | } |