Home | Libraries | People | FAQ | More |
boost::itl::interval_base_map — Implements a map as a map of intervals (base class).
template<class SubType , typename DomainT , typename CodomainT ,
class Traits = itl::partial_absorber,
ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, DomainT),
ITL_COMBINE Combine = ITL_COMBINE_INSTANCE(itl::inplace_plus, CodomainT),
ITL_SECTION Section = ITL_SECTION_INSTANCE(itl::inplace_et, CodomainT),
template< class, ITL_COMPARE >class Interval = itl::interval,
ITL_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 itl::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 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 Interval< DomainT, Compare > interval_type; // The interval type of the map.
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 interval_type::difference_type difference_type; // The difference type of an interval which is sometimes different form the domain_type.
typedef interval_type::size_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 inverse< codomain_intersect >::type inverse_codomain_intersect; // Inverse Combine functor for codomain value intersection.
typedef exclusive_less< interval_type > interval_compare; // Comparison functor for intervals which are keys as well.
typedef exclusive_less< 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 ITL_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::itl::element_iterator< iterator > element_iterator; // element iterator: Depreciated, see documentation.
typedef boost::itl::element_iterator< const_iterator > element_const_iterator; // const element iterator: Depreciated, see documentation.
typedef boost::itl::element_iterator< reverse_iterator > element_reverse_iterator; // element reverse iterator: Depreciated, see documentation.
typedef boost::itl::element_iterator< const_reverse_iterator > element_const_reverse_iterator; // element const reverse iterator: Depreciated, see documentation.
// construct/copy/destruct
interval_base_map();
interval_base_map(const interval_base_map &);
interval_base_map& operator=(const interval_base_map &);
// public member functions
typedef ITL_COMPARE_DOMAIN(Compare, DomainT) ;
typedef ITL_COMBINE_CODOMAIN(Combine, CodomainT) ;
typedef ITL_SECTION_CODOMAIN(Section, CodomainT) ;
void swap(interval_base_map &) ;
template<class Predicate >
SubType & assign_if(const interval_base_map &, const Predicate &) ;
void clear() ;
bool empty() const;
bool contains(const domain_type &) const;
bool contains(const interval_type &) const;
template<class SetType >
bool contains(const interval_base_set< SetType, DomainT, Compare, Interval, Alloc > &) const;
bool contains(const element_type &) const;
bool contains(const segment_type &) const;
template<class MapType >
bool contains(const interval_base_map< MapType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &) const;
template<class MapType >
bool contained_in(const interval_base_map< MapType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &) const;
size_type cardinality() const;
size_type size() const;
difference_type length() const;
size_t interval_count() const;
size_t iterative_size() const;
DomainT lower() const;
DomainT upper() const;
DomainT first() const;
DomainT last() const;
const_iterator find(const domain_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 &) ;
template<class SetSubType >
SubType & erase(const interval_base_set< SetSubType, DomainT, Compare, Interval, Alloc > &) ;
SubType & erase(const interval_base_map &) ;
void erase(iterator) ;
void erase(iterator, iterator) ;
template<class Predicate > SubType & erase_if(const Predicate &) ;
void add_intersection(interval_base_map &, const domain_type &) const;
void add_intersection(interval_base_map &, const element_type &) const;
void add_intersection(interval_base_map &, const segment_type &) const;
void add_intersection(interval_base_map &, const interval_type &) const;
template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet>
void add_intersection(interval_base_map &,
const IntervalSet< DomainT, Compare, Interval, Alloc > &) const;
template<template< class DomT, class CodomT, class Trts, ITL_COMPARE Comp, ITL_COMBINE Combi, ITL_SECTION Sect, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalMap>
void add_intersection(interval_base_map &,
const IntervalMap< DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &) const;
bool intersects(const domain_type &) const;
bool intersects(const interval_type &) const;
bool intersects(const element_type &) const;
bool intersects(const segment_type &) const;
SubType & flip(const element_type &) ;
SubType & flip(const segment_type &) ;
template<class SubType2 >
SubType & flip(const interval_base_map< SubType2, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > &) ;
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;
element_iterator elements_begin() ;
element_iterator elements_end() ;
element_const_iterator elements_begin() const;
element_const_iterator elements_end() const;
element_reverse_iterator elements_rbegin() ;
element_reverse_iterator elements_rend() ;
element_const_reverse_iterator elements_rbegin() const;
element_const_reverse_iterator elements_rend() const;
std::string as_string() const;
interval_base_map & join() ;
void absorb_neutrons() ;
void uniform_bounds(itl::bound_type) ;
template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet>
void domain(IntervalSet< DomainT, Compare, Interval, Alloc > &) const;
void sum(codomain_type &) const;
codomain_type sum() const;
sub_type & self() ;
// private member functions
template<class Combiner > SubType & _add(const segment_type &) ;
template<class Combiner > SubType & _subtract(const segment_type &) ;
// public static functions
template<typename IteratorT > static const key_type & key_value(IteratorT) ;
template<typename IteratorT >
static const data_type & data_value(IteratorT) ;
template<typename IteratorT >
static codomain_type codomain_value(IteratorT) ;
template<typename LeftIterT , typename RightIterT >
static bool key_less(LeftIterT, RightIterT) ;
static value_type
make_domain_element(const domain_type &, const codomain_type &) ;
// protected member functions
sub_type * that() ;
const sub_type * that() const;
iterator prior(iterator) ;
const_iterator prior(const_iterator) const;
template<class Combiner > bool combine(iterator &, const codomain_type &) ;
template<class Combiner >
std::pair< iterator, bool >
map_insert(const interval_type &, const codomain_type &) ;
template<class Combiner >
std::pair< iterator, bool >
map_insert(iterator, const interval_type &, const codomain_type &) ;
template<class Combiner >
std::pair< iterator, bool >
map_add(iterator, const interval_type &, const codomain_type &) ;
template<class Combiner >
iterator gap_insert(iterator, const interval_type &,
const codomain_type &) ;
};
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& operator=(const interval_base_map & src);
Assignment operator
interval_base_map
public member functionstypedef ITL_COMPARE_DOMAIN(Compare, DomainT) ;
typedef ITL_COMBINE_CODOMAIN(Combine, CodomainT) ;
typedef ITL_SECTION_CODOMAIN(Section, CodomainT) ;
void swap(interval_base_map & object) ;
swap the content of containers
template<class Predicate > SubType & assign_if(const interval_base_map & src, const Predicate & pred) ;
Copy all elements if predicate pred
holds
void clear() ;
clear the map
bool empty() const;
is the map empty?
bool contains(const domain_type & key) const;
Does the map contain the domain element key
?
bool contains(const interval_type & sub_interval) const;
Does the map contain the interval sub_interval
?
template<class SetType > bool contains(const interval_base_set< SetType, DomainT, Compare, Interval, Alloc > & sub_set) const;
Does the map contain the key key set sub_set
?
bool contains(const element_type & key_value_pair) const;
Does the map contain the key_value_pair = (key,value)
?
bool contains(const segment_type & interval_value_pair) const;
Does the map contain all element value pairs represented by the interval_value_pair
?
template<class MapType > bool contains(const interval_base_map< MapType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & sub) const;
Does *this
container contain sub
?
template<class MapType > bool contained_in(const interval_base_map< MapType, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & super) const;
*this
is subset of super
?
size_type cardinality() const;
Number of elements in the map (cardinality).
size_type size() const;
An interval map's size is it's cardinality
difference_type length() const;
The length of the interval container which is the sum of interval lengths
size_t interval_count() const;
Number of intervals which is also the size of the iteration over the object
size_t iterative_size() const;
Size of the iteration over this container
DomainT lower() const;
Lower bound of the first interval
DomainT upper() const;
Upper bound of the last interval
DomainT first() const;
Smallest element of the map (wrt. the partial ordering on DomainT). first() does not exist for continuous datatypes and open interval bounds.
DomainT last() const;
Largest element of the map (wrt. the partial ordering on DomainT). last() does not exist for continuous datatypes and open interval bounds.
const_iterator find(const domain_type & key) const;
Find the interval value pair, that contains key
codomain_type operator()(const domain_type & key) 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.
template<class SetSubType > SubType & erase(const interval_base_set< SetSubType, DomainT, Compare, Interval, Alloc > & operand) ;
Erase all value pairs for a set of intervals.
SubType & erase(const interval_base_map & eraser) ;
Erase all value pairs from *this
map that are elements of 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)
.
template<class Predicate > SubType & erase_if(const Predicate & pred) ;
Remove all elements where property p
holds, keep all others
void add_intersection(interval_base_map & section, const domain_type & key) const;
The intersection of key
in *this
map is added to section
. This can also be used to find key
in *this
map
void add_intersection(interval_base_map & section, const element_type & key_value_pair) const;
The intersection of key_value_pair
and *this
map is added to section
.
void add_intersection(interval_base_map & section, const segment_type & interval_value_pair) const;
The intersection of interval_value_pair
and *this
map is added to section
.
void add_intersection(interval_base_map & section, const interval_type & inter_val) const;
The intersection of inter_val
with *this
map is added to section
.
template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> void add_intersection(interval_base_map & section, const IntervalSet< DomainT, Compare, Interval, Alloc > & sectant) const;
The intersection of set sectant
with *this
map is added to section
.
template<template< class DomT, class CodomT, class Trts, ITL_COMPARE Comp, ITL_COMBINE Combi, ITL_SECTION Sect, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalMap> void add_intersection(interval_base_map & intersection, const IntervalMap< DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & sectant) const;
The intersection of map sectant
with *this
map is added to section
.
bool intersects(const domain_type & key) const;
Returns true
, if element key
is found in *this
map. Complexity: logarithmic.
bool intersects(const interval_type & inter_val) const;
Returns true
, if inter_val
intersects with *this
map. Complexity: Logarithmic in iterative size.
bool intersects(const element_type & key_value_pair) const;
Returns true
, if key_value_pair
is found in *this
map. Complexity: logarithmic.
bool intersects(const segment_type & interval_value_pair) const;
Returns true
, if interval_value_pair
intersects with *this
map: Complexity: Linear in iterative_size.
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.
template<class SubType2 > SubType & flip(const interval_base_map< SubType2, DomainT, CodomainT, Traits, Compare, Combine, Section, Interval, Alloc > & operand) ;
The intersection of *this
and operand
is erased from *this
. The complemenary value pairs are added to *this
.
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;
element_iterator elements_begin() ;
element_iterator elements_end() ;
element_const_iterator elements_begin() const;
element_const_iterator elements_end() const;
element_reverse_iterator elements_rbegin() ;
element_reverse_iterator elements_rend() ;
element_const_reverse_iterator elements_rbegin() const;
element_const_reverse_iterator elements_rend() const;
std::string as_string() const;
Object as string
interval_base_map & join() ;
Join bounding intervals
void absorb_neutrons() ;
All value pairs (I,y) that have neutral elements
y==codomain_type
() as associated values are removed form the map.
void uniform_bounds(itl::bound_type bounded) ;
Set all intervals in the map to be of type bounded
. Requires Integral<domain_type>.
Interval bounds of different types are created by opeations on interval maps. This function allows to reset them uniformly without, of course, changing their value. This is only possible for discrete domain datatypes.
template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> void domain(IntervalSet< DomainT, Compare, Interval, Alloc > & dom) const;
Gives the domain of the map as interval set
void sum(codomain_type & total) const;
codomain_type sum() const;
sub_type & self() ;
interval_base_map
private member functionstemplate<class Combiner > SubType & _add(const segment_type & interval_value_pair) ;
Addition of an interval value pair to the map. On overlap an aggregation is performed using functor Combiner
. This function is not public, because the `codomain_combine` shall be an invariant for all itl maps.
template<class Combiner > SubType & _subtract(const segment_type & interval_value_pair) ;
Subtraction of an interval value pair from the map. On overlap an aggregation is performed using functor Combiner. This function is not public, because the `codomain_combine` shall be an invariant for all itl maps.
interval_base_map
public static functionstemplate<typename IteratorT > static const key_type & key_value(IteratorT value_) ;
template<typename IteratorT > static const data_type & data_value(IteratorT value_) ;
template<typename IteratorT > static codomain_type codomain_value(IteratorT value_) ;
template<typename LeftIterT , typename RightIterT > static bool key_less(LeftIterT left_, RightIterT right_) ;
static value_type make_domain_element(const domain_type & dom_val, const codomain_type & codom_val) ;
interval_base_map
protected member functionssub_type * that() ;
const sub_type * that() const;
iterator prior(iterator it_) ;
const_iterator prior(const_iterator it_) const;
template<class Combiner > bool combine(iterator & it_, const codomain_type & co_val) ;
template<class Combiner > std::pair< iterator, bool > map_insert(const interval_type & inter_val, const codomain_type & co_val) ;
template<class Combiner > std::pair< iterator, bool > map_insert(iterator prior_, const interval_type & inter_val, const codomain_type & co_val) ;
template<class Combiner > std::pair< iterator, bool > map_add(iterator prior_, const interval_type & inter_val, const codomain_type & co_val) ;
template<class Combiner > iterator gap_insert(iterator prior_, const interval_type & inter_val, const codomain_type & co_val) ;