ceph/src/boost/libs/icl/test/test_interval_set_shared.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2010: Joachim Faulhaber
   3 +------------------------------------------------------------------------------+
   4    Distributed under the Boost Software License, Version 1.0.
   5       (See accompanying file LICENCE.txt or copy at
   6            http://www.boost.org/LICENSE_1_0.txt)
   7 +-----------------------------------------------------------------------------*/
   8 #ifndef LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
   9 #define LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
  10
  11 #include "portability.hpp"
  12
  13 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
  14 void interval_set_fundamentals_4_ordered_types()
  15 {
  16     typedef IntervalSet<T> IntervalSetT;
  17     typedef typename IntervalSetT::interval_type IntervalT;
  18     typedef typename IntervalSet<T>::size_type       size_T;
  19     typedef typename IntervalSet<T>::difference_type diff_T;
  20
  21     // ordered types is the largest set of instance types.
  22     // Because we can not generate values via incrementation for e.g. string,
  23     // we are able to test operations only for the most basic values
  24     // identity_element (0, empty, T() ...) and unit_element.
  25
  26     T v0 = boost::icl::identity_element<T>::value();
  27     T v1 = unit_element<T>::value();
  28     IntervalT I0_0I(v0);
  29     IntervalT I1_1I(v1);
  30     IntervalT I0_1I(v0, v1, interval_bounds::closed());
  31
  32     //-------------------------------------------------------------------------
  33     //empty set
  34     //-------------------------------------------------------------------------
  35     BOOST_CHECK_EQUAL(IntervalSet<T>().empty(), true);
  36     BOOST_CHECK_EQUAL(icl::is_empty(IntervalSet<T>()), true);
  37     BOOST_CHECK_EQUAL(cardinality(IntervalSet<T>()), boost::icl::identity_element<size_T>::value());
  38     BOOST_CHECK_EQUAL(IntervalSet<T>().size(), boost::icl::identity_element<size_T>::value());
  39     BOOST_CHECK_EQUAL(interval_count(IntervalSet<T>()), 0);
  40     BOOST_CHECK_EQUAL(IntervalSet<T>().iterative_size(), 0);
  41     BOOST_CHECK_EQUAL(iterative_size(IntervalSet<T>()), 0);
  42     BOOST_CHECK_EQUAL(IntervalSet<T>(), IntervalSet<T>());
  43
  44     IntervalT mt_interval = boost::icl::identity_element<IntervalT>::value();
  45     BOOST_CHECK_EQUAL(mt_interval, IntervalT());
  46     IntervalSet<T> mt_set = boost::icl::identity_element<IntervalSet<T> >::value();
  47     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  48
  49     //adding emptieness to emptieness yields emptieness ;)
  50     mt_set.add(mt_interval).add(mt_interval);
  51     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  52     mt_set.insert(mt_interval).insert(mt_interval);
  53     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  54     (mt_set += mt_interval) += mt_interval;
  55     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  56     BOOST_CHECK_EQUAL(hull(mt_set), boost::icl::identity_element<IntervalT >::value());
  57
  58     //subtracting emptieness
  59     mt_set.subtract(mt_interval).subtract(mt_interval);
  60     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  61     mt_set.erase(mt_interval).erase(mt_interval);
  62     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  63     (mt_set -= mt_interval) -= mt_interval;
  64     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  65
  66     //subtracting elements form emptieness
  67     mt_set.subtract(v0).subtract(v1);
  68     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  69     mt_set.erase(v0).erase(v1);
  70     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  71     (mt_set -= v1) -= v0;
  72     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  73
  74     //subtracting intervals form emptieness
  75     mt_set.subtract(I0_1I).subtract(I1_1I);
  76     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  77     mt_set.erase(I0_1I).erase(I1_1I);
  78     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  79     (mt_set -= I1_1I) -= I0_1I;
  80     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  81
  82     //insecting emptieness
  83     //mt_set.insect(mt_interval).insect(mt_interval);
  84     //BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  85     (mt_set &= mt_interval) &= mt_interval;
  86     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  87     //insecting emptieness with elements
  88     (mt_set &= v1) &= v0;
  89     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  90     //insecting emptieness with intervals
  91     (mt_set &= I1_1I) &= I0_1I;
  92     BOOST_CHECK_EQUAL(mt_set, IntervalSet<T>());
  93
  94     //-------------------------------------------------------------------------
  95     //unary set
  96     //-------------------------------------------------------------------------
  97     IntervalSet<T> single_I0_0I_from_element(v0);
  98     IntervalSet<T> single_I0_0I_from_interval(I0_0I);
  99     IntervalSet<T> single_I0_0I(single_I0_0I_from_interval);
 100
 101     BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I_from_interval);
 102     BOOST_CHECK_EQUAL(single_I0_0I_from_element, single_I0_0I);
 103     BOOST_CHECK_EQUAL(icl::hull(single_I0_0I).lower(), I0_0I.lower());
 104     BOOST_CHECK_EQUAL(icl::hull(single_I0_0I).upper(), I0_0I.upper());
 105
 106     IntervalSet<T> single_I1_1I_from_element(v1);
 107     IntervalSet<T> single_I1_1I_from_interval(I1_1I);
 108     IntervalSet<T> single_I1_1I(single_I1_1I_from_interval);
 109
 110     BOOST_CHECK_EQUAL(single_I1_1I_from_element, single_I1_1I_from_interval);
 111     BOOST_CHECK_EQUAL(single_I1_1I_from_element, single_I1_1I);
 112
 113     IntervalSet<T> single_I0_1I_from_interval(I0_1I);
 114     IntervalSet<T> single_I0_1I(single_I0_1I_from_interval);
 115
 116     BOOST_CHECK_EQUAL(single_I0_1I_from_interval, single_I0_1I);
 117     BOOST_CHECK_EQUAL(hull(single_I0_1I), I0_1I);
 118     BOOST_CHECK_EQUAL(hull(single_I0_1I).lower(), I0_1I.lower());
 119     BOOST_CHECK_EQUAL(hull(single_I0_1I).upper(), I0_1I.upper());
 120
 121     //contains predicate
 122     BOOST_CHECK_EQUAL(icl::contains(single_I0_0I, v0), true);
 123     BOOST_CHECK_EQUAL(icl::contains(single_I0_0I, I0_0I), true);
 124     BOOST_CHECK_EQUAL(icl::contains(single_I1_1I, v1), true);
 125     BOOST_CHECK_EQUAL(icl::contains(single_I1_1I, I1_1I), true);
 126
 127     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, v0), true);
 128     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, I0_1I), true);
 129     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, v1), true);
 130     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, I1_1I), true);
 131
 132     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I0_0I), true);
 133     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I1_1I), true);
 134     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I, single_I0_1I), true);
 135
 136     BOOST_CHECK_EQUAL(cardinality(single_I0_0I), unit_element<size_T>::value());
 137     BOOST_CHECK_EQUAL(single_I0_0I.size(), unit_element<size_T>::value());
 138     BOOST_CHECK_EQUAL(interval_count(single_I0_0I), 1);
 139     BOOST_CHECK_EQUAL(single_I0_0I.iterative_size(), 1);
 140     BOOST_CHECK_EQUAL(iterative_size(single_I0_0I), 1);
 141 }
 142
 143
 144
 145 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 146 void interval_set_ctor_4_bicremental_types()
 147 {
 148     typedef IntervalSet<T> IntervalSetT;
 149     typedef typename IntervalSetT::interval_type IntervalT;
 150
 151     T v4 = make<T>(4);
 152     IntervalT I4_4I(v4);
 153
 154     IntervalSet<T> _I4_4I;
 155     BOOST_CHECK_EQUAL( _I4_4I.empty(), true );
 156     IntervalSet<T> _I4_4I_1;
 157     IntervalSet<T> _I4_4I_2;
 158     IntervalSet<T> _I4_4I_3;
 159     _I4_4I   += v4;
 160     _I4_4I_1 += I4_4I;
 161     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_1 );
 162     _I4_4I_2.add(v4);
 163     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_2 );
 164     _I4_4I_3.add(I4_4I);
 165     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_3 );
 166     _I4_4I_1.add(v4).add(I4_4I);
 167     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_1 );
 168     _I4_4I_1.insert(v4).insert(I4_4I);
 169     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_1 );
 170     (_I4_4I_1 += v4) += I4_4I;
 171     BOOST_CHECK_EQUAL( _I4_4I,                    _I4_4I_1 );
 172
 173     BOOST_CHECK_EQUAL( cardinality(_I4_4I),      unit_element<typename IntervalSet<T>::size_type>::value()  );
 174     BOOST_CHECK_EQUAL( _I4_4I.size(),             unit_element<typename IntervalSet<T>::size_type>::value()  );
 175     BOOST_CHECK_EQUAL( interval_count(_I4_4I),   1  );
 176     BOOST_CHECK_EQUAL( _I4_4I.iterative_size(),   1  );
 177     BOOST_CHECK_EQUAL( iterative_size(_I4_4I),   1  );
 178     BOOST_CHECK_EQUAL( hull(_I4_4I).lower(),      v4 );
 179     BOOST_CHECK_EQUAL( hull(_I4_4I).upper(),      v4 );
 180
 181     IntervalSet<T> _I4_4I_copy(_I4_4I);
 182     IntervalSet<T> _I4_4I_assigned;
 183     _I4_4I_assigned = _I4_4I;
 184     BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_copy );
 185     BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_assigned );
 186     _I4_4I_assigned.clear();
 187     BOOST_CHECK_EQUAL( true,   _I4_4I_assigned.empty() );
 188
 189     _I4_4I_assigned.swap(_I4_4I_copy);
 190     BOOST_CHECK_EQUAL( true,   _I4_4I_copy.empty() );
 191     BOOST_CHECK_EQUAL( _I4_4I, _I4_4I_assigned );
 192
 193 }
 194
 195 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 196 void interval_set_add_sub_4_bicremental_types()
 197 {
 198     typedef IntervalSet<T> IntervalSetT;
 199     typedef typename IntervalSetT::interval_type IntervalT;
 200
 201     T v0 = make<T>(0);
 202     T v5 = make<T>(5);
 203     T v6 = make<T>(6);
 204     T v9 = make<T>(9);
 205     IntervalT I5_6I(v5,v6,interval_bounds::closed());
 206     IntervalT I5_9I(v5,v9,interval_bounds::closed());
 207     IntervalT I0_9I = IntervalT::closed(v0, v9);
 208
 209     BOOST_CHECK_EQUAL( IntervalSet<T>(I5_6I).add(v0).add(v9),
 210                        IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0) );
 211
 212     IntervalSet<T> set_A = IntervalSet<T>(I5_6I).add(v0).add(v9);
 213     IntervalSet<T> set_B = IntervalSet<T>().insert(v9).insert(I5_6I).insert(v0);
 214     BOOST_CHECK_EQUAL( set_A, set_B );
 215     BOOST_CHECK_EQUAL( hull(set_A), I0_9I );
 216     BOOST_CHECK_EQUAL( hull(set_A).lower(), I0_9I.lower() );
 217     BOOST_CHECK_EQUAL( hull(set_A).upper(), I0_9I.upper() );
 218
 219     IntervalSet<T> set_A1 = set_A, set_B1 = set_B,
 220                    set_A2 = set_A, set_B2 = set_B;
 221
 222     set_A1.subtract(I5_6I).subtract(v9);
 223     set_B1.erase(v9).erase(I5_6I);
 224     BOOST_CHECK_EQUAL( set_A1, set_B1 );
 225
 226     set_A2.subtract(I5_9I);
 227     set_B2.erase(I5_9I);
 228     BOOST_CHECK_EQUAL( set_A1, set_B1 );
 229     BOOST_CHECK_EQUAL( set_A1, set_A2 );
 230     BOOST_CHECK_EQUAL( set_B1, set_B2 );
 231 }
 232
 233
 234 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 235 void interval_set_distinct_4_bicremental_types()
 236 {
 237     typedef IntervalSet<T> IntervalSetT;
 238     typedef typename IntervalSetT::interval_type IntervalT;
 239     typedef typename IntervalSet<T>::size_type       size_T;
 240     typedef typename IntervalSet<T>::difference_type diff_T;
 241     T v1 = make<T>(1);
 242     T v3 = make<T>(3);
 243     T v5 = make<T>(5);
 244
 245     size_T s3 = make<size_T>(3);
 246
 247
 248     IntervalSet<T> is_1_3_5;
 249     is_1_3_5.add(v1).add(v3).add(v5);
 250
 251     BOOST_CHECK_EQUAL( cardinality(is_1_3_5),       s3 );
 252     BOOST_CHECK_EQUAL( is_1_3_5.size(),             s3 );
 253     BOOST_CHECK_EQUAL( interval_count(is_1_3_5),   3 );
 254     BOOST_CHECK_EQUAL( iterative_size(is_1_3_5),   3 );
 255     BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(),   3 );
 256 }
 257
 258
 259 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 260 void interval_set_distinct_4_bicremental_continuous_types()
 261 {
 262     typedef IntervalSet<T> IntervalSetT;
 263     typedef typename IntervalSetT::interval_type IntervalT;
 264     typedef typename IntervalSet<T>::size_type       size_T;
 265     typedef typename IntervalSet<T>::difference_type diff_T;
 266     T v1 = make<T>(1);
 267     T v3 = make<T>(3);
 268     T v5 = make<T>(5);
 269
 270     size_T s3 = make<size_T>(3);
 271     diff_T d0 = make<diff_T>(0);
 272     diff_T d2 = make<diff_T>(2);
 273
 274     IntervalSet<T> is_1_3_5;
 275     is_1_3_5.add(v1).add(v3).add(v5);
 276
 277     BOOST_CHECK_EQUAL( cardinality(is_1_3_5),      s3 );
 278     BOOST_CHECK_EQUAL( is_1_3_5.size(),             s3 );
 279     BOOST_CHECK_EQUAL( icl::length(is_1_3_5),       d0 );
 280     BOOST_CHECK_EQUAL( interval_count(is_1_3_5),   3 );
 281     BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(),   3 );
 282     BOOST_CHECK_EQUAL( iterative_size(is_1_3_5),   3 );
 283
 284
 285
 286     IntervalSet<T> is_123_5;
 287     is_123_5 = is_1_3_5;
 288     is_123_5 += IntervalT::open(v1,v3);
 289
 290     BOOST_CHECK_EQUAL( cardinality(is_123_5),      icl::infinity<size_T>::value() );
 291     BOOST_CHECK_EQUAL( is_123_5.size(),             icl::infinity<size_T>::value() );
 292     BOOST_CHECK_EQUAL( icl::length(is_123_5),           d2 );
 293 }
 294
 295
 296 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 297 void interval_set_isolate_4_bicremental_continuous_types()
 298 {
 299     typedef IntervalSet<T> IntervalSetT;
 300     typedef typename IntervalSetT::interval_type IntervalT;
 301     typedef typename IntervalSet<T>::size_type       size_T;
 302     typedef typename IntervalSet<T>::difference_type diff_T;
 303
 304     T v0 = make<T>(0);
 305     T v2 = make<T>(2);
 306     T v4 = make<T>(4);
 307     IntervalT I0_4I = IntervalT::closed(v0,v4);
 308     IntervalT C0_2D = IntervalT::open(v0,v2);
 309     IntervalT C2_4D = IntervalT::open(v2,v4);
 310     //   {[0               4]}
 311     // - {   (0,2)   (2,4)   }
 312     // = {[0]     [2]     [4]}
 313     IntervalSet<T> iso_set = IntervalSet<T>(I0_4I);
 314     IntervalSet<T> gap_set;
 315     gap_set.add(C0_2D).add(C2_4D);
 316     BOOST_CHECK_EQUAL( true, true );
 317     iso_set -= gap_set;
 318
 319     BOOST_CHECK_EQUAL( cardinality(iso_set), static_cast<size_T>(3) );
 320     BOOST_CHECK_EQUAL( iso_set.iterative_size(), static_cast<std::size_t>(3) );
 321     BOOST_CHECK_EQUAL( iterative_size(iso_set), static_cast<std::size_t>(3) );
 322
 323     IntervalSet<T> iso_set2;
 324     iso_set2.add(I0_4I);
 325     iso_set2.subtract(C0_2D).subtract(C2_4D);
 326
 327     IntervalSet<T> iso_set3(I0_4I);
 328     (iso_set3 -= C0_2D) -= C2_4D;
 329
 330     IntervalSet<T> iso_set4;
 331     iso_set4.insert(I0_4I);
 332     iso_set4.erase(C0_2D).erase(C2_4D);
 333
 334     BOOST_CHECK_EQUAL( iso_set, iso_set2 );
 335     BOOST_CHECK_EQUAL( iso_set, iso_set3 );
 336     BOOST_CHECK_EQUAL( iso_set, iso_set4 );
 337 }
 338
 339
 340 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 341 void interval_set_element_compare_4_bicremental_types()
 342 {
 343     typedef IntervalSet<T> IntervalSetT;
 344     typedef typename IntervalSetT::interval_type IntervalT;
 345     typedef IntervalSet<T> ISet;
 346
 347     BOOST_CHECK_EQUAL( is_element_equal( ISet(),         ISet()),         true );
 348     BOOST_CHECK_EQUAL( is_element_equal( ISet(),         ISet(I_D(0,1))), false );
 349     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet()),         false );
 350     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)), ISet(I_D(0,1))), true );
 351
 352     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,5)), ISet(I_D(3,8))), false );
 353     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(3,8)), ISet(I_D(0,5))), false );
 354
 355     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)),          ISet(I_D(0,1))          ), true  );
 356     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,1)),          ISet(I_D(0,1))+I_D(1,2) ), false );
 357     BOOST_CHECK_EQUAL( is_element_equal( I_D(1,2)+ISet(I_D(0,1)), ISet(I_D(0,1))          ), false );
 358     BOOST_CHECK_EQUAL( is_element_equal( I_D(1,2)+ISet(I_D(0,1)), ISet(I_D(0,1))+I_D(1,2) ), true  );
 359
 360     //[0   1)[1   2)
 361     //[0          2)
 362     BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(1,2)), ISet(I_D(0,2))          ), true );
 363     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,2)),          ISet(I_D(0,1))+I_D(1,2) ), true );
 364
 365     //[0   1)  [2   3)
 366     //[0            3)
 367     BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(2,3)), ISet(I_D(0,3))          ), false );
 368     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(0,3)),          ISet(I_D(0,1))+I_D(2,3) ), false );
 369
 370     //[0   2)[2       4)
 371     //  [1            4)
 372     BOOST_CHECK_EQUAL( is_element_equal( I_D(0,2)+ISet(I_D(2,4)), ISet(I_D(1,4))          ), false );
 373     BOOST_CHECK_EQUAL( is_element_equal( ISet(I_D(1,4)),          ISet(I_D(0,2))+I_D(2,4) ), false );
 374
 375     //[0     2)[2       4)
 376     //[0 1)[1     3)[3  4)
 377     BOOST_CHECK_EQUAL( is_element_equal( I_D(0,2)+ISet(I_D(2,4)), I_D(0,1)+ISet(I_D(1,4))+I_D(3,4) ), true );
 378     BOOST_CHECK_EQUAL( is_element_equal( I_D(0,1)+ISet(I_D(1,4))+I_D(3,4), I_D(0,2)+ISet(I_D(2,4)) ), true );
 379 }
 380
 381 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 382 void interval_set_contains_4_bicremental_types()
 383 {
 384     typedef IntervalSet<T> IntervalSetT;
 385     typedef typename IntervalSetT::interval_type IntervalT;
 386     //LAW: x.add(e).contains(e);
 387     //LAW: z = x + y => contains(z, x) && contains(z, y);
 388     T v1 = make<T>(1);
 389     T v3 = make<T>(3);
 390     T v5 = make<T>(5);
 391     T v7 = make<T>(7);
 392     T v8 = make<T>(8);
 393     T v9 = make<T>(9);
 394     T v11 = make<T>(11);
 395     IntervalSet<T> is(v1);
 396     BOOST_CHECK_EQUAL( icl::contains(is, v1), true );
 397
 398     BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().add(make<T>(2)), make<T>(2)), true );
 399     BOOST_CHECK_EQUAL( icl::contains(IntervalSet<T>().insert(make<T>(2)), make<T>(2)), true );
 400     BOOST_CHECK_EQUAL( icl::contains((is += IntervalT(v3,v7)), IntervalT(v3,v7)), true );
 401
 402     IntervalSet<T> is0 = is;
 403
 404     IntervalSet<T> is2(IntervalT::closed(v5,v8));
 405     is2.add(v9).add(v11);
 406     is += is2;
 407     BOOST_CHECK_EQUAL( contains(is, is2), true );
 408
 409     is = is0;
 410     IntervalSet<T> is3(IntervalT::closed(v5,v8));
 411     is3.insert(v9).insert(v11);
 412     is += is3;
 413     BOOST_CHECK_EQUAL( contains(is, is3), true );
 414 }
 415
 416
 417 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 418 void interval_set_operators_4_bicremental_types()
 419 {
 420     typedef IntervalSet<T> IntervalSetT;
 421     typedef typename IntervalSetT::interval_type IntervalT;
 422     T v0 = make<T>(0);
 423     T v1 = make<T>(1);
 424     T v3 = make<T>(3);
 425     T v5 = make<T>(5);
 426     T v7 = make<T>(7);
 427     T v8 = make<T>(8);
 428     IntervalSet<T> left, left2, right, all, all2, section, complement, naught;
 429     left.add(IntervalT::closed(v0,v1)).add(IntervalT::closed(v3,v5));
 430     (right += IntervalT::closed(v3,v5)) += IntervalT::closed(v7,v8);
 431
 432     BOOST_CHECK_EQUAL( disjoint(left, right), false );
 433
 434     (all += left) += right;
 435     (section += left) &= right;
 436     (complement += all) -= section;
 437     (all2 += section) += complement;
 438
 439     BOOST_CHECK_EQUAL( disjoint(section, complement), true );
 440     BOOST_CHECK_EQUAL( all, all2 );
 441
 442     BOOST_CHECK_EQUAL( icl::contains(all, left), true );
 443     BOOST_CHECK_EQUAL( icl::contains(all, right), true );
 444     BOOST_CHECK_EQUAL( icl::contains(all, complement), true );
 445
 446     BOOST_CHECK_EQUAL( icl::contains(left, section), true );
 447     BOOST_CHECK_EQUAL( icl::contains(right, section), true );
 448
 449     BOOST_CHECK_EQUAL( within(left, all), true );
 450     BOOST_CHECK_EQUAL( within(right, all), true );
 451     BOOST_CHECK_EQUAL( within(complement, all), true );
 452     BOOST_CHECK_EQUAL( within(section, left), true );
 453     BOOST_CHECK_EQUAL( within(section, right), true );
 454 }
 455
 456
 457 // Test for nontrivial intersection of interval sets with intervals and values
 458 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 459 void interval_set_base_intersect_4_bicremental_types()
 460 {
 461     typedef IntervalSet<T> IntervalSetT;
 462     typedef typename IntervalSetT::interval_type IntervalT;
 463     T v0 = make<T>(0);
 464     T v1 = make<T>(1);
 465     T v2 = make<T>(2);
 466     T v3 = make<T>(3);
 467     T v6 = make<T>(6);
 468     T v7 = make<T>(7);
 469     T v8 = make<T>(8);
 470     T v9 = make<T>(9);
 471
 472     IntervalT I0_3D = IntervalT::right_open(v0,v3);
 473     IntervalT I1_3D = IntervalT::right_open(v1,v3);
 474     IntervalT I1_8D = IntervalT::right_open(v1,v8);
 475     IntervalT I2_7D = IntervalT::right_open(v2,v7);
 476     IntervalT I2_3D = IntervalT::right_open(v2,v3);
 477     IntervalT I6_7D = IntervalT::right_open(v6,v7);
 478     IntervalT I6_8D = IntervalT::right_open(v6,v8);
 479     IntervalT I6_9D = IntervalT::right_open(v6,v9);
 480
 481     //--------------------------------------------------------------------------
 482     // IntervalSet
 483     //--------------------------------------------------------------------------
 484     //split_A      [0       3)       [6    9)
 485     //         &=      [1                8)
 486     //split_AB ->      [1   3)       [6  8)
 487     //         &=        [2             7)
 488     //         ->        [2 3)       [6 7)
 489     IntervalSet<T>    split_A, split_B, split_AB, split_ab, split_ab2;
 490
 491     split_A.add(I0_3D).add(I6_9D);
 492     split_AB = split_A;
 493     split_AB &= I1_8D;
 494     split_ab.add(I1_3D).add(I6_8D);
 495
 496     BOOST_CHECK_EQUAL( split_AB, split_ab );
 497
 498     split_AB = split_A;
 499     (split_AB &= I1_8D) &= I2_7D;
 500     split_ab2.add(I2_3D).add(I6_7D);
 501
 502     BOOST_CHECK_EQUAL( split_AB, split_ab2 );
 503
 504
 505     //--------------------------------------------------------------------------
 506     //split_A      [0       3)       [6    9)
 507     //         &=       1
 508     //split_AB ->      [1]
 509     //         +=         (1             7)
 510     //         ->      [1](1             7)
 511     split_A.add(I0_3D).add(I6_9D);
 512     split_AB = split_A;
 513     split_AB &= v1;
 514     split_ab.clear();
 515     split_ab.add(v1);
 516
 517     BOOST_CHECK_EQUAL( split_AB, split_ab );
 518
 519     split_AB = split_A;
 520     (split_AB &= v1) += IntervalT::open(v1,v7);
 521     split_ab2.clear();
 522     split_ab2 += IntervalT::right_open(v1,v7);
 523
 524     BOOST_CHECK_EQUAL( is_element_equal(split_AB, split_ab2), true );
 525 }
 526
 527
 528 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 529 void interval_set_flip_4_bicremental_types()
 530 {
 531     typedef IntervalSet<T> IntervalSetT;
 532     typedef typename IntervalSetT::interval_type IntervalT;
 533     typedef IntervalSetT ISet;
 534
 535     IntervalSetT set_a, set_b, lhs, rhs;
 536     //[0     2)
 537     //    [1     3)
 538     //[0 1)   [2 3) : {[0 2)} ^= [2 3)
 539     //gcc seed ambiguities with std::_Ios_Iostate& std::operator^= here:
 540     // BOOST_CHECK_EQUAL(ISet(I_D(0,2)) ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3));
 541     set_a = ISet(I_D(0,2));
 542     BOOST_CHECK_EQUAL(set_a ^= I_D(1,3), ISet(I_D(0,1)) + I_D(2,3));
 543
 544     //    [1     3)
 545     //[0     2)
 546     //[0 1)   [2 3) : {[1 3)} ^= [0 2)
 547     set_a = ISet(I_D(1,3));
 548     BOOST_CHECK_EQUAL(set_a ^= I_D(0,2), ISet(I_D(0,1)) + I_D(2,3));
 549
 550     //[0     2)      (3  5]
 551     //    [1      3)
 552     //[0 1)   [2  3) (3  5] : a ^= b
 553     set_a.clear();
 554     set_a.add(I_D(0,2)).add(C_I(3,5));
 555     set_b.add(I_D(1,3));
 556     lhs = set_a;
 557     lhs ^= set_b;
 558     rhs.add(I_D(0,1)).add(I_D(2,3)).add(C_I(3,5));
 559     BOOST_CHECK_EQUAL(lhs, rhs);
 560 }
 561
 562
 563 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 564 void interval_set_infix_plus_overload_4_bicremental_types()
 565 {
 566     typedef IntervalSet<T> IntervalSetT;
 567     typedef typename IntervalSetT::interval_type IntervalT;
 568     IntervalT itv = I_D(3,5);
 569
 570     IntervalSetT set_a, set_b;
 571     set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
 572     set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
 573
 574     BOOST_CHECK_EQUAL(set_a + set_b, set_b + set_a);
 575     // This checks all cases of is_interval_set_derivative<T>
 576     BOOST_CHECK_EQUAL(set_a + itv, itv + set_a);
 577     BOOST_CHECK_EQUAL(set_b + MK_v(4), MK_v(4) + set_b);
 578 }
 579
 580
 581 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 582 void interval_set_infix_pipe_overload_4_bicremental_types()
 583 {
 584     typedef IntervalSet<T> IntervalSetT;
 585     typedef typename IntervalSetT::interval_type IntervalT;
 586
 587     IntervalT itv = I_D(3,5);
 588
 589     IntervalSetT set_a, set_b;
 590     set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
 591     set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
 592
 593     BOOST_CHECK_EQUAL(set_a | set_b, set_b | set_a);
 594     //This checks all cases of is_interval_set_derivative<T>
 595     BOOST_CHECK_EQUAL(set_a | itv, itv | set_a);
 596     BOOST_CHECK_EQUAL(set_b | MK_v(4), MK_v(4) | set_b);
 597 }
 598
 599
 600
 601 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 602 void interval_set_infix_minus_overload_4_bicremental_types()
 603 {
 604     typedef IntervalSet<T> IntervalSetT;
 605     typedef typename IntervalSetT::interval_type IntervalT;
 606
 607     IntervalT itv = I_D(3,5);
 608
 609     IntervalSetT set_a, set_b;
 610     set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
 611     set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
 612
 613     BOOST_CHECK_EQUAL(set_a - set_b, (set_b + set_a) - set_b);
 614     //This checks all cases of is_interval_set_derivative<T>
 615     BOOST_CHECK_EQUAL(set_a - itv, (itv + set_a)  - itv);
 616     BOOST_CHECK_EQUAL(set_b - MK_v(4), (MK_v(4) + set_b) - MK_v(4));
 617 }
 618
 619
 620 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 621 void interval_set_infix_et_overload_4_bicremental_types()
 622 {
 623     typedef IntervalSet<T> IntervalSetT;
 624     typedef typename IntervalSetT::interval_type IntervalT;
 625
 626     IntervalT itv = I_D(3,5);
 627
 628     IntervalSetT set_a, set_b;
 629     set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
 630     set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
 631
 632     BOOST_CHECK_EQUAL(set_a & set_b, set_b & set_a);
 633     //This checks all cases of is_interval_set_derivative<T>
 634     BOOST_CHECK_EQUAL(set_a & itv, itv & set_a);
 635     BOOST_CHECK_EQUAL(set_b & MK_v(4), MK_v(4) & set_b);
 636 }
 637
 638
 639
 640 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 641 void interval_set_infix_caret_overload_4_bicremental_types()
 642 {
 643     typedef IntervalSet<T> IntervalSetT;
 644     typedef typename IntervalSetT::interval_type IntervalT;
 645
 646     IntervalT itv = I_D(3,5);
 647
 648     IntervalSetT set_a, set_b;
 649     set_a.add(C_D(1,3)).add(I_D(8,9)).add(I_I(6,11));
 650     set_b.add(I_D(0,9)).add(I_I(3,6)).add(I_D(5,7));
 651
 652     BOOST_CHECK_EQUAL(set_a ^ set_b, set_b ^ set_a);
 653     //This checks all cases of is_interval_set_derivative<T>
 654     BOOST_CHECK_EQUAL(set_a ^ itv, itv ^ set_a);
 655     BOOST_CHECK_EQUAL(set_b ^ MK_v(4), MK_v(4) ^ set_b);
 656 }
 657
 658
 659
 660 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 661 void interval_set_find_4_bicremental_types()
 662 {
 663     typedef IntervalSet<T> IntervalSetT;
 664     typedef typename IntervalSetT::interval_type IntervalT;
 665     typedef typename IntervalSetT::const_iterator c_iterator;
 666
 667     IntervalSetT set_a;
 668     set_a.add(C_D(1,3)).add(I_I(6,11));
 669
 670     typename IntervalSetT::const_iterator found = set_a.find(MK_v(6));
 671
 672     BOOST_CHECK_EQUAL( *found, I_I(6,11) );
 673
 674     found = set_a.find(MK_v(5));
 675
 676     BOOST_CHECK_EQUAL( found == set_a.end(), true );
 677
 678     c_iterator found1 = set_a.find(MK_v(6));
 679     c_iterator found2 = icl::find(set_a, MK_v(6));
 680
 681     BOOST_CHECK      ( found1 == found2 );
 682     BOOST_CHECK_EQUAL( *found1, *found2 );
 683     BOOST_CHECK_EQUAL( *found1, I_I(6,11) );
 684
 685     found1 = set_a.find(MK_v(5));
 686
 687     BOOST_CHECK_EQUAL( found1 == set_a.end(), true );
 688
 689     //LAW map c; key k: k in dom(c) => contains(c, *find(c, k))
 690     BOOST_CHECK( icl::contains(set_a, *icl::find(set_a, MK_v(2))) );
 691     BOOST_CHECK( icl::contains(set_a, *set_a.find(MK_v(11))) );
 692
 693     BOOST_CHECK(  icl::contains(set_a, MK_v(2)) );
 694     BOOST_CHECK(  icl::contains(set_a, MK_v(10)) );
 695     BOOST_CHECK( !icl::contains(set_a, MK_v(1)) );
 696     BOOST_CHECK( !icl::contains(set_a, MK_v(3)) );
 697
 698     BOOST_CHECK(  icl::intersects(set_a, MK_v(2)) );
 699     BOOST_CHECK(  icl::intersects(set_a, MK_v(10)) );
 700     BOOST_CHECK( !icl::intersects(set_a, MK_v(1)) );
 701     BOOST_CHECK( !icl::intersects(set_a, MK_v(3)) );
 702 }
 703
 704
 705 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 706 void interval_set_intersects_4_bicremental_types()
 707 {
 708     typedef IntervalSet<T> IntervalSetT;
 709     typedef typename IntervalSetT::interval_type IntervalT;
 710     typedef typename IntervalSetT::key_type      KeyT;
 711
 712     IntervalT between = I_D(3,5);
 713
 714     IntervalSetT set_a;
 715     set_a.add(C_D(1,3)).add(I_I(6,11));
 716     //         (1   3)         [6    11]
 717     BOOST_CHECK( icl::intersects(set_a, MK_v(2)) );
 718     BOOST_CHECK( icl::intersects(set_a, MK_v(11)) );
 719     BOOST_CHECK( icl::disjoint(set_a, MK_v(3)) );
 720     BOOST_CHECK( icl::disjoint(set_a, MK_v(5)) );
 721
 722     BOOST_CHECK( icl::intersects(set_a, C_D(1,3)) );
 723     BOOST_CHECK( icl::intersects(set_a, I_D(8,10)) );
 724     BOOST_CHECK( icl::disjoint(set_a, between) );
 725     BOOST_CHECK( icl::disjoint(set_a, I_I(0,1)) );
 726
 727     IntervalSetT to_12 = IntervalSetT(I_D(0, 13));
 728     IntervalSetT complement_a = to_12 - set_a;
 729     BOOST_CHECK( icl::disjoint(set_a, complement_a) );
 730     BOOST_CHECK( icl::intersects(to_12, set_a) );
 731
 732     BOOST_CHECK_EQUAL( icl::lower(set_a), icl::lower(*(set_a.begin())) );
 733     BOOST_CHECK_EQUAL( icl::lower(set_a), MK_v(1) );
 734     BOOST_CHECK_EQUAL( icl::upper(set_a), icl::upper(*(set_a.rbegin())) );
 735     BOOST_CHECK_EQUAL( icl::upper(set_a), MK_v(11) );
 736 }
 737
 738
 739 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 740 void interval_set_range_4_discrete_types()
 741 {
 742     typedef IntervalSet<T> IntervalSetT;
 743     typedef typename IntervalSetT::interval_type IntervalT;
 744     typedef typename IntervalSetT::key_type      KeyT;
 745
 746     IntervalSetT set_a;
 747     set_a.add(C_D(1,3)).add(I_I(6,11));
 748     //         (1   3)         [6    11]
 749     BOOST_CHECK_EQUAL( icl::first(set_a), icl::first(*(set_a.begin())) );
 750     BOOST_CHECK_EQUAL( icl::first(set_a), MK_v(2) );
 751     BOOST_CHECK_EQUAL( icl::last(set_a), icl::last(*(set_a.rbegin())) );
 752     BOOST_CHECK_EQUAL( icl::last(set_a), MK_v(11) );
 753 }
 754
 755
 756 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 757 void interval_bitset_find_4_integral_types()
 758 {
 759     typedef IntervalSet<T> IntervalSetT;
 760     typedef typename IntervalSetT::interval_type IntervalT;
 761     typedef typename IntervalSetT::bitset_type BitsT;
 762
 763     IntervalT itv = I_D(3,5);
 764
 765     IntervalSetT set_a;
 766     set_a.add(C_D(1,3)).add(I_I(6,11));
 767
 768     typename IntervalSetT::const_iterator found = set_a.find(MK_v(6));
 769
 770     BOOST_CHECK( (found->second).contains(6) );
 771
 772     found = set_a.find(MK_v(5));
 773     BOOST_CHECK( found == set_a.end() );
 774
 775     set_a.add(MK_v(64));
 776     found = set_a.find(MK_v(64));
 777     BOOST_CHECK( (found->second).contains(0) );
 778
 779     set_a.add(MK_v(65));
 780     found = set_a.find(MK_v(65));
 781     BOOST_CHECK( (found->second).contains(1) );
 782
 783     found = set_a.find(MK_v(66));
 784     BOOST_CHECK( found == set_a.end() );
 785 }
 786
 787 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 788 void interval_set_element_iter_4_discrete_types()
 789 {
 790     typedef IntervalSet<T> IntervalSetT;
 791     typedef typename IntervalSetT::interval_type IntervalT;
 792     typedef std::vector<T> VectorT;
 793
 794     IntervalSetT set_a;
 795     set_a.add(I_I(1,3)).add(I_I(6,7));
 796
 797     VectorT vec(5), cev(5);
 798     vec[0]=MK_v(1);vec[1]=MK_v(2);vec[2]=MK_v(3);vec[3]=MK_v(6);vec[4]=MK_v(7);
 799     cev[0]=MK_v(7);cev[1]=MK_v(6);cev[2]=MK_v(3);cev[3]=MK_v(2);cev[4]=MK_v(1);
 800
 801     VectorT dest;
 802     std::copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest));
 803     BOOST_CHECK_EQUAL( vec == dest, true );
 804
 805     dest.clear();
 806     std::copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest));
 807     BOOST_CHECK_EQUAL( cev == dest, true );
 808
 809     dest.clear();
 810     std::reverse_copy(elements_begin(set_a), elements_end(set_a), std::back_inserter(dest));
 811     BOOST_CHECK_EQUAL( cev == dest, true );
 812
 813     dest.clear();
 814     std::reverse_copy(elements_rbegin(set_a), elements_rend(set_a), std::back_inserter(dest));
 815     BOOST_CHECK_EQUAL( vec == dest, true );
 816 }
 817
 818
 819 template <ICL_IntervalSet_TEMPLATE(_T) IntervalSet, class T>
 820 void interval_set_move_4_discrete_types()
 821 {
 822     typedef IntervalSet<T> IntervalSetT;
 823     typedef typename IntervalSetT::interval_type IntervalT;
 824     typedef std::vector<T> VectorT;
 825
 826     //JODO static_cast fails for gcc compilers
 827     //IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4)))));
 828     IntervalSetT set_A(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,4)).add(I_D(0,0)) )));
 829     IntervalSetT set_B(boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_D(0,2)).add(I_D(2,4)).add(I_D(0,4)))));
 830
 831     BOOST_CHECK( icl::is_element_equal(set_A, set_B) );
 832     BOOST_CHECK_EQUAL( set_A, join(set_B) );
 833
 834     //JODO static_cast fails for gcc compilers
 835     //set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4))));
 836     set_A = boost::move(static_cast<IntervalSetT&>(IntervalSetT(I_I(1,4)).add(I_D(0,0))));
 837     set_B = boost::move(static_cast<IntervalSetT&>(IntervalSetT(C_I(0,2)).insert(I_D(3,5)).add(C_D(0,5))));
 838
 839     BOOST_CHECK( icl::is_element_equal(set_A, set_B) );
 840     BOOST_CHECK_EQUAL( set_A, join(set_B) );
 841 }
 842
 843
 844
 845 #endif // LIBS_ICL_TEST_TEST_INTERVAL_SET_SHARED_HPP_JOFA_080920
 846