ceph/src/boost/libs/icl/include/boost/icl/split_interval_set.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2007-2009: Joachim Faulhaber
   3 Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
   4 +------------------------------------------------------------------------------+
   5    Distributed under the Boost Software License, Version 1.0.
   6       (See accompanying file LICENCE.txt or copy at
   7            http://www.boost.org/LICENSE_1_0.txt)
   8 +-----------------------------------------------------------------------------*/
   9 #ifndef BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
  10 #define BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
  11
  12 #include <boost/icl/type_traits/is_interval_splitter.hpp>
  13 #include <boost/icl/interval_base_set.hpp>
  14 #include <boost/icl/interval_set.hpp>
  15
  16 namespace boost{namespace icl
  17 {
  18
  19 /** \brief implements a set as a set of intervals - on insertion
  20     overlapping intervals are split */
  21 template
  22 <
  23     typename                  DomainT,
  24     ICL_COMPARE               Compare  = ICL_COMPARE_INSTANCE(ICL_COMPARE_DEFAULT, DomainT),
  25     ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
  26     ICL_ALLOC                 Alloc    = std::allocator
  27 >
  28 class split_interval_set:
  29     public interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
  30                              DomainT,Compare,Interval,Alloc>
  31 {
  32 public:
  33     typedef split_interval_set<DomainT,Compare,Interval,Alloc> type;
  34     typedef interval_base_set<type,DomainT,Compare,Interval,Alloc> base_type;
  35
  36     typedef interval_set<DomainT,Compare,Interval,Alloc> joint_type;
  37     typedef type overloadable_type;
  38     typedef type key_object_type;
  39
  40     /// The domain type of the set
  41     typedef DomainT   domain_type;
  42     /// The codomaintype is the same as domain_type
  43     typedef DomainT   codomain_type;
  44
  45     /// The element type of the set
  46     typedef DomainT   element_type;
  47     /// The interval type of the set
  48     typedef ICL_INTERVAL_TYPE(Interval,DomainT,Compare) interval_type;
  49     /// The segment type of the set
  50     typedef interval_type   segment_type;
  51
  52     /// Comparison functor for domain values
  53     typedef ICL_COMPARE_DOMAIN(Compare,DomainT) domain_compare;
  54     /// Comparison functor for intervals
  55     typedef exclusive_less_than<interval_type> interval_compare;
  56
  57     /// Comparison functor for keys
  58     typedef exclusive_less_than<interval_type> key_compare;
  59
  60     /// The allocator type of the set
  61     typedef Alloc<interval_type> allocator_type;
  62
  63     /// allocator type of the corresponding element set
  64     typedef Alloc<DomainT> domain_allocator_type;
  65
  66     /// The corresponding atomized type representing this interval container of elements
  67     typedef typename base_type::atomized_type atomized_type;
  68
  69     /// Container type for the implementation
  70     typedef typename base_type::ImplSetT ImplSetT;
  71
  72     /// key type of the implementing container
  73     typedef typename ImplSetT::key_type   key_type;
  74     /// data type of the implementing container
  75     typedef typename ImplSetT::value_type data_type;
  76     /// value type of the implementing container
  77     typedef typename ImplSetT::value_type value_type;
  78
  79     /// iterator for iteration over intervals
  80     typedef typename ImplSetT::iterator iterator;
  81     /// const_iterator for iteration over intervals
  82     typedef typename ImplSetT::const_iterator const_iterator;
  83
  84     enum { fineness = 3 };
  85
  86 public:
  87     //==========================================================================
  88     //= Construct, copy, destruct
  89     //==========================================================================
  90     /// Default constructor for the empty object
  91     split_interval_set(): base_type() {}
  92
  93     /// Copy constructor
  94     split_interval_set(const split_interval_set& src): base_type(src) {}
  95
  96     /// Copy constructor for base_type
  97     template<class SubType>
  98     split_interval_set
  99         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
 100     { this->assign(src); }
 101
 102     /// Constructor for a single element
 103     explicit split_interval_set(const interval_type& elem): base_type() { this->add(elem); }
 104     /// Constructor for a single interval
 105     explicit split_interval_set(const domain_type& itv): base_type() { this->add(itv); }
 106
 107     /// Assignment from a base interval_set.
 108     template<class SubType>
 109     void assign(const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
 110     {
 111         this->clear();
 112         this->_set.insert(src.begin(), src.end());
 113     }
 114
 115     /// Assignment operator for base type
 116     template<class SubType>
 117     split_interval_set& operator =
 118         (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& src)
 119     {
 120         this->assign(src);
 121         return *this;
 122     }
 123
 124 #   ifndef BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 125     //==========================================================================
 126     //= Move semantics
 127     //==========================================================================
 128
 129     /// Move constructor
 130     split_interval_set(split_interval_set&& src)
 131         : base_type(boost::move(src))
 132     {}
 133
 134     /// Move assignment operator
 135     split_interval_set& operator = (split_interval_set src)
 136     {
 137         base_type::operator=(boost::move(src));
 138         return *this;
 139     }
 140     //==========================================================================
 141 #   else
 142
 143     /// Assignment operator
 144     split_interval_set& operator = (const split_interval_set& src)
 145     {
 146         base_type::operator=(src);
 147         return *this;
 148     }
 149
 150 #   endif // BOOST_ICL_NO_CXX11_RVALUE_REFERENCES
 151
 152 private:
 153     // Private functions that shall be accessible by the baseclass:
 154     friend class
 155         interval_base_set<split_interval_set<DomainT,Compare,Interval,Alloc>,
 156                                              DomainT,Compare,Interval,Alloc>;
 157
 158     iterator handle_inserted(iterator inserted_)
 159     {
 160         return inserted_;
 161     }
 162
 163     iterator add_over(const interval_type& addend, iterator last_)
 164     {
 165         iterator first_ = this->_set.lower_bound(addend);
 166         //BOOST_ASSERT(next(last_) == this->_set.upper_bound(inter_val));
 167
 168         iterator it_ = first_;
 169         interval_type rest_interval = addend;
 170
 171         this->add_front(rest_interval, it_);
 172         this->add_main (rest_interval, it_, last_);
 173         this->add_rear (rest_interval, it_);
 174         return it_;
 175     }
 176
 177     iterator add_over(const interval_type& addend)
 178     {
 179         std::pair<iterator,iterator> overlap = this->equal_range(addend);
 180         iterator first_ = overlap.first,
 181                  end_   = overlap.second,
 182                  last_  = end_; --last_;
 183
 184         iterator it_ = first_;
 185         interval_type rest_interval = addend;
 186
 187         this->add_front(rest_interval, it_);
 188         this->add_main (rest_interval, it_, last_);
 189         this->add_rear (rest_interval, it_);
 190
 191         return it_;
 192     }
 193
 194 } ;
 195
 196
 197 //-----------------------------------------------------------------------------
 198 // type traits
 199 //-----------------------------------------------------------------------------
 200 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 201 struct is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
 202 {
 203     typedef is_set<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
 204     BOOST_STATIC_CONSTANT(bool, value = true);
 205 };
 206
 207 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 208 struct is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
 209 {
 210     typedef is_interval_container<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
 211     BOOST_STATIC_CONSTANT(bool, value = true);
 212 };
 213
 214 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 215 struct is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
 216 {
 217     typedef is_interval_splitter<icl::split_interval_set<DomainT,Compare,Interval,Alloc> > type;
 218     BOOST_STATIC_CONSTANT(bool, value = true);
 219 };
 220
 221 //-----------------------------------------------------------------------------
 222 // type representation
 223 //-----------------------------------------------------------------------------
 224 template <class DomainT, ICL_COMPARE Compare, ICL_INTERVAL(ICL_COMPARE)  Interval, ICL_ALLOC Alloc>
 225 struct type_to_string<icl::split_interval_set<DomainT,Compare,Interval,Alloc> >
 226 {
 227     static std::string apply()
 228     { return "sp_itv_set<"+ type_to_string<DomainT>::apply() +">"; }
 229 };
 230
 231
 232 }} // namespace icl boost
 233
 234 #endif // BOOST_ICL_SPLIT_INTERVAL_SET_HPP_JOFA_990223
 235
 236
 237