Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

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;

PrevUpHomeNext