...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
boost::icl::interval_base_set — Implements a set as a set of intervals (base class).
// In header: <boost/icl/interval_base_set.hpp> 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: // types typedef interval_base_set< SubType, DomainT, Compare, Interval, Alloc > type; typedef SubType sub_type; // The designated derived or sub_type of this base class. typedef type overloadable_type; // Auxilliary type for overloadresolution. typedef DomainT domain_type; // The domain type of the set. typedef DomainT codomain_type; // The codomaintype is the same as domain_type. typedef DomainT element_type; // The element type of the set. typedef interval_type segment_type; // The segment type of the set. typedef difference_type_of< domain_type >::type difference_type; // The difference type of an interval which is sometimes different form the data_type. typedef size_type_of< domain_type >::type size_type; // The size type of an interval which is mostly std::size_t. typedef exclusive_less_than< interval_type > interval_compare; // Comparison functor for intervals. typedef exclusive_less_than< interval_type > key_compare; // Comparison functor for keys. typedef ICL_IMPL_SPACE::set< DomainT, domain_compare, Alloc< DomainT > > atomized_type; // The atomized type representing the corresponding container of elements. typedef Alloc< interval_type > allocator_type; // The allocator type of the set. typedef Alloc< DomainT > domain_allocator_type; // allocator type of the corresponding element set typedef ICL_IMPL_SPACE::set< interval_type, key_compare, allocator_type > ImplSetT; // Container type for the implementation. typedef ImplSetT::key_type key_type; // key type of the implementing container typedef ImplSetT::key_type data_type; // data type of the implementing container typedef ImplSetT::value_type value_type; // value type of the implementing container typedef ImplSetT::pointer pointer; // pointer type typedef ImplSetT::const_pointer const_pointer; // const pointer type typedef ImplSetT::reference reference; // reference type typedef ImplSetT::const_reference const_reference; // const reference type typedef ImplSetT::iterator iterator; // iterator for iteration over intervals typedef ImplSetT::const_iterator const_iterator; // const_iterator for iteration over intervals typedef ImplSetT::reverse_iterator reverse_iterator; // iterator for reverse iteration over intervals typedef ImplSetT::const_reverse_iterator const_reverse_iterator; // const_iterator for iteration over intervals typedef boost::icl::element_iterator< iterator > element_iterator; // element iterator: Depreciated, see documentation. typedef boost::icl::element_iterator< const_iterator > element_const_iterator; // element const iterator: Depreciated, see documentation. typedef boost::icl::element_iterator< reverse_iterator > element_reverse_iterator; // element reverse iterator: Depreciated, see documentation. typedef boost::icl::element_iterator< const_reverse_iterator > element_const_reverse_iterator; // element const reverse iterator: Depreciated, see documentation. // construct/copy/destruct interval_base_set(); interval_base_set(const interval_base_set &); interval_base_set(interval_base_set &&); interval_base_set& operator=(const interval_base_set &); interval_base_set& operator=(interval_base_set &&); // public member functions typedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare); typedef ICL_COMPARE_DOMAIN(Compare, DomainT); typedef ICL_COMPARE_DOMAIN(Compare, segment_type); BOOST_STATIC_CONSTANT(int, fineness = 0); void swap(interval_base_set &); void clear(); bool empty() const; size_type size() const; std::size_t iterative_size() const; const_iterator find(const element_type &) const; const_iterator find(const interval_type &) const; SubType & add(const element_type &); SubType & add(const segment_type &); iterator add(iterator, const segment_type &); SubType & subtract(const element_type &); SubType & subtract(const segment_type &); SubType & insert(const element_type &); SubType & insert(const segment_type &); iterator insert(iterator, const segment_type &); SubType & erase(const element_type &); SubType & erase(const segment_type &); void erase(iterator); void erase(iterator, iterator); SubType & flip(const element_type &); SubType & flip(const segment_type &); iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; reverse_iterator rbegin(); reverse_iterator rend(); const_reverse_iterator rbegin() const; const_reverse_iterator rend() const; iterator lower_bound(const value_type &); iterator upper_bound(const value_type &); const_iterator lower_bound(const value_type &) const; const_iterator upper_bound(const value_type &) const; std::pair< iterator, iterator > equal_range(const key_type &); std::pair< const_iterator, const_iterator > equal_range(const key_type &) const; // private member functions iterator _add(const segment_type &); iterator _add(iterator, const segment_type &); // protected member functions void add_front(const interval_type &, iterator &); void add_main(interval_type &, iterator &, const iterator &); void add_segment(const interval_type &, iterator &); void add_rear(const interval_type &, iterator &); sub_type * that(); const sub_type * that() const; };
interval_base_set
public
construct/copy/destructinterval_base_set();
Default constructor for the empty object
interval_base_set(const interval_base_set & src);
Copy constructor
interval_base_set(interval_base_set && src);
Move constructor
interval_base_set& operator=(const interval_base_set & src);
Assignment operator
interval_base_set& operator=(interval_base_set && src);
Move assignment operator
interval_base_set
public member functionstypedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare);The interval type of the set.
typedef ICL_COMPARE_DOMAIN(Compare, DomainT);Comparison functor for domain values.
typedef ICL_COMPARE_DOMAIN(Compare, segment_type);
BOOST_STATIC_CONSTANT(int, fineness = 0);
void swap(interval_base_set & operand);
swap the content of containers
void clear();
sets the container empty
bool empty() const;
is the container empty?
size_type size() const;
An interval set's size is it's cardinality
std::size_t iterative_size() const;
Size of the iteration over this container
const_iterator find(const element_type & key_value) const;
Find the interval, that contains element key_value
const_iterator find(const interval_type & key_interval) const;
Find the first interval, that collides with interval key_interval
SubType & add(const element_type & key);
Add a single element key
to the set
SubType & add(const segment_type & inter_val);
Add an interval of elements inter_val
to the set
iterator add(iterator prior_, const segment_type & inter_val);
Add an interval of elements inter_val
to the set. Iterator prior_
is a hint to the position inter_val
can be inserted after.
SubType & subtract(const element_type & key);
Subtract a single element key
from the set
SubType & subtract(const segment_type & inter_val);
Subtract an interval of elements inter_val
from the set
SubType & insert(const element_type & key);
Insert an element key
into the set
SubType & insert(const segment_type & inter_val);
Insert an interval of elements inter_val
to the set
iterator insert(iterator prior_, const segment_type & inter_val);
Insert an interval of elements inter_val
to the set. Iterator prior_
is a hint to the position inter_val
can be inserted after.
SubType & erase(const element_type & key);
Erase an element key
from the set
SubType & erase(const segment_type & inter_val);
Erase an interval of elements inter_val
from the set
void erase(iterator position);
Erase the interval that iterator position
points to.
void erase(iterator first, iterator past);
Erase all intervals in the range [first,past)
of iterators.
SubType & flip(const element_type & key);
If *this
set contains key
it is erased, otherwise it is added.
SubType & flip(const segment_type & inter_val);
If *this
set contains inter_val
it is erased, otherwise it is added.
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
iterator lower_bound(const value_type & interval);
iterator upper_bound(const value_type & interval);
const_iterator lower_bound(const value_type & interval) const;
const_iterator upper_bound(const value_type & interval) const;
std::pair< iterator, iterator > equal_range(const key_type & interval);
std::pair< const_iterator, const_iterator > equal_range(const key_type & interval) const;
interval_base_set
protected member functionsvoid 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_);
sub_type * that();
const sub_type * that() const;