Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2008-2010: Joachim Faulhaber
Chris@16: +------------------------------------------------------------------------------+
Chris@16:    Distributed under the Boost Software License, Version 1.0.
Chris@16:       (See accompanying file LICENCE.txt or copy at
Chris@16:            http://www.boost.org/LICENSE_1_0.txt)
Chris@16: +-----------------------------------------------------------------------------*/
Chris@16: #ifndef BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
Chris@16: #define BOOST_ICL_INTERVAL_SET_ALGO_HPP_JOFA_081005
Chris@16: 
Chris@16: #include <boost/next_prior.hpp>
Chris@16: #include <boost/icl/detail/notate.hpp>
Chris@16: #include <boost/icl/detail/relation_state.hpp>
Chris@16: #include <boost/icl/type_traits/identity_element.hpp>
Chris@16: #include <boost/icl/type_traits/is_map.hpp>
Chris@16: #include <boost/icl/type_traits/is_total.hpp>
Chris@16: #include <boost/icl/type_traits/is_combinable.hpp>
Chris@16: #include <boost/icl/concept/set_value.hpp>
Chris@16: #include <boost/icl/concept/map_value.hpp>
Chris@16: #include <boost/icl/interval_combining_style.hpp>
Chris@16: #include <boost/icl/detail/element_comparer.hpp>
Chris@16: #include <boost/icl/detail/interval_subset_comparer.hpp>
Chris@16: #include <boost/icl/detail/associated_value.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: namespace Interval_Set
Chris@16: {
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: // Lexicographical comparison on ranges of two interval container 
Chris@16: //------------------------------------------------------------------------------
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: bool is_element_equal(const LeftT& left, const RightT& right)
Chris@16: {
Chris@16:     return subset_compare
Chris@16:             (
Chris@16:                 left, right, 
Chris@16:                 left.begin(), left.end(), 
Chris@16:                 right.begin(), right.end()
Chris@16:             ) == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: bool is_element_less(const LeftT& left, const RightT& right)
Chris@16: {
Chris@16:     return element_compare
Chris@16:             (
Chris@16:                 left, right, 
Chris@16:                 left.begin(), left.end(), 
Chris@16:                 right.begin(), right.end()
Chris@16:             )  == comparison::less;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: bool is_element_greater(const LeftT& left, const RightT& right)
Chris@16: {
Chris@16:     return element_compare
Chris@16:             (
Chris@16:                 left, right, 
Chris@16:                 left.begin(), left.end(), 
Chris@16:                 right.begin(), right.end()
Chris@16:             )  == comparison::greater;
Chris@16: }
Chris@16: 
Chris@16: //------------------------------------------------------------------------------
Chris@16: // Subset/superset compare on ranges of two interval container 
Chris@16: //------------------------------------------------------------------------------
Chris@16: 
Chris@16: template<class IntervalContainerT>
Chris@16: bool is_joinable(const IntervalContainerT& container, 
Chris@16:                  typename IntervalContainerT::const_iterator first, 
Chris@16:                  typename IntervalContainerT::const_iterator past) 
Chris@16: {
Chris@16:     if(first == container.end())
Chris@16:         return true;
Chris@16: 
Chris@16:     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
Chris@16:     ++next_;
Chris@16: 
Chris@16:     while(next_ != container.end() && it_ != past)
Chris@16:         if(!icl::touches(key_value<IntervalContainerT>(it_++),
Chris@16:                          key_value<IntervalContainerT>(next_++)))
Chris@16:             return false;
Chris@16: 
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: bool is_inclusion_equal(const LeftT& left, const RightT& right)
Chris@16: {
Chris@16:     return subset_compare
Chris@16:             (
Chris@16:                 left, right, 
Chris@16:                 left.begin(), left.end(), 
Chris@16:                 right.begin(), right.end()
Chris@16:             ) == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, 
Chris@16:                              is_total<RightT> >,
Chris@16:                    bool>::type
Chris@16: within(const LeftT&, const RightT&)
Chris@16: {
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<mpl::and_<is_concept_combinable<is_interval_set, is_interval_map, LeftT, RightT>, 
Chris@16:                              mpl::not_<is_total<RightT> > >,
Chris@16:                    bool>::type
Chris@16: within(const LeftT& sub, const RightT& super)
Chris@16: {
Chris@16:     int result =
Chris@16:         subset_compare
Chris@16:         (
Chris@16:             sub, super, 
Chris@16:             sub.begin(), sub.end(), 
Chris@16:             super.begin(), super.end()
Chris@16:         );
Chris@16:     return result == inclusion::subset || result == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_map, is_interval_map, LeftT, RightT>, 
Chris@16:                    bool>::type
Chris@16: within(const LeftT& sub, const RightT& super)
Chris@16: {
Chris@16:     int result =
Chris@16:         subset_compare
Chris@16:         (
Chris@16:             sub, super, 
Chris@16:             sub.begin(), sub.end(), 
Chris@16:             super.begin(), super.end()
Chris@16:         );
Chris@16:     return result == inclusion::subset || result == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, 
Chris@16:                    bool>::type
Chris@16: within(const LeftT& sub, const RightT& super)
Chris@16: {
Chris@16:     int result =
Chris@16:         subset_compare
Chris@16:         (
Chris@16:             sub, super, 
Chris@16:             sub.begin(), sub.end(), 
Chris@16:             super.begin(), super.end()
Chris@16:         );
Chris@16:     return result == inclusion::subset || result == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, 
Chris@16:                              is_total<LeftT> >,
Chris@16:                    bool>::type
Chris@16: contains(const LeftT&, const RightT&)
Chris@16: {
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<mpl::and_<is_concept_combinable<is_interval_map, is_interval_set, LeftT, RightT>, 
Chris@16:                              mpl::not_<is_total<LeftT> > >,
Chris@16:                    bool>::type
Chris@16: contains(const LeftT& super, const RightT& sub)
Chris@16: {
Chris@16:     int result =
Chris@16:         subset_compare
Chris@16:         (
Chris@16:             super, sub, 
Chris@16:             super.begin(), super.end(), 
Chris@16:             sub.begin(), sub.end()
Chris@16:         );
Chris@16:     return result == inclusion::superset || result == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: typename enable_if<is_concept_combinable<is_interval_set, is_interval_set, LeftT, RightT>, 
Chris@16:                    bool>::type
Chris@16: contains(const LeftT& super, const RightT& sub)
Chris@16: {
Chris@16:     int result =
Chris@16:         subset_compare
Chris@16:         (
Chris@16:             super, sub, 
Chris@16:             super.begin(), super.end(), 
Chris@16:             sub.begin(), sub.end()
Chris@16:         );
Chris@16:     return result == inclusion::superset || result == inclusion::equal;
Chris@16: }
Chris@16: 
Chris@16: template<class IntervalContainerT>
Chris@16: bool is_dense(const IntervalContainerT& container, 
Chris@16:               typename IntervalContainerT::const_iterator first, 
Chris@16:               typename IntervalContainerT::const_iterator past) 
Chris@16: {
Chris@16:     if(first == container.end())
Chris@16:         return true;
Chris@16: 
Chris@16:     typename IntervalContainerT::const_iterator it_ = first, next_ = first;
Chris@16:     ++next_;
Chris@16: 
Chris@16:     while(next_ != container.end() && it_ != past)
Chris@16:         if(!icl::touches(key_value<IntervalContainerT>(it_++), 
Chris@16:                          key_value<IntervalContainerT>(next_++)))
Chris@16:             return false;
Chris@16: 
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: } // namespace Interval_Set
Chris@16: 
Chris@16: namespace segmental
Chris@16: {
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline bool joinable(const Type& _Type, typename Type::iterator& some, typename Type::iterator& next)
Chris@16: {
Chris@16:     // assert: next != end && some++ == next
Chris@16:     return touches(key_value<Type>(some), key_value<Type>(next)) 
Chris@16:         && co_equal(some, next, &_Type, &_Type); 
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline void join_nodes(Type& object, typename Type::iterator& left_, 
Chris@16:                                      typename Type::iterator& right_)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     interval_type right_interval = key_value<Type>(right_);
Chris@16:     object.erase(right_);
Chris@16:     const_cast<interval_type&>(key_value<Type>(left_)) 
Chris@16:         = hull(key_value<Type>(left_), right_interval);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename Type::iterator 
Chris@16:     join_on_left(Type& object, typename Type::iterator& left_, 
Chris@16:                                typename Type::iterator& right_)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     // both left and right are in the set and they are neighbours
Chris@16:     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
Chris@16:     BOOST_ASSERT(joinable(object, left_, right_));
Chris@16: 
Chris@16:     join_nodes(object, left_, right_);
Chris@16:     return left_;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename Type::iterator 
Chris@16:     join_on_right(Type& object, typename Type::iterator& left_, 
Chris@16:                                 typename Type::iterator& right_)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     // both left and right are in the map and they are neighbours
Chris@16:     BOOST_ASSERT(exclusive_less(key_value<Type>(left_), key_value<Type>(right_)));
Chris@16:     BOOST_ASSERT(joinable(object, left_, right_));
Chris@16: 
Chris@16:     join_nodes(object, left_, right_);
Chris@16:     right_ = left_;
Chris@16:     return right_;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename Type::iterator join_left(Type& object, typename Type::iterator& it_)
Chris@16: {
Chris@16:     typedef typename Type::iterator iterator;
Chris@16: 
Chris@16:     if(it_ == object.begin())
Chris@16:         return it_;
Chris@16: 
Chris@16:     // there is a predecessor
Chris@16:     iterator pred_ = it_;
Chris@16:     if(joinable(object, --pred_, it_)) 
Chris@16:         return join_on_right(object, pred_, it_); 
Chris@16: 
Chris@16:     return it_;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename Type::iterator join_right(Type& object, typename Type::iterator& it_)
Chris@16: {
Chris@16:     typedef typename Type::iterator iterator;
Chris@16: 
Chris@16:     if(it_ == object.end())
Chris@16:         return it_;
Chris@16: 
Chris@16:     // there is a successor
Chris@16:     iterator succ_ = it_;
Chris@16: 
Chris@16:     if(++succ_ != object.end() && joinable(object, it_, succ_)) 
Chris@16:         return join_on_left(object, it_, succ_);
Chris@16: 
Chris@16:     return it_;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename Type::iterator join_neighbours(Type& object, typename Type::iterator& it_)
Chris@16: {
Chris@16:            join_left (object, it_); 
Chris@16:     return join_right(object, it_);
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename Type::iterator 
Chris@16:     join_under(Type& object, const typename Type::value_type& addend)
Chris@16: {
Chris@16:     //ASSERT: There is at least one interval in object that overlaps with addend
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::value_type    value_type;
Chris@16: 
Chris@16:     std::pair<iterator,iterator> overlap = object.equal_range(addend);
Chris@16:     iterator first_ = overlap.first,
Chris@16:              end_   = overlap.second,
Chris@16:              last_  = end_; --last_;
Chris@16: 
Chris@16:     iterator second_= first_; ++second_;
Chris@16: 
Chris@16:     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
Chris@16:     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
Chris@16: 
Chris@16:     object.erase(second_, end_);
Chris@16: 
Chris@16:     const_cast<value_type&>(key_value<Type>(first_)) 
Chris@16:         = hull(hull(left_resid, addend), right_resid);
Chris@16:     return first_;
Chris@16: }
Chris@16: 
Chris@16: template<class Type>
Chris@16: inline typename Type::iterator 
Chris@16:     join_under(Type& object, const typename Type::value_type& addend,
Chris@16:                                    typename Type::iterator last_)
Chris@16: {
Chris@16:     //ASSERT: There is at least one interval in object that overlaps with addend
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::value_type    value_type;
Chris@16: 
Chris@16:     iterator first_ = object.lower_bound(addend);
Chris@16:     //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
Chris@16:     iterator second_= boost::next(first_), end_ = boost::next(last_);
Chris@16: 
Chris@16:     interval_type left_resid  = right_subtract(key_value<Type>(first_), addend);
Chris@16:     interval_type right_resid =  left_subtract(key_value<Type>(last_) , addend);
Chris@16: 
Chris@16:     object.erase(second_, end_);
Chris@16: 
Chris@16:     const_cast<value_type&>(key_value<Type>(first_)) 
Chris@16:         = hull(hull(left_resid, addend), right_resid);
Chris@16:     return first_;
Chris@16: }
Chris@16: 
Chris@16: } // namespace segmental
Chris@16: 
Chris@16: namespace Interval_Set
Chris@16: {
Chris@16: using namespace segmental;
Chris@16: 
Chris@16: template<class Type, int combining_style>
Chris@16: struct on_style;
Chris@16: 
Chris@16: template<class Type>
Chris@16: struct on_style<Type, interval_combine::joining>
Chris@16: {
Chris@16:     typedef          on_style            type;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16: 
Chris@16:     inline static iterator handle_inserted(Type& object, iterator inserted_)
Chris@16:     { return join_neighbours(object, inserted_); }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend, iterator last_)
Chris@16:     {
Chris@16:         iterator joined_ = join_under(object, addend, last_);
Chris@16:         return join_neighbours(object, joined_);
Chris@16:     }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend)
Chris@16:     {
Chris@16:         iterator joined_ = join_under(object, addend);
Chris@16:         return join_neighbours(object, joined_);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template<class Type>
Chris@16: struct on_style<Type, interval_combine::separating>
Chris@16: {
Chris@16:     typedef          on_style            type;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16: 
Chris@16:     inline static iterator handle_inserted(Type&, iterator inserted_)
Chris@16:     { return inserted_; }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend, iterator last_)
Chris@16:     {
Chris@16:         return join_under(object, addend, last_);
Chris@16:     }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend)
Chris@16:     {
Chris@16:         return join_under(object, addend);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template<class Type>
Chris@16: struct on_style<Type, interval_combine::splitting>
Chris@16: {
Chris@16:     typedef          on_style            type;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16: 
Chris@16:     inline static iterator handle_inserted(Type&, iterator inserted_)
Chris@16:     { return inserted_; }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend, iterator last_)
Chris@16:     {
Chris@16:         iterator first_ = object.lower_bound(addend);
Chris@16:         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
Chris@16: 
Chris@16:         iterator it_ = first_;
Chris@16:         interval_type rest_interval = addend;
Chris@16: 
Chris@16:         add_front(object, rest_interval, it_);
Chris@16:         add_main (object, rest_interval, it_, last_);
Chris@16:         add_rear (object, rest_interval, it_);
Chris@16:         return it_;
Chris@16:     }
Chris@16: 
Chris@16:     inline static iterator add_over
Chris@16:         (Type& object, const interval_type& addend)
Chris@16:     {
Chris@16:         std::pair<iterator,iterator> overlap = object.equal_range(addend);
Chris@16:         iterator first_ = overlap.first,
Chris@16:                  end_   = overlap.second,
Chris@16:                  last_  = end_; --last_;
Chris@16: 
Chris@16:         iterator it_ = first_;
Chris@16:         interval_type rest_interval = addend;
Chris@16: 
Chris@16:         add_front(object, rest_interval, it_);
Chris@16:         add_main (object, rest_interval, it_, last_);
Chris@16:         add_rear (object, rest_interval, it_);
Chris@16: 
Chris@16:         return it_;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: void add_front(Type& object, const typename Type::interval_type& inter_val, 
Chris@16:                                    typename Type::iterator&      first_)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     // If the collision sequence has a left residual 'left_resid' it will
Chris@16:     // be split, to provide a standardized start of algorithms:
Chris@16:     // The addend interval 'inter_val' covers the beginning of the collision sequence.
Chris@16: 
Chris@16:     // only for the first there can be a left_resid: a part of *first_ left of inter_val
Chris@16:     interval_type left_resid = right_subtract(key_value<Type>(first_), inter_val);
Chris@16: 
Chris@16:     if(!icl::is_empty(left_resid))
Chris@16:     {   //            [------------ . . .
Chris@16:         // [left_resid---first_ --- . . .
Chris@16:         iterator prior_ = cyclic_prior(object, first_);
Chris@16:         const_cast<interval_type&>(key_value<Type>(first_)) 
Chris@16:             = left_subtract(key_value<Type>(first_), left_resid);
Chris@16:         //NOTE: Only splitting
Chris@16:         object._insert(prior_, icl::make_value<Type>(left_resid, co_value<Type>(first_)));
Chris@16:     }
Chris@16: 
Chris@16:     //POST:
Chris@16:     // [----- inter_val ---- . . .
Chris@16:     // ...[-- first_ --...
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: void add_segment(Type& object, const typename Type::interval_type& inter_val, 
Chris@16:                                      typename Type::iterator&      it_      )
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     interval_type lead_gap = right_subtract(inter_val, *it_);
Chris@16:     if(!icl::is_empty(lead_gap))
Chris@16:         //           [lead_gap--- . . .
Chris@16:         // [prior_)           [-- it_ ...
Chris@16:         object._insert(prior(it_), lead_gap);
Chris@16: 
Chris@16:     // . . . --------- . . . addend interval
Chris@16:     //      [-- it_ --)      has a common part with the first overval
Chris@16:     ++it_;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: void add_main(Type& object, typename Type::interval_type& rest_interval, 
Chris@16:                             typename Type::iterator&      it_,
Chris@16:                       const typename Type::iterator&      last_)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     interval_type cur_interval;
Chris@16:     while(it_ != last_)
Chris@16:     {
Chris@16:         cur_interval = *it_ ;
Chris@16:         add_segment(object, rest_interval, it_);
Chris@16:         // shrink interval
Chris@16:         rest_interval = left_subtract(rest_interval, cur_interval);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: void add_rear(Type& object, const typename Type::interval_type& inter_val, 
Chris@16:                                   typename Type::iterator&      it_      )
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16: 
Chris@16:     iterator prior_ = cyclic_prior(object, it_);
Chris@16:     interval_type cur_itv = *it_;
Chris@16: 
Chris@16:     interval_type lead_gap = right_subtract(inter_val, cur_itv);
Chris@16:     if(!icl::is_empty(lead_gap))
Chris@16:         //          [lead_gap--- . . .
Chris@16:         // [prior_)          [-- it_ ...
Chris@16:         object._insert(prior_, lead_gap);
Chris@16:     
Chris@16:     interval_type end_gap = left_subtract(inter_val, cur_itv);
Chris@16:     if(!icl::is_empty(end_gap))
Chris@16:         // [---------------end_gap)
Chris@16:         //      [-- it_ --)
Chris@16:         it_ = object._insert(it_, end_gap);
Chris@16:     else
Chris@16:     {
Chris@16:         // only for the last there can be a right_resid: a part of *it_ right of addend
Chris@16:         interval_type right_resid = left_subtract(cur_itv, inter_val);
Chris@16: 
Chris@16:         if(!icl::is_empty(right_resid))
Chris@16:         {
Chris@16:             // [--------------)
Chris@16:             //      [-- it_ --right_resid)
Chris@16:             const_cast<interval_type&>(*it_) = right_subtract(*it_, right_resid);
Chris@16:             it_ = object._insert(it_, right_resid);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: typename Type::iterator 
Chris@16:     add(Type& object, const typename Type::value_type& addend)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     typedef typename on_style<Type, Type::fineness>::type on_style_;
Chris@16: 
Chris@16:     if(icl::is_empty(addend)) 
Chris@16:         return object.end();
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion = object._insert(addend);
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return on_style_::handle_inserted(object, insertion.first);
Chris@16:     else
Chris@16:         return on_style_::add_over(object, addend, insertion.first);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template<class Type>
Chris@16: typename Type::iterator 
Chris@16:     add(Type& object, typename Type::iterator    prior_, 
Chris@16:                 const typename Type::value_type& addend)
Chris@16: {
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     typedef typename on_style<Type, Type::fineness>::type on_style_;
Chris@16: 
Chris@16:     if(icl::is_empty(addend)) 
Chris@16:         return prior_;
Chris@16: 
Chris@16:     iterator insertion = object._insert(prior_, addend);
Chris@16: 
Chris@16:     if(*insertion == addend)
Chris@16:         return on_style_::handle_inserted(object, insertion);
Chris@16:     else
Chris@16:         return on_style_::add_over(object, addend);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction
Chris@16: //==============================================================================
Chris@16: template<class Type>
Chris@16: void subtract(Type& object, const typename Type::value_type& minuend)
Chris@16: {
Chris@16:     typedef typename Type::iterator      iterator;
Chris@16:     typedef typename Type::interval_type interval_type;
Chris@16:     typedef typename Type::value_type    value_type;
Chris@16: 
Chris@16:     if(icl::is_empty(minuend)) return;
Chris@16: 
Chris@16:     std::pair<iterator, iterator> exterior = object.equal_range(minuend);
Chris@16:     if(exterior.first == exterior.second) return;
Chris@16: 
Chris@16:     iterator first_ = exterior.first;
Chris@16:     iterator end_   = exterior.second;
Chris@16:     iterator last_  = end_; --last_;
Chris@16: 
Chris@16:     interval_type leftResid = right_subtract(*first_, minuend);
Chris@16:     interval_type rightResid; 
Chris@16:     if(first_ != end_  )
Chris@16:         rightResid = left_subtract(*last_ , minuend);
Chris@16: 
Chris@16:     object.erase(first_, end_);
Chris@16: 
Chris@16:     if(!icl::is_empty(leftResid))
Chris@16:         object._insert(leftResid);
Chris@16: 
Chris@16:     if(!icl::is_empty(rightResid))
Chris@16:         object._insert(rightResid);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace Interval_Set
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif 
Chris@16: