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

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2010-2010: Joachim Faulhaber
   3 +------------------------------------------------------------------------------+
   4    Distributed under the Boost Software License, Version 1.0.
   5       (See accompanying file LICENCE.txt or copy at
   6            http://www.boost.org/LICENSE_1_0.txt)
   7 +-----------------------------------------------------------------------------*/
   8 #ifndef BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
   9 #define BOOST_ICL_CONCEPT_INTERVAL_SET_HPP_JOFA_100920
  10
  11 #include <boost/icl/type_traits/is_combinable.hpp>
  12 #include <boost/icl/type_traits/interval_type_of.hpp>
  13 #include <boost/icl/detail/set_algo.hpp>
  14 #include <boost/icl/detail/interval_set_algo.hpp>
  15 #include <boost/icl/concept/interval.hpp>
  16
  17 namespace boost{ namespace icl
  18 {
  19
  20 //==============================================================================
  21 //= Containedness<IntervalSet>
  22 //==============================================================================
  23 //------------------------------------------------------------------------------
  24 //- bool contains(c T&, c P&) T:{S} P:{e i S} fragment_types
  25 //------------------------------------------------------------------------------
  26 template<class Type>
  27 typename enable_if<is_interval_set<Type>, bool>::type
  28 contains(const Type& super, const typename Type::element_type& element)
  29 {
  30     return !(icl::find(super, element) == super.end());
  31 }
  32
  33 template<class Type>
  34 typename enable_if<is_interval_set<Type>, bool>::type
  35 contains(const Type& super, const typename Type::segment_type& inter_val)
  36 {
  37     typedef typename Type::const_iterator const_iterator;
  38     if(icl::is_empty(inter_val))
  39         return true;
  40
  41     std::pair<const_iterator, const_iterator> exterior
  42         = super.equal_range(inter_val);
  43     if(exterior.first == exterior.second)
  44         return false;
  45
  46     const_iterator last_overlap = cyclic_prior(super, exterior.second);
  47
  48     return
  49         icl::contains(hull(*(exterior.first), *last_overlap), inter_val)
  50     &&  Interval_Set::is_joinable(super, exterior.first, last_overlap);
  51 }
  52
  53 template<class Type, class OperandT>
  54 typename enable_if<has_same_concept<is_interval_set, Type, OperandT>,
  55                    bool>::type
  56 contains(const Type& super, const OperandT& sub)
  57 {
  58     return Interval_Set::contains(super, sub);
  59 }
  60
  61 //==============================================================================
  62 //= Addition<IntervalSet>
  63 //==============================================================================
  64 //------------------------------------------------------------------------------
  65 //- T& add(T&, c P&) T:{S} P:{e i} fragment_types
  66 //------------------------------------------------------------------------------
  67 template<class Type>
  68 typename enable_if<is_interval_set<Type>, Type>::type&
  69 add(Type& object, const typename Type::segment_type& operand)
  70 {
  71     return object.add(operand);
  72 }
  73
  74 template<class Type>
  75 inline typename enable_if<is_interval_set<Type>, Type>::type&
  76 add(Type& object, const typename Type::element_type& operand)
  77 {
  78     typedef typename Type::segment_type segment_type;
  79     return icl::add(object, icl::singleton<segment_type>(operand));
  80 }
  81
  82 //------------------------------------------------------------------------------
  83 //- T& add(T&, J, c P&) T:{S} P:{i} interval_type
  84 //------------------------------------------------------------------------------
  85 template<class Type>
  86 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
  87 add(Type& object, typename Type::iterator      prior,
  88             const typename Type::segment_type& operand)
  89 {
  90     return object.add(prior, operand);
  91 }
  92
  93 //==============================================================================
  94 //= Insertion<IntervalSet>
  95 //==============================================================================
  96 //------------------------------------------------------------------------------
  97 //- T& insert(T&, c P&) T:{S} P:{e i} fragment_types
  98 //------------------------------------------------------------------------------
  99 template<class Type>
 100 inline typename enable_if<is_interval_set<Type>, Type>::type&
 101 insert(Type& object, const typename Type::segment_type& operand)
 102 {
 103     return icl::add(object, operand);
 104 }
 105
 106 template<class Type>
 107 inline typename enable_if<is_interval_set<Type>, Type>::type&
 108 insert(Type& object, const typename Type::element_type& operand)
 109 {
 110     return icl::add(object, operand);
 111 }
 112
 113 //------------------------------------------------------------------------------
 114 //- T& insert(T&, J, c P&) T:{S} P:{i} with hint
 115 //------------------------------------------------------------------------------
 116 template<class Type>
 117 inline typename enable_if<is_interval_set<Type>, typename Type::iterator>::type
 118 insert(Type& object, typename Type::iterator      prior,
 119                const typename Type::segment_type& operand)
 120 {
 121     return icl::add(object, prior, operand);
 122 }
 123
 124 //==============================================================================
 125 //= Subtraction<IntervalSet>
 126 //==============================================================================
 127 //------------------------------------------------------------------------------
 128 //- T& subtract(T&, c P&) T:{S} P:{e i} fragment_type
 129 //------------------------------------------------------------------------------
 130 template<class Type>
 131 typename enable_if<is_interval_set<Type>, Type>::type&
 132 subtract(Type& object, const typename Type::segment_type& operand)
 133 {
 134     return object.subtract(operand);
 135 }
 136
 137 template<class Type>
 138 inline typename enable_if<is_interval_set<Type>, Type>::type&
 139 subtract(Type& object, const typename Type::element_type& operand)
 140 {
 141     typedef typename Type::segment_type segment_type;
 142     return icl::subtract(object, icl::singleton<segment_type>(operand));
 143 }
 144
 145 //==============================================================================
 146 //= Erasure<IntervalSet>
 147 //==============================================================================
 148 //------------------------------------------------------------------------------
 149 //- T& erase(T&, c P&) T:{S} P:{e i} fragment_types
 150 //------------------------------------------------------------------------------
 151 template<class Type>
 152 typename enable_if<is_interval_set<Type>, Type>::type&
 153 erase(Type& object, const typename Type::segment_type& minuend)
 154 {
 155     return icl::subtract(object, minuend);
 156 }
 157
 158 template<class Type>
 159 typename enable_if<is_interval_set<Type>, Type>::type&
 160 erase(Type& object, const typename Type::element_type& minuend)
 161 {
 162     return icl::subtract(object, minuend);
 163 }
 164
 165 //==============================================================================
 166 //= Intersection
 167 //==============================================================================
 168 //------------------------------------------------------------------------------
 169 //- void add_intersection(T&, c T&, c P&) T:{S} P:{e i} fragment_types
 170 //------------------------------------------------------------------------------
 171 template<class Type>
 172 typename enable_if<is_interval_set<Type>, void>::type
 173 add_intersection(Type& section, const Type& object,
 174                  const typename Type::element_type& operand)
 175 {
 176     typedef typename Type::const_iterator const_iterator;
 177     const_iterator found = icl::find(object, operand);
 178     if(found != object.end())
 179         icl::add(section, operand);
 180 }
 181
 182
 183 template<class Type>
 184 typename enable_if<is_interval_set<Type>, void>::type
 185 add_intersection(Type& section, const Type& object,
 186                  const typename Type::segment_type& segment)
 187 {
 188     typedef typename Type::const_iterator const_iterator;
 189     typedef typename Type::iterator       iterator;
 190     typedef typename Type::interval_type  interval_type;
 191
 192     if(icl::is_empty(segment))
 193         return;
 194
 195     std::pair<const_iterator, const_iterator> exterior
 196         = object.equal_range(segment);
 197     if(exterior.first == exterior.second)
 198         return;
 199
 200     iterator prior_ = section.end();
 201     for(const_iterator it_=exterior.first; it_ != exterior.second; it_++)
 202     {
 203         interval_type common_interval = key_value<Type>(it_) & segment;
 204         if(!icl::is_empty(common_interval))
 205             prior_ = section.insert(prior_, common_interval);
 206     }
 207 }
 208
 209 //==============================================================================
 210 //= Symmetric difference<IntervalSet>
 211 //==============================================================================
 212 //------------------------------------------------------------------------------
 213 //- T& flip(T&, c P&) T:{S} P:{e i S'} fragment_types
 214 //------------------------------------------------------------------------------
 215 template<class Type>
 216 typename enable_if<is_interval_set<Type>, Type>::type&
 217 flip(Type& object, const typename Type::element_type& operand)
 218 {
 219     if(icl::contains(object, operand))
 220         return object -= operand;
 221     else
 222         return object += operand;
 223 }
 224
 225 template<class Type>
 226 typename enable_if<is_interval_set<Type>, Type>::type&
 227 flip(Type& object, const typename Type::segment_type& segment)
 228 {
 229     typedef typename Type::const_iterator const_iterator;
 230     typedef typename Type::interval_type  interval_type;
 231     // That which is common shall be subtracted
 232     // That which is not shall be added
 233     // So x has to be 'complementary added' or flipped
 234     interval_type span = segment;
 235     std::pair<const_iterator, const_iterator> exterior
 236         = object.equal_range(span);
 237
 238     const_iterator fst_ = exterior.first;
 239     const_iterator end_ = exterior.second;
 240
 241     interval_type covered, left_over;
 242     const_iterator it_ = fst_;
 243     while(it_ != end_)
 244     {
 245         covered = *it_++;
 246         //[a      ...  : span
 247         //     [b ...  : covered
 248         //[a  b)       : left_over
 249         left_over = right_subtract(span, covered);
 250         icl::subtract(object, span & covered); //That which is common shall be subtracted
 251         icl::add(object, left_over);           //That which is not shall be added
 252
 253         //...      d) : span
 254         //... c)      : covered
 255         //     [c  d) : span'
 256         span = left_subtract(span, covered);
 257     }
 258
 259     //If span is not empty here, it_ is not in the set so it_ shall be added
 260     icl::add(object, span);
 261     return object;
 262 }
 263
 264
 265 template<class Type, class OperandT>
 266 typename enable_if<is_concept_compatible<is_interval_set, Type, OperandT>, Type>::type&
 267 flip(Type& object, const OperandT& operand)
 268 {
 269     typedef typename OperandT::const_iterator const_iterator;
 270
 271     if(operand.empty())
 272         return object;
 273
 274     const_iterator common_lwb, common_upb;
 275
 276     if(!Set::common_range(common_lwb, common_upb, operand, object))
 277         return object += operand;
 278
 279     const_iterator it_ = operand.begin();
 280
 281     // All elements of operand left of the common range are added
 282     while(it_ != common_lwb)
 283         icl::add(object, *it_++);
 284     // All elements of operand in the common range are symmertrically subtracted
 285     while(it_ != common_upb)
 286         icl::flip(object, *it_++);
 287     // All elements of operand right of the common range are added
 288     while(it_ != operand.end())
 289         icl::add(object, *it_++);
 290
 291     return object;
 292 }
 293
 294 //==============================================================================
 295 //= Set selection
 296 //==============================================================================
 297 template<class Type>
 298 typename enable_if<is_interval_set<Type>, Type>::type&
 299 domain(Type& dom, const Type& object)
 300 {
 301     typedef typename Type::const_iterator const_iterator;
 302     typedef typename Type::iterator       iterator;
 303     dom.clear();
 304     const_iterator it_    = object.begin();
 305     iterator       prior_ = dom.end();
 306
 307     while(it_ != object.end())
 308         prior_ = icl::insert(dom, prior_, *it_++);
 309
 310     return dom;
 311 }
 312
 313 template<class Type>
 314 typename enable_if<is_interval_set<Type>, Type>::type&
 315 between(Type& in_between, const Type& object)
 316 {
 317     typedef typename Type::const_iterator const_iterator;
 318     typedef typename Type::iterator       iterator;
 319     in_between.clear();
 320     const_iterator it_ = object.begin(), pred_;
 321     iterator prior_ = in_between.end();
 322
 323     if(it_ != object.end())
 324         pred_ = it_++;
 325
 326     while(it_ != object.end())
 327         prior_ = icl::insert(in_between, prior_,
 328                              icl::between(*pred_++, *it_++));
 329
 330     return in_between;
 331 }
 332
 333
 334 //==============================================================================
 335 //= Streaming
 336 //==============================================================================
 337 template<class CharType, class CharTraits, class Type>
 338 typename enable_if<is_interval_set<Type>,
 339                    std::basic_ostream<CharType, CharTraits> >::type&
 340 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
 341 {
 342     stream << "{";
 343     ICL_const_FORALL(typename Type, it_, object)
 344         stream << (*it_);
 345
 346     return stream << "}";
 347 }
 348
 349
 350 }} // namespace boost icl
 351
 352 #endif
 353
 354