Chris@16: /*-----------------------------------------------------------------------------+
Chris@16: Copyright (c) 2007-2011: Joachim Faulhaber
Chris@16: Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
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_BASE_SET_H_JOFA_990223
Chris@16: #define BOOST_ICL_INTERVAL_BASE_SET_H_JOFA_990223
Chris@16: 
Chris@16: #include <boost/icl/impl_config.hpp>
Chris@16: 
Chris@16: #if defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION)
Chris@16: #   include <boost/container/set.hpp>
Chris@16: #elif defined(ICL_USE_STD_IMPLEMENTATION)
Chris@16: #   include <set>
Chris@16: #else // Default for implementing containers
Chris@16: #   include <set>
Chris@16: #endif
Chris@16: 
Chris@16: #include <limits>
Chris@16: #include <boost/next_prior.hpp> 
Chris@16: #include <boost/icl/associative_interval_container.hpp>
Chris@16: #include <boost/icl/type_traits/interval_type_default.hpp>
Chris@16: #include <boost/icl/interval.hpp>
Chris@16: #include <boost/icl/type_traits/infinity.hpp>
Chris@16: #include <boost/icl/type_traits/is_interval_joiner.hpp>
Chris@16: #include <boost/icl/type_traits/is_interval_separator.hpp>
Chris@16: #include <boost/icl/type_traits/is_interval_splitter.hpp>
Chris@16: #include <boost/icl/detail/interval_set_algo.hpp>
Chris@16: #include <boost/icl/detail/exclusive_less_than.hpp>
Chris@16: 
Chris@16: #include <boost/icl/right_open_interval.hpp>
Chris@16: #include <boost/icl/continuous_interval.hpp>
Chris@16: #include <boost/icl/detail/notate.hpp>
Chris@16: #include <boost/icl/detail/element_iterator.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: /** \brief Implements a set as a set of intervals (base class) */
Chris@16: template 
Chris@16: <
Chris@16:     typename             SubType,
Chris@16:     typename             DomainT, 
Chris@16:     ICL_COMPARE Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
Chris@16:     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
Chris@16:     ICL_ALLOC   Alloc    = std::allocator
Chris@16: > 
Chris@16: class interval_base_set
Chris@16: {
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Associated types
Chris@16:     //==========================================================================
Chris@16:     typedef interval_base_set<SubType,DomainT,Compare,Interval,Alloc> type;
Chris@16: 
Chris@16:     /// The designated \e derived or \e sub_type of this base class
Chris@16:     typedef SubType sub_type;
Chris@16: 
Chris@16:     /// Auxilliary type for overloadresolution
Chris@16:     typedef type overloadable_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Data
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The domain type of the set
Chris@16:     typedef DomainT   domain_type;
Chris@16:     /// The codomaintype is the same as domain_type
Chris@16:     typedef DomainT   codomain_type;
Chris@16: 
Chris@16:     /// The element type of the set
Chris@16:     typedef DomainT   element_type;
Chris@16: 
Chris@16:     /// The interval type of the set
Chris@16:     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
Chris@16:     /// The segment type of the set
Chris@16:     typedef interval_type   segment_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Size
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The difference type of an interval which is sometimes different form the data_type
Chris@16:     typedef typename difference_type_of<domain_type>::type difference_type;
Chris@16: 
Chris@16:     /// The size type of an interval which is mostly std::size_t
Chris@16:     typedef typename size_type_of<domain_type>::type size_type;
Chris@16: 
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Order
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// Comparison functor for domain values
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,DomainT)      domain_compare;
Chris@16:     typedef ICL_COMPARE_DOMAIN(Compare,segment_type) segment_compare;
Chris@16:     /// Comparison functor for intervals
Chris@16:     typedef exclusive_less_than<interval_type>       interval_compare;
Chris@16: 
Chris@16:     /// Comparison functor for keys
Chris@16:     typedef exclusive_less_than<interval_type> key_compare;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Related types
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The atomized type representing the corresponding container of elements
Chris@16:     typedef typename ICL_IMPL_SPACE::set<DomainT,domain_compare,Alloc<DomainT> > atomized_type;
Chris@16: 
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     //- Associated types: Implementation and stl related
Chris@16:     //--------------------------------------------------------------------------
Chris@16:     /// The allocator type of the set
Chris@16:     typedef Alloc<interval_type> allocator_type;
Chris@16: 
Chris@16:     /// allocator type of the corresponding element set
Chris@16:     typedef Alloc<DomainT> domain_allocator_type;
Chris@16: 
Chris@16:     /// Container type for the implementation 
Chris@16:     typedef typename ICL_IMPL_SPACE::set<interval_type,key_compare,allocator_type> ImplSetT;
Chris@16: 
Chris@16:     /// key type of the implementing container
Chris@16:     typedef typename ImplSetT::key_type   key_type;
Chris@16:     /// data type of the implementing container
Chris@16:     typedef typename ImplSetT::key_type   data_type;
Chris@16:     /// value type of the implementing container
Chris@16:     typedef typename ImplSetT::value_type value_type;
Chris@16: 
Chris@16:     /// pointer type
Chris@16:     typedef typename ImplSetT::pointer         pointer;
Chris@16:     /// const pointer type
Chris@16:     typedef typename ImplSetT::const_pointer   const_pointer;
Chris@16:     /// reference type
Chris@16:     typedef typename ImplSetT::reference       reference;
Chris@16:     /// const reference type
Chris@16:     typedef typename ImplSetT::const_reference const_reference;
Chris@16: 
Chris@16:     /// iterator for iteration over intervals
Chris@16:     typedef typename ImplSetT::iterator iterator;
Chris@16:     /// const_iterator for iteration over intervals
Chris@16:     typedef typename ImplSetT::const_iterator const_iterator;
Chris@16:     /// iterator for reverse iteration over intervals
Chris@16:     typedef typename ImplSetT::reverse_iterator reverse_iterator;
Chris@16:     /// const_iterator for iteration over intervals
Chris@16:     typedef typename ImplSetT::const_reverse_iterator const_reverse_iterator;
Chris@16: 
Chris@16:     /// element iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<iterator> element_iterator; 
Chris@16:     /// element const iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<const_iterator> element_const_iterator; 
Chris@16:     /// element reverse iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<reverse_iterator> element_reverse_iterator; 
Chris@16:     /// element const reverse iterator: Depreciated, see documentation.
Chris@16:     typedef boost::icl::element_iterator<const_reverse_iterator> element_const_reverse_iterator; 
Chris@16: 
Chris@16:     BOOST_STATIC_CONSTANT(int, fineness = 0); 
Chris@16: 
Chris@16: public:
Chris@16:     //==========================================================================
Chris@16:     //= Construct, copy, destruct
Chris@16:     //==========================================================================
Chris@16:     /** Default constructor for the empty object */
Chris@16:     interval_base_set(){}
Chris@16: 
Chris@16:     /** Copy constructor */
Chris@16:     interval_base_set(const interval_base_set& src): _set(src._set)
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:     }
Chris@16: 
Chris@16: #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16:     //==========================================================================
Chris@16:     //= Move semantics
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Move constructor */
Chris@16:     interval_base_set(interval_base_set&& src): _set(boost::move(src._set))
Chris@16:     {
Chris@16:         BOOST_CONCEPT_ASSERT((DefaultConstructibleConcept<DomainT>));
Chris@16:         BOOST_CONCEPT_ASSERT((LessThanComparableConcept<DomainT>));
Chris@16:     }
Chris@16: 
Chris@16:     /** Move assignment operator */
Chris@101:     interval_base_set& operator = (interval_base_set src) 
Chris@101:     {                           //call by value sice 'src' is a "sink value"
Chris@16:         this->_set = boost::move(src._set);
Chris@16:         return *this; 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@101: #   else
Chris@101: 
Chris@101:     /** Copy assignment operator */
Chris@101:     interval_base_set& operator = (const interval_base_set& src) 
Chris@101:     { 
Chris@101:         this->_set = src._set;
Chris@101:         return *this; 
Chris@101:     }
Chris@101: 
Chris@16: #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
Chris@16: 
Chris@16:     /** swap the content of containers */
Chris@16:     void swap(interval_base_set& operand) { _set.swap(operand._set); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Containedness
Chris@16:     //==========================================================================
Chris@16:     /** sets the container empty */
Chris@16:     void clear() { icl::clear(*that()); }
Chris@16:     /** is the container empty? */
Chris@16:     bool empty()const { return icl::is_empty(*that()); }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Size
Chris@16:     //==========================================================================
Chris@16:     /** An interval set's size is it's cardinality */
Chris@16:     size_type size()const
Chris@16:     {
Chris@16:         return icl::cardinality(*that());
Chris@16:     }
Chris@16: 
Chris@16:     /** Size of the iteration over this container */
Chris@16:     std::size_t iterative_size()const 
Chris@16:     { 
Chris@16:         return _set.size(); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Selection
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Find the interval, that contains element \c key_value */
Chris@16:     const_iterator find(const element_type& key_value)const
Chris@16:     { 
Chris@16:         return icl::find(*this, key_value);
Chris@16:         //CL return this->_set.find(icl::singleton<segment_type>(key)); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Find the first interval, that collides with interval \c key_interval */
Chris@16:     const_iterator find(const interval_type& key_interval)const
Chris@16:     { 
Chris@16:         return this->_set.find(key_interval); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Addition
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Add a single element \c key to the set */
Chris@16:     SubType& add(const element_type& key) 
Chris@16:     {
Chris@16:         return icl::add(*that(), key);
Chris@16:     }
Chris@16: 
Chris@16:     /** Add an interval of elements \c inter_val to the set */
Chris@16:     SubType& add(const segment_type& inter_val) 
Chris@16:     {
Chris@16:         _add(inter_val);
Chris@16:         return *that();
Chris@16:     }
Chris@16: 
Chris@16:     /** Add an interval of elements \c inter_val to the set. Iterator 
Chris@16:         \c prior_ is a hint to the position \c inter_val can be 
Chris@16:         inserted after. */
Chris@16:     iterator add(iterator prior_, const segment_type& inter_val) 
Chris@16:     { 
Chris@16:         return _add(prior_, inter_val);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Subtraction
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     /** Subtract a single element \c key from the set */
Chris@16:     SubType& subtract(const element_type& key) 
Chris@16:     { 
Chris@16:         return icl::subtract(*that(), key);
Chris@16:     }
Chris@16: 
Chris@16:     /** Subtract an interval of elements \c inter_val from the set */
Chris@16:     SubType& subtract(const segment_type& inter_val); 
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Insertion
Chris@16:     //==========================================================================
Chris@16:     /** Insert an element \c key into the set */
Chris@16:     SubType& insert(const element_type& key) 
Chris@16:     { 
Chris@16:         return add(key); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Insert an interval of elements \c inter_val to the set */
Chris@16:     SubType& insert(const segment_type& inter_val) 
Chris@16:     { 
Chris@16:         return add(inter_val); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Insert an interval of elements \c inter_val to the set. Iterator 
Chris@16:         \c prior_ is a hint to the position \c inter_val can be 
Chris@16:         inserted after. */
Chris@16:     iterator insert(iterator prior_, const segment_type& inter_val) 
Chris@16:     { 
Chris@16:         return add(prior_, inter_val); 
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Erasure
Chris@16:     //==========================================================================
Chris@16:     /** Erase an element \c key from the set */
Chris@16:     SubType& erase(const element_type& key) 
Chris@16:     { 
Chris@16:         return subtract(key); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Erase an interval of elements \c inter_val from the set */
Chris@16:     SubType& erase(const segment_type& inter_val) 
Chris@16:     { 
Chris@16:         return subtract(inter_val); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Erase the interval that iterator \c position points to. */
Chris@16:     void erase(iterator position)
Chris@16:     { 
Chris@16:         _set.erase(position); 
Chris@16:     }
Chris@16: 
Chris@16:     /** Erase all intervals in the range <tt>[first,past)</tt> of iterators. */
Chris@16:     void erase(iterator first, iterator past)
Chris@16:     { 
Chris@16:         _set.erase(first, past); 
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Symmetric difference
Chris@16:     //==========================================================================
Chris@16:     /** If \c *this set contains \c key it is erased, otherwise it is added. */
Chris@16:     SubType& flip(const element_type& key)
Chris@16:     {
Chris@16:         return icl::flip(*that(), key);
Chris@16:     }
Chris@16: 
Chris@16:     /** If \c *this set contains \c inter_val it is erased, otherwise it is added. */
Chris@16:     SubType& flip(const segment_type& inter_val)
Chris@16:     {
Chris@16:         return icl::flip(*that(), inter_val);
Chris@16:     }
Chris@16: 
Chris@16:     //==========================================================================
Chris@16:     //= Iterator related
Chris@16:     //==========================================================================
Chris@16: 
Chris@16:     iterator begin() { return _set.begin(); }
Chris@16:     iterator end()   { return _set.end(); }
Chris@16:     const_iterator begin()const { return _set.begin(); }
Chris@16:     const_iterator end()const   { return _set.end(); }
Chris@16:     reverse_iterator rbegin() { return _set.rbegin(); }
Chris@16:     reverse_iterator rend()   { return _set.rend(); }
Chris@16:     const_reverse_iterator rbegin()const { return _set.rbegin(); }
Chris@16:     const_reverse_iterator rend()const   { return _set.rend(); }
Chris@16: 
Chris@16:     iterator lower_bound(const value_type& interval)
Chris@16:     { return _set.lower_bound(interval); }
Chris@16: 
Chris@16:     iterator upper_bound(const value_type& interval)
Chris@16:     { return _set.upper_bound(interval); }
Chris@16: 
Chris@16:     const_iterator lower_bound(const value_type& interval)const
Chris@16:     { return _set.lower_bound(interval); }
Chris@16: 
Chris@16:     const_iterator upper_bound(const value_type& interval)const
Chris@16:     { return _set.upper_bound(interval); }
Chris@16: 
Chris@16:     std::pair<iterator,iterator> equal_range(const key_type& interval)
Chris@16:     { 
Chris@16:         return std::pair<iterator,iterator>
Chris@16:             (_set.lower_bound(interval), _set.upper_bound(interval)); 
Chris@16:     }
Chris@16: 
Chris@16:     std::pair<const_iterator,const_iterator> 
Chris@16:         equal_range(const key_type& interval)const
Chris@16:     { 
Chris@16:         return std::pair<const_iterator,const_iterator>
Chris@16:             (_set.lower_bound(interval), _set.upper_bound(interval)); 
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     iterator _add(const segment_type& addend);
Chris@16:     iterator _add(iterator prior, const segment_type& addend);
Chris@16: 
Chris@16: protected:
Chris@16:     void add_front(const interval_type& inter_val, iterator& first_);
Chris@16:     void add_main(interval_type& inter_val, iterator& it_, const iterator& last_);
Chris@16:     void add_segment(const interval_type& inter_val, iterator& it_);
Chris@16:     void add_rear(const interval_type& inter_val, iterator& it_);
Chris@16: 
Chris@16: protected:
Chris@16:     sub_type* that() { return static_cast<sub_type*>(this); }
Chris@16:     const sub_type* that()const { return static_cast<const sub_type*>(this); }
Chris@16: 
Chris@16: protected:
Chris@16:     ImplSetT _set;
Chris@16: } ;
Chris@16: 
Chris@16: 
Chris@16: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::add_front(const interval_type& inter_val, iterator& first_)
Chris@16: {
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(*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(*this, first_);
Chris@16:         const_cast<interval_type&>(*first_) = left_subtract(*first_, left_resid);
Chris@16:         //NOTE: Only splitting
Chris@16:         this->_set.insert(prior_, left_resid);
Chris@16:     }
Chris@16: 
Chris@16:     //POST:
Chris@16:     // [----- inter_val ---- . . .
Chris@16:     // ...[-- first_ --...
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::add_segment(const interval_type& inter_val, iterator& it_)
Chris@16: {
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:         this->_set.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: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::add_main(interval_type& rest_interval, iterator& it_, const iterator& last_)
Chris@16: {
Chris@16:     interval_type cur_interval;
Chris@16:     while(it_ != last_)
Chris@16:     {
Chris@16:         cur_interval = *it_ ;
Chris@16:         add_segment(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: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline void interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::add_rear(const interval_type& inter_val, iterator& it_)
Chris@16: {
Chris@16:     iterator prior_ = cyclic_prior(*this, 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:         this->_set.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_ = this->_set.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_ = this->_set.insert(it_, right_resid);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Addition
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator 
Chris@16:     interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::_add(const segment_type& addend)
Chris@16: {
Chris@101:     typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator;
Chris@16:     if(icl::is_empty(addend)) 
Chris@16:         return this->_set.end();
Chris@16: 
Chris@16:     std::pair<iterator,bool> insertion = this->_set.insert(addend);
Chris@16: 
Chris@16:     if(insertion.second)
Chris@16:         return that()->handle_inserted(insertion.first);
Chris@16:     else
Chris@101:     {
Chris@101:         iterator last_ = prior(this->_set.upper_bound(addend));
Chris@101:         return that()->add_over(addend, last_);
Chris@101:     }
Chris@16: }
Chris@16: 
Chris@16: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator 
Chris@16:     interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::_add(iterator prior_, const segment_type& addend)
Chris@16: {
Chris@101:     typedef typename interval_base_set<SubType,DomainT,Compare,Interval,Alloc>::iterator iterator;
Chris@101:     if(icl::is_empty(addend))
Chris@16:         return prior_;
Chris@16: 
Chris@16:     iterator insertion = this->_set.insert(prior_, addend);
Chris@16: 
Chris@16:     if(*insertion == addend)
Chris@16:         return that()->handle_inserted(insertion);
Chris@16:     else
Chris@101:     {
Chris@101:         iterator last_ = prior(this->_set.upper_bound(addend));
Chris@101:         return that()->add_over(addend, last_);
Chris@101:     }
Chris@16: }
Chris@16: 
Chris@16: //==============================================================================
Chris@16: //= Subtraction
Chris@16: //==============================================================================
Chris@16: template <class SubType, class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE) Interval, ICL_ALLOC Alloc>
Chris@16: inline SubType& interval_base_set<SubType,DomainT,Compare,Interval,Alloc>
Chris@16:     ::subtract(const segment_type& minuend)
Chris@16: {
Chris@16:     if(icl::is_empty(minuend)) 
Chris@16:         return *that();
Chris@16: 
Chris@16:     std::pair<iterator, iterator> exterior = equal_range(minuend);
Chris@16:     if(exterior.first == exterior.second) 
Chris@16:         return *that();
Chris@16: 
Chris@16:     iterator first_ = exterior.first;
Chris@16:     iterator end_   = exterior.second;
Chris@16:     iterator last_  = prior(end_);
Chris@16: 
Chris@16:     interval_type left_resid = right_subtract(*first_, minuend);
Chris@16:     interval_type right_resid; 
Chris@16:     if(first_ != end_)
Chris@16:         right_resid = left_subtract(*last_ , minuend);
Chris@16: 
Chris@16:     this->_set.erase(first_, end_);
Chris@16: 
Chris@16:     if(!icl::is_empty(left_resid))
Chris@16:         this->_set.insert(left_resid);
Chris@16: 
Chris@16:     if(!icl::is_empty(right_resid))
Chris@16:         this->_set.insert(right_resid);
Chris@16: 
Chris@16:     return *that();
Chris@16: }
Chris@16: 
Chris@16: //-----------------------------------------------------------------------------
Chris@16: // type traits
Chris@16: //-----------------------------------------------------------------------------
Chris@16: template<class SubType,
Chris@16:          class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct is_set<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_set<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: template<class SubType,
Chris@16:          class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
Chris@16: struct is_interval_container<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> >
Chris@16: { 
Chris@16:     typedef is_interval_container<icl::interval_base_set<SubType,DomainT,Compare,Interval,Alloc> > type;
Chris@16:     BOOST_STATIC_CONSTANT(bool, value = true); 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: }} // namespace icl boost
Chris@16: 
Chris@16: #endif
Chris@16: 
Chris@16: