| Home | Libraries | People | FAQ | More

## 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(std::less, 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& operator=(const 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;
    };

## 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 ICL_INTERVAL_TYPE(Interval, DomainT, Compare);

   The interval type of the map.

2.     typedef ICL_COMPARE_DOMAIN(Compare, DomainT);

   Comparison functor for domain values.

3.     typedef ICL_COMPARE_DOMAIN(Compare, segment_type);

4.     typedef ICL_COMBINE_CODOMAIN(Combine, CodomainT);

   Combine functor for codomain value aggregation.

5.      BOOST_STATIC_CONSTANT(bool,
                              is_total_invertible = (Traits::is_total &&has_inverse< codomain_type >::value));

6.      BOOST_STATIC_CONSTANT(int, fineness = 0);

7.     void swap(interval_base_map & object);

   swap the content of containers

8.     void clear();

   clear the map

9.     bool empty() const;

   is the map empty?

10.     size_type size() const;

    An interval map's size is it's cardinality

11.     std::size_t iterative_size() const;

    Size of the iteration over this container

12.     const_iterator find(const domain_type & key_value) const;

    Find the interval value pair, that contains `key`

13.     const_iterator find(const interval_type & key_interval) const;

    Find the first interval value pair, that collides with interval `key_interval`

14.     codomain_type operator()(const domain_type & key_value) const;

    Total select function.

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

    Addition of a key value pair to the map

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

    Addition of an interval value pair to the map.

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

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

    Subtraction of a key value pair from the map

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

    Subtraction of an interval value pair from the map.

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

    Insertion of a `key_value_pair` into the map.

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

    Insertion of an `interval_value_pair` into the map.

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

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

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

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

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

    Erase a `key_value_pair` from the map.

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

    Erase an `interval_value_pair` from the map.

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

    Erase a key value pair for `key`.

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

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

29.     void erase(iterator position);

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

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

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

31.     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`.

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

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

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

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

34.     iterator lower_bound(const key_type & interval);

35.     iterator upper_bound(const key_type & interval);

36.     const_iterator lower_bound(const key_type & interval) const;

37.     const_iterator upper_bound(const key_type & interval) const;

38.     std::pair< iterator, iterator > equal_range(const key_type & interval);

39.     std::pair< const_iterator, const_iterator >
        equal_range(const key_type & interval) const;

40.     iterator begin();

41.     iterator end();

42.     const_iterator begin() const;

43.     const_iterator end() const;

44.     reverse_iterator rbegin();

45.     reverse_iterator rend();

46.     const_reverse_iterator rbegin() const;

47.     const_reverse_iterator rend() const;

### `interval_base_map` private member functions

1.     template<typename Combiner>
         iterator _add(const segment_type & interval_value_pair);

2.     template<typename Combiner>
         iterator _add(iterator prior_, const segment_type & interval_value_pair);

3.     template<typename Combiner>
         void _subtract(const segment_type & interval_value_pair);

4.     iterator _insert(const segment_type & interval_value_pair);

5.     iterator _insert(iterator prior_, const segment_type & interval_value_pair);

6.     template<typename Combiner>
         void add_segment(const interval_type & inter_val, const CodomainT & co_val,
                          iterator & it_);

7.     template<typename Combiner>
         void add_main(interval_type & inter_val, const CodomainT & co_val,
                       iterator & it_, const iterator & last_);

8.     template<typename Combiner>
         void add_rear(const interval_type & inter_val, const CodomainT & co_val,
                       iterator & it_);

9.     void add_front(const interval_type & inter_val, iterator & first_);

10.     void subtract_front(const interval_type & inter_val, iterator & first_);

11.     template<typename Combiner>
          void subtract_main(const CodomainT & co_val, iterator & it_,
                             const iterator & last_);

12.     template<typename Combiner>
          void subtract_rear(interval_type & inter_val, const CodomainT & co_val,
                             iterator & it_);

13.     void insert_main(const interval_type &, const CodomainT &, iterator &,
                         const iterator &);

14.     void erase_rest(interval_type &, const CodomainT &, iterator &,
                        const iterator &);

15.     template<typename FragmentT>
          void total_add_intersection(SubType & section, const FragmentT & fragment) const;

16.     void partial_add_intersection(SubType & section, const segment_type & operand) const;

17.     void partial_add_intersection(SubType & section, const element_type & operand) const;

### `interval_base_map` protected member functions

1.     template<typename Combiner>
         iterator gap_insert(iterator prior_, const interval_type & inter_val,
                             const codomain_type & co_val);

2.     template<typename Combiner>
         std::pair< iterator, bool >
         add_at(const iterator & prior_, const interval_type & inter_val,
                const codomain_type & co_val);

3.     std::pair< iterator, bool >
       insert_at(const iterator & prior_, const interval_type & inter_val,
                 const codomain_type & co_val);

4.     sub_type * that();

5.     const sub_type * that() const;