ceph/src/boost/boost/icl/detail/interval_set_algo.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 BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
   9 #define BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
  10
  11 #include <boost/next_prior.hpp>
  12 #include <boost/icl/detail/notate.hpp>
  13 #include <boost/icl/detail/relation_state.hpp>
  14 #include <boost/icl/type_traits/identity_element.hpp>
  15 #include <boost/icl/type_traits/is_map.hpp>
  16 #include <boost/icl/type_traits/is_total.hpp>
  17 #include <boost/icl/type_traits/is_combinable.hpp>
  18 #include <boost/icl/concept/set_value.hpp>
  19 #include <boost/icl/concept/map_value.hpp>
  20 #include <boost/icl/interval_combining_style.hpp>
  21 #include <boost/icl/detail/element_comparer.hpp>
  22 #include <boost/icl/detail/interval_subset_comparer.hpp>
  23 #include <boost/icl/detail/associated_value.hpp>
  24
  25 namespace boost{namespace icl
  26 {
  27
  28 namespace Interval_Set
  29 {
  30
  31 //------------------------------------------------------------------------------
  32 // Lexicographical comparison on ranges of two interval container
  33 //------------------------------------------------------------------------------
  34
  35 template<class LeftT, class RightT>
  36 bool is_element_equal(const LeftT& left, const RightT& right)
  37 {
  38     return subset_compare
  39             (
  40                 left, right,
  41                 left.begin(), left.end(),
  42                 right.begin(), right.end()
  43             ) == inclusion::equal;
  44 }
  45
  46 template<class LeftT, class RightT>
  47 bool is_element_less(const LeftT& left, const RightT& right)
  48 {
  49     return element_compare
  50             (
  51                 left, right,
  52                 left.begin(), left.end(),
  53                 right.begin(), right.end()
  54             )  == comparison::less;
  55 }
  56
  57 template<class LeftT, class RightT>
  58 bool is_element_greater(const LeftT& left, const RightT& right)
  59 {
  60     return element_compare
  61             (
  62                 left, right,
  63                 left.begin(), left.end(),
  64                 right.begin(), right.end()
  65             )  == comparison::greater;
  66 }
  67
  68 //------------------------------------------------------------------------------
  69 // Subset/superset compare on ranges of two interval container
  70 //------------------------------------------------------------------------------
  71
  72 template<class IntervalContainerT>
  73 bool is_joinable(const IntervalContainerT& container,
  74                  typename IntervalContainerT::const_iterator first,
  75                  typename IntervalContainerT::const_iterator past)
  76 {
  77     if(first == container.end())
  78         return true;
  79
  80     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
  81     ++next_;
  82
  83     while(next_ != container.end() && it_ != past)
  84         if(!icl::touches(key_value<IntervalContainerT>(it_++),
  85                          key_value<IntervalContainerT>(next_++)))
  86             return false;
  87
  88     return true;
  89 }
  90
  91
  92 template<class LeftT, class RightT>
  93 bool is_inclusion_equal(const LeftT& left, const RightT& right)
  94 {
  95     return subset_compare
  96             (
  97                 left, right,
  98                 left.begin(), left.end(),
  99                 right.begin(), right.end()
 100             ) == inclusion::equal;
 101 }
 102
 103 template<class LeftT, class RightT>
 104 typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>,
 105                              is_total<RightT> >,
 106                    bool>::type
 107 within(const LeftT&, const RightT&)
 108 {
 109     return true;
 110 }
 111
 112 template<class LeftT, class RightT>
 113 typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>,
 114                              mpl::not_<is_total<RightT> > >,
 115                    bool>::type
 116 within(const LeftT& sub, const RightT& super)
 117 {
 118     int result =
 119         subset_compare
 120         (
 121             sub, super,
 122             sub.begin(), sub.end(),
 123             super.begin(), super.end()
 124         );
 125     return result == inclusion::subset || result == inclusion::equal;
 126 }
 127
 128
 129 template<class LeftT, class RightT>
 130 typename enable_if<is_concept_combinable<is_interval_map, is_interval_map, LeftT, RightT>,
 131                    bool>::type
 132 within(const LeftT& sub, const RightT& super)
 133 {
 134     int result =
 135         subset_compare
 136         (
 137             sub, super,
 138             sub.begin(), sub.end(),
 139             super.begin(), super.end()
 140         );
 141     return result == inclusion::subset || result == inclusion::equal;
 142 }
 143
 144 template<class LeftT, class RightT>
 145 typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>,
 146                    bool>::type
 147 within(const LeftT& sub, const RightT& super)
 148 {
 149     int result =
 150         subset_compare
 151         (
 152             sub, super,
 153             sub.begin(), sub.end(),
 154             super.begin(), super.end()
 155         );
 156     return result == inclusion::subset || result == inclusion::equal;
 157 }
 158
 159
 160
 161 template<class LeftT, class RightT>
 162 typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>,
 163                              is_total<LeftT> >,
 164                    bool>::type
 165 contains(const LeftT&, const RightT&)
 166 {
 167     return true;
 168 }
 169
 170 template<class LeftT, class RightT>
 171 typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>,
 172                              mpl::not_<is_total<LeftT> > >,
 173                    bool>::type
 174 contains(const LeftT& super, const RightT& sub)
 175 {
 176     int result =
 177         subset_compare
 178         (
 179             super, sub,
 180             super.begin(), super.end(),
 181             sub.begin(), sub.end()
 182         );
 183     return result == inclusion::superset || result == inclusion::equal;
 184 }
 185
 186 template<class LeftT, class RightT>
 187 typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>,
 188                    bool>::type
 189 contains(const LeftT& super, const RightT& sub)
 190 {
 191     int result =
 192         subset_compare
 193         (
 194             super, sub,
 195             super.begin(), super.end(),
 196             sub.begin(), sub.end()
 197         );
 198     return result == inclusion::superset || result == inclusion::equal;
 199 }
 200
 201 template<class IntervalContainerT>
 202 bool is_dense(const IntervalContainerT& container,
 203               typename IntervalContainerT::const_iterator first,
 204               typename IntervalContainerT::const_iterator past)
 205 {
 206     if(first == container.end())
 207         return true;
 208
 209     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
 210     ++next_;
 211
 212     while(next_ != container.end() && it_ != past)
 213         if(!icl::touches(key_value<IntervalContainerT>(it_++),
 214                          key_value<IntervalContainerT>(next_++)))
 215             return false;
 216
 217     return true;
 218 }
 219
 220 } // namespace Interval_Set
 221
 222 namespace segmental
 223 {
 224
 225 template<class Type>
 226 inline bool joinable(const Type& _Type, typename Type::iterator& some, typename Type::iterator& next)
 227 {
 228     // assert: next != end && some++ == next
 229     return touches(key_value<Type>(some), key_value<Type>(next))
 230         && co_equal(some, next, &_Type, &_Type);
 231 }
 232
 233 template<class Type>
 234 inline void join_nodes(Type& object, typename Type::iterator& left_,
 235                                      typename Type::iterator& right_)
 236 {
 237     typedef typename Type::interval_type interval_type;
 238     interval_type right_interval = key_value<Type>(right_);
 239     object.erase(right_);
 240     const_cast<interval_type&>(key_value<Type>(left_))
 241         = hull(key_value<Type>(left_), right_interval);
 242 }
 243
 244 template<class Type>
 245 inline typename Type::iterator
 246     join_on_left(Type& object, typename Type::iterator& left_,
 247                                typename Type::iterator& right_)
 248 {
 249     //CL typedef typename Type::interval_type interval_type;
 250     // both left and right are in the set and they are neighbours
 251     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
 252     BOOST_ASSERT(joinable(object, left_, right_));
 253
 254     join_nodes(object, left_, right_);
 255     return left_;
 256 }
 257
 258 template<class Type>
 259 inline typename Type::iterator
 260     join_on_right(Type& object, typename Type::iterator& left_,
 261                                 typename Type::iterator& right_)
 262 {
 263     //CL typedef typename Type::interval_type interval_type;
 264     // both left and right are in the map and they are neighbours
 265     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
 266     BOOST_ASSERT(joinable(object, left_, right_));
 267
 268     join_nodes(object, left_, right_);
 269     right_ = left_;
 270     return right_;
 271 }
 272
 273 template<class Type>
 274 typename Type::iterator join_left(Type& object, typename Type::iterator& it_)
 275 {
 276     typedef typename Type::iterator iterator;
 277
 278     if(it_ == object.begin())
 279         return it_;
 280
 281     // there is a predecessor
 282     iterator pred_ = it_;
 283     if(joinable(object, --pred_, it_))
 284         return join_on_right(object, pred_, it_);
 285
 286     return it_;
 287 }
 288
 289 template<class Type>
 290 typename Type::iterator join_right(Type& object, typename Type::iterator& it_)
 291 {
 292     typedef typename Type::iterator iterator;
 293
 294     if(it_ == object.end())
 295         return it_;
 296
 297     // there is a successor
 298     iterator succ_ = it_;
 299
 300     if(++succ_ != object.end() && joinable(object, it_, succ_))
 301         return join_on_left(object, it_, succ_);
 302
 303     return it_;
 304 }
 305
 306 template<class Type>
 307 typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_)
 308 {
 309            join_left (object, it_);
 310     return join_right(object, it_);
 311 }
 312
 313 template<class Type>
 314 inline typename Type::iterator
 315     join_under(Type& object, const typename Type::value_type& addend)
 316 {
 317     //ASSERT: There is at least one interval in object that overlaps with addend
 318     typedef typename Type::iterator      iterator;
 319     typedef typename Type::interval_type interval_type;
 320     typedef typename Type::value_type    value_type;
 321
 322     std::pair<iterator,iterator> overlap = object.equal_range(addend);
 323     iterator first_ = overlap.first,
 324              end_   = overlap.second,
 325              last_  = end_; --last_;
 326
 327     iterator second_= first_; ++second_;
 328
 329     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
 330     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
 331
 332     object.erase(second_, end_);
 333
 334     const_cast<value_type&>(key_value<Type>(first_))
 335         = hull(hull(left_resid, addend), right_resid);
 336     return first_;
 337 }
 338
 339 template<class Type>
 340 inline typename Type::iterator
 341     join_under(Type& object, const typename Type::value_type& addend,
 342                                    typename Type::iterator last_)
 343 {
 344     //ASSERT: There is at least one interval in object that overlaps with addend
 345     typedef typename Type::iterator      iterator;
 346     typedef typename Type::interval_type interval_type;
 347     typedef typename Type::value_type    value_type;
 348
 349     iterator first_ = object.lower_bound(addend);
 350     //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
 351     iterator second_= boost::next(first_), end_ = boost::next(last_);
 352
 353     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
 354     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
 355
 356     object.erase(second_, end_);
 357
 358     const_cast<value_type&>(key_value<Type>(first_))
 359         = hull(hull(left_resid, addend), right_resid);
 360     return first_;
 361 }
 362
 363 } // namespace segmental
 364
 365 namespace Interval_Set
 366 {
 367 using namespace segmental;
 368
 369 template<class Type, int combining_style>
 370 struct on_style;
 371
 372 template<class Type>
 373 struct on_style<Type, interval_combine::joining>
 374 {
 375     typedef          on_style            type;
 376     typedef typename Type::interval_type interval_type;
 377     typedef typename Type::iterator      iterator;
 378
 379     inline static iterator handle_inserted(Type& object, iterator inserted_)
 380     { return join_neighbours(object, inserted_); }
 381
 382     inline static iterator add_over
 383         (Type& object, const interval_type& addend, iterator last_)
 384     {
 385         iterator joined_ = join_under(object, addend, last_);
 386         return join_neighbours(object, joined_);
 387     }
 388
 389     inline static iterator add_over
 390         (Type& object, const interval_type& addend)
 391     {
 392         iterator joined_ = join_under(object, addend);
 393         return join_neighbours(object, joined_);
 394     }
 395 };
 396
 397 template<class Type>
 398 struct on_style<Type, interval_combine::separating>
 399 {
 400     typedef          on_style            type;
 401     typedef typename Type::interval_type interval_type;
 402     typedef typename Type::iterator      iterator;
 403
 404     inline static iterator handle_inserted(Type&, iterator inserted_)
 405     { return inserted_; }
 406
 407     inline static iterator add_over
 408         (Type& object, const interval_type& addend, iterator last_)
 409     {
 410         return join_under(object, addend, last_);
 411     }
 412
 413     inline static iterator add_over
 414         (Type& object, const interval_type& addend)
 415     {
 416         return join_under(object, addend);
 417     }
 418 };
 419
 420 template<class Type>
 421 struct on_style<Type, interval_combine::splitting>
 422 {
 423     typedef          on_style            type;
 424     typedef typename Type::interval_type interval_type;
 425     typedef typename Type::iterator      iterator;
 426
 427     inline static iterator handle_inserted(Type&, iterator inserted_)
 428     { return inserted_; }
 429
 430     inline static iterator add_over
 431         (Type& object, const interval_type& addend, iterator last_)
 432     {
 433         iterator first_ = object.lower_bound(addend);
 434         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
 435
 436         iterator it_ = first_;
 437         interval_type rest_interval = addend;
 438
 439         add_front(object, rest_interval, it_);
 440         add_main (object, rest_interval, it_, last_);
 441         add_rear (object, rest_interval, it_);
 442         return it_;
 443     }
 444
 445     inline static iterator add_over
 446         (Type& object, const interval_type& addend)
 447     {
 448         std::pair<iterator,iterator> overlap = object.equal_range(addend);
 449         iterator first_ = overlap.first,
 450                  end_   = overlap.second,
 451                  last_  = end_; --last_;
 452
 453         iterator it_ = first_;
 454         interval_type rest_interval = addend;
 455
 456         add_front(object, rest_interval, it_);
 457         add_main (object, rest_interval, it_, last_);
 458         add_rear (object, rest_interval, it_);
 459
 460         return it_;
 461     }
 462 };
 463
 464
 465 template<class Type>
 466 void add_front(Type& object, const typename Type::interval_type& inter_val,
 467                                    typename Type::iterator&      first_)
 468 {
 469     typedef typename Type::interval_type interval_type;
 470     typedef typename Type::iterator      iterator;
 471     // If the collision sequence has a left residual 'left_resid' it will
 472     // be split, to provide a standardized start of algorithms:
 473     // The addend interval 'inter_val' covers the beginning of the collision sequence.
 474
 475     // only for the first there can be a left_resid: a part of *first_ left of inter_val
 476     interval_type left_resid = right_subtract(key_value<Type>(first_), inter_val);
 477
 478     if(!icl::is_empty(left_resid))
 479     {   //            [------------ . . .
 480         // [left_resid---first_ --- . . .
 481         iterator prior_ = cyclic_prior(object, first_);
 482         const_cast<interval_type&>(key_value<Type>(first_))
 483             = left_subtract(key_value<Type>(first_), left_resid);
 484         //NOTE: Only splitting
 485         object._insert(prior_, icl::make_value<Type>(left_resid, co_value<Type>(first_)));
 486     }
 487
 488     //POST:
 489     // [----- inter_val ---- . . .
 490     // ...[-- first_ --...
 491 }
 492
 493
 494 template<class Type>
 495 void add_segment(Type& object, const typename Type::interval_type& inter_val,
 496                                      typename Type::iterator&      it_      )
 497 {
 498     typedef typename Type::interval_type interval_type;
 499     interval_type lead_gap = right_subtract(inter_val, *it_);
 500     if(!icl::is_empty(lead_gap))
 501         //           [lead_gap--- . . .
 502         // [prior_)           [-- it_ ...
 503         object._insert(prior(it_), lead_gap);
 504
 505     // . . . --------- . . . addend interval
 506     //      [-- it_ --)      has a common part with the first overval
 507     ++it_;
 508 }
 509
 510
 511 template<class Type>
 512 void add_main(Type& object, typename Type::interval_type& rest_interval,
 513                             typename Type::iterator&      it_,
 514                       const typename Type::iterator&      last_)
 515 {
 516     typedef typename Type::interval_type interval_type;
 517     interval_type cur_interval;
 518     while(it_ != last_)
 519     {
 520         cur_interval = *it_ ;
 521         add_segment(object, rest_interval, it_);
 522         // shrink interval
 523         rest_interval = left_subtract(rest_interval, cur_interval);
 524     }
 525 }
 526
 527
 528 template<class Type>
 529 void add_rear(Type& object, const typename Type::interval_type& inter_val,
 530                                   typename Type::iterator&      it_      )
 531 {
 532     typedef typename Type::interval_type interval_type;
 533     typedef typename Type::iterator      iterator;
 534
 535     iterator prior_ = cyclic_prior(object, it_);
 536     interval_type cur_itv = *it_;
 537
 538     interval_type lead_gap = right_subtract(inter_val, cur_itv);
 539     if(!icl::is_empty(lead_gap))
 540         //          [lead_gap--- . . .
 541         // [prior_)          [-- it_ ...
 542         object._insert(prior_, lead_gap);
 543
 544     interval_type end_gap = left_subtract(inter_val, cur_itv);
 545     if(!icl::is_empty(end_gap))
 546         // [---------------end_gap)
 547         //      [-- it_ --)
 548         it_ = object._insert(it_, end_gap);
 549     else
 550     {
 551         // only for the last there can be a right_resid: a part of *it_ right of addend
 552         interval_type right_resid = left_subtract(cur_itv, inter_val);
 553
 554         if(!icl::is_empty(right_resid))
 555         {
 556             // [--------------)
 557             //      [-- it_ --right_resid)
 558             const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid);
 559             it_ = object._insert(it_, right_resid);
 560         }
 561     }
 562 }
 563
 564
 565 //==============================================================================
 566 //= Addition
 567 //==============================================================================
 568 template<class Type>
 569 typename Type::iterator
 570     add(Type& object, const typename Type::value_type& addend)
 571 {
 572     //CL typedef typename Type::interval_type interval_type;
 573     typedef typename Type::iterator      iterator;
 574     typedef typename on_style<Type, Type::fineness>::type on_style_;
 575
 576     if(icl::is_empty(addend))
 577         return object.end();
 578
 579     std::pair<iterator,bool> insertion = object._insert(addend);
 580
 581     if(insertion.second)
 582         return on_style_::handle_inserted(object, insertion.first);
 583     else
 584         return on_style_::add_over(object, addend, insertion.first);
 585 }
 586
 587
 588 template<class Type>
 589 typename Type::iterator
 590     add(Type& object, typename Type::iterator    prior_,
 591                 const typename Type::value_type& addend)
 592 {
 593     //CL typedef typename Type::interval_type interval_type;
 594     typedef typename Type::iterator      iterator;
 595     typedef typename on_style<Type, Type::fineness>::type on_style_;
 596
 597     if(icl::is_empty(addend))
 598         return prior_;
 599
 600     iterator insertion = object._insert(prior_, addend);
 601
 602     if(*insertion == addend)
 603         return on_style_::handle_inserted(object, insertion);
 604     else
 605         return on_style_::add_over(object, addend);
 606 }
 607
 608
 609 //==============================================================================
 610 //= Subtraction
 611 //==============================================================================
 612 template<class Type>
 613 void subtract(Type& object, const typename Type::value_type& minuend)
 614 {
 615     typedef typename Type::iterator      iterator;
 616     typedef typename Type::interval_type interval_type;
 617     //CL typedef typename Type::value_type    value_type;
 618
 619     if(icl::is_empty(minuend)) return;
 620
 621     std::pair<iterator, iterator> exterior = object.equal_range(minuend);
 622     if(exterior.first == exterior.second) return;
 623
 624     iterator first_ = exterior.first;
 625     iterator end_   = exterior.second;
 626     iterator last_  = end_; --last_;
 627
 628     interval_type leftResid = right_subtract(*first_, minuend);
 629     interval_type rightResid;
 630     if(first_ != end_  )
 631         rightResid = left_subtract(*last_ , minuend);
 632
 633     object.erase(first_, end_);
 634
 635     if(!icl::is_empty(leftResid))
 636         object._insert(leftResid);
 637
 638     if(!icl::is_empty(rightResid))
 639         object._insert(rightResid);
 640 }
 641
 642
 643 } // namespace Interval_Set
 644
 645 }} // namespace icl boost
 646
 647 #endif
 648