icl/detail/interval_set_algo.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2008-2010: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
0009 #define BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
0010
0011 #include <boost/next_prior.hpp>
0012 #include <boost/icl/detail/notate.hpp>
0013 #include <boost/icl/detail/relation_state.hpp>
0014 #include <boost/icl/type_traits/identity_element.hpp>
0015 #include <boost/icl/type_traits/is_map.hpp>
0016 #include <boost/icl/type_traits/is_total.hpp>
0017 #include <boost/icl/type_traits/is_combinable.hpp>
0018 #include <boost/icl/concept/set_value.hpp>
0019 #include <boost/icl/concept/map_value.hpp>
0020 #include <boost/icl/interval_combining_style.hpp>
0021 #include <boost/icl/detail/element_comparer.hpp>
0022 #include <boost/icl/detail/interval_subset_comparer.hpp>
0023 #include <boost/icl/detail/associated_value.hpp>
0024
0025 namespace boost{namespace icl
0026 {
0027
0028 namespace Interval_Set
0029 {
0030
0031 //------------------------------------------------------------------------------
0032 // Lexicographical comparison on ranges of two interval container
0033 //------------------------------------------------------------------------------
0034
0035 template<class LeftT, class RightT>
0036 bool is_element_equal(const LeftT& left, const RightT& right)
0037 {
0038     return subset_compare
0039             (
0040                 left, right,
0041                 left.begin(), left.end(),
0042                 right.begin(), right.end()
0043             ) == inclusion::equal;
0044 }
0045
0046 template<class LeftT, class RightT>
0047 bool is_element_less(const LeftT& left, const RightT& right)
0048 {
0049     return element_compare
0050             (
0051                 left, right,
0052                 left.begin(), left.end(),
0053                 right.begin(), right.end()
0054             )  == comparison::less;
0055 }
0056
0057 template<class LeftT, class RightT>
0058 bool is_element_greater(const LeftT& left, const RightT& right)
0059 {
0060     return element_compare
0061             (
0062                 left, right,
0063                 left.begin(), left.end(),
0064                 right.begin(), right.end()
0065             )  == comparison::greater;
0066 }
0067
0068 //------------------------------------------------------------------------------
0069 // Subset/superset compare on ranges of two interval container
0070 //------------------------------------------------------------------------------
0071
0072 template<class IntervalContainerT>
0073 bool is_joinable(const IntervalContainerT& container,
0074                  typename IntervalContainerT::const_iterator first,
0075                  typename IntervalContainerT::const_iterator past)
0076 {
0077     if(first == container.end())
0078         return true;
0079
0080     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
0081     ++next_;
0082
0083     while(next_ != container.end() && it_ != past)
0084         if(!icl::touches(key_value<IntervalContainerT>(it_++),
0085                          key_value<IntervalContainerT>(next_++)))
0086             return false;
0087
0088     return true;
0089 }
0090
0091
0092 template<class LeftT, class RightT>
0093 bool is_inclusion_equal(const LeftT& left, const RightT& right)
0094 {
0095     return subset_compare
0096             (
0097                 left, right,
0098                 left.begin(), left.end(),
0099                 right.begin(), right.end()
0100             ) == inclusion::equal;
0101 }
0102
0103 template<class LeftT, class RightT>
0104 typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>,
0105                              is_total<RightT> >,
0106                    bool>::type
0107 within(const LeftT&, const RightT&)
0108 {
0109     return true;
0110 }
0111
0112 template<class LeftT, class RightT>
0113 typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>,
0114                              mpl::not_<is_total<RightT> > >,
0115                    bool>::type
0116 within(const LeftT& sub, const RightT& super)
0117 {
0118     int result =
0119         subset_compare
0120         (
0121             sub, super,
0122             sub.begin(), sub.end(),
0123             super.begin(), super.end()
0124         );
0125     return result == inclusion::subset || result == inclusion::equal;
0126 }
0127
0128
0129 template<class LeftT, class RightT>
0130 typename enable_if<is_concept_combinable<is_interval_map, is_interval_map, LeftT, RightT>,
0131                    bool>::type
0132 within(const LeftT& sub, const RightT& super)
0133 {
0134     int result =
0135         subset_compare
0136         (
0137             sub, super,
0138             sub.begin(), sub.end(),
0139             super.begin(), super.end()
0140         );
0141     return result == inclusion::subset || result == inclusion::equal;
0142 }
0143
0144 template<class LeftT, class RightT>
0145 typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>,
0146                    bool>::type
0147 within(const LeftT& sub, const RightT& super)
0148 {
0149     int result =
0150         subset_compare
0151         (
0152             sub, super,
0153             sub.begin(), sub.end(),
0154             super.begin(), super.end()
0155         );
0156     return result == inclusion::subset || result == inclusion::equal;
0157 }
0158
0159
0160
0161 template<class LeftT, class RightT>
0162 typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>,
0163                              is_total<LeftT> >,
0164                    bool>::type
0165 contains(const LeftT&, const RightT&)
0166 {
0167     return true;
0168 }
0169
0170 template<class LeftT, class RightT>
0171 typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>,
0172                              mpl::not_<is_total<LeftT> > >,
0173                    bool>::type
0174 contains(const LeftT& super, const RightT& sub)
0175 {
0176     int result =
0177         subset_compare
0178         (
0179             super, sub,
0180             super.begin(), super.end(),
0181             sub.begin(), sub.end()
0182         );
0183     return result == inclusion::superset || result == inclusion::equal;
0184 }
0185
0186 template<class LeftT, class RightT>
0187 typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>,
0188                    bool>::type
0189 contains(const LeftT& super, const RightT& sub)
0190 {
0191     int result =
0192         subset_compare
0193         (
0194             super, sub,
0195             super.begin(), super.end(),
0196             sub.begin(), sub.end()
0197         );
0198     return result == inclusion::superset || result == inclusion::equal;
0199 }
0200
0201 template<class IntervalContainerT>
0202 bool is_dense(const IntervalContainerT& container,
0203               typename IntervalContainerT::const_iterator first,
0204               typename IntervalContainerT::const_iterator past)
0205 {
0206     if(first == container.end())
0207         return true;
0208
0209     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
0210     ++next_;
0211
0212     while(next_ != container.end() && it_ != past)
0213         if(!icl::touches(key_value<IntervalContainerT>(it_++),
0214                          key_value<IntervalContainerT>(next_++)))
0215             return false;
0216
0217     return true;
0218 }
0219
0220 } // namespace Interval_Set
0221
0222 namespace segmental
0223 {
0224
0225 template<class Type>
0226 inline bool joinable(const Type& _Type, typename Type::iterator& some, typename Type::iterator& next)
0227 {
0228     // assert: next != end && some++ == next
0229     return touches(key_value<Type>(some), key_value<Type>(next))
0230         && co_equal(some, next, &_Type, &_Type);
0231 }
0232
0233 template<class Type>
0234 inline void join_nodes(Type& object, typename Type::iterator& left_,
0235                                      typename Type::iterator& right_)
0236 {
0237     typedef typename Type::interval_type interval_type;
0238     interval_type right_interval = key_value<Type>(right_);
0239     object.erase(right_);
0240     const_cast<interval_type&>(key_value<Type>(left_))
0241         = hull(key_value<Type>(left_), right_interval);
0242 }
0243
0244 template<class Type>
0245 inline typename Type::iterator
0246     join_on_left(Type& object, typename Type::iterator& left_,
0247                                typename Type::iterator& right_)
0248 {
0249     //CL typedef typename Type::interval_type interval_type;
0250     // both left and right are in the set and they are neighbours
0251     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
0252     BOOST_ASSERT(joinable(object, left_, right_));
0253
0254     join_nodes(object, left_, right_);
0255     return left_;
0256 }
0257
0258 template<class Type>
0259 inline typename Type::iterator
0260     join_on_right(Type& object, typename Type::iterator& left_,
0261                                 typename Type::iterator& right_)
0262 {
0263     //CL typedef typename Type::interval_type interval_type;
0264     // both left and right are in the map and they are neighbours
0265     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
0266     BOOST_ASSERT(joinable(object, left_, right_));
0267
0268     join_nodes(object, left_, right_);
0269     right_ = left_;
0270     return right_;
0271 }
0272
0273 template<class Type>
0274 typename Type::iterator join_left(Type& object, typename Type::iterator& it_)
0275 {
0276     typedef typename Type::iterator iterator;
0277
0278     if(it_ == object.begin())
0279         return it_;
0280
0281     // there is a predecessor
0282     iterator pred_ = it_;
0283     if(joinable(object, --pred_, it_))
0284         return join_on_right(object, pred_, it_);
0285
0286     return it_;
0287 }
0288
0289 template<class Type>
0290 typename Type::iterator join_right(Type& object, typename Type::iterator& it_)
0291 {
0292     typedef typename Type::iterator iterator;
0293
0294     if(it_ == object.end())
0295         return it_;
0296
0297     // there is a successor
0298     iterator succ_ = it_;
0299
0300     if(++succ_ != object.end() && joinable(object, it_, succ_))
0301         return join_on_left(object, it_, succ_);
0302
0303     return it_;
0304 }
0305
0306 template<class Type>
0307 typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_)
0308 {
0309            join_left (object, it_);
0310     return join_right(object, it_);
0311 }
0312
0313 template<class Type>
0314 inline typename Type::iterator
0315     join_under(Type& object, const typename Type::value_type& addend)
0316 {
0317     //ASSERT: There is at least one interval in object that overlaps with addend
0318     typedef typename Type::iterator      iterator;
0319     typedef typename Type::interval_type interval_type;
0320     typedef typename Type::value_type    value_type;
0321
0322     std::pair<iterator,iterator> overlap = object.equal_range(addend);
0323     iterator first_ = overlap.first,
0324              end_   = overlap.second,
0325              last_  = end_; --last_;
0326
0327     iterator second_= first_; ++second_;
0328
0329     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
0330     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
0331
0332     object.erase(second_, end_);
0333
0334     const_cast<value_type&>(key_value<Type>(first_))
0335         = hull(hull(left_resid, addend), right_resid);
0336     return first_;
0337 }
0338
0339 template<class Type>
0340 inline typename Type::iterator
0341     join_under(Type& object, const typename Type::value_type& addend,
0342                                    typename Type::iterator last_)
0343 {
0344     //ASSERT: There is at least one interval in object that overlaps with addend
0345     typedef typename Type::iterator      iterator;
0346     typedef typename Type::interval_type interval_type;
0347     typedef typename Type::value_type    value_type;
0348
0349     iterator first_ = object.lower_bound(addend);
0350     //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
0351     iterator second_= boost::next(first_), end_ = boost::next(last_);
0352
0353     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
0354     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
0355
0356     object.erase(second_, end_);
0357
0358     const_cast<value_type&>(key_value<Type>(first_))
0359         = hull(hull(left_resid, addend), right_resid);
0360     return first_;
0361 }
0362
0363 } // namespace segmental
0364
0365 namespace Interval_Set
0366 {
0367 using namespace segmental;
0368
0369 template<class Type, int combining_style>
0370 struct on_style;
0371
0372 template<class Type>
0373 struct on_style<Type, interval_combine::joining>
0374 {
0375     typedef          on_style            type;
0376     typedef typename Type::interval_type interval_type;
0377     typedef typename Type::iterator      iterator;
0378
0379     inline static iterator handle_inserted(Type& object, iterator inserted_)
0380     { return join_neighbours(object, inserted_); }
0381
0382     inline static iterator add_over
0383         (Type& object, const interval_type& addend, iterator last_)
0384     {
0385         iterator joined_ = join_under(object, addend, last_);
0386         return join_neighbours(object, joined_);
0387     }
0388
0389     inline static iterator add_over
0390         (Type& object, const interval_type& addend)
0391     {
0392         iterator joined_ = join_under(object, addend);
0393         return join_neighbours(object, joined_);
0394     }
0395 };
0396
0397 template<class Type>
0398 struct on_style<Type, interval_combine::separating>
0399 {
0400     typedef          on_style            type;
0401     typedef typename Type::interval_type interval_type;
0402     typedef typename Type::iterator      iterator;
0403
0404     inline static iterator handle_inserted(Type&, iterator inserted_)
0405     { return inserted_; }
0406
0407     inline static iterator add_over
0408         (Type& object, const interval_type& addend, iterator last_)
0409     {
0410         return join_under(object, addend, last_);
0411     }
0412
0413     inline static iterator add_over
0414         (Type& object, const interval_type& addend)
0415     {
0416         return join_under(object, addend);
0417     }
0418 };
0419
0420 template<class Type>
0421 struct on_style<Type, interval_combine::splitting>
0422 {
0423     typedef          on_style            type;
0424     typedef typename Type::interval_type interval_type;
0425     typedef typename Type::iterator      iterator;
0426
0427     inline static iterator handle_inserted(Type&, iterator inserted_)
0428     { return inserted_; }
0429
0430     inline static iterator add_over
0431         (Type& object, const interval_type& addend, iterator last_)
0432     {
0433         iterator first_ = object.lower_bound(addend);
0434         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
0435
0436         iterator it_ = first_;
0437         interval_type rest_interval = addend;
0438
0439         add_front(object, rest_interval, it_);
0440         add_main (object, rest_interval, it_, last_);
0441         add_rear (object, rest_interval, it_);
0442         return it_;
0443     }
0444
0445     inline static iterator add_over
0446         (Type& object, const interval_type& addend)
0447     {
0448         std::pair<iterator,iterator> overlap = object.equal_range(addend);
0449         iterator first_ = overlap.first,
0450                  end_   = overlap.second,
0451                  last_  = end_; --last_;
0452
0453         iterator it_ = first_;
0454         interval_type rest_interval = addend;
0455
0456         add_front(object, rest_interval, it_);
0457         add_main (object, rest_interval, it_, last_);
0458         add_rear (object, rest_interval, it_);
0459
0460         return it_;
0461     }
0462 };
0463
0464
0465 template<class Type>
0466 void add_front(Type& object, const typename Type::interval_type& inter_val,
0467                                    typename Type::iterator&      first_)
0468 {
0469     typedef typename Type::interval_type interval_type;
0470     typedef typename Type::iterator      iterator;
0471     // If the collision sequence has a left residual 'left_resid' it will
0472     // be split, to provide a standardized start of algorithms:
0473     // The addend interval 'inter_val' covers the beginning of the collision sequence.
0474
0475     // only for the first there can be a left_resid: a part of *first_ left of inter_val
0476     interval_type left_resid = right_subtract(key_value<Type>(first_), inter_val);
0477
0478     if(!icl::is_empty(left_resid))
0479     {   //            [------------ . . .
0480         // [left_resid---first_ --- . . .
0481         iterator prior_ = cyclic_prior(object, first_);
0482         const_cast<interval_type&>(key_value<Type>(first_))
0483             = left_subtract(key_value<Type>(first_), left_resid);
0484         //NOTE: Only splitting
0485         object._insert(prior_, icl::make_value<Type>(left_resid, co_value<Type>(first_)));
0486     }
0487
0488     //POST:
0489     // [----- inter_val ---- . . .
0490     // ...[-- first_ --...
0491 }
0492
0493
0494 template<class Type>
0495 void add_segment(Type& object, const typename Type::interval_type& inter_val,
0496                                      typename Type::iterator&      it_      )
0497 {
0498     typedef typename Type::interval_type interval_type;
0499     interval_type lead_gap = right_subtract(inter_val, *it_);
0500     if(!icl::is_empty(lead_gap))
0501         //           [lead_gap--- . . .
0502         // [prior_)           [-- it_ ...
0503         object._insert(prior(it_), lead_gap);
0504
0505     // . . . --------- . . . addend interval
0506     //      [-- it_ --)      has a common part with the first overval
0507     ++it_;
0508 }
0509
0510
0511 template<class Type>
0512 void add_main(Type& object, typename Type::interval_type& rest_interval,
0513                             typename Type::iterator&      it_,
0514                       const typename Type::iterator&      last_)
0515 {
0516     typedef typename Type::interval_type interval_type;
0517     interval_type cur_interval;
0518     while(it_ != last_)
0519     {
0520         cur_interval = *it_ ;
0521         add_segment(object, rest_interval, it_);
0522         // shrink interval
0523         rest_interval = left_subtract(rest_interval, cur_interval);
0524     }
0525 }
0526
0527
0528 template<class Type>
0529 void add_rear(Type& object, const typename Type::interval_type& inter_val,
0530                                   typename Type::iterator&      it_      )
0531 {
0532     typedef typename Type::interval_type interval_type;
0533     typedef typename Type::iterator      iterator;
0534
0535     iterator prior_ = cyclic_prior(object, it_);
0536     interval_type cur_itv = *it_;
0537
0538     interval_type lead_gap = right_subtract(inter_val, cur_itv);
0539     if(!icl::is_empty(lead_gap))
0540         //          [lead_gap--- . . .
0541         // [prior_)          [-- it_ ...
0542         object._insert(prior_, lead_gap);
0543
0544     interval_type end_gap = left_subtract(inter_val, cur_itv);
0545     if(!icl::is_empty(end_gap))
0546         // [---------------end_gap)
0547         //      [-- it_ --)
0548         it_ = object._insert(it_, end_gap);
0549     else
0550     {
0551         // only for the last there can be a right_resid: a part of *it_ right of addend
0552         interval_type right_resid = left_subtract(cur_itv, inter_val);
0553
0554         if(!icl::is_empty(right_resid))
0555         {
0556             // [--------------)
0557             //      [-- it_ --right_resid)
0558             const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid);
0559             it_ = object._insert(it_, right_resid);
0560         }
0561     }
0562 }
0563
0564
0565 //==============================================================================
0566 //= Addition
0567 //==============================================================================
0568 template<class Type>
0569 typename Type::iterator
0570     add(Type& object, const typename Type::value_type& addend)
0571 {
0572     //CL typedef typename Type::interval_type interval_type;
0573     typedef typename Type::iterator      iterator;
0574     typedef typename on_style<Type, Type::fineness>::type on_style_;
0575
0576     if(icl::is_empty(addend))
0577         return object.end();
0578
0579     std::pair<iterator,bool> insertion = object._insert(addend);
0580
0581     if(insertion.second)
0582         return on_style_::handle_inserted(object, insertion.first);
0583     else
0584         return on_style_::add_over(object, addend, insertion.first);
0585 }
0586
0587
0588 template<class Type>
0589 typename Type::iterator
0590     add(Type& object, typename Type::iterator    prior_,
0591                 const typename Type::value_type& addend)
0592 {
0593     //CL typedef typename Type::interval_type interval_type;
0594     typedef typename Type::iterator      iterator;
0595     typedef typename on_style<Type, Type::fineness>::type on_style_;
0596
0597     if(icl::is_empty(addend))
0598         return prior_;
0599
0600     iterator insertion = object._insert(prior_, addend);
0601
0602     if(*insertion == addend)
0603         return on_style_::handle_inserted(object, insertion);
0604     else
0605         return on_style_::add_over(object, addend);
0606 }
0607
0608
0609 //==============================================================================
0610 //= Subtraction
0611 //==============================================================================
0612 template<class Type>
0613 void subtract(Type& object, const typename Type::value_type& minuend)
0614 {
0615     typedef typename Type::iterator      iterator;
0616     typedef typename Type::interval_type interval_type;
0617     //CL typedef typename Type::value_type    value_type;
0618
0619     if(icl::is_empty(minuend)) return;
0620
0621     std::pair<iterator, iterator> exterior = object.equal_range(minuend);
0622     if(exterior.first == exterior.second) return;
0623
0624     iterator first_ = exterior.first;
0625     iterator end_   = exterior.second;
0626     iterator last_  = end_; --last_;
0627
0628     interval_type leftResid = right_subtract(*first_, minuend);
0629     interval_type rightResid;
0630     if(first_ != end_  )
0631         rightResid = left_subtract(*last_ , minuend);
0632
0633     object.erase(first_, end_);
0634
0635     if(!icl::is_empty(leftResid))
0636         object._insert(leftResid);
0637
0638     if(!icl::is_empty(rightResid))
0639         object._insert(rightResid);
0640 }
0641
0642
0643 } // namespace Interval_Set
0644
0645 }} // namespace icl boost
0646
0647 #endif
0648