git.sesse.net Git - casparcg/blob - dependencies/boost/boost/icl/concept/element_associator.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_ASSOCIATOR_HPP_JOFA_100921
   9 #define BOOST_ICL_CONCEPT_ELEMENT_ASSOCIATOR_HPP_JOFA_100921
  10
  11 #include <boost/config.hpp>
  12 #include <boost/icl/type_traits/is_associative_element_container.hpp>
  13 #include <boost/icl/type_traits/is_key_container_of.hpp>
  14 #include <boost/icl/type_traits/is_combinable.hpp>
  15 #include <boost/icl/detail/subset_comparer.hpp>
  16 #include <boost/icl/concept/element_set.hpp>
  17 #include <boost/icl/concept/element_map.hpp>
  18
  19 namespace boost{ namespace icl
  20 {
  21
  22 //==============================================================================
  23 //= Size
  24 //==============================================================================
  25 template<class Type>
  26 typename enable_if<is_element_container<Type>, std::size_t>::type
  27 iterative_size(const Type& object)
  28 {
  29     return object.size();
  30 }
  31
  32 template<class Type>
  33 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
  34 size(const Type& object)
  35 {
  36     return icl::iterative_size(object);
  37 }
  38
  39 template<class Type>
  40 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
  41 cardinality(const Type& object)
  42 {
  43     return icl::iterative_size(object);
  44 }
  45
  46
  47 //==============================================================================
  48 //= Containedness<ElementSet|ElementMap>
  49 //==============================================================================
  50 //------------------------------------------------------------------------------
  51 //- bool within(c P&, c T&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
  52 //------------------------------------------------------------------------------
  53 /** Checks if a key is in the associative container */
  54 template<class Type>
  55 typename enable_if<is_associative_element_container<Type>, bool>::type
  56 within(const typename Type::key_type& key, const Type& super)
  57 {
  58     return !(super.find(key) == super.end());
  59 }
  60
  61 //------------------------------------------------------------------------------
  62 //- bool within(c P&, c T&) T:{s}|{m} P:{s'} fragment_types|key_types
  63 //------------------------------------------------------------------------------
  64 template<class SubT, class SuperT>
  65 typename enable_if<mpl::and_< is_associative_element_container<SuperT>
  66                             , is_key_container_of<SubT, SuperT> >,
  67                    bool>::type
  68 within(const SubT& sub, const SuperT& super)
  69 {
  70     if(icl::is_empty(sub))                return true;
  71     if(icl::is_empty(super))              return false;
  72     if(icl::size(super) < icl::size(sub)) return false;
  73
  74     typename SubT::const_iterator common_lwb_;
  75     typename SubT::const_iterator common_upb_;
  76     if(!Set::common_range(common_lwb_, common_upb_, sub, super))
  77         return false;
  78
  79     typename SubT::const_iterator sub_ = sub.begin();
  80     typename SuperT::const_iterator super_;
  81     while(sub_ != sub.end())
  82     {
  83         super_ = super.find(key_value<SubT>(sub_));
  84         if(super_ == super.end())
  85             return false;
  86         else if(!co_equal(sub_, super_, &sub, &super))
  87             return false;
  88
  89         ++sub_;
  90     }
  91     return true;
  92 }
  93
  94 //------------------------------------------------------------------------------
  95 //- bool contains(c T&, c P&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
  96 //------------------------------------------------------------------------------
  97 template<class Type>
  98 typename enable_if<is_associative_element_container<Type>, bool>::type
  99 contains(const Type& super, const typename Type::key_type& key)
 100 {
 101     return icl::within(key, super);
 102 }
 103
 104 //------------------------------------------------------------------------------
 105 //- bool contains(c T&, c P&) T:{s}|{m} P:{s'} fragment_types|key_types
 106 //------------------------------------------------------------------------------
 107 template<class SubT, class SuperT>
 108 typename enable_if<mpl::and_< is_associative_element_container<SuperT>
 109                             , is_key_container_of<SubT, SuperT> >,
 110                    bool>::type
 111 contains(const SuperT& super, const SubT& sub)
 112 {
 113     return icl::within(sub, super);
 114 }
 115
 116 //==============================================================================
 117 //= Equivalences and Orderings
 118 //==============================================================================
 119
 120 #ifdef BOOST_MSVC
 121 #pragma warning(push)
 122 #pragma warning(disable:4996) //'std::equal': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'
 123 #endif                        // I do guarantee here that I am using the parameters correctly :)
 124
 125 /** Standard equality, which is lexicographical equality of the sets
 126     as sequences, that are given by their Compare order. */
 127 template<class Type>
 128 inline typename enable_if<is_associative_element_container<Type>, bool>::type
 129 operator == (const Type& left, const Type& right)
 130 {
 131     return left.size() == right.size()
 132         && std::equal(left.begin(), left.end(), right.begin());
 133 }
 134
 135 #ifdef BOOST_MSVC
 136 #pragma warning(pop)
 137 #endif
 138
 139 template<class Type>
 140 inline typename enable_if<is_associative_element_container<Type>, bool>::type
 141 is_element_equal(const Type& left, const Type& right)
 142 { return left == right; }
 143
 144
 145 /* Strict weak less ordering which is given by the Compare order */
 146 template<class Type>
 147 inline typename enable_if<is_associative_element_container<Type>, bool>::type
 148 operator < (const Type& left, const Type& right)
 149 {
 150     return std::lexicographical_compare(
 151         left.begin(), left.end(), right.begin(), right.end(),
 152         typename Type::element_compare()
 153         );
 154 }
 155
 156 template<class LeftT, class RightT>
 157 typename enable_if<is_concept_equivalent<is_element_container,LeftT, RightT>,
 158                    int>::type
 159 inclusion_compare(const LeftT& left, const RightT& right)
 160 {
 161     return Set::subset_compare(left, right,
 162                                left.begin(), left.end(),
 163                                right.begin(), right.end());
 164 }
 165
 166 //==============================================================================
 167 //= Addition
 168 //==============================================================================
 169 template <class Type>
 170 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 171 operator += (Type& object, const typename Type::value_type& operand)
 172 {
 173     return icl::add(object, operand);
 174 }
 175
 176 template <class Type>
 177 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 178 operator + (Type object, const typename Type::value_type& operand)
 179 {
 180     return object += operand;
 181 }
 182
 183 template <class Type>
 184 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 185 operator + (const typename Type::value_type& operand, Type object)
 186 {
 187     return object += operand;
 188 }
 189
 190 template <class Type>
 191 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 192 operator += (Type& object, const Type& operand)
 193 {
 194     if(&object == &operand)
 195         return object;
 196
 197     typename Type::iterator prior_ = object.end();
 198     ICL_const_FORALL(typename Type, it_, operand)
 199         prior_ = icl::add(object, prior_, *it_);
 200
 201     return object;
 202 }
 203
 204 template <class Type>
 205 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 206 operator + (Type object, const Type& operand)
 207 {
 208     return object += operand;
 209 }
 210
 211 //==============================================================================
 212 template <class Type>
 213 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 214 operator |= (Type& object, const typename Type::value_type& operand)
 215 {
 216     return icl::add(object, operand);
 217 }
 218
 219 template <class Type>
 220 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 221 operator | (Type object, const typename Type::value_type& operand)
 222 {
 223     return object += operand;
 224 }
 225
 226 template <class Type>
 227 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 228 operator | (const typename Type::value_type& operand, Type object)
 229 {
 230     return object += operand;
 231 }
 232
 233 template <class Type>
 234 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 235 operator |= (Type& object, const Type& operand)
 236 {
 237     return object += operand;
 238 }
 239
 240 template <class Type>
 241 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 242 operator | (Type object, const Type& operand)
 243 {
 244     return object += operand;
 245 }
 246
 247
 248 //==============================================================================
 249 //= Insertion
 250 //==============================================================================
 251 //------------------------------------------------------------------------------
 252 //- V insert(T&, c P&) T:{s}|{m} P:{e}|{b} fragment_type
 253 //------------------------------------------------------------------------------
 254 template<class Type>
 255 typename enable_if<is_associative_element_container<Type>,
 256                    std::pair<typename Type::iterator,bool> >::type
 257 insert(Type& object, const typename Type::value_type& operand)
 258 {
 259     return object.insert(operand);
 260 }
 261
 262 template<class Type>
 263 typename enable_if<is_associative_element_container<Type>,
 264                    typename Type::iterator>::type
 265 insert(Type& object, typename Type::iterator      prior,
 266                const typename Type::value_type& operand)
 267 {
 268     return object.insert(prior, operand);
 269 }
 270
 271 //------------------------------------------------------------------------------
 272 //- T insert(T&, c T&) T:{s m}  map fragment_type
 273 //------------------------------------------------------------------------------
 274 template<class Type>
 275 typename enable_if<is_associative_element_container<Type>, Type>::type&
 276 insert(Type& object, const Type& addend)
 277 {
 278     typedef typename Type::iterator iterator;
 279
 280     iterator prior_ = object.end();
 281     ICL_const_FORALL(typename Type, elem_, addend)
 282         icl::insert(object, prior_, *elem_);
 283
 284     return object;
 285 }
 286
 287
 288 //==============================================================================
 289 //= Erasure
 290 //==============================================================================
 291 template<class Type>
 292 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
 293 erase(Type& object, const typename Type::key_type& key_value)
 294 {
 295     typedef typename Type::size_type size_type;
 296     typename Type::iterator it_ = object.find(key_value);
 297     if(it_ != object.end())
 298     {
 299         object.erase(it_);
 300         return unit_element<size_type>::value();
 301     }
 302     return identity_element<size_type>::value();
 303 }
 304
 305 template<class Type>
 306 typename enable_if<is_associative_element_container<Type>, Type>::type&
 307 erase(Type& object, const Type& erasure)
 308 {
 309     ICL_const_FORALL(typename Type, elem_, erasure)
 310         icl::erase(object, *elem_);
 311
 312     return object;
 313 }
 314
 315
 316
 317 //==============================================================================
 318 //= Subtraction<ElementSet|ElementMap>
 319 //==============================================================================
 320 template <class Type>
 321 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 322 operator -= (Type& object, const typename Type::value_type& operand)
 323 {
 324     return icl::subtract(object, operand);
 325 }
 326
 327 template <class Type>
 328 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 329 operator - (Type object, const typename Type::value_type& operand)
 330 {
 331     return object -= operand;
 332 }
 333
 334 template <class Type>
 335 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 336 operator -= (Type& object, const Type& subtrahend)
 337 {
 338     ICL_const_FORALL(typename Type, it_, subtrahend)
 339         icl::subtract(object, *it_);
 340
 341     return object;
 342 }
 343
 344 template <class Type>
 345 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 346 operator - (Type object, const Type& subtrahend)
 347 {
 348     return object -= subtrahend;
 349 }
 350
 351
 352 //==============================================================================
 353 //= Intersection
 354 //==============================================================================
 355 //------------------------------------------------------------------------------
 356 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{e}{e} key_type
 357 //------------------------------------------------------------------------------
 358 template<class Type>
 359 inline typename enable_if<is_associative_element_container<Type>, void>::type
 360 add_intersection(Type& section, const Type&              object,
 361                        const typename Type::key_type& operand)
 362 {
 363     typedef typename Type::const_iterator const_iterator;
 364     const_iterator it_ = object.find(operand);
 365     if(it_ != object.end())
 366         icl::add(section, *it_);
 367 }
 368
 369 //------------------------------------------------------------------------------
 370 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{s}{s} set key_type
 371 //------------------------------------------------------------------------------
 372 template<class Type>
 373 inline typename enable_if<is_associative_element_container<Type>, void>::type
 374 add_intersection(Type& section, const Type& object,
 375                  const typename key_container_type_of<Type>::type& operand)
 376 {
 377     typedef typename key_container_type_of<Type>::type key_container_type;
 378     typedef typename key_container_type::const_iterator const_iterator;
 379     const_iterator common_lwb_, common_upb_;
 380     if(!Set::common_range(common_lwb_, common_upb_, operand, object))
 381         return;
 382
 383     const_iterator sec_ = common_lwb_;
 384     while(sec_ != common_upb_)
 385         add_intersection(section, object, *sec_++);
 386 }
 387
 388 //------------------------------------------------------------------------------
 389 //- Intersection<ElementMap|ElementSet>
 390 //------------------------------------------------------------------------------
 391 template<class Type>
 392 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 393 operator &= (Type& object, const typename Type::key_type& operand)
 394 {
 395     Type section;
 396     add_intersection(section, object, operand);
 397     object.swap(section);
 398     return object;
 399 }
 400
 401 template<class Type>
 402 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 403 operator & (Type object, const typename Type::key_type& operand)
 404 {
 405     return object &= operand;
 406 }
 407
 408 template<class Type>
 409 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 410 operator & (const typename Type::key_type& operand, Type object)
 411 {
 412     return object &= operand;
 413 }
 414
 415 template<class Type>
 416 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 417 operator &= (Type& object, const typename key_container_type_of<Type>::type& operand)
 418 {
 419     Type section;
 420     add_intersection(section, object, operand);
 421     object.swap(section);
 422     return object;
 423 }
 424
 425 template<class Type>
 426 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 427 operator & (Type object, const Type& operand)
 428 {
 429     return object &= operand;
 430 }
 431 //------------------------------------------------------------------------------
 432
 433 template<class Type, class CoType>
 434 inline typename enable_if<is_associative_element_container<Type>, bool>::type
 435 disjoint(const Type& left, const Type& right)
 436 {
 437     return !intersects(left, right);
 438 }
 439
 440 //==============================================================================
 441 //= Symmetric difference<ElementSet|ElementMap>
 442 //==============================================================================
 443 template<class Type>
 444 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 445 operator ^ (Type object, const typename Type::value_type& operand)
 446 {
 447     return icl::flip(object, operand);
 448 }
 449
 450 template<class Type>
 451 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 452 operator ^ (const typename Type::value_type& operand, Type object)
 453 {
 454     return icl::flip(object, operand);
 455 }
 456
 457 template<class Type>
 458 inline typename enable_if<is_associative_element_container<Type>, Type>::type
 459 operator ^ (Type object, const Type& operand)
 460 {
 461     return object ^= operand;
 462 }
 463
 464
 465 //==============================================================================
 466 //= Manipulation by predicates
 467 //==============================================================================
 468 template<class Type, class Predicate>
 469 typename enable_if<is_associative_element_container<Type>, Type>::type&
 470 erase_if(const Predicate& pred, Type& object)
 471 {
 472     typename Type::iterator it_ = object.begin();
 473     while(it_ != object.end())
 474         if(pred(*it_))
 475             icl::erase(object, it_++);
 476         else ++it_;
 477     return object;
 478 }
 479
 480 template<class Type, class Predicate>
 481 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 482 add_if(const Predicate& pred, Type& object, const Type& src)
 483 {
 484     typename Type::const_iterator it_ = src.begin();
 485     while(it_ != src.end())
 486         if(pred(*it_))
 487             icl::add(object, *it_++);
 488
 489     return object;
 490 }
 491
 492 template<class Type, class Predicate>
 493 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
 494 assign_if(const Predicate& pred, Type& object, const Type& src)
 495 {
 496     icl::clear(object);
 497     return add_if(object, src, pred);
 498 }
 499
 500
 501
 502 }} // namespace boost icl
 503
 504 #endif
 505
 506