ceph/src/boost/boost/icl/interval_set.hpp

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