Class template interval_base_map

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

Synopsis

// 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, bool has_set_semantics> 
  struct on_codomain_model {
  };
  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, bool is_total> 
  struct on_definedness {
  };
  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, bool is_total_invertible> 
  struct on_invertible {
  };
  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 is_total, bool absorbs_identities> 
  struct on_total_absorbable {
  };
  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 &);
  };

  // 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);
  interval_base_map();
  interval_base_map(const interval_base_map &);
  interval_base_map(interval_base_map &&);
  interval_base_map & operator=(interval_base_map);
  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;
};

Description

`interval_base_map` public member functions

typedef 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);

```
interval_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=(interval_base_map src);

Move assignment operator

```
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 functions

template<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 functions

template<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;
```

Boost C++ Libraries