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