...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_map — Implements a map as a map of intervals (base class).
// In header: <boost/icl/interval_base_map.hpp>
template<typename SubType, typename DomainT, typename CodomainT,
typename Traits = icl::partial_absorber,
ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
ICL_COMBINE Combine = ICL_COMBINE_INSTANCE(icl::inplace_plus, CodomainT),
ICL_SECTION Section = ICL_SECTION_INSTANCE(icl::inter_section, CodomainT),
ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
ICL_ALLOC Alloc = std::allocator>
class interval_base_map {
public:
// types
typedef interval_base_map< SubType, DomainT, CodomainT, Traits, Compare, Combine, Section, 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 Traits traits; // Traits of an itl map.
typedef icl::map< DomainT, CodomainT, Traits, Compare, Combine, Section, Alloc > atomized_type; // The atomized type representing the corresponding container of elements.
typedef DomainT domain_type; // Domain type (type of the keys) of the map.
typedef boost::call_traits< DomainT >::param_type domain_param;
typedef CodomainT codomain_type; // Domain type (type of the keys) of the map.
typedef mapping_pair< domain_type, codomain_type > domain_mapping_type; // Auxiliary type to help the compiler resolve ambiguities when using std::make_pair.
typedef domain_mapping_type element_type; // Conceptual is a map a set of elements of type element_type
.
typedef std::pair< interval_type, CodomainT > interval_mapping_type; // Auxiliary type for overload resolution.
typedef std::pair< interval_type, CodomainT > segment_type; // Type of an interval containers segment, that is spanned by an interval.
typedef difference_type_of< domain_type >::type difference_type; // The difference type of an interval which is sometimes different form the domain_type.
typedef size_type_of< domain_type >::type size_type; // The size type of an interval which is mostly std::size_t.
typedef inverse< codomain_combine >::type inverse_codomain_combine; // Inverse Combine functor for codomain value aggregation.
typedef mpl::if_< has_set_semantics< codomain_type >, ICL_SECTION_CODOMAIN(Section, CodomainT), codomain_combine >::type codomain_intersect; // Intersection functor for codomain values.
typedef inverse< codomain_intersect >::type inverse_codomain_intersect; // Inverse Combine functor for codomain value intersection.
typedef exclusive_less_than< interval_type > interval_compare; // Comparison functor for intervals which are keys as well.
typedef exclusive_less_than< interval_type > key_compare; // Comparison functor for keys.
typedef Alloc< std::pair< const interval_type, codomain_type > > allocator_type; // The allocator type of the set.
typedef ICL_IMPL_SPACE::map< interval_type, codomain_type, key_compare, allocator_type > ImplMapT; // Container type for the implementation.
typedef ImplMapT::key_type key_type; // key type of the implementing container
typedef ImplMapT::value_type value_type; // value type of the implementing container
typedef ImplMapT::value_type::second_type data_type; // data type of the implementing container
typedef ImplMapT::pointer pointer; // pointer type
typedef ImplMapT::const_pointer const_pointer; // const pointer type
typedef ImplMapT::reference reference; // reference type
typedef ImplMapT::const_reference const_reference; // const reference type
typedef ImplMapT::iterator iterator; // iterator for iteration over intervals
typedef ImplMapT::const_iterator const_iterator; // const_iterator for iteration over intervals
typedef ImplMapT::reverse_iterator reverse_iterator; // iterator for reverse iteration over intervals
typedef ImplMapT::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; // const element 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.
typedef on_absorbtion< type, codomain_combine, Traits::absorbs_identities >::type on_codomain_absorbtion;
// member classes/structs/unions
template<typename Type>
struct on_codomain_model<Type, false> {
// types
typedef Type::interval_type interval_type;
typedef Type::codomain_type codomain_type;
typedef Type::segment_type segment_type;
typedef Type::codomain_combine codomain_combine;
// public static functions
static void add(Type &, interval_type &, const codomain_type &,
const codomain_type &);
};
template<typename Type>
struct on_codomain_model<Type, true> {
// types
typedef Type::interval_type interval_type;
typedef Type::codomain_type codomain_type;
typedef Type::segment_type segment_type;
typedef Type::codomain_combine codomain_combine;
typedef Type::inverse_codomain_intersect inverse_codomain_intersect;
// public static functions
static void add(Type &, interval_type &, const codomain_type &,
const codomain_type &);
};
template<typename Type>
struct on_definedness<Type, false> {
// public static functions
static void add_intersection(Type &, const Type &, const segment_type &);
};
template<typename Type>
struct on_definedness<Type, true> {
// public static functions
static void add_intersection(Type &, const Type &, const segment_type &);
};
template<typename Type>
struct on_invertible<Type, false> {
// types
typedef Type::segment_type segment_type;
typedef Type::inverse_codomain_combine inverse_codomain_combine;
// public static functions
static void subtract(Type &, const segment_type &);
};
template<typename Type>
struct on_invertible<Type, true> {
// types
typedef Type::segment_type segment_type;
typedef Type::inverse_codomain_combine inverse_codomain_combine;
// public static functions
static void subtract(Type &, const segment_type &);
};
template<typename Type, bool absorbs_identities>
struct on_total_absorbable<Type, false, absorbs_identities> {
// types
typedef Type::segment_type segment_type;
typedef Type::codomain_type codomain_type;
typedef Type::interval_type interval_type;
typedef Type::value_type value_type;
typedef Type::const_iterator const_iterator;
typedef Type::set_type set_type;
typedef Type::inverse_codomain_intersect inverse_codomain_intersect;
// public static functions
static void flip(Type &, const segment_type &);
};
template<typename Type>
struct on_total_absorbable<Type, true, false> {
// types
typedef Type::segment_type segment_type;
typedef Type::codomain_type codomain_type;
// public static functions
static void flip(Type &, const segment_type &);
};
template<typename Type>
struct on_total_absorbable<Type, true, true> {
// public static functions
static void flip(Type &, const typename Type::segment_type &);
};
// construct/copy/destruct
interval_base_map();
interval_base_map(const interval_base_map &);
interval_base_map(interval_base_map &&);
interval_base_map& operator=(const interval_base_map &);
interval_base_map& operator=(interval_base_map &&);
// public member functions
typedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare);
typedef ICL_COMPARE_DOMAIN(Compare, DomainT);
typedef ICL_COMPARE_DOMAIN(Compare, segment_type);
typedef ICL_COMBINE_CODOMAIN(Combine, CodomainT);
BOOST_STATIC_CONSTANT(bool,
is_total_invertible = (Traits::is_total &&has_inverse< codomain_type >::value));
BOOST_STATIC_CONSTANT(int, fineness = 0);
void swap(interval_base_map &);
void clear();
bool empty() const;
size_type size() const;
std::size_t iterative_size() const;
const_iterator find(const domain_type &) const;
const_iterator find(const interval_type &) const;
codomain_type operator()(const domain_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 & set(const element_type &);
SubType & set(const segment_type &);
SubType & erase(const element_type &);
SubType & erase(const segment_type &);
SubType & erase(const domain_type &);
SubType & erase(const interval_type &);
void erase(iterator);
void erase(iterator, iterator);
void add_intersection(SubType &, const segment_type &) const;
SubType & flip(const element_type &);
SubType & flip(const segment_type &);
iterator lower_bound(const key_type &);
iterator upper_bound(const key_type &);
const_iterator lower_bound(const key_type &) const;
const_iterator upper_bound(const key_type &) const;
std::pair< iterator, iterator > equal_range(const key_type &);
std::pair< const_iterator, const_iterator >
equal_range(const key_type &) const;
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;
// private member functions
template<typename Combiner> iterator _add(const segment_type &);
template<typename Combiner> iterator _add(iterator, const segment_type &);
template<typename Combiner> void _subtract(const segment_type &);
iterator _insert(const segment_type &);
iterator _insert(iterator, const segment_type &);
template<typename Combiner>
void add_segment(const interval_type &, const CodomainT &, iterator &);
template<typename Combiner>
void add_main(interval_type &, const CodomainT &, iterator &,
const iterator &);
template<typename Combiner>
void add_rear(const interval_type &, const CodomainT &, iterator &);
void add_front(const interval_type &, iterator &);
void subtract_front(const interval_type &, iterator &);
template<typename Combiner>
void subtract_main(const CodomainT &, iterator &, const iterator &);
template<typename Combiner>
void subtract_rear(interval_type &, const CodomainT &, iterator &);
void insert_main(const interval_type &, const CodomainT &, iterator &,
const iterator &);
void erase_rest(interval_type &, const CodomainT &, iterator &,
const iterator &);
template<typename FragmentT>
void total_add_intersection(SubType &, const FragmentT &) const;
void partial_add_intersection(SubType &, const segment_type &) const;
void partial_add_intersection(SubType &, const element_type &) const;
// protected member functions
template<typename Combiner>
iterator gap_insert(iterator, const interval_type &,
const codomain_type &);
template<typename Combiner>
std::pair< iterator, bool >
add_at(const iterator &, const interval_type &, const codomain_type &);
std::pair< iterator, bool >
insert_at(const iterator &, const interval_type &, const codomain_type &);
sub_type * that();
const sub_type * that() const;
};
interval_base_map
public
construct/copy/destructinterval_base_map();
Default constructor for the empty object
interval_base_map(const interval_base_map & src);
Copy constructor
interval_base_map(interval_base_map && src);
Move constructor
interval_base_map& operator=(const interval_base_map & src);
Copy assignment operator
interval_base_map& operator=(interval_base_map && src);
Move assignment operator
interval_base_map
public member functionstypedef ICL_INTERVAL_TYPE(Interval, DomainT, Compare);The interval type of the
map
. typedef ICL_COMPARE_DOMAIN(Compare, DomainT);Comparison functor for domain values.
typedef ICL_COMPARE_DOMAIN(Compare, segment_type);
typedef ICL_COMBINE_CODOMAIN(Combine, CodomainT);Combine functor for codomain value aggregation.
BOOST_STATIC_CONSTANT(bool, is_total_invertible = (Traits::is_total &&has_inverse< codomain_type >::value));
BOOST_STATIC_CONSTANT(int, fineness = 0);
void swap(interval_base_map & object);
swap the content of containers
void clear();
clear the map
bool empty() const;
is the map
empty?
size_type size() const;
An interval map's size is it's cardinality
std::size_t iterative_size() const;
Size of the iteration over this container
const_iterator find(const domain_type & key_value) const;
Find the interval value pair, that contains key
const_iterator find(const interval_type & key_interval) const;
Find the first interval value pair, that collides with interval key_interval
codomain_type operator()(const domain_type & key_value) const;
Total select function.
SubType & add(const element_type & key_value_pair);
Addition of a key value pair to the map
SubType & add(const segment_type & interval_value_pair);
Addition of an interval value pair to the map
.
iterator add(iterator prior_, const segment_type & interval_value_pair);
Addition of an interval value pair interval_value_pair
to the map
. Iterator prior_
is a hint to the position interval_value_pair
can be inserted after.
SubType & subtract(const element_type & key_value_pair);
Subtraction of a key value pair from the map
SubType & subtract(const segment_type & interval_value_pair);
Subtraction of an interval value pair from the map
.
SubType & insert(const element_type & key_value_pair);
Insertion of a key_value_pair
into the map
.
SubType & insert(const segment_type & interval_value_pair);
Insertion of an interval_value_pair
into the map
.
iterator insert(iterator prior, const segment_type & interval_value_pair);
Insertion of an interval_value_pair
into the map
. Iterator prior_
. serves as a hint to insert after the element prior
point to.
SubType & set(const element_type & key_value_pair);
With key_value_pair = (k,v)
set value v
for key k
SubType & set(const segment_type & interval_value_pair);
With interval_value_pair = (I,v)
set value v
for all keys in interval I
in the map
.
SubType & erase(const element_type & key_value_pair);
Erase a key_value_pair
from the map
.
SubType & erase(const segment_type & interval_value_pair);
Erase an interval_value_pair
from the map
.
SubType & erase(const domain_type & key);
Erase a key value pair for key
.
SubType & erase(const interval_type & inter_val);
Erase all value pairs within the range of the interval inter_val
from the map
.
void erase(iterator position);
Erase all value pairs within the range of the interval that iterator position
points to.
void erase(iterator first, iterator past);
Erase all value pairs for a range of iterators [first,past)
.
void add_intersection(SubType & section, const segment_type & interval_value_pair) const;
The intersection of interval_value_pair
and *this
map
is added to section
.
SubType & flip(const element_type & key_value_pair);
If *this
map
contains key_value_pair
it is erased, otherwise it is added.
SubType & flip(const segment_type & interval_value_pair);
If *this
map
contains interval_value_pair
it is erased, otherwise it is added.
iterator lower_bound(const key_type & interval);
iterator upper_bound(const key_type & interval);
const_iterator lower_bound(const key_type & interval) const;
const_iterator upper_bound(const key_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;
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;
interval_base_map
private member functionstemplate<typename Combiner> iterator _add(const segment_type & interval_value_pair);
template<typename Combiner> iterator _add(iterator prior_, const segment_type & interval_value_pair);
template<typename Combiner> void _subtract(const segment_type & interval_value_pair);
iterator _insert(const segment_type & interval_value_pair);
iterator _insert(iterator prior_, const segment_type & interval_value_pair);
template<typename Combiner> void add_segment(const interval_type & inter_val, const CodomainT & co_val, iterator & it_);
template<typename Combiner> void add_main(interval_type & inter_val, const CodomainT & co_val, iterator & it_, const iterator & last_);
template<typename Combiner> void add_rear(const interval_type & inter_val, const CodomainT & co_val, iterator & it_);
void add_front(const interval_type & inter_val, iterator & first_);
void subtract_front(const interval_type & inter_val, iterator & first_);
template<typename Combiner> void subtract_main(const CodomainT & co_val, iterator & it_, const iterator & last_);
template<typename Combiner> void subtract_rear(interval_type & inter_val, const CodomainT & co_val, iterator & it_);
void insert_main(const interval_type &, const CodomainT &, iterator &, const iterator &);
void erase_rest(interval_type &, const CodomainT &, iterator &, const iterator &);
template<typename FragmentT> void total_add_intersection(SubType & section, const FragmentT & fragment) const;
void partial_add_intersection(SubType & section, const segment_type & operand) const;
void partial_add_intersection(SubType & section, const element_type & operand) const;
interval_base_map
protected member functionstemplate<typename Combiner> iterator gap_insert(iterator prior_, const interval_type & inter_val, const codomain_type & co_val);
template<typename Combiner> std::pair< iterator, bool > add_at(const iterator & prior_, const interval_type & inter_val, const codomain_type & co_val);
std::pair< iterator, bool > insert_at(const iterator & prior_, const interval_type & inter_val, const codomain_type & co_val);
sub_type * that();
const sub_type * that() const;