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