/*-----------------------------------------------------------------------------+ | |
Copyright (c) 2007-2009: 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_INTERPROCESS_IMPLEMENTATION) | |
#include <boost/interprocess/containers/set.hpp> | |
#elif defined(ICL_USE_BOOST_MOVE_IMPLEMENTATION) | |
#include <boost/container/set.hpp> | |
#else | |
#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(std::less, 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){} | |
/** Assignment operator */ | |
interval_base_set& operator = (const interval_base_set& src) | |
{ | |
this->_set = src._set; | |
return *this; | |
} | |
/** 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 _set.equal_range(interval); } | |
std::pair<const_iterator,const_iterator> equal_range(const key_type& interval)const | |
{ return _set.equal_range(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) | |
{ | |
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 | |
return that()->add_over(addend, insertion.first); | |
} | |
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) | |
{ | |
if(icl::is_empty(addend)) | |
return prior_; | |
iterator insertion = this->_set.insert(prior_, addend); | |
if(*insertion == addend) | |
return that()->handle_inserted(insertion); | |
else | |
return that()->add_over(addend); | |
} | |
//============================================================================== | |
//= 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 = this->_set.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 | |