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

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2012: 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_MAP_SHARED_HPP_JOFA_081005
   9 #define LIBS_ICL_TEST_TEST_INTERVAL_MAP_SHARED_HPP_JOFA_081005
  10
  11 #include "portability.hpp"
  12
  13 template
  14 <
  15 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
  16     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
  17 #else
  18     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
  19 #endif
  20     class T, class U
  21 >
  22 void interval_map_fundamentals_4_ordered_types()
  23 {
  24     typedef IntervalMap<T,U> IntervalMapT;
  25     typedef typename IntervalMapT::interval_type   IntervalT;
  26     typedef typename IntervalMapT::size_type       size_T;
  27     typedef typename IntervalMapT::difference_type diff_T;
  28
  29     // ordered types is the largest set of instance types.
  30     // Because we can not generate values via incrementation for e.g. string,
  31     // we are able to test operations only for the most basic values
  32     // identity_element (0, empty, T() ...) and unit_element.
  33
  34     T v0 = boost::icl::identity_element<T>::value();
  35     T v1 = unit_element<T>::value();
  36     IntervalT I0_0I(v0);
  37     IntervalT I1_1I(v1);
  38 #ifndef BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
  39     IntervalT I0_1I(v0, v1, interval_bounds::closed());
  40 #else
  41     IntervalT I0_1I = icl::interval<T>::closed(v0, v1);
  42 #endif
  43     U u1 = unit_element<U>::value();
  44
  45     //-------------------------------------------------------------------------
  46     //empty set
  47     //-------------------------------------------------------------------------
  48     BOOST_CHECK_EQUAL(IntervalMapT().empty(), true);
  49     BOOST_CHECK_EQUAL(icl::is_empty(IntervalMapT()), true);
  50     BOOST_CHECK_EQUAL(cardinality(IntervalMapT()), boost::icl::identity_element<size_T>::value());
  51     BOOST_CHECK_EQUAL(IntervalMapT().size(), boost::icl::identity_element<size_T>::value());
  52     BOOST_CHECK_EQUAL(icl::size(IntervalMapT()), boost::icl::identity_element<size_T>::value());
  53     BOOST_CHECK_EQUAL(interval_count(IntervalMapT()), 0);
  54     BOOST_CHECK_EQUAL(IntervalMapT().iterative_size(), 0);
  55     BOOST_CHECK_EQUAL(iterative_size(IntervalMapT()), 0);
  56     BOOST_CHECK_EQUAL(IntervalMapT(), IntervalMapT());
  57
  58     IntervalT mt_interval = boost::icl::identity_element<IntervalT >::value();
  59     BOOST_CHECK_EQUAL(mt_interval, IntervalT());
  60     typename IntervalMapT::value_type mt_u1 = make_pair(mt_interval, u1);
  61     IntervalMapT mt_map = boost::icl::identity_element<IntervalMapT >::value();
  62     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  63
  64     //adding emptieness to emptieness yields emptieness ;)
  65     mt_map.add(mt_u1).add(mt_u1);
  66     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  67     mt_map.insert(mt_u1).insert(mt_u1);
  68     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  69     (mt_map += mt_u1) += mt_u1;
  70     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  71     BOOST_CHECK_EQUAL(hull(mt_map), boost::icl::identity_element<IntervalT >::value());
  72
  73     //subtracting emptieness
  74     mt_map.subtract(mt_u1).subtract(mt_u1);
  75     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  76
  77     mt_map.erase(mt_interval).erase(mt_interval);
  78     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  79     (mt_map -= mt_u1) -= mt_u1;
  80     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  81
  82     //subtracting elements form emptieness
  83     typename IntervalMapT::domain_mapping_type v0_u1 = make_pair(v0,u1);
  84     typename IntervalMapT::domain_mapping_type v1_u1 = make_pair(v1,u1);
  85     //mt_map.subtract(make_pair(v0,u1)).subtract(make_pair(v1,u1));
  86     mt_map.subtract(v0_u1).subtract(v1_u1);
  87     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  88     mt_map.erase(v0_u1).erase(v1_u1);
  89     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  90     (mt_map -= v0_u1) -= v1_u1;
  91     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  92
  93     //subtracting intervals form emptieness
  94     typename IntervalMapT::segment_type I0_0I_u1 = make_pair(I0_0I,u1);
  95     typename IntervalMapT::segment_type I0_1I_u1 = make_pair(I0_1I,u1);
  96     typename IntervalMapT::segment_type I1_1I_u1 = make_pair(I1_1I,u1);
  97     mt_map.subtract(I0_1I_u1).subtract(I1_1I_u1);
  98     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
  99     mt_map.erase(I0_1I_u1).erase(I1_1I_u1);
 100     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
 101     (mt_map -= I0_1I_u1) -= I1_1I_u1;
 102     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
 103
 104     mt_map.erase(I0_1I).erase(I1_1I);
 105     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
 106
 107     //insecting emptieness
 108     (mt_map &= mt_u1) &= mt_u1;
 109     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
 110     (mt_map &= mt_interval) &= mt_interval;
 111     BOOST_CHECK_EQUAL(mt_map, IntervalMapT());
 112
 113
 114
 115     //-------------------------------------------------------------------------
 116     //unary set
 117     //-------------------------------------------------------------------------
 118     IntervalMapT single_I0_0I_u1_from_element(v0_u1);
 119     IntervalMapT single_I0_0I_u1_from_interval(I0_0I_u1);
 120     IntervalMapT single_I0_0I_u1(single_I0_0I_u1_from_interval);
 121
 122     BOOST_CHECK_EQUAL(single_I0_0I_u1_from_element, single_I0_0I_u1_from_interval);
 123     BOOST_CHECK_EQUAL(single_I0_0I_u1_from_element, single_I0_0I_u1);
 124     BOOST_CHECK_EQUAL(hull(single_I0_0I_u1), I0_0I);
 125     BOOST_CHECK_EQUAL(hull(single_I0_0I_u1).lower(), I0_0I.lower());
 126     BOOST_CHECK_EQUAL(hull(single_I0_0I_u1).upper(), I0_0I.upper());
 127
 128     IntervalMapT single_I1_1I_u1_from_element(v1_u1);
 129     IntervalMapT single_I1_1I_u1_from_interval(I1_1I_u1);
 130     IntervalMapT single_I1_1I_u1(single_I1_1I_u1_from_interval);
 131
 132     BOOST_CHECK_EQUAL(single_I1_1I_u1_from_element, single_I1_1I_u1_from_interval);
 133     BOOST_CHECK_EQUAL(single_I1_1I_u1_from_element, single_I1_1I_u1);
 134
 135     IntervalMapT single_I0_1I_u1_from_interval(I0_1I_u1);
 136     IntervalMapT single_I0_1I_u1(single_I0_1I_u1_from_interval);
 137
 138     BOOST_CHECK_EQUAL(single_I0_1I_u1_from_interval, single_I0_1I_u1);
 139     BOOST_CHECK_EQUAL(hull(single_I0_1I_u1), I0_1I);
 140     BOOST_CHECK_EQUAL(hull(single_I0_1I_u1).lower(), I0_1I.lower());
 141     BOOST_CHECK_EQUAL(hull(single_I0_1I_u1).upper(), I0_1I.upper());
 142
 143     //contains predicate
 144     BOOST_CHECK_EQUAL(icl::contains(single_I0_0I_u1, v0), true);
 145     BOOST_CHECK_EQUAL(icl::contains(single_I0_0I_u1, v0_u1), true);
 146     BOOST_CHECK_EQUAL(icl::contains(single_I0_0I_u1, I0_0I_u1), true);
 147
 148     BOOST_CHECK_EQUAL(icl::contains(single_I1_1I_u1, v1), true);
 149     BOOST_CHECK_EQUAL(icl::contains(single_I1_1I_u1, v1_u1), true);
 150     BOOST_CHECK_EQUAL(icl::contains(single_I1_1I_u1, I1_1I_u1), true);
 151
 152     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, v0), true);
 153     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, I0_1I_u1), true);
 154     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, v1), true);
 155     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, I1_1I_u1), true);
 156
 157     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, single_I0_0I_u1), true);
 158     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, single_I1_1I_u1), true);
 159     BOOST_CHECK_EQUAL(icl::contains(single_I0_1I_u1, single_I0_1I_u1), true);
 160
 161     BOOST_CHECK_EQUAL(cardinality(single_I0_0I_u1), unit_element<size_T>::value());
 162     BOOST_CHECK_EQUAL(single_I0_0I_u1.size(), unit_element<size_T>::value());
 163     BOOST_CHECK_EQUAL(interval_count(single_I0_0I_u1), 1);
 164     BOOST_CHECK_EQUAL(single_I0_0I_u1.iterative_size(), 1);
 165     BOOST_CHECK_EQUAL(iterative_size(single_I0_0I_u1), 1);
 166
 167 }
 168
 169 template
 170 <
 171 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 172     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 173 #else
 174     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 175 #endif
 176     class T, class U
 177 >
 178 void interval_map_ctor_4_bicremental_types()
 179 {
 180     typedef IntervalMap<T,U> IntervalMapT;
 181     typedef typename IntervalMapT::interval_type   IntervalT;
 182
 183     T v4 = make<T>(4);
 184     U u2 = make<U>(2);
 185     IntervalT I4_4I(v4);
 186     typename IntervalMapT::domain_mapping_type v4_u2(v4,u2);
 187     typename IntervalMapT::value_type I4_4I_u2(I4_4I,u2);
 188
 189     IntervalMapT _I4_4I_u2;
 190     BOOST_CHECK_EQUAL( _I4_4I_u2.empty(), true );
 191     IntervalMapT _I4_4I_u2_1;
 192     IntervalMapT _I4_4I_u2_2;
 193     IntervalMapT _I4_4I_u2_3;
 194     _I4_4I_u2   += v4_u2;
 195     _I4_4I_u2_1 += I4_4I_u2;
 196     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_1 );
 197     _I4_4I_u2_2.add(v4_u2);
 198     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_2 );
 199     _I4_4I_u2_3.add(I4_4I_u2);
 200     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_3 );
 201
 202     _I4_4I_u2.clear();
 203     _I4_4I_u2.add(I4_4I_u2).add(I4_4I_u2);
 204     IntervalMapT _I4_4I_u4(make_pair(I4_4I, make<U>(4)));
 205     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u4 );
 206
 207     _I4_4I_u2.clear();
 208     _I4_4I_u2.insert(I4_4I_u2).insert(I4_4I_u2);
 209     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_1 );
 210
 211     BOOST_CHECK_EQUAL( cardinality(_I4_4I_u2), unit_element<typename IntervalMapT::size_type>::value()  );
 212     BOOST_CHECK_EQUAL( _I4_4I_u2.size(),       unit_element<typename IntervalMapT::size_type>::value()  );
 213     BOOST_CHECK_EQUAL( interval_count(_I4_4I_u2),   1  );
 214     BOOST_CHECK_EQUAL( _I4_4I_u2.iterative_size(),  1  );
 215     BOOST_CHECK_EQUAL( iterative_size(_I4_4I_u2),   1  );
 216
 217     if(has_dynamic_bounds<IntervalT>::value)
 218     {
 219         BOOST_CHECK_EQUAL( hull(_I4_4I_u2).lower(), v4 );
 220         BOOST_CHECK_EQUAL( hull(_I4_4I_u2).upper(), v4 );
 221     }
 222
 223     IntervalMapT _I4_4I_u2_copy(_I4_4I_u2);
 224     IntervalMapT _I4_4I_u2_assigned;
 225     _I4_4I_u2_assigned = _I4_4I_u2;
 226     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_copy );
 227     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_assigned );
 228
 229     _I4_4I_u2_assigned.clear();
 230     BOOST_CHECK_EQUAL( true,   _I4_4I_u2_assigned.empty() );
 231
 232     _I4_4I_u2_assigned.swap(_I4_4I_u2_copy);
 233     BOOST_CHECK_EQUAL( true,   _I4_4I_u2_copy.empty() );
 234     BOOST_CHECK_EQUAL( _I4_4I_u2, _I4_4I_u2_assigned );
 235 }
 236
 237
 238 template
 239 <
 240 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 241     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 242 #else
 243     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 244 #endif
 245     class T, class U
 246 >
 247 void interval_map_add_sub_4_bicremental_types()
 248 {
 249     typedef IntervalMap<T,U> IntervalMapT;
 250     typedef typename IntervalMapT::interval_type   IntervalT;
 251
 252     T v0 = make<T>(0);
 253     T v5 = make<T>(5);
 254     T v6 = make<T>(6);
 255     T v9 = make<T>(9);
 256     U u1 = make<U>(1);
 257 #ifndef BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
 258     IntervalT I5_6I(v5,v6, interval_bounds::closed());
 259     IntervalT I5_9I(v5,v9, interval_bounds::closed());
 260     IntervalT I0_9I = IntervalT::closed(v0, v9);
 261 #else
 262     IntervalT I5_6I = icl::interval<T>::closed(v5,v6);
 263     IntervalT I5_9I = icl::interval<T>::closed(v5,v9);
 264     IntervalT I0_9I = icl::interval<T>::closed(v0,v9);
 265 #endif
 266     typename IntervalMapT::domain_mapping_type v0_u1 = make_pair(v0, u1);
 267     typename IntervalMapT::domain_mapping_type v9_u1 = make_pair(v9, u1);
 268     typename IntervalMapT::value_type I5_6I_u1 = make_pair(I5_6I, u1);
 269     typename IntervalMapT::value_type I5_9I_u1 = make_pair(I5_9I, u1);
 270
 271     BOOST_CHECK_EQUAL( IntervalMapT(I5_6I_u1).add(v0_u1).add(v9_u1),
 272                        IntervalMapT().add(v9_u1).add(I5_6I_u1).add(v0_u1) );
 273
 274     IntervalMapT map_A = IntervalMapT(I5_6I_u1).add(v0_u1).add(v9_u1);
 275     IntervalMapT map_B = IntervalMapT().insert(v9_u1).insert(I5_6I_u1).insert(v0_u1);
 276     BOOST_CHECK_EQUAL( map_A, map_B );
 277     BOOST_CHECK_EQUAL( hull(map_A), I0_9I );
 278     BOOST_CHECK_EQUAL( hull(map_A).lower(), I0_9I.lower() );
 279     BOOST_CHECK_EQUAL( hull(map_A).upper(), I0_9I.upper() );
 280
 281     IntervalMapT map_A1 = map_A, map_B1 = map_B,
 282                  map_A2 = map_A, map_B2 = map_B;
 283
 284     map_A1.subtract(I5_6I_u1).subtract(v9_u1);
 285     map_B1.erase(v9_u1).erase(I5_6I_u1);
 286     BOOST_CHECK_EQUAL( map_A1, map_B1 );
 287
 288     map_B1 = map_B;
 289     map_B2.erase(v9).erase(I5_6I);
 290     BOOST_CHECK_EQUAL( map_A1, map_B2 );
 291
 292     map_A2.subtract(I5_9I_u1);
 293     map_B2.erase(I5_9I);
 294     BOOST_CHECK_EQUAL( map_A2, map_B2 );
 295 }
 296
 297 template
 298 <
 299 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 300     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 301 #else
 302     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 303 #endif
 304     class T, class U
 305 >
 306 void interval_map_distinct_4_bicremental_types()
 307 {
 308     typedef IntervalMap<T,U> IntervalMapT;
 309     typedef typename IntervalMapT::interval_type   IntervalT;
 310     typedef typename IntervalMap<T,U>::size_type       size_T;
 311     typedef typename IntervalMap<T,U>::difference_type diff_T;
 312     T v1 = make<T>(1);
 313     T v3 = make<T>(3);
 314     T v5 = make<T>(5);
 315     U u1 = make<U>(1);
 316     typename IntervalMapT::domain_mapping_type v1_u1(v1,u1);
 317     typename IntervalMapT::domain_mapping_type v3_u1(v3,u1);
 318     typename IntervalMapT::domain_mapping_type v5_u1(v5,u1);
 319
 320     size_T s3 = make<size_T>(3);
 321
 322     IntervalMapT is_1_3_5;
 323     is_1_3_5.add(v1_u1).add(v3_u1).add(v5_u1);
 324
 325     BOOST_CHECK_EQUAL( cardinality(is_1_3_5),      s3 );
 326     BOOST_CHECK_EQUAL( is_1_3_5.size(),             s3 );
 327     BOOST_CHECK_EQUAL( interval_count(is_1_3_5),   3 );
 328     BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(),   3 );
 329     BOOST_CHECK_EQUAL( iterative_size(is_1_3_5),   3 );
 330 }
 331
 332 template
 333 <
 334 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 335     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 336 #else
 337     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 338 #endif
 339     class T, class U
 340 >
 341 void interval_map_distinct_4_bicremental_continuous_types()
 342 {
 343 #ifndef BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
 344
 345     typedef IntervalMap<T,U> IntervalMapT;
 346     typedef typename IntervalMapT::interval_type   IntervalT;
 347     typedef typename IntervalMapT::size_type       size_T;
 348     typedef typename IntervalMapT::difference_type diff_T;
 349     T v1 = make<T>(1);
 350     T v3 = make<T>(3);
 351     T v5 = make<T>(5);
 352     U u1 = make<U>(1);
 353     typename IntervalMapT::domain_mapping_type v1_u1(v1,u1);
 354     typename IntervalMapT::domain_mapping_type v3_u1(v3,u1);
 355     typename IntervalMapT::domain_mapping_type v5_u1(v5,u1);
 356
 357     size_T s3 = make<size_T>(3);
 358     diff_T d0 = make<diff_T>(0);
 359     diff_T d2 = make<diff_T>(2);
 360
 361     IntervalMapT is_1_3_5;
 362     is_1_3_5.add(v1_u1).add(v3_u1).add(v5_u1);
 363
 364     BOOST_CHECK_EQUAL( cardinality(is_1_3_5),      s3 );
 365     BOOST_CHECK_EQUAL( is_1_3_5.size(),            s3 );
 366     icl::length(is_1_3_5);
 367     BOOST_CHECK_EQUAL( icl::length(is_1_3_5),      d0 );
 368     BOOST_CHECK_EQUAL( interval_count(is_1_3_5),   3 );
 369     BOOST_CHECK_EQUAL( is_1_3_5.iterative_size(),  3 );
 370     BOOST_CHECK_EQUAL( iterative_size(is_1_3_5),   3 );
 371
 372
 373     IntervalMapT is_123_5;
 374     is_123_5 = is_1_3_5;
 375     //OPROM: open problem: Ambiguity resolving value_type and mapping_type for overloaded o= operators.
 376     //is_123_5 += make_pair(IntervalT::open(v1,v3),u1);                 //error C2593: 'operator +=' is ambiguous
 377     //is_123_5 += make_pair<IntervalT, U>(IntervalT::open(v1,v3),u1); //error C2593: 'operator +=' is ambiguous
 378     //USASO: unsatisfctory solution 1: explicit IntervalMapT::value_type instead of make_pair
 379     is_123_5 += typename IntervalMapT::value_type(icl::interval<T>::open(v1,v3),u1);
 380     //USASO: unsatisfctory solution 2: not implementing mapping_type version of o=
 381
 382     BOOST_CHECK_EQUAL( cardinality(is_123_5),      icl::infinity<size_T>::value() );
 383     BOOST_CHECK_EQUAL( is_123_5.size(),            icl::infinity<size_T>::value() );
 384     BOOST_CHECK_EQUAL( icl::length(is_123_5),      d2 );
 385
 386 #endif //BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
 387 }
 388
 389 template
 390 <
 391 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 392     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 393 #else
 394     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 395 #endif
 396     class T, class U
 397 >
 398 void interval_map_isolate_4_bicremental_continuous_types()
 399 {
 400 #ifndef BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
 401
 402     typedef IntervalMap<T,U> IntervalMapT;
 403     typedef typename IntervalMapT::interval_type   IntervalT;
 404     typedef typename IntervalMapT::size_type       size_T;
 405     typedef typename IntervalMapT::difference_type diff_T;
 406
 407     T v0 = make<T>(0);
 408     T v2 = make<T>(2);
 409     T v4 = make<T>(4);
 410     U u1 = make<U>(1);
 411     IntervalT I0_4I = icl::interval<T>::closed(v0,v4);
 412     IntervalT C0_2D = icl::interval<T>::open(v0,v2);
 413     IntervalT C2_4D = icl::interval<T>::open(v2,v4);
 414     typename IntervalMapT::value_type I0_4I_u1(I0_4I,u1);
 415     typename IntervalMapT::value_type C0_2D_u1(C0_2D,u1);
 416     typename IntervalMapT::value_type C2_4D_u1(C2_4D,u1);
 417     //   {[0               4]}
 418     // - {   (0,2)   (2,4)   }
 419     // = {[0]     [2]     [4]}
 420     IntervalMapT iso_map = IntervalMapT(I0_4I_u1);
 421     IntervalMapT gap_set;
 422     gap_set.add(C0_2D_u1).add(C2_4D_u1);
 423     iso_map -= gap_set;
 424
 425     BOOST_CHECK_EQUAL( cardinality(iso_map), static_cast<size_T>(3) );
 426     BOOST_CHECK_EQUAL( iso_map.iterative_size(), static_cast<std::size_t>(3) );
 427     BOOST_CHECK_EQUAL( iterative_size(iso_map), static_cast<std::size_t>(3) );
 428     BOOST_CHECK_EQUAL( iterative_size(iso_map), static_cast<std::size_t>(3) );
 429
 430     IntervalMapT iso_map2;
 431     iso_map2.add(I0_4I_u1);
 432     iso_map2.subtract(C0_2D_u1).subtract(C2_4D_u1);
 433
 434     IntervalMapT iso_map3(I0_4I_u1);
 435     (iso_map3 -= C0_2D_u1) -= C2_4D_u1;
 436
 437     IntervalMapT iso_map4;
 438     iso_map4.insert(I0_4I_u1);
 439     iso_map4.erase(C0_2D_u1).erase(C2_4D_u1);
 440
 441     BOOST_CHECK_EQUAL( iso_map, iso_map2 );
 442     BOOST_CHECK_EQUAL( iso_map, iso_map3 );
 443     BOOST_CHECK_EQUAL( iso_map, iso_map4 );
 444 #endif //BOOST_ICL_USE_STATIC_BOUNDED_INTERVALS
 445 }
 446
 447
 448 template
 449 <
 450 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 451     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 452 #else
 453     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 454 #endif
 455     class T, class U
 456 >
 457 void interval_map_contains_4_bicremental_types()
 458 {
 459     typedef IntervalMap<T,U> IntervalMapT;
 460     typedef typename IntervalMapT::interval_type   IntervalT;
 461     typedef typename IntervalMapT::set_type IntervalSetT;
 462
 463     IntervalMapT itv_map;
 464     itv_map.add(K_v(3,1));
 465
 466     BOOST_CHECK_EQUAL( icl::contains(itv_map, MK_v(3)), true );
 467     BOOST_CHECK_EQUAL( icl::contains(itv_map, K_v(3,1)), true );
 468
 469     BOOST_CHECK_EQUAL( icl::contains(IntervalMapT().add(K_v(3,1)), K_v(3,1)), true );
 470     BOOST_CHECK_EQUAL( icl::contains(IntervalMapT().add(K_v(3,1)), MK_v(3)), true );
 471     BOOST_CHECK_EQUAL( icl::contains(IntervalMapT().insert(K_v(3,1)), K_v(3,1)), true );
 472     itv_map.clear();
 473     BOOST_CHECK_EQUAL( icl::contains((itv_map += IIv(3,7,1)), IIv(3,7,1)), true );
 474     BOOST_CHECK_EQUAL( icl::contains(itv_map, IIv(3,7,2)), false );
 475     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(3,7)),   true );
 476     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(4,6)),   true );
 477     BOOST_CHECK_EQUAL( icl::contains((itv_map += CIv(7,9,1)),IIv(3,9,1)), true );
 478     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(4,8)),   true );
 479     BOOST_CHECK_EQUAL( icl::contains((itv_map += IIv(11,12,1)), IIv(3,12,1)), false );
 480     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(4,11)),  false );
 481
 482     IntervalMapT itv_map0 = itv_map;
 483
 484     itv_map.clear();
 485     IntervalMapT itv_map2(IIv(5,8,1));
 486     itv_map2.add(K_v(9,1)).add(K_v(11,1));
 487     itv_map += itv_map2;
 488     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_map2), true );
 489     IntervalSetT itv_set2;
 490     icl::domain(itv_set2, itv_map2);
 491     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_set2), true );
 492 }
 493
 494 template
 495 <
 496 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 497     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 498 #else
 499     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 500 #endif
 501     class T, class U
 502 >
 503 void interval_map_contains_key_objects_4_bicremental_types()
 504 {
 505     typedef IntervalMap<T,U> IntervalMapT;
 506     typedef typename IntervalMapT::interval_type   IntervalT;
 507     typedef typename IntervalMapT::set_type IntervalSetT;
 508     IntervalMapT itv_map;
 509
 510     itv_map.add(IDv(1,3,1));
 511     BOOST_CHECK_EQUAL( icl::contains(itv_map, MK_v(0)), false );
 512     BOOST_CHECK_EQUAL( icl::contains(itv_map, MK_v(2)), true );
 513     BOOST_CHECK_EQUAL( icl::contains(itv_map, MK_v(3)), false );
 514
 515     itv_map.add(IDv(3,6,2));
 516     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(0,0)), false );
 517     contains(itv_map, I_I(2,4));
 518     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(2,4)), true );
 519     BOOST_CHECK_EQUAL( icl::contains(itv_map, I_I(6,6)), false );
 520
 521     itv_map.add(IDv(8,9,2));
 522
 523     IntervalSetT itv_set;
 524     itv_set.add(C_I(1,2)).add(C_D(2,6)).add(I_I(8,8));
 525     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_set), true );
 526     itv_set.add(I_I(1,4));
 527     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_set), true );
 528     itv_set.add(I_I(1,4));
 529     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_set), true );
 530     itv_set.add(I_I(7,7));
 531     BOOST_CHECK_EQUAL( icl::contains(itv_map, itv_set), false );
 532
 533 }
 534
 535
 536 template
 537 <
 538 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 539     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 540 #else
 541     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 542 #endif
 543     class T, class U
 544 >
 545 void interval_map_operators_4_bicremental_types()
 546 {
 547     typedef IntervalMap<T,U> IntervalMapT;
 548     typedef typename IntervalMapT::interval_type   IntervalT;
 549     T v0 = make<T>(0);
 550     T v1 = make<T>(1);
 551     T v3 = make<T>(3);
 552     T v5 = make<T>(5);
 553     T v7 = make<T>(7);
 554     T v8 = make<T>(8);
 555     U u1 = make<U>(1);
 556     //typename IntervalMapT::interval_type I3_5I(icl::interval<T>::closed(v3,v5));
 557     typename IntervalMapT::value_type I0_1I_u1(icl::interval<T>::closed(v0,v1),u1);
 558     typename IntervalMapT::value_type I3_5I_u1(icl::interval<T>::closed(v3,v5),u1);
 559     typename IntervalMapT::value_type I7_8I_u1(icl::interval<T>::closed(v7,v8),u1);
 560
 561     IntervalMapT left, left2, right, all, section, complement;
 562     left.add(I0_1I_u1).add(I3_5I_u1);
 563     (right += I3_5I_u1) += I7_8I_u1;
 564     BOOST_CHECK_EQUAL( disjoint(left, right), false );
 565     BOOST_CHECK_EQUAL( intersects(left, right), true );
 566
 567     (all += left) += right;
 568     (section += left) &= right;
 569     all -= section;
 570     complement += all;
 571     //complement.erase(I3_5I);
 572     icl::erase(complement, section);
 573     BOOST_CHECK_EQUAL( disjoint(section, complement), true );
 574     BOOST_CHECK_EQUAL( intersects(section, complement), false );
 575 }
 576
 577
 578 // Test for nontrivial intersection of interval maps with intervals and values
 579 template
 580 <
 581 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 582     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 583 #else
 584     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 585 #endif
 586     class T, class U
 587 >
 588 void interval_map_base_intersect_4_bicremental_types()
 589 {
 590     typedef IntervalMap<T,U> IntervalMapT;
 591     typedef typename IntervalMapT::interval_type   IntervalT;
 592
 593     T v0 = make<T>(0);
 594     T v1 = make<T>(1);
 595     T v2 = make<T>(2);
 596     T v3 = make<T>(3);
 597     T v4 = make<T>(4);
 598     T v5 = make<T>(5);
 599     T v6 = make<T>(6);
 600     T v7 = make<T>(7);
 601     T v8 = make<T>(8);
 602     T v9 = make<T>(9);
 603
 604     U u1 = make<U>(1);
 605
 606     IntervalT I0_3D = icl::interval<T>::right_open(v0,v3);
 607     IntervalT I1_3D = icl::interval<T>::right_open(v1,v3);
 608     IntervalT I1_4D = icl::interval<T>::right_open(v1,v4);
 609     IntervalT I1_8D = icl::interval<T>::right_open(v1,v8);
 610     IntervalT I2_7D = icl::interval<T>::right_open(v2,v7);
 611     IntervalT I2_3D = icl::interval<T>::right_open(v2,v3);
 612     IntervalT I5_8D = icl::interval<T>::right_open(v5,v8);
 613     IntervalT I6_7D = icl::interval<T>::right_open(v6,v7);
 614     IntervalT I6_8D = icl::interval<T>::right_open(v6,v8);
 615     IntervalT I6_9D = icl::interval<T>::right_open(v6,v9);
 616
 617     typename IntervalMapT::value_type I0_3D_1(I0_3D, u1);
 618     typename IntervalMapT::value_type I6_9D_1(I6_9D, u1);
 619     typename IntervalMapT::value_type I1_3D_1(I1_3D, u1);
 620     typename IntervalMapT::value_type I6_8D_1(I6_8D, u1);
 621     typename IntervalMapT::value_type I2_3D_1(I2_3D, u1);
 622     typename IntervalMapT::value_type I6_7D_1(I6_7D, u1);
 623
 624     //--------------------------------------------------------------------------
 625     //map_A        [0       3)       [6    9)
 626     //                     1           1
 627     //         &=      [1                8)
 628     //map_AB   ->      [1   3)       [6  8)
 629     //                     1           1
 630     //         &=        [2             7)
 631     //         ->        [2 3)       [6 7)
 632     //                     1           1
 633     IntervalMap<T,U> map_A, map_AB, map_ab, map_ab2;
 634     interval_set<T>  set_B;
 635     map_A.add(I0_3D_1).add(I6_9D_1);
 636     map_AB = map_A;
 637     map_AB &= I1_8D;
 638     map_ab.add(I1_3D_1).add(I6_8D_1);
 639
 640     BOOST_CHECK_EQUAL( map_AB, map_ab );
 641
 642     map_AB = map_A;
 643     (map_AB &= I1_8D) &= I2_7D;
 644     map_ab2.add(I2_3D_1).add(I6_7D_1);
 645
 646     BOOST_CHECK_EQUAL( map_AB, map_ab2 );
 647
 648     //--------------------------------------------------------------------------
 649     //map_A        [0       3)       [6    9)
 650     //                     1           1
 651     //         &=      [1     4)  [5     8)
 652     //map_AB   ->      [1   3)       [6  8)
 653     //                     1           1
 654     //         &=        [2   4)  [5    7)
 655     //         ->        [2 3)       [6 7)
 656     //                     1           1
 657     map_A.clear();
 658     map_A.add(I0_3D_1).add(I6_9D_1);
 659     set_B.add(I1_4D).add(I5_8D);
 660     map_AB = map_A;
 661
 662     map_AB &= set_B;
 663     map_ab.clear();
 664     map_ab.add(I1_3D_1).add(I6_8D_1);
 665     BOOST_CHECK_EQUAL( map_AB, map_ab );
 666
 667     //--------------------------------------------------------------------------
 668     //map_A      [0       3)       [6       9)
 669     //                1                1
 670     //         &=     1
 671     //map_AB ->      [1]
 672     //                1
 673
 674     map_A.clear();
 675     map_A.add(I0_3D_1).add(I6_9D_1);
 676     map_AB = map_A;
 677     map_AB &= v1;
 678     map_ab.clear();
 679     map_ab.add(mapping_pair<T,U>(v1,u1));
 680
 681     BOOST_CHECK_EQUAL( map_AB, map_ab );
 682 }
 683
 684
 685 // Test for nontrivial erasure of interval maps with intervals and interval sets
 686 template
 687 <
 688 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 689     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 690 #else
 691     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 692 #endif
 693     class T, class U
 694 >
 695 void interval_map_base_erase_4_bicremental_types()
 696 {
 697     typedef IntervalMap<T,U> IntervalMapT;
 698     typedef typename IntervalMapT::interval_type   IntervalT;
 699
 700     T v0 = make<T>(0);
 701     T v1 = make<T>(1);
 702     T v2 = make<T>(2);
 703     T v3 = make<T>(3);
 704     T v4 = make<T>(4);
 705     T v5 = make<T>(5);
 706     T v6 = make<T>(6);
 707     T v7 = make<T>(7);
 708     T v8 = make<T>(8);
 709     T v9 = make<T>(9);
 710
 711     U u1 = make<U>(1);
 712
 713     IntervalT I0_1D = icl::interval<T>::right_open(v0,v1);
 714     IntervalT I0_2D = icl::interval<T>::right_open(v0,v2);
 715     IntervalT I0_3D = icl::interval<T>::right_open(v0,v3);
 716     IntervalT I1_3D = icl::interval<T>::right_open(v1,v3);
 717     //IntervalT I1_4D = icl::interval<T>::right_open(v1,v4);
 718     IntervalT I1_8D = icl::interval<T>::right_open(v1,v8);
 719     IntervalT I2_4D = icl::interval<T>::right_open(v2,v4);
 720     IntervalT I2_7D = icl::interval<T>::right_open(v2,v7);
 721     IntervalT I2_3D = icl::interval<T>::right_open(v2,v3);
 722     IntervalT I5_7D = icl::interval<T>::right_open(v5,v7);
 723     //IntervalT I5_8D = icl::interval<T>::right_open(v5,v8);
 724     IntervalT I6_7D = icl::interval<T>::right_open(v6,v7);
 725     IntervalT I6_8D = icl::interval<T>::right_open(v6,v8);
 726     IntervalT I6_9D = icl::interval<T>::right_open(v6,v9);
 727     IntervalT I7_9D = icl::interval<T>::right_open(v7,v9);
 728     IntervalT I8_9D = icl::interval<T>::right_open(v8,v9);
 729
 730     typename IntervalMapT::value_type I0_1D_1(I0_1D, u1);
 731     typename IntervalMapT::value_type I0_3D_1(I0_3D, u1);
 732     typename IntervalMapT::value_type I0_2D_1(I0_2D, u1);
 733     typename IntervalMapT::value_type I6_9D_1(I6_9D, u1);
 734     typename IntervalMapT::value_type I1_3D_1(I1_3D, u1);
 735     typename IntervalMapT::value_type I6_8D_1(I6_8D, u1);
 736     typename IntervalMapT::value_type I2_3D_1(I2_3D, u1);
 737     typename IntervalMapT::value_type I6_7D_1(I6_7D, u1);
 738     typename IntervalMapT::value_type I7_9D_1(I7_9D, u1);
 739     typename IntervalMapT::value_type I8_9D_1(I8_9D, u1);
 740
 741     //--------------------------------------------------------------------------
 742     //map_A        [0        3)       [6       9)
 743     //                  1                  1
 744     //      erase        [2              7)
 745     //map_A2   ->  [0   2)                [7   9)
 746     //                 1                    1
 747     //      erase      [1                   8)
 748     //         ->  [0 1)                    [8 9)
 749     //               1                       1
 750     IntervalMap<T,U> map_A, map_A2, map_A3, map_check2, map_check3;
 751     interval_set<T>  set_B;
 752     map_A.add(I0_3D_1).add(I6_9D_1);
 753     map_A2 = map_A;
 754     map_A2.erase(I2_7D);
 755     map_check2.add(I0_2D_1).add(I7_9D_1);
 756     BOOST_CHECK_EQUAL( map_A2, map_check2 );
 757
 758     map_A3 = map_A2;
 759     map_A3.erase(I1_8D);
 760     map_check3.add(I0_1D_1).add(I8_9D_1);
 761     BOOST_CHECK_EQUAL( map_A3, map_check3 );
 762
 763
 764     //--------------------------------------------------------------------------
 765     //map_A        [0        3)       [6       9)
 766     //                  1                  1
 767     //      erase        [2              7)
 768     //         ->  [0   2)                [7   9)
 769     //                 1                    1
 770     //      erase      [1                   8)
 771     //         ->  [0 1)                    [8 9)
 772     //               1                       1
 773     map_A3 = map_A;
 774     map_A3.erase(I2_7D).erase(I1_8D);
 775     BOOST_CHECK_EQUAL( map_A3, map_check3 );
 776
 777     //--------------------------------------------------------------------------
 778     //map_A        [0        3)       [6       9)
 779     //                  1                  1
 780     //         -=        [2              7)
 781     //         ->  [0   2)                [7   9)
 782     //                 1                    1
 783     //         -=      [1                   8)
 784     //         ->  [0 1)                    [8 9)
 785     //               1                       1
 786     map_A3 = map_A;
 787     (map_A3 -= I2_7D) -= I1_8D;
 788     BOOST_CHECK_EQUAL( map_A3, map_check3 );
 789
 790     //--------------------------------------------------------------------------
 791     //map_A        [0        3)       [6       9)
 792     //                  1                  1
 793     //      erase        [2    4)   [5   7)
 794     //         ->  [0   2)                [7   9)
 795     //                 1                    1
 796     map_A3 = map_A;
 797     set_B.add(I2_4D).add(I5_7D);
 798     map_A3 -= set_B;
 799     BOOST_CHECK_EQUAL( map_A3, map_check2 );
 800 }
 801
 802
 803 // Test first_collision
 804 template
 805 <
 806 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 807     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 808 #else
 809     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 810 #endif
 811     class T, class U
 812 >
 813 void interval_map_base_is_disjoint_4_bicremental_types()
 814 {
 815     typedef IntervalMap<T,U> IntervalMapT;
 816     typedef typename IntervalMapT::interval_type   IntervalT;
 817     typedef typename IntervalMap<T,U>::interval_set_type IntervalSetT;
 818
 819     T v0 = make<T>(0);
 820     T v1 = make<T>(1);
 821     T v3 = make<T>(3);
 822     T v5 = make<T>(5);
 823     T v6 = make<T>(6);
 824     T v7 = make<T>(7);
 825     T v8 = make<T>(8);
 826     T v9 = make<T>(9);
 827
 828     U u1 = make<U>(1);
 829
 830     IntervalT I0_1D = icl::interval<T>::right_open(v0,v1);
 831     IntervalT I1_3D = icl::interval<T>::right_open(v1,v3);
 832     IntervalT I3_6D = icl::interval<T>::right_open(v3,v6);
 833     IntervalT I5_7D = icl::interval<T>::right_open(v5,v7);
 834     IntervalT I6_8D = icl::interval<T>::right_open(v6,v8);
 835     IntervalT I8_9D = icl::interval<T>::right_open(v8,v9);
 836
 837     typename IntervalMapT::value_type I0_1D_1(I0_1D, u1);
 838     typename IntervalMapT::value_type I1_3D_1(I1_3D, u1);
 839     typename IntervalMapT::value_type I3_6D_1(I3_6D, u1);
 840     typename IntervalMapT::value_type I5_7D_1(I5_7D, u1);
 841     typename IntervalMapT::value_type I6_8D_1(I6_8D, u1);
 842     typename IntervalMapT::value_type I8_9D_1(I8_9D, u1);
 843
 844     //--------------------------------------------------------------------------
 845     //map_A          [1      3)       [6       8)
 846     //                  1                  1
 847     //map_B      [0 1)        [3     6)         [8 9)
 848     //             1              1               1
 849     IntervalMapT map_A, map_B;
 850     IntervalSetT set_A, set_B;
 851
 852     map_A.add(I1_3D_1).add(I6_8D_1);
 853     map_B.add(I0_1D_1).add(I3_6D_1).add(I8_9D_1);
 854     BOOST_CHECK_EQUAL( disjoint(map_A, map_B), true );
 855     BOOST_CHECK_EQUAL( disjoint(map_B, map_A), true );
 856     BOOST_CHECK_EQUAL( intersects(map_A, map_B), false );
 857     BOOST_CHECK_EQUAL( intersects(map_B, map_A), false );
 858
 859     icl::domain(set_A, map_A);
 860     icl::domain(set_B, map_B);
 861     BOOST_CHECK_EQUAL( disjoint(map_A, set_B), true );
 862     BOOST_CHECK_EQUAL( disjoint(set_B, map_A), true );
 863     BOOST_CHECK_EQUAL( disjoint(set_A, map_B), true );
 864     BOOST_CHECK_EQUAL( disjoint(map_B, set_A), true );
 865     BOOST_CHECK_EQUAL( intersects(map_A, set_B), false );
 866     BOOST_CHECK_EQUAL( intersects(set_B, map_A), false );
 867     BOOST_CHECK_EQUAL( intersects(set_A, map_B), false );
 868     BOOST_CHECK_EQUAL( intersects(map_B, set_A), false );
 869
 870     map_A += I5_7D_1;
 871
 872     BOOST_CHECK_EQUAL( disjoint(map_A, map_B), false );
 873     BOOST_CHECK_EQUAL( disjoint(map_B, map_A), false );
 874     BOOST_CHECK_EQUAL( intersects(map_A, map_B),  true );
 875     BOOST_CHECK_EQUAL( intersects(map_B, map_A),  true );
 876
 877     icl::domain(set_A, map_A);
 878     icl::domain(set_B, map_B);
 879     BOOST_CHECK_EQUAL( disjoint(map_A, set_B), false );
 880     BOOST_CHECK_EQUAL( disjoint(set_B, map_A), false );
 881     BOOST_CHECK_EQUAL( disjoint(set_A, map_B), false );
 882     BOOST_CHECK_EQUAL( disjoint(map_B, set_A), false );
 883     BOOST_CHECK_EQUAL( intersects(map_A, set_B), true );
 884     BOOST_CHECK_EQUAL( intersects(set_B, map_A), true );
 885     BOOST_CHECK_EQUAL( intersects(set_A, map_B), true );
 886     BOOST_CHECK_EQUAL( intersects(map_B, set_A), true );
 887 }
 888
 889 template
 890 <
 891 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 892     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 893 #else
 894     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 895 #endif
 896     class T, class U
 897 >
 898 void interval_map_flip_4_bicremental_types()
 899 {
 900     typedef IntervalMap<T,U> IntervalMapT;
 901     typedef typename IntervalMapT::interval_type   IntervalT;
 902     typedef IntervalMapT IMap;
 903
 904     IntervalMapT set_a;
 905     //[0     2)
 906     //    1
 907     //    [1     3)
 908     //        1
 909     //[0 1)   [2 3) : {[0 2)->1} ^= ([2 3)->1)
 910     //  1       1
 911     //BOOST_CHECK_EQUAL(IMap(IDv(0,2,1)) ^= (IDv(1,3,1)), IMap(IDv(0,1,1)) + IDv(2,3,1));
 912     set_a = IMap(IDv(0,2,1));
 913     IntervalMapT set_b = set_a;
 914     BOOST_CHECK_EQUAL(set_a ^= IDv(1,3,1), IMap(IDv(0,1,1)) + IDv(2,3,1));
 915 }
 916
 917 template
 918 <
 919 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 920     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 921 #else
 922     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 923 #endif
 924     class T, class U
 925 >
 926 void interval_map_infix_plus_overload_4_bicremental_types()
 927 {
 928     typedef IntervalMap<T,U> IntervalMapT;
 929     typedef typename IntervalMapT::interval_type   IntervalT;
 930     typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
 931     std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
 932     mapping_pair<T,U> map_pair = K_v(4,3);
 933
 934     IntervalMapT map_a, map_b;
 935     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
 936     map_b.add(IDv(0,9,2)).add(IIv(3,6,1)).add(IDv(5,7,1));
 937
 938     BOOST_CHECK_EQUAL(map_a + map_b, map_b + map_a);
 939     //This checks all cases of is_interval_map_derivative<T>
 940     BOOST_CHECK_EQUAL(map_a + val_pair1, val_pair1 + map_a);
 941     BOOST_CHECK_EQUAL(map_b + val_pair2, val_pair2 + map_b);
 942     BOOST_CHECK_EQUAL(map_b + map_pair, map_pair + map_b);
 943 }
 944
 945 template
 946 <
 947 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 948     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 949 #else
 950     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 951 #endif
 952     class T, class U
 953 >
 954 void interval_map_infix_pipe_overload_4_bicremental_types()
 955 {
 956     typedef IntervalMap<T,U> IntervalMapT;
 957     typedef typename IntervalMapT::interval_type   IntervalT;
 958     typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
 959     std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
 960     mapping_pair<T,U> map_pair = K_v(4,3);
 961
 962     IntervalMapT map_a, map_b;
 963     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
 964     map_b.add(IDv(0,9,2)).add(IIv(3,6,1)).add(IDv(5,7,1));
 965
 966     BOOST_CHECK_EQUAL(map_a | map_b, map_b | map_a);
 967     //This checks all cases of is_interval_map_derivative<T>
 968     BOOST_CHECK_EQUAL(map_a | val_pair1, val_pair1 | map_a);
 969     BOOST_CHECK_EQUAL(map_b | val_pair2, val_pair2 | map_b);
 970     BOOST_CHECK_EQUAL(map_b | map_pair, map_pair | map_b);
 971 }
 972
 973
 974
 975 template
 976 <
 977 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
 978     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
 979 #else
 980     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
 981 #endif
 982     class T, class U
 983 >
 984 void interval_map_infix_minus_overload_4_bicremental_types()
 985 {
 986     typedef IntervalMap<T,U> IntervalMapT;
 987     typedef typename IntervalMapT::interval_type   IntervalT;
 988
 989     typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
 990     std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
 991     mapping_pair<T,U> map_pair = K_v(4,3);
 992
 993     IntervalT itv = C_D(4,11);
 994     typename IntervalMapT::interval_mapping_type itv_v = CDv(4,11,3);
 995
 996     IntervalMapT map_a, map_b, map_c;
 997     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
 998     map_b.add(IDv(0,9,2)).add(IIv(3,6,1)).add(IDv(5,7,1));
 999     map_c = map_a;
1000
1001     interval_set<T>          join_set_a;
1002     separate_interval_set<T> sep_set_a;
1003     split_interval_set<T>    split_set_a;
1004     join_set_a .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,9));
1005     sep_set_a  .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,11));
1006     split_set_a.add(I_I(0,0)).add(I_D(8,7)).add(I_I(6,11));
1007
1008     //Happy day overloading
1009     BOOST_CHECK_EQUAL(map_a - map_b, (map_c = map_a) -= map_b);
1010     BOOST_CHECK_EQUAL(map_a - map_b, map_c);
1011
1012     //This checks all cases of is_interval_map_derivative<T>
1013     BOOST_CHECK_EQUAL((map_a - val_pair1) + val_pair1, (map_a + val_pair1) - val_pair1);
1014     BOOST_CHECK_EQUAL((map_b - val_pair2) + val_pair2, (map_b + val_pair2) - val_pair2);
1015     BOOST_CHECK_EQUAL((map_b - map_pair)  + map_pair,  (map_b + map_pair)  - map_pair);
1016
1017     //This checks all cases of is_interval_set_derivative<T>
1018     BOOST_CHECK_EQUAL(map_a - itv,     (map_a + itv_v) - itv);
1019     BOOST_CHECK_EQUAL(map_b - MK_v(8), (IIv(8,8,3) + map_b) - MK_v(8));
1020
1021     //This checks all cases of is_interval_set_companion<T>
1022     BOOST_CHECK_EQUAL(map_a - split_set_a, ((split_set_a & map_a) + map_a) - split_set_a);
1023     BOOST_CHECK_EQUAL(map_a - sep_set_a,   ((sep_set_a   & map_a) + map_a) - sep_set_a);
1024     BOOST_CHECK_EQUAL(map_a - join_set_a,  ((join_set_a  & map_a) + map_a) - join_set_a);
1025 }
1026
1027
1028 template
1029 <
1030 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1031     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1032 #else
1033     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1034 #endif
1035     class T, class U
1036 >
1037 void interval_map_infix_et_overload_4_bicremental_types()
1038 {
1039     typedef IntervalMap<T,U> IntervalMapT;
1040     typedef typename IntervalMapT::interval_type   IntervalT;
1041
1042     typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1043     std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1044     mapping_pair<T,U> map_pair = K_v(4,3);
1045
1046     IntervalT itv = C_D(4,11);
1047
1048     IntervalMapT map_a, map_b;
1049     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1050     map_b.add(IDv(0,9,2)).add(IIv(3,6,1)).add(IDv(5,7,1));
1051
1052     interval_set<T>          join_set_a;
1053     separate_interval_set<T> sep_set_a;
1054     split_interval_set<T>    split_set_a;
1055     join_set_a .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,9));
1056     sep_set_a  .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,11));
1057     split_set_a.add(I_I(0,0)).add(I_D(8,7)).add(I_I(6,11));
1058
1059     //Happy day overloading
1060     BOOST_CHECK_EQUAL(map_a & map_b, map_b & map_a);
1061
1062     //This checks all cases of is_interval_map_derivative<T>
1063     BOOST_CHECK_EQUAL(map_a & val_pair1, val_pair1 & map_a);
1064     BOOST_CHECK_EQUAL(map_b & val_pair2, val_pair2 & map_b);
1065     BOOST_CHECK_EQUAL(map_b & map_pair, map_pair & map_b);
1066
1067     //This checks all cases of is_interval_set_derivative<T>
1068     BOOST_CHECK_EQUAL(map_a & itv, itv & map_a);
1069     BOOST_CHECK_EQUAL(map_b & MK_v(8), MK_v(8) & map_b);
1070
1071     //This checks all cases of is_interval_set_companion<T>
1072     BOOST_CHECK_EQUAL(map_a & split_set_a, split_set_a & map_a);
1073     BOOST_CHECK_EQUAL(map_a & sep_set_a,   sep_set_a   & map_a);
1074     BOOST_CHECK_EQUAL(map_a & join_set_a,  join_set_a  & map_a);
1075 }
1076
1077
1078 template
1079 <
1080 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1081     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1082 #else
1083     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1084 #endif
1085     class T, class U
1086 >
1087 void interval_map_infix_caret_overload_4_bicremental_types()
1088 {
1089     typedef IntervalMap<T,U> IntervalMapT;
1090     typedef typename IntervalMapT::interval_type   IntervalT;
1091
1092     typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1093     std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1094     mapping_pair<T,U> map_pair = K_v(4,3);
1095
1096     //IntervalT itv = C_D(4,11);
1097
1098     IntervalMapT map_a, map_b;
1099     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1100     map_b.add(IDv(0,9,2)).add(IIv(3,6,1)).add(IDv(5,7,1));
1101
1102     interval_set<T>          join_set_a;
1103     separate_interval_set<T> sep_set_a;
1104     split_interval_set<T>    split_set_a;
1105     join_set_a .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,9));
1106     sep_set_a  .add(I_D(0,4)).add(I_I(4,6)).add(I_D(5,11));
1107     split_set_a.add(I_I(0,0)).add(I_D(8,7)).add(I_I(6,11));
1108
1109     //Happy day overloading
1110     BOOST_CHECK_EQUAL(map_a ^ map_b, map_b ^ map_a);
1111
1112     //This checks all cases of is_interval_map_derivative<T>
1113     BOOST_CHECK_EQUAL(map_a ^ val_pair1, val_pair1 ^ map_a);
1114     BOOST_CHECK_EQUAL(map_b ^ val_pair2, val_pair2 ^ map_b);
1115     BOOST_CHECK_EQUAL(map_b ^ map_pair,  map_pair ^ map_b);
1116 }
1117
1118 template
1119 <
1120 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1121     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1122 #else
1123     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1124 #endif
1125     class T, class U
1126 >
1127 void interval_map_find_4_bicremental_types()
1128 {
1129     typedef IntervalMap<T,U> IntervalMapT;
1130     typedef typename IntervalMapT::interval_type  IntervalT;
1131     typedef typename IntervalMapT::const_iterator c_iterator;
1132
1133     //CL typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1134     //std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1135     //mapping_pair<T,U> map_pair = K_v(4,3);
1136
1137     IntervalMapT map_a;
1138     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1139     // {(1  3)    [6  8)[8 9)[9  11)
1140     //     1         3    4     3
1141     //          5? 6?
1142     c_iterator found1 = map_a.find(MK_v(6));
1143     c_iterator found2 = icl::find(map_a, MK_v(6));
1144
1145     BOOST_CHECK      ( found1 == found2 );
1146     BOOST_CHECK_EQUAL( found1->second, found2->second );
1147     BOOST_CHECK_EQUAL( found1->second, MK_u(3) );
1148     BOOST_CHECK_EQUAL( map_a(MK_v(6)), MK_u(3) );
1149
1150     found1 = map_a.find(MK_v(5));
1151
1152     BOOST_CHECK_EQUAL( found1 == map_a.end(), true );
1153     BOOST_CHECK_EQUAL( map_a(MK_v(5)), MK_u(0) );
1154     BOOST_CHECK_EQUAL( map_a(MK_v(8)), MK_u(4) );
1155
1156     //LAW map c; key k: k in dom(c) => contains(c, (k, find(c, k)->second))
1157     BOOST_CHECK( icl::contains(map_a, K_v(2, icl::find(map_a, MK_v(2))->second)) );
1158     BOOST_CHECK( icl::contains(map_a, K_v(11, map_a.find(MK_v(11))->second)) );
1159
1160     BOOST_CHECK(  icl::contains(map_a, MK_v(2)) );
1161     BOOST_CHECK(  icl::contains(map_a, MK_v(10)) );
1162     BOOST_CHECK( !icl::contains(map_a, MK_v(1)) );
1163     BOOST_CHECK( !icl::contains(map_a, MK_v(3)) );
1164     BOOST_CHECK( !icl::contains(map_a, MK_v(12)) );
1165
1166     BOOST_CHECK(  icl::intersects(map_a, MK_v(2)) );
1167     BOOST_CHECK(  icl::intersects(map_a, MK_v(10)) );
1168     BOOST_CHECK( !icl::intersects(map_a, MK_v(1)) );
1169     BOOST_CHECK( !icl::intersects(map_a, MK_v(3)) );
1170     BOOST_CHECK( !icl::intersects(map_a, MK_v(12)) );
1171 }
1172
1173
1174 template
1175 <
1176 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1177     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1178 #else
1179     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1180 #endif
1181     class T, class U
1182 >
1183 void interval_map_find_4_numeric_continuous_types()
1184 {
1185 #ifndef BOOST_ICL_TEST_CHRONO
1186     typedef IntervalMap<T,U> IntervalMapT;
1187     typedef typename IntervalMapT::interval_type  IntervalT;
1188     typedef typename IntervalMapT::const_iterator c_iterator;
1189
1190     T q_1_2 = MK_v(1) / MK_v(2);//JODO Doesn't work with chrono
1191     T q_3_2 = MK_v(3) / MK_v(2);
1192     T q_1_3 = MK_v(1) / MK_v(3);
1193     T q_2_3 = MK_v(2) / MK_v(3);
1194     T q_4_3 = MK_v(4) / MK_v(3);
1195     T q_5_3 = MK_v(5) / MK_v(3);
1196
1197     IntervalMapT map_a;
1198     map_a.add(MK_seg(IntervalT(q_1_3, q_2_3), 1)).add(MK_seg(IntervalT(q_4_3, q_5_3), 2));
1199     // {[1/3   2/3)    [4/3   5/3)}
1200     //       1              2
1201
1202     c_iterator found1 = map_a.find(q_1_2);
1203     c_iterator found2 = icl::find(map_a, q_1_2);
1204     BOOST_CHECK      ( found1 == found2 );
1205     BOOST_CHECK_EQUAL( found1->second, found2->second );
1206     BOOST_CHECK_EQUAL( found1->second, MK_u(1) );
1207
1208     found1 = map_a.find(q_3_2);
1209     found2 = icl::find(map_a, q_3_2);
1210     BOOST_CHECK      ( found1 == found2 );
1211     BOOST_CHECK_EQUAL( found1->second, found2->second );
1212     BOOST_CHECK_EQUAL( found1->second, MK_u(2) );
1213
1214     if( mpl::or_<mpl::not_<is_static_left_open<IntervalT> >, boost::is_signed<T> >::value )
1215     {
1216         found1 = map_a.find(MK_v(0));
1217         found2 = icl::find(map_a, MK_v(0));
1218         BOOST_CHECK      ( found1 == found2 );
1219         BOOST_CHECK      ( found1 == map_a.end() );
1220     }
1221
1222     found1 = map_a.find(MK_v(1));
1223     found2 = icl::find(map_a, MK_v(1));
1224     BOOST_CHECK      ( found1 == found2 );
1225     BOOST_CHECK      ( found1 == map_a.end() );
1226
1227     if( mpl::or_<mpl::not_<is_static_left_open<IntervalT> >, boost::is_signed<T> >::value )
1228     {
1229         BOOST_CHECK( !icl::contains(map_a, MK_v(0)) );
1230     }
1231     BOOST_CHECK(  icl::contains(map_a, q_1_2) );
1232     BOOST_CHECK( !icl::contains(map_a, MK_v(1)) );
1233     BOOST_CHECK(  icl::contains(map_a, q_3_2) );
1234     BOOST_CHECK( !icl::contains(map_a, MK_v(2)) );
1235 #endif
1236 }
1237
1238
1239 template
1240 <
1241 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1242     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1243 #else
1244     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1245 #endif
1246     class T, class U
1247 >
1248 void interval_map_range_4_bicremental_types()
1249 {
1250     typedef IntervalMap<T,U> IntervalMapT;
1251     typedef typename IntervalMapT::interval_type  IntervalT;
1252     typedef typename IntervalMapT::const_iterator c_iterator;
1253
1254     //CL typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1255     //std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1256     //mapping_pair<T,U> map_pair = K_v(4,3);
1257
1258     IntervalMapT map_a;
1259     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1260     // {(1  3)    [6  8)[8 9)[9  11)
1261     //     1         3    4     3
1262     //    [2        7) := itv
1263
1264     IntervalT itv = I_D(2, 7);
1265     c_iterator lwb1 = icl::find(map_a, itv);
1266     c_iterator lwb2 = map_a.lower_bound(itv);
1267
1268     BOOST_CHECK      ( lwb1 == lwb2 );
1269     BOOST_CHECK_EQUAL( lwb1->second, lwb2->second );
1270     BOOST_CHECK_EQUAL( lwb1->second, MK_u(1) );
1271
1272     c_iterator upb1 = map_a.upper_bound(itv);
1273     BOOST_CHECK_EQUAL( upb1->second, MK_u(4) );
1274
1275     std::pair<c_iterator,c_iterator> exterior =  map_a.equal_range(itv);
1276     BOOST_CHECK      ( lwb1 == exterior.first );
1277     BOOST_CHECK      ( upb1 == exterior.second );
1278 }
1279
1280
1281 template
1282 <
1283 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1284     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1285 #else
1286     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1287 #endif
1288     class T, class U
1289 >
1290 void interval_map_set_4_bicremental_types()
1291 {
1292     typedef IntervalMap<T,U> IntervalMapT;
1293     typedef typename IntervalMapT::interval_type   IntervalT;
1294
1295     //CL typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1296     //std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1297     //mapping_pair<T,U> map_pair = K_v(4,3);
1298
1299     IntervalMapT map_a;
1300     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1301
1302     BOOST_CHECK_EQUAL( icl::contains(map_a.set(CDv(2,10,4)), CDv(2,10,4)), true );
1303     BOOST_CHECK_EQUAL( icl::contains(map_a.set(K_v(4,5)), K_v(4,5)), true );
1304     BOOST_CHECK_EQUAL( icl::contains(map_a.set(K_v(4,5)).set(CDv(3,5,6)), CDv(3,5,6)), true );
1305 }
1306
1307
1308 template
1309 <
1310     class T, class U, class Trt,
1311 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1312     ICL_IntervalMap_TEMPLATE(T,U,Traits,Trt) IntervalMap
1313 #else
1314     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,Trt) IntervalMap
1315 #endif
1316 >
1317 void interval_map_inclusion_compare_4_bicremental_types()
1318 {
1319     typedef IntervalMap<T,U,Trt> IntervalMapT;
1320     typedef typename IntervalMapT::interval_type   IntervalT;
1321     typedef typename IntervalMap<T,U,Trt>::set_type IntervalSetT;
1322     typedef icl::map<T,U,Trt> MapT;
1323     typedef std::set<T> SetT;
1324
1325     IntervalMapT itv_map_sub_a, itv_map_a, itv_map_a2, itv_map_super_a,
1326                  itv_map_b, itv_map_c;
1327     itv_map_sub_a.add(IDv(2,4,1)).add(IIv(6,7,3));
1328     itv_map_a = itv_map_sub_a;
1329     itv_map_a.add(IIv(9,9,1));
1330     itv_map_a2 = itv_map_a;
1331     itv_map_c = itv_map_sub_a;
1332     itv_map_c.erase(MK_v(7)).add(IIv(11,11,2));
1333     itv_map_b = itv_map_a;
1334     itv_map_b.set(IIv(6,7,2));
1335
1336
1337     BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), IntervalMapT()), inclusion::equal );
1338     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_a), inclusion::equal );
1339     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_a2), inclusion::equal );
1340
1341     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, IntervalMapT()), inclusion::superset );
1342     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_sub_a), inclusion::superset );
1343     BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), itv_map_a), inclusion::subset );
1344     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_sub_a, itv_map_a), inclusion::subset );
1345
1346     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_b), inclusion::unrelated );
1347     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, itv_map_c), inclusion::unrelated );
1348
1349     IntervalSetT set_sub_a, set_a, set_a2, set_b, set_c;
1350     icl::domain(set_a, itv_map_a);
1351     icl::domain(set_a2, itv_map_a2);
1352     icl::domain(set_sub_a, itv_map_sub_a);
1353
1354     BOOST_CHECK_EQUAL( inclusion_compare(IntervalMapT(), IntervalSetT()), inclusion::equal );
1355     BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), IntervalMapT()), inclusion::equal );
1356     BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), IntervalSetT()), inclusion::equal );
1357
1358     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, set_a), inclusion::equal );
1359     BOOST_CHECK_EQUAL( inclusion_compare(set_a, itv_map_a), inclusion::equal );
1360     BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_a2), inclusion::equal );
1361
1362     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, IntervalSetT()), inclusion::superset );
1363     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_a, set_sub_a), inclusion::superset );
1364
1365     BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), itv_map_a), inclusion::subset );
1366     BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, itv_map_a), inclusion::subset );
1367
1368     BOOST_CHECK_EQUAL( inclusion_compare(set_a, IntervalSetT()), inclusion::superset );
1369     BOOST_CHECK_EQUAL( inclusion_compare(set_a, set_sub_a), inclusion::superset );
1370
1371     BOOST_CHECK_EQUAL( inclusion_compare(IntervalSetT(), set_a), inclusion::subset );
1372     BOOST_CHECK_EQUAL( inclusion_compare(set_sub_a, set_a), inclusion::subset );
1373
1374     BOOST_CHECK_EQUAL( inclusion_compare(set_a, itv_map_c), inclusion::unrelated );
1375     BOOST_CHECK_EQUAL( inclusion_compare(itv_map_c, set_a), inclusion::unrelated );
1376
1377 }
1378
1379 template
1380 <
1381     class T, class U, class Trt,
1382 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1383     ICL_IntervalMap_TEMPLATE(T,U,Traits,Trt) IntervalMap
1384 #else
1385     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,Trt) IntervalMap
1386 #endif
1387 >
1388 void interval_map_std_copy_via_inserter_4_bicremental_types()
1389 {
1390     typedef IntervalMap<T,U,Trt> IntervalMapT; //Nedded for the test value generator
1391     typedef typename IntervalMapT::interval_type   IntervalT;
1392
1393     // Check equality of copying using handcoded loop or std::copy via inserter.
1394     typedef std::pair<IntervalT, U> SegmentT;
1395     std::vector<SegmentT> seg_vec_a;
1396     IntervalMapT std_copied_map;
1397
1398     // For an empty sequence
1399     test_interval_map_copy_via_inserter(seg_vec_a, std_copied_map);
1400
1401     // For an singleton sequence
1402     seg_vec_a.push_back(IDv(0,1,1));
1403     test_interval_map_copy_via_inserter(seg_vec_a, std_copied_map);
1404
1405     // Two separate segments
1406     seg_vec_a.push_back(IDv(3,5,1));
1407     test_interval_map_copy_via_inserter(seg_vec_a, std_copied_map);
1408
1409     // Touching case
1410     seg_vec_a.push_back(IDv(5,7,1));
1411     test_interval_map_copy_via_inserter(seg_vec_a, std_copied_map);
1412
1413     // Overlapping case
1414     seg_vec_a.push_back(IDv(6,9,1));
1415     test_interval_map_copy_via_inserter(seg_vec_a, std_copied_map);
1416
1417 }
1418
1419
1420 template
1421 <
1422     class T, class U, class Trt,
1423 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1424     ICL_IntervalMap_TEMPLATE(T,U,Traits,Trt) IntervalMap
1425 #else
1426     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,Trt) IntervalMap
1427 #endif
1428 >
1429 void interval_map_element_iter_4_discrete_types()
1430 {
1431     typedef IntervalMap<T,U,Trt> IntervalMapT;
1432     typedef typename IntervalMapT::interval_type   IntervalT;
1433     typedef typename IntervalMapT::element_iterator ReptatorT;
1434     typedef std::vector<std::pair<T,U> > VectorT;
1435
1436     IntervalMapT map_a;
1437     map_a.insert(IIv(1,3,1)).insert(IIv(6,7,2));
1438
1439     typename IntervalMapT::atomized_type ato_map_a;
1440     //ReptatorT el_it = elements_begin(map_a);
1441
1442     VectorT vec(5), cev(5);
1443     vec[0]=sK_v(1,1);vec[1]=sK_v(2,1);vec[2]=sK_v(3,1);vec[3]=sK_v(6,2);vec[4]=sK_v(7,2);
1444     cev[0]=sK_v(7,2);cev[1]=sK_v(6,2);cev[2]=sK_v(3,1);cev[3]=sK_v(2,1);cev[4]=sK_v(1,1);
1445
1446     VectorT dest;
1447     std::copy(elements_begin(map_a), elements_end(map_a), std::back_inserter(dest));
1448     BOOST_CHECK_EQUAL( vec == dest, true );
1449
1450     dest.clear();
1451     std::copy(elements_rbegin(map_a), elements_rend(map_a), std::back_inserter(dest));
1452     BOOST_CHECK_EQUAL( cev == dest, true );
1453
1454     dest.clear();
1455     std::reverse_copy(elements_rbegin(map_a), elements_rend(map_a), std::back_inserter(dest));
1456     BOOST_CHECK_EQUAL( vec == dest, true );
1457
1458     dest.clear();
1459     std::reverse_copy(elements_begin(map_a), elements_end(map_a), std::back_inserter(dest));
1460     BOOST_CHECK_EQUAL( cev == dest, true );
1461
1462 }
1463
1464
1465 template
1466 <
1467 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1468     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1469 #else
1470     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1471 #endif
1472     class T, class U
1473 >
1474 void interval_map_intersects_4_bicremental_types()
1475 {
1476     // Test of intersects and disjoint for domain_type and interval_type.
1477     typedef IntervalMap<T,U> IntervalMapT;
1478     typedef typename IntervalMapT::interval_type   IntervalT;
1479
1480     //CL typename IntervalMapT::interval_mapping_type val_pair1 = IDv(6,9,1);
1481     //std::pair<const IntervalT, U> val_pair2 = IDv(3,5,3);
1482     //mapping_pair<T,U> map_pair = K_v(4,3);
1483
1484     IntervalMapT map_a;
1485     map_a.add(CDv(1,3,1)).add(IDv(8,9,1)).add(IIv(6,11,3));
1486
1487     BOOST_CHECK( icl::is_interval_container<IntervalMapT>::value );
1488     BOOST_CHECK( icl::has_domain_type<IntervalMapT>::value );
1489     BOOST_CHECK( (boost::is_same<T, typename domain_type_of<IntervalMapT>::type>::value) );
1490
1491     BOOST_CHECK( icl::intersects(map_a,  MK_v(2) ) );
1492     BOOST_CHECK( icl::intersects(map_a,  MK_v(11)) );
1493     BOOST_CHECK( icl::disjoint(map_a, MK_v(1) ) );
1494     BOOST_CHECK( icl::disjoint(map_a, MK_v(12)) );
1495
1496     BOOST_CHECK( icl::intersects(map_a, I_D(2,3)) );
1497     BOOST_CHECK( icl::intersects(map_a, I_D(6,8)) );
1498     BOOST_CHECK( icl::disjoint(map_a,   I_D(3,5)) );
1499     BOOST_CHECK( icl::disjoint(map_a,  I_D(12,14)) );
1500
1501     //-------------------------------------+
1502     //   (1   3)      [6   8)[8 9)[9    11]
1503     //      1            3     4      3
1504     mapping_pair<T,U> map_pair_2_1  = K_v(2,1);
1505     BOOST_CHECK( icl::intersects(map_a,  map_pair_2_1 ) );
1506     BOOST_CHECK( icl::intersects(map_a,  K_v(6,3) ) );
1507     BOOST_CHECK( icl::intersects(map_a,  IDv(6,8,3) ) );
1508     BOOST_CHECK( icl::intersects(map_a,  CIv(8,11,3) ) );
1509     BOOST_CHECK( icl::intersects(map_a,  IIv(6,11,3) ) );
1510     BOOST_CHECK( icl::intersects(map_a,  IIv(6,11,5) ) );
1511     BOOST_CHECK(!icl::intersects(map_a,  IDv(4,6,5) ) );
1512
1513     BOOST_CHECK( icl::disjoint(map_a,  IDv(4,6,5) ) );
1514     BOOST_CHECK(!icl::disjoint(map_a,  IDv(0,12,1) ) );
1515 }
1516
1517
1518 template
1519 <
1520 #if (defined(__GNUC__) && (__GNUC__ < 4)) //MEMO Can be simplified, if gcc-3.4 is obsolete
1521     ICL_IntervalMap_TEMPLATE(T,U,Traits,partial_absorber) IntervalMap,
1522 #else
1523     ICL_IntervalMap_TEMPLATE(_T,_U,Traits,partial_absorber) IntervalMap,
1524 #endif
1525     class T, class U
1526 >
1527 void interval_map_move_4_discrete_types()
1528 {
1529 #   ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
1530     typedef IntervalMap<T,U> IntervalMapT;
1531     typedef typename IntervalMapT::interval_type   IntervalT;
1532
1533     IntervalMapT map_A(boost::move(IntervalMapT(IDv(0,4,2))));
1534     IntervalMapT map_B(boost::move(IntervalMapT(IDv(0,2,1)).add(IDv(2,4,1)).add(IDv(0,4,1))));
1535
1536     BOOST_CHECK( icl::is_element_equal(map_A, map_B) );
1537     BOOST_CHECK_EQUAL( map_A, join(map_B) );
1538
1539     map_A = boost::move(IntervalMapT(IIv(1,4,2)));
1540     map_B = boost::move(IntervalMapT(CIv(0,2,1)).insert(IDv(3,5,1)).add(CDv(0,5,1)));
1541
1542     BOOST_CHECK( icl::is_element_equal(map_A, map_B) );
1543     BOOST_CHECK_EQUAL( map_A, join(map_B) );
1544
1545 #   endif // BOOST_NO_CXX11_RVALUE_REFERENCES
1546 }
1547
1548
1549 #endif // LIBS_ICL_TEST_TEST_INTERVAL_MAP_SHARED_HPP_JOFA_081005
1550