ceph/src/test/common/test_interval_set.cc

   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 }