ceph/src/boost/libs/icl/include/boost/icl/concept/element_map.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_ELEMENT_MAP_HPP_JOFA_100921
   9 #define BOOST_ICL_CONCEPT_ELEMENT_MAP_HPP_JOFA_100921
  10
  11 #include <boost/mpl/and.hpp>
  12 #include <boost/mpl/not.hpp>
  13 #include <boost/icl/detail/on_absorbtion.hpp>
  14 #include <boost/icl/type_traits/unit_element.hpp>
  15 #include <boost/icl/type_traits/is_total.hpp>
  16 #include <boost/icl/type_traits/absorbs_identities.hpp>
  17 #include <boost/icl/type_traits/is_associative_element_container.hpp>
  18 #include <boost/icl/type_traits/is_combinable.hpp>
  19
  20 #include <boost/icl/concept/map_value.hpp>
  21 #include <boost/icl/detail/map_algo.hpp>
  22
  23
  24 namespace boost{ namespace icl
  25 {
  26
  27 //NOTE: Some forward declarations are needed by some compilers.
  28 template<class Type, class Predicate>
  29 typename enable_if<is_associative_element_container<Type>, Type>::type&
  30 erase_if(const Predicate& pred, Type& object);
  31
  32
  33 //==============================================================================
  34 //= Containedness<ElementMap>
  35 //==============================================================================
  36 //------------------------------------------------------------------------------
  37 //- bool within(c P&, c T&) T:{m} P:{b} fragment_types
  38 //------------------------------------------------------------------------------
  39 /** Checks if a key-value pair is in the map */
  40 template<class Type>
  41 typename enable_if<is_element_map<Type>, bool>::type
  42 within(const typename Type::element_type& value_pair, const Type& super)
  43 {
  44     typedef typename Type::const_iterator const_iterator;
  45     const_iterator found_ = super.find(value_pair.first);
  46     return found_ != super.end() && (*found_).second == value_pair.second;
  47 }
  48
  49 //------------------------------------------------------------------------------
  50 //- bool contains(c T&, c P&) T:{m} P:{b} fragment_types
  51 //------------------------------------------------------------------------------
  52 template<class Type>
  53 typename enable_if<is_element_map<Type>, bool>::type
  54 contains(const Type& super, const typename Type::element_type& value_pair)
  55 {
  56     return icl::within(value_pair, super);
  57 }
  58
  59 //==============================================================================
  60 //= Equivalences and Orderings<ElementMap>
  61 //==============================================================================
  62
  63 /** Protonic equality is equality on all elements that do not carry an identity element as content. */
  64 template<class Type>
  65 inline typename enable_if<is_element_map<Type>, bool>::type
  66 is_distinct_equal(const Type& lhs, const Type& rhs)
  67 {
  68     return Map::lexicographical_distinct_equal(lhs, rhs);
  69 }
  70
  71 //==============================================================================
  72 //= Addition<ElementMap>
  73 //==============================================================================
  74 /** \c add inserts \c value_pair into the map if it's key does
  75     not exist in the map.
  76     If \c value_pairs's key value exists in the map, it's data
  77     value is added to the data value already found in the map. */
  78 template <class Type>
  79 typename enable_if<is_element_map<Type>, Type>::type&
  80 add(Type& object, const typename Type::value_type& value_pair)
  81 {
  82     return object.add(value_pair);
  83 }
  84
  85 /** \c add add \c value_pair into the map using \c prior as a hint to
  86     insert \c value_pair after the position \c prior is pointing to. */
  87 template <class Type>
  88 typename enable_if<is_element_map<Type>, typename Type::iterator>::type
  89 add(Type& object, typename Type::iterator prior,
  90     const typename Type::value_type& value_pair)
  91 {
  92     return object.add(prior, value_pair);
  93 }
  94
  95 //==============================================================================
  96 //= Erasure
  97 //==============================================================================
  98 //------------------------------------------------------------------------------
  99 //- T& erase(T&, c P&) T:{m} P:{b} fragment_type
 100 //------------------------------------------------------------------------------
 101 template <class Type>
 102 typename enable_if<is_element_map<Type>, typename Type::size_type>::type
 103 erase(Type& object, const typename Type::element_type& value_pair)
 104 {
 105     typedef typename Type::size_type             size_type;
 106     typedef typename Type::iterator              iterator;
 107     typedef typename Type::on_identity_absorbtion on_identity_absorbtion;
 108
 109     if(on_identity_absorbtion::is_absorbable(value_pair.second))
 110         return identity_element<size_type>::value();
 111
 112     iterator it_ = object.find(value_pair.first);
 113     if(it_ != object.end() && value_pair.second == (*it_).second)
 114     {
 115         object.erase(it_);
 116         return unit_element<size_type>::value();
 117     }
 118
 119     return identity_element<size_type>::value();
 120 }
 121
 122 template<class Type>
 123 typename enable_if<is_element_map<Type>, Type>::type&
 124 erase(Type& object, const typename Type::set_type& erasure)
 125 {
 126     typedef typename Type::set_type set_type;
 127     ICL_const_FORALL(typename set_type, elem_, erasure)
 128         icl::erase(object, *elem_);
 129
 130     return object;
 131 }
 132
 133 //==============================================================================
 134 //= Subtraction
 135 //==============================================================================
 136 //------------------------------------------------------------------------------
 137 //- T& subtract(T&, c P&) T:{m} P:{b} fragment_type
 138 //------------------------------------------------------------------------------
 139 template <class Type>
 140 inline typename enable_if<is_element_map<Type>, Type>::type&
 141 subtract(Type& object, const typename Type::element_type& operand)
 142 {
 143     return object.subtract(operand);
 144 }
 145
 146 //------------------------------------------------------------------------------
 147 //- T& subtract(T&, c P&) T:{m} P:{e} key_type
 148 //------------------------------------------------------------------------------
 149 template <class Type>
 150 typename enable_if<is_element_map<Type>, Type>::type&
 151 subtract(Type& object, const typename Type::domain_type& key_value)
 152 {
 153     return icl::erase(object, key_value);
 154 }
 155
 156 //------------------------------------------------------------------------------
 157 //- T& subtract(T&, c P&) T:{m} P:{s} set key_type
 158 //------------------------------------------------------------------------------
 159 template <class Type>
 160 inline typename enable_if<is_element_map<Type>, Type>::type&
 161 operator -= (Type& object, const typename Type::set_type& operand)
 162 {
 163     typedef typename Type::set_type           set_type;
 164     typedef typename set_type::const_iterator co_iterator;
 165     typedef typename Type::iterator           iterator;
 166
 167     co_iterator common_lwb_, common_upb_;
 168     if(!Set::common_range(common_lwb_, common_upb_, operand, object))
 169         return object;
 170
 171     co_iterator it_ = common_lwb_;
 172     iterator    common_;
 173
 174     while(it_ != common_upb_)
 175         object.erase(*it_++);
 176
 177     return object;
 178 }
 179
 180 template <class Type>
 181 inline typename enable_if<is_element_map<Type>, Type>::type
 182 operator - (Type object, const typename Type::set_type& subtrahend)
 183 {
 184     return object -= subtrahend;
 185 }
 186
 187 //==============================================================================
 188 //= Selective Update<ElementMap>
 189 //==============================================================================
 190 //------------------------------------------------------------------------------
 191 //- T& set_at(T&, c P&) T:{m} P:{b}
 192 //------------------------------------------------------------------------------
 193 template<class Type>
 194 inline typename enable_if<is_element_map<Type>, Type>::type&
 195 set_at(Type& object, const typename Type::element_type& operand)
 196 {
 197     typedef typename Type::iterator         iterator;
 198     typedef typename Type::codomain_combine codomain_combine;
 199     typedef on_absorbtion<Type,codomain_combine,absorbs_identities<Type>::value>
 200                                             on_identity_absorbtion;
 201
 202     if(!on_identity_absorbtion::is_absorbable(operand.second))
 203     {
 204         std::pair<iterator,bool> insertion = object.insert(operand);
 205         if(!insertion.second)
 206             insertion->second = operand.second;
 207     }
 208     return object;
 209 }
 210
 211
 212 //==============================================================================
 213 //= Intersection
 214 //==============================================================================
 215 template<class Type>
 216 inline typename enable_if<is_element_map<Type>, void>::type
 217 add_intersection(Type& section, const Type&               object,
 218                        const typename Type::element_type& operand)
 219 {
 220     object.add_intersection(section, operand);
 221 }
 222
 223 template<class Type>
 224 inline typename enable_if<is_element_map<Type>, void>::type
 225 add_intersection(Type& section, const Type& object, const Type& operand)
 226 {
 227     ICL_const_FORALL(typename Type, it_, operand)
 228         icl::add_intersection(section, object, *it_);
 229 }
 230
 231 //------------------------------------------------------------------------------
 232 //- T& op &=(T&, c P&) T:{m} P:{b m} fragment_types
 233 //------------------------------------------------------------------------------
 234
 235 template<class Type>
 236 inline typename enable_if<mpl::and_<is_element_map<Type>, is_total<Type> >, Type>::type&
 237 operator &=(Type& object, const typename Type::element_type& operand)
 238 {
 239     object.add(operand);
 240     return object;
 241 }
 242
 243 template<class Type>
 244 inline typename enable_if<mpl::and_<is_element_map<Type>, mpl::not_<is_total<Type> > >, Type>::type&
 245 operator &=(Type& object, const typename Type::element_type& operand)
 246 {
 247     Type section;
 248     icl::add_intersection(section, object, operand);
 249     object.swap(section);
 250     return object;
 251 }
 252
 253 template<class Type>
 254 inline typename enable_if<is_element_map<Type>, Type>::type
 255 operator & (Type object, const typename Type::element_type& operand)
 256 {
 257     return object &= operand;
 258 }
 259
 260 template<class Type>
 261 inline typename enable_if<is_element_map<Type>, Type>::type
 262 operator & (const typename Type::element_type& operand, Type object)
 263 {
 264     return object &= operand;
 265 }
 266
 267
 268 template<class Type>
 269 inline typename enable_if<mpl::and_<is_element_map<Type>, is_total<Type> >, Type>::type&
 270 operator &=(Type& object, const Type& operand)
 271 {
 272     object += operand;
 273     return object;
 274 }
 275
 276 template<class Type>
 277 inline typename enable_if<mpl::and_<is_element_map<Type>, mpl::not_<is_total<Type> > >, Type>::type&
 278 operator &=(Type& object, const Type& operand)
 279 {
 280     Type section;
 281     icl::add_intersection(section, object, operand);
 282     object.swap(section);
 283     return object;
 284 }
 285
 286 template<class Type>
 287 inline typename enable_if<is_element_map<Type>, Type>::type
 288 operator & (Type object, const typename Type::key_object_type& operand)
 289 {
 290     return object &= operand;
 291 }
 292
 293 template<class Type>
 294 inline typename enable_if<is_element_map<Type>, Type>::type
 295 operator & (const typename Type::key_object_type& operand, Type object)
 296 {
 297     return object &= operand;
 298 }
 299
 300 //==============================================================================
 301 //= Intersection<ElementMap> bool intersects(x,y)
 302 //==============================================================================
 303 template<class Type, class CoType>
 304 inline typename enable_if< mpl::and_< is_element_map<Type>
 305                                     , is_total<Type>      >
 306                          , bool>::type
 307 intersects(const Type&, const CoType&)
 308 {
 309     return true;
 310 }
 311
 312 template<class Type>
 313 inline typename enable_if< mpl::and_< is_element_map<Type>
 314                                     , mpl::not_<is_total<Type> > >
 315                          , bool>::type
 316 intersects(const Type& object, const typename Type::domain_type& operand)
 317 {
 318     return icl::contains(object, operand);
 319 }
 320
 321 template<class Type>
 322 inline typename enable_if< mpl::and_< is_element_map<Type>
 323                                     , mpl::not_<is_total<Type> > >
 324                          , bool>::type
 325 intersects(const Type& object, const typename Type::set_type& operand)
 326 {
 327     if(object.iterative_size() < operand.iterative_size())
 328         return Map::intersects(object, operand);
 329     else
 330         return Map::intersects(operand, object);
 331 }
 332
 333 template<class Type>
 334 inline typename enable_if< mpl::and_< is_element_map<Type>
 335                                     , mpl::not_<is_total<Type> > >
 336                          , bool>::type
 337 intersects(const Type& object, const typename Type::element_type& operand)
 338 {
 339     Type intersection;
 340     icl::add_intersection(intersection, object, operand);
 341     return !intersection.empty();
 342 }
 343
 344 template<class Type>
 345 inline typename enable_if< mpl::and_< is_element_map<Type>
 346                                     , mpl::not_<is_total<Type> > >
 347                          , bool>::type
 348 intersects(const Type& object, const Type& operand)
 349 {
 350     if(object.iterative_size() < operand.iterative_size())
 351         return Map::intersects(object, operand);
 352     else
 353         return Map::intersects(operand, object);
 354 }
 355
 356 //==============================================================================
 357 //= Symmetric difference
 358 //==============================================================================
 359 template<class Type>
 360 inline typename enable_if<is_element_map<Type>, Type>::type&
 361 flip(Type& object, const typename Type::element_type& operand)
 362 {
 363     return object.flip(operand);
 364 }
 365
 366 template<class Type, class CoType>
 367 inline typename enable_if< mpl::and_< is_element_map<Type>
 368                                     , is_total<Type>
 369                                     , absorbs_identities<Type> >
 370                          , Type>::type&
 371 operator ^= (Type& object, const CoType&)
 372 {
 373     icl::clear(object);
 374     return object;
 375 }
 376
 377 template<class Type>
 378 inline typename enable_if< mpl::and_< is_element_map<Type>
 379                                     , is_total<Type>
 380                                     , mpl::not_<absorbs_identities<Type> > >
 381                          , Type>::type&
 382 operator ^= (Type& object, const typename Type::element_type& operand)
 383 {
 384     return object.flip(operand);
 385 }
 386
 387 template<class Type>
 388 inline typename enable_if< mpl::and_< is_element_map<Type>
 389                                     , is_total<Type>
 390                                     , mpl::not_<absorbs_identities<Type> > >
 391                          , Type>::type&
 392 operator ^= (Type& object, const Type& operand)
 393 {
 394     ICL_const_FORALL(typename Type, it_, operand)
 395         icl::flip(object, *it_);
 396
 397     ICL_FORALL(typename Type, it2_, object)
 398         (*it2_).second = identity_element<typename Type::codomain_type>::value();
 399
 400     return object;
 401 }
 402
 403
 404 template<class Type>
 405 inline typename enable_if< mpl::and_< is_element_map<Type>
 406                                     , mpl::not_<is_total<Type> > >
 407                          , Type>::type&
 408 operator ^= (Type& object, const typename Type::element_type& operand)
 409 {
 410     return icl::flip(object, operand);
 411 }
 412
 413 template<class Type>
 414 inline typename enable_if< mpl::and_< is_element_map<Type>
 415                                     , mpl::not_<is_total<Type> > >
 416                          , Type>::type&
 417 operator ^= (Type& object, const Type& operand)
 418 {
 419     typedef typename Type::const_iterator const_iterator;
 420     const_iterator it_ = operand.begin();
 421     while(it_ != operand.end())
 422         icl::flip(object, *it_++);
 423
 424     return object;
 425 }
 426
 427
 428 //==============================================================================
 429 //= Set selection
 430 //==============================================================================
 431 template<class Type>
 432 inline typename enable_if<is_element_map<Type>,
 433                           typename Type::set_type>::type&
 434 domain(typename Type::set_type& domain_set, const Type& object)
 435 {
 436     typename Type::set_type::iterator prior_ = domain_set.end();
 437     typename Type::const_iterator it_ = object.begin();
 438     while(it_ != object.end())
 439         prior_ = domain_set.insert(prior_, (*it_++).first);
 440
 441     return domain_set;
 442 }
 443
 444 //==============================================================================
 445 //= Neutron absorbtion
 446 //==============================================================================
 447 template<class Type>
 448 inline typename enable_if<mpl::and_< is_element_map<Type>
 449                                    , absorbs_identities<Type> >, Type>::type&
 450 absorb_identities(Type& object)
 451 {
 452     typedef typename Type::element_type element_type;
 453     return icl::erase_if(content_is_identity_element<element_type>(), object);
 454 }
 455
 456 template<class Type>
 457 inline typename enable_if<mpl::and_< is_element_map<Type>
 458                                    , mpl::not_<absorbs_identities<Type> > >
 459                          , Type>::type&
 460 absorb_identities(Type&){}
 461
 462 //==============================================================================
 463 //= Streaming<ElementMap>
 464 //==============================================================================
 465 template<class CharType, class CharTraits, class Type>
 466 inline typename enable_if<is_element_map<Type>, std::basic_ostream<CharType, CharTraits> >::type&
 467 operator << (std::basic_ostream<CharType, CharTraits>& stream, const Type& object)
 468 {
 469     stream << "{";
 470     ICL_const_FORALL(typename Type, it, object)
 471         stream << "(" << it->first << "->" << it->second << ")";
 472
 473     return stream << "}";
 474 }
 475
 476
 477 }} // namespace boost icl
 478
 479 #endif
 480
 481