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