Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template interval_base_map

boost::itl::interval_base_map — Implements a map as a map of intervals (base class).

Synopsis

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 &) ;
};

Description

interval_base_map public construct/copy/destruct

  1. interval_base_map();

    Default constructor for the empty object

  2. interval_base_map(const interval_base_map & src);

    Copy constructor

  3. interval_base_map& operator=(const interval_base_map & src);

    Assignment operator

interval_base_map public member functions

  1. typedef ITL_COMPARE_DOMAIN(Compare, DomainT) ;
  2. typedef ITL_COMBINE_CODOMAIN(Combine, CodomainT) ;
  3. typedef ITL_SECTION_CODOMAIN(Section, CodomainT) ;
  4. void swap(interval_base_map & object) ;

    swap the content of containers

  5. template<class Predicate > 
      SubType & assign_if(const interval_base_map & src, const Predicate & pred) ;

    Copy all elements if predicate pred holds

  6. void clear() ;

    clear the map

  7. bool empty() const;

    is the map empty?

  8. bool contains(const domain_type & key) const;

    Does the map contain the domain element key?

  9. bool contains(const interval_type & sub_interval) const;

    Does the map contain the interval sub_interval ?

  10. 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 ?

  11. bool contains(const element_type & key_value_pair) const;

    Does the map contain the key_value_pair = (key,value)?

  12. bool contains(const segment_type & interval_value_pair) const;

    Does the map contain all element value pairs represented by the interval_value_pair ?

  13. 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?

  14. 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?

  15. size_type cardinality() const;

    Number of elements in the map (cardinality).

  16. size_type size() const;

    An interval map's size is it's cardinality

  17. difference_type length() const;

    The length of the interval container which is the sum of interval lengths

  18. size_t interval_count() const;

    Number of intervals which is also the size of the iteration over the object

  19. size_t iterative_size() const;

    Size of the iteration over this container

  20. DomainT lower() const;

    Lower bound of the first interval

  21. DomainT upper() const;

    Upper bound of the last interval

  22. 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.

  23. 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.

  24. const_iterator find(const domain_type & key) const;

    Find the interval value pair, that contains key

  25. codomain_type operator()(const domain_type & key) const;

    Total select function.

  26. SubType & add(const element_type & key_value_pair) ;

    Addition of a key value pair to the map

  27. SubType & add(const segment_type & interval_value_pair) ;

    Addition of an interval value pair to the map.

  28. 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.

  29. SubType & subtract(const element_type & key_value_pair) ;

    Subtraction of a key value pair from the map

  30. SubType & subtract(const segment_type & interval_value_pair) ;

    Subtraction of an interval value pair from the map.

  31. SubType & insert(const element_type & key_value_pair) ;

    Insertion of a key_value_pair into the map.

  32. SubType & insert(const segment_type & interval_value_pair) ;

    Insertion of an interval_value_pair into the map.

  33. 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.

  34. SubType & set(const element_type & key_value_pair) ;

    With key_value_pair = (k,v) set value v for key k

  35. 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.

  36. SubType & erase(const element_type & key_value_pair) ;

    Erase a key_value_pair from the map.

  37. SubType & erase(const segment_type & interval_value_pair) ;

    Erase an interval_value_pair from the map.

  38. SubType & erase(const domain_type & key) ;

    Erase a key value pair for key.

  39. SubType & erase(const interval_type & inter_val) ;

    Erase all value pairs within the range of the interval inter_val from the map.

  40. template<class SetSubType > 
      SubType & erase(const interval_base_set< SetSubType, DomainT, Compare, Interval, Alloc > & operand) ;

    Erase all value pairs for a set of intervals.

  41. SubType & erase(const interval_base_map & eraser) ;

    Erase all value pairs from *this map that are elements of map

  42. void erase(iterator position) ;

    Erase all value pairs within the range of the interval that iterator position points to.

  43. void erase(iterator first, iterator past) ;

    Erase all value pairs for a range of iterators [first,past).

  44. template<class Predicate > SubType & erase_if(const Predicate & pred) ;

    Remove all elements where property p holds, keep all others

  45. 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

  46. 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.

  47. 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.

  48. 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.

  49. 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.

  50. 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.

  51. bool intersects(const domain_type & key) const;

    Returns true, if element key is found in *this map. Complexity: logarithmic.

  52. bool intersects(const interval_type & inter_val) const;

    Returns true, if inter_val intersects with *this map. Complexity: Logarithmic in iterative size.

  53. bool intersects(const element_type & key_value_pair) const;

    Returns true, if key_value_pair is found in *this map. Complexity: logarithmic.

  54. bool intersects(const segment_type & interval_value_pair) const;

    Returns true, if interval_value_pair intersects with *this map: Complexity: Linear in iterative_size.

  55. SubType & flip(const element_type & key_value_pair) ;

    If *this map contains key_value_pair it is erased, otherwise it is added.

  56. SubType & flip(const segment_type & interval_value_pair) ;

    If *this map contains interval_value_pair it is erased, otherwise it is added.

  57. 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.

  58. iterator lower_bound(const key_type & interval) ;
  59. iterator upper_bound(const key_type & interval) ;
  60. const_iterator lower_bound(const key_type & interval) const;
  61. const_iterator upper_bound(const key_type & interval) const;
  62. std::pair< iterator, iterator > equal_range(const key_type & interval) ;
  63. std::pair< const_iterator, const_iterator > 
    equal_range(const key_type & interval) const;
  64. iterator begin() ;
  65. iterator end() ;
  66. const_iterator begin() const;
  67. const_iterator end() const;
  68. reverse_iterator rbegin() ;
  69. reverse_iterator rend() ;
  70. const_reverse_iterator rbegin() const;
  71. const_reverse_iterator rend() const;
  72. element_iterator elements_begin() ;
  73. element_iterator elements_end() ;
  74. element_const_iterator elements_begin() const;
  75. element_const_iterator elements_end() const;
  76. element_reverse_iterator elements_rbegin() ;
  77. element_reverse_iterator elements_rend() ;
  78. element_const_reverse_iterator elements_rbegin() const;
  79. element_const_reverse_iterator elements_rend() const;
  80. std::string as_string() const;

    Object as string

  81. interval_base_map & join() ;

    Join bounding intervals

  82. void absorb_neutrons() ;

    All value pairs (I,y) that have neutral elements y==codomain_type() as associated values are removed form the map.

  83. 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.

  84. 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

  85. void sum(codomain_type & total) const;
  86. codomain_type sum() const;
  87. sub_type & self() ;

interval_base_map private member functions

  1. template<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.

  2. 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 functions

  1. template<typename IteratorT > 
      static const key_type & key_value(IteratorT value_) ;
  2. template<typename IteratorT > 
      static const data_type & data_value(IteratorT value_) ;
  3. template<typename IteratorT > 
      static codomain_type codomain_value(IteratorT value_) ;
  4. template<typename LeftIterT , typename RightIterT > 
      static bool key_less(LeftIterT left_, RightIterT right_) ;
  5. static value_type 
    make_domain_element(const domain_type & dom_val, 
                        const codomain_type & codom_val) ;

interval_base_map protected member functions

  1. sub_type * that() ;
  2. const sub_type * that() const;
  3. iterator prior(iterator it_) ;
  4. const_iterator prior(const_iterator it_) const;
  5. template<class Combiner > 
      bool combine(iterator & it_, const codomain_type & co_val) ;
  6. template<class Combiner > 
      std::pair< iterator, bool > 
      map_insert(const interval_type & inter_val, const codomain_type & co_val) ;
  7. template<class Combiner > 
      std::pair< iterator, bool > 
      map_insert(iterator prior_, const interval_type & inter_val, 
                 const codomain_type & co_val) ;
  8. template<class Combiner > 
      std::pair< iterator, bool > 
      map_add(iterator prior_, const interval_type & inter_val, 
              const codomain_type & co_val) ;
  9. template<class Combiner > 
      iterator gap_insert(iterator prior_, const interval_type & inter_val, 
                          const codomain_type & co_val) ;

PrevUpHomeNext