Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Class template interval_base_set

boost::itl::interval_base_set — Implements a set as a set of intervals (base class).

Synopsis

template<typename SubType , typename DomainT , 
         ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, DomainT), 
         template< class, ITL_COMPARE >class Interval = itl::interval, 
         ITL_ALLOC Alloc = std::allocator> 
class interval_base_set {
public:
  // types
  typedef interval_base_set< SubType, DomainT, Compare, 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 itl::set< DomainT, Compare, Alloc >                               atomized_type;                   // The atomized type representing the corresponding container of elements. 
  typedef DomainT                                                           domain_type;                     // The domain type of the set. 
  typedef DomainT                                                           codomain_type;                   // The codomaintype is the same as domain_type. 
  typedef DomainT                                                           element_type;                    // The element type of the set. 
  typedef Interval< DomainT, Compare >                                      interval_type;                   // The interval type of the set. 
  typedef interval_type                                                     segment_type;                    // The segment type of the set. 
  typedef interval_type::difference_type                                    difference_type;                 // The difference type of an interval which is sometimes different form the data_type. 
  typedef interval_type::size_type                                          size_type;                       // The size type of an interval which is mostly std::size_t. 
  typedef exclusive_less< interval_type >                                   interval_compare;                // Comparison functor for intervals. 
  typedef exclusive_less< interval_type >                                   key_compare;                     // Comparison functor for keys. 
  typedef Alloc< interval_type >                                            allocator_type;                  // The allocator type of the set. 
  typedef Alloc< DomainT >                                                  domain_allocator_type;           // allocator type of the corresponding element set 
  typedef ITL_IMPL_SPACE::set< interval_type, key_compare, allocator_type > ImplSetT;                        // Container type for the implementation. 
  typedef ImplSetT::key_type                                                key_type;                        // key type of the implementing container 
  typedef ImplSetT::key_type                                                data_type;                       // data type of the implementing container 
  typedef ImplSetT::value_type                                              value_type;                      // value type of the implementing container 
  typedef ImplSetT::pointer                                                 pointer;                         // pointer type 
  typedef ImplSetT::const_pointer                                           const_pointer;                   // const pointer type 
  typedef ImplSetT::reference                                               reference;                       // reference type 
  typedef ImplSetT::const_reference                                         const_reference;                 // const reference type 
  typedef ImplSetT::iterator                                                iterator;                        // iterator for iteration over intervals 
  typedef ImplSetT::const_iterator                                          const_iterator;                  // const_iterator for iteration over intervals 
  typedef ImplSetT::reverse_iterator                                        reverse_iterator;                // iterator for reverse iteration over intervals 
  typedef ImplSetT::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;          // element const 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_set();
  interval_base_set(const interval_base_set &);
  interval_base_set& operator=(const interval_base_set &);

  // public member functions
  typedef ITL_COMPARE_DOMAIN(Compare, DomainT) ;
  void swap(interval_base_set &) ;
  void clear() ;
  bool empty() const;
  bool contains(const element_type &) const;
  bool contains(const segment_type &) const;
  bool contains(const interval_base_set &) const;
  template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> 
    bool contains(const IntervalSet< DomainT, Compare, Interval, Alloc > &) const;
  template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> 
    bool contained_in(const IntervalSet< DomainT, Compare, Interval, Alloc > &) const;
  size_type cardinality() const;
  size_type size() const;
  difference_type length() const;
  std::size_t interval_count() const;
  std::size_t iterative_size() const;
  DomainT lower() const;
  DomainT upper() const;
  DomainT first() const;
  DomainT last() const;
  const_iterator find(const element_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 & erase(const element_type &) ;
  SubType & erase(const segment_type &) ;
  void erase(iterator) ;
  void erase(iterator, iterator) ;
  void add_intersection(interval_base_set &, const element_type &) const;
  void add_intersection(interval_base_set &, const segment_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_set &, 
                          const IntervalSet< DomainT, Compare, Interval, Alloc > &) const;
  bool intersects(const element_type &) const;
  bool intersects(const interval_type &) const;
  SubType & flip(const element_type &) ;
  SubType & flip(const segment_type &) ;
  template<class SubType2 > 
    SubType & flip(const interval_base_set< SubType2, DomainT, Compare, Interval, Alloc > &) ;
  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;
  iterator lower_bound(const value_type &) ;
  iterator upper_bound(const value_type &) ;
  const_iterator lower_bound(const value_type &) const;
  const_iterator upper_bound(const value_type &) const;
  std::pair< iterator, iterator > equal_range(const key_type &) ;
  std::pair< const_iterator, const_iterator > 
  equal_range(const key_type &) 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;
  interval_base_set & join() ;
  void uniform_bounds(itl::bound_type) ;
  const std::string as_string() const;
  sub_type & self() ;

  // public static functions
  template<typename IteratorT > static const key_type & key_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;
  iterator gap_insert(iterator, const interval_type &) ;
};

Description

interval_base_set public construct/copy/destruct

  1. interval_base_set();

    Default constructor for the empty object

  2. interval_base_set(const interval_base_set & src);

    Copy constructor

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

    Assignment operator

interval_base_set public member functions

  1. typedef ITL_COMPARE_DOMAIN(Compare, DomainT) ;
  2. void swap(interval_base_set & x) ;

    swap the content of containers

  3. void clear() ;

    sets the container empty

  4. bool empty() const;

    is the container empty?

  5. bool contains(const element_type & key) const;

    Does the container contain the element key ?

  6. bool contains(const segment_type & sub_interval) const;

    Does the container contain the interval sub_interval ?

  7. bool contains(const interval_base_set & sub) const;

    Does the container contain the subcontainer sub ?

  8. template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> 
      bool contains(const IntervalSet< DomainT, Compare, Interval, Alloc > & sub) const;

    Does *this container contain sub?

  9. template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> 
      bool contained_in(const IntervalSet< DomainT, Compare, Interval, Alloc > & super) const;

    Is *this container contained in super?

  10. size_type cardinality() const;

    Number of elements in the set (cardinality). Infinite for continuous domain datatyps

  11. size_type size() const;

    An interval set's size is it's cardinality

  12. difference_type length() const;

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

  13. std::size_t interval_count() const;

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

  14. std::size_t iterative_size() const;

    Size of the iteration over this container

  15. DomainT lower() const;

    lower bound of all intervals in the object

  16. DomainT upper() const;

    upper bound of all intervals in the object

  17. DomainT first() const;

    Smallest element of the set (wrt. the partial ordering on DomainT). first() does not exist for continuous datatypes and open interval bounds.

  18. DomainT last() const;

    Largest element of the set (wrt. the partial ordering on DomainT). last() does not exist for continuous datatypes and open interval bounds.

  19. const_iterator find(const element_type & key) const;

    Find the interval value pair, that contains element key

  20. SubType & add(const element_type & key) ;

    Add a single element key to the set

  21. SubType & add(const segment_type & inter_val) ;

    Add an interval of elements inter_val to the set

  22. iterator add(iterator prior_, const segment_type & inter_val) ;

    Add an interval of elements inter_val to the set. Iterator prior_ is a hint to the position inter_val can be inserted after.

  23. SubType & subtract(const element_type & key) ;

    Subtract a single element key from the set

  24. SubType & subtract(const segment_type & inter_val) ;

    Subtract an interval of elements inter_val from the set

  25. SubType & insert(const element_type & key) ;

    Insert an element key into the set

  26. SubType & insert(const segment_type & inter_val) ;

    Insert an interval of elements inter_val to the set

  27. iterator insert(iterator prior_, const segment_type & inter_val) ;

    Insert an interval of elements inter_val to the set. Iterator prior_ is a hint to the position inter_val can be inserted after.

  28. SubType & erase(const element_type & key) ;

    Erase an element key from the set

  29. SubType & erase(const segment_type & inter_val) ;

    Erase an interval of elements inter_val from the set

  30. void erase(iterator position) ;

    Erase the interval that iterator position points to.

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

    Erase all intervals in the range [first,past) of iterators.

  32. void add_intersection(interval_base_set & section, const element_type & key) const;

    The intersection of key in *this set is added to section. The function can be used as a find function.

  33. void add_intersection(interval_base_set & section, 
                          const segment_type & inter_val) const;

    The intersection of inter_val in *this set is added to section.

  34. template<template< class DomT, ITL_COMPARE Comp, template< class DomT2, ITL_COMPARE >class Interv, ITL_ALLOC Allc > class IntervalSet> 
      void add_intersection(interval_base_set & intersection, 
                            const IntervalSet< DomainT, Compare, Interval, Alloc > & sectant) const;

    The intersection of set sectant with *this set is added to section.

  35. bool intersects(const element_type & key) const;

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

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

    Returns true, if inter_val intersects with *this map. Complexity: logarithmic.

  37. SubType & flip(const element_type & key) ;

    If *this set contains key it is erased, otherwise it is added.

  38. SubType & flip(const segment_type & inter_val) ;

    If *this set contains inter_val it is erased, otherwise it is added.

  39. template<class SubType2 > 
      SubType & flip(const interval_base_set< SubType2, DomainT, Compare, Interval, Alloc > & operand) ;

    The intersection of *this and operand is erased from *this. The complemenary elements are added to *this.

  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;
  48. iterator lower_bound(const value_type & interval) ;
  49. iterator upper_bound(const value_type & interval) ;
  50. const_iterator lower_bound(const value_type & interval) const;
  51. const_iterator upper_bound(const value_type & interval) const;
  52. std::pair< iterator, iterator > equal_range(const key_type & interval) ;
  53. std::pair< const_iterator, const_iterator > 
    equal_range(const key_type & interval) const;
  54. element_iterator elements_begin() ;
  55. element_iterator elements_end() ;
  56. element_const_iterator elements_begin() const;
  57. element_const_iterator elements_end() const;
  58. element_reverse_iterator elements_rbegin() ;
  59. element_reverse_iterator elements_rend() ;
  60. element_const_reverse_iterator elements_rbegin() const;
  61. element_const_reverse_iterator elements_rend() const;
  62. interval_base_set & join() ;

    Join bordering intervals

  63. void uniform_bounds(itl::bound_type bounded) ;

    Set interval bounds to the type bt for intervals in the set. Interval bounds of different types are created by opeations on interval sets. This function allows to reset them uniformly without, of course, changing their value. This is only possible for discrete domain datatypes.

  64. const std::string as_string() const;

    Interval container's string representation

  65. sub_type & self() ;

interval_base_set public static functions

  1. template<typename IteratorT > 
      static const key_type & key_value(IteratorT value_) ;
  2. template<typename IteratorT > 
      static codomain_type codomain_value(IteratorT value_) ;
  3. template<typename LeftIterT , typename RightIterT > 
      static bool key_less(LeftIterT lhs_, RightIterT rhs_) ;
  4. static value_type 
    make_domain_element(const domain_type & dom_val, const codomain_type &) ;

interval_base_set 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. iterator gap_insert(iterator prior_, const interval_type & inter_val) ;

PrevUpHomeNext