icl/concept/element_associator.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2010-2010: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_CONCEPT_ELEMENT_ASSOCIATOR_HPP_JOFA_100921
0009 #define BOOST_ICL_CONCEPT_ELEMENT_ASSOCIATOR_HPP_JOFA_100921
0010
0011 #include <boost/config.hpp>
0012 #include <boost/icl/type_traits/is_associative_element_container.hpp>
0013 #include <boost/icl/type_traits/is_key_container_of.hpp>
0014 #include <boost/icl/type_traits/is_combinable.hpp>
0015 #include <boost/icl/detail/subset_comparer.hpp>
0016 #include <boost/icl/concept/element_set.hpp>
0017 #include <boost/icl/concept/element_map.hpp>
0018
0019 namespace boost{ namespace icl
0020 {
0021
0022 //==============================================================================
0023 //= Size
0024 //==============================================================================
0025 template<class Type>
0026 typename enable_if<is_element_container<Type>, std::size_t>::type
0027 iterative_size(const Type& object)
0028 {
0029     return object.size();
0030 }
0031
0032 template<class Type>
0033 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
0034 size(const Type& object)
0035 {
0036     return icl::iterative_size(object);
0037 }
0038
0039 template<class Type>
0040 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
0041 cardinality(const Type& object)
0042 {
0043     return icl::iterative_size(object);
0044 }
0045
0046
0047 //==============================================================================
0048 //= Containedness<ElementSet|ElementMap>
0049 //==============================================================================
0050 //------------------------------------------------------------------------------
0051 //- bool within(c P&, c T&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
0052 //------------------------------------------------------------------------------
0053 /** Checks if a key is in the associative container */
0054 template<class Type>
0055 typename enable_if<is_associative_element_container<Type>, bool>::type
0056 within(const typename Type::key_type& key, const Type& super)
0057 {
0058     return !(super.find(key) == super.end());
0059 }
0060
0061 //------------------------------------------------------------------------------
0062 //- bool within(c P&, c T&) T:{s}|{m} P:{s'} fragment_types|key_types
0063 //------------------------------------------------------------------------------
0064 template<class SubT, class SuperT>
0065 typename enable_if<mpl::and_< is_associative_element_container<SuperT>
0066                             , is_key_container_of<SubT, SuperT> >,
0067                    bool>::type
0068 within(const SubT& sub, const SuperT& super)
0069 {
0070     if(icl::is_empty(sub))                return true;
0071     if(icl::is_empty(super))              return false;
0072     if(icl::size(super) < icl::size(sub)) return false;
0073
0074     typename SubT::const_iterator common_lwb_;
0075     typename SubT::const_iterator common_upb_;
0076     if(!Set::common_range(common_lwb_, common_upb_, sub, super))
0077         return false;
0078
0079     typename SubT::const_iterator sub_ = sub.begin();
0080     typename SuperT::const_iterator super_;
0081     while(sub_ != sub.end())
0082     {
0083         super_ = super.find(key_value<SubT>(sub_));
0084         if(super_ == super.end())
0085             return false;
0086         else if(!co_equal(sub_, super_, &sub, &super))
0087             return false;
0088
0089         ++sub_;
0090     }
0091     return true;
0092 }
0093
0094 //------------------------------------------------------------------------------
0095 //- bool contains(c T&, c P&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
0096 //------------------------------------------------------------------------------
0097 template<class Type>
0098 typename enable_if<is_associative_element_container<Type>, bool>::type
0099 contains(const Type& super, const typename Type::key_type& key)
0100 {
0101     return icl::within(key, super);
0102 }
0103
0104 //------------------------------------------------------------------------------
0105 //- bool contains(c T&, c P&) T:{s}|{m} P:{s'} fragment_types|key_types
0106 //------------------------------------------------------------------------------
0107 template<class SubT, class SuperT>
0108 typename enable_if<mpl::and_< is_associative_element_container<SuperT>
0109                             , is_key_container_of<SubT, SuperT> >,
0110                    bool>::type
0111 contains(const SuperT& super, const SubT& sub)
0112 {
0113     return icl::within(sub, super);
0114 }
0115
0116 //==============================================================================
0117 //= Equivalences and Orderings
0118 //==============================================================================
0119
0120 #ifdef BOOST_MSVC
0121 #pragma warning(push)
0122 #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'
0123 #endif                        // I do guarantee here that I am using the parameters correctly :)
0124
0125 /** Standard equality, which is lexicographical equality of the sets
0126     as sequences, that are given by their Compare order. */
0127 template<class Type>
0128 inline typename enable_if<is_associative_element_container<Type>, bool>::type
0129 operator == (const Type& left, const Type& right)
0130 {
0131     return left.size() == right.size()
0132         && std::equal(left.begin(), left.end(), right.begin());
0133 }
0134
0135 #ifdef BOOST_MSVC
0136 #pragma warning(pop)
0137 #endif
0138
0139 template<class Type>
0140 inline typename enable_if<is_associative_element_container<Type>, bool>::type
0141 is_element_equal(const Type& left, const Type& right)
0142 { return left == right; }
0143
0144
0145 /* Strict weak less ordering which is given by the Compare order */
0146 template<class Type>
0147 inline typename enable_if<is_associative_element_container<Type>, bool>::type
0148 operator < (const Type& left, const Type& right)
0149 {
0150     return std::lexicographical_compare(
0151         left.begin(), left.end(), right.begin(), right.end(),
0152         typename Type::element_compare()
0153         );
0154 }
0155
0156 template<class LeftT, class RightT>
0157 typename enable_if<is_concept_equivalent<is_element_container,LeftT, RightT>,
0158                    int>::type
0159 inclusion_compare(const LeftT& left, const RightT& right)
0160 {
0161     return Set::subset_compare(left, right,
0162                                left.begin(), left.end(),
0163                                right.begin(), right.end());
0164 }
0165
0166 //==============================================================================
0167 //= Addition
0168 //==============================================================================
0169 template <class Type>
0170 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0171 operator += (Type& object, const typename Type::value_type& operand)
0172 {
0173     return icl::add(object, operand);
0174 }
0175
0176 template <class Type>
0177 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0178 operator + (Type object, const typename Type::value_type& operand)
0179 {
0180     return object += operand;
0181 }
0182
0183 template <class Type>
0184 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0185 operator + (const typename Type::value_type& operand, Type object)
0186 {
0187     return object += operand;
0188 }
0189
0190 template <class Type>
0191 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0192 operator += (Type& object, const Type& operand)
0193 {
0194     if(&object == &operand)
0195         return object;
0196
0197     typename Type::iterator prior_ = object.end();
0198     ICL_const_FORALL(typename Type, it_, operand)
0199         prior_ = icl::add(object, prior_, *it_);
0200
0201     return object;
0202 }
0203
0204 template <class Type>
0205 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0206 operator + (Type object, const Type& operand)
0207 {
0208     return object += operand;
0209 }
0210
0211 //==============================================================================
0212 template <class Type>
0213 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0214 operator |= (Type& object, const typename Type::value_type& operand)
0215 {
0216     return icl::add(object, operand);
0217 }
0218
0219 template <class Type>
0220 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0221 operator | (Type object, const typename Type::value_type& operand)
0222 {
0223     return object += operand;
0224 }
0225
0226 template <class Type>
0227 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0228 operator | (const typename Type::value_type& operand, Type object)
0229 {
0230     return object += operand;
0231 }
0232
0233 template <class Type>
0234 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0235 operator |= (Type& object, const Type& operand)
0236 {
0237     return object += operand;
0238 }
0239
0240 template <class Type>
0241 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0242 operator | (Type object, const Type& operand)
0243 {
0244     return object += operand;
0245 }
0246
0247
0248 //==============================================================================
0249 //= Insertion
0250 //==============================================================================
0251 //------------------------------------------------------------------------------
0252 //- V insert(T&, c P&) T:{s}|{m} P:{e}|{b} fragment_type
0253 //------------------------------------------------------------------------------
0254 template<class Type>
0255 typename enable_if<is_associative_element_container<Type>,
0256                    std::pair<typename Type::iterator,bool> >::type
0257 insert(Type& object, const typename Type::value_type& operand)
0258 {
0259     return object.insert(operand);
0260 }
0261
0262 template<class Type>
0263 typename enable_if<is_associative_element_container<Type>,
0264                    typename Type::iterator>::type
0265 insert(Type& object, typename Type::iterator      prior,
0266                const typename Type::value_type& operand)
0267 {
0268     return object.insert(prior, operand);
0269 }
0270
0271 //------------------------------------------------------------------------------
0272 //- T insert(T&, c T&) T:{s m}  map fragment_type
0273 //------------------------------------------------------------------------------
0274 template<class Type>
0275 typename enable_if<is_associative_element_container<Type>, Type>::type&
0276 insert(Type& object, const Type& addend)
0277 {
0278     typedef typename Type::iterator iterator;
0279
0280     iterator prior_ = object.end();
0281     ICL_const_FORALL(typename Type, elem_, addend)
0282         icl::insert(object, prior_, *elem_);
0283
0284     return object;
0285 }
0286
0287
0288 //==============================================================================
0289 //= Erasure
0290 //==============================================================================
0291 template<class Type>
0292 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
0293 erase(Type& object, const typename Type::key_type& key_value)
0294 {
0295     typedef typename Type::size_type size_type;
0296     typename Type::iterator it_ = object.find(key_value);
0297     if(it_ != object.end())
0298     {
0299         object.erase(it_);
0300         return unit_element<size_type>::value();
0301     }
0302     return identity_element<size_type>::value();
0303 }
0304
0305 template<class Type>
0306 typename enable_if<is_associative_element_container<Type>, Type>::type&
0307 erase(Type& object, const Type& erasure)
0308 {
0309     ICL_const_FORALL(typename Type, elem_, erasure)
0310         icl::erase(object, *elem_);
0311
0312     return object;
0313 }
0314
0315
0316
0317 //==============================================================================
0318 //= Subtraction<ElementSet|ElementMap>
0319 //==============================================================================
0320 template <class Type>
0321 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0322 operator -= (Type& object, const typename Type::value_type& operand)
0323 {
0324     return icl::subtract(object, operand);
0325 }
0326
0327 template <class Type>
0328 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0329 operator - (Type object, const typename Type::value_type& operand)
0330 {
0331     return object -= operand;
0332 }
0333
0334 template <class Type>
0335 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0336 operator -= (Type& object, const Type& subtrahend)
0337 {
0338     ICL_const_FORALL(typename Type, it_, subtrahend)
0339         icl::subtract(object, *it_);
0340
0341     return object;
0342 }
0343
0344 template <class Type>
0345 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0346 operator - (Type object, const Type& subtrahend)
0347 {
0348     return object -= subtrahend;
0349 }
0350
0351
0352 //==============================================================================
0353 //= Intersection
0354 //==============================================================================
0355 //------------------------------------------------------------------------------
0356 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{e}{e} key_type
0357 //------------------------------------------------------------------------------
0358 template<class Type>
0359 inline typename enable_if<is_associative_element_container<Type>, void>::type
0360 add_intersection(Type& section, const Type&              object,
0361                        const typename Type::key_type& operand)
0362 {
0363     typedef typename Type::const_iterator const_iterator;
0364     const_iterator it_ = object.find(operand);
0365     if(it_ != object.end())
0366         icl::add(section, *it_);
0367 }
0368
0369 //------------------------------------------------------------------------------
0370 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{s}{s} set key_type
0371 //------------------------------------------------------------------------------
0372 template<class Type>
0373 inline typename enable_if<is_associative_element_container<Type>, void>::type
0374 add_intersection(Type& section, const Type& object,
0375                  const typename key_container_type_of<Type>::type& operand)
0376 {
0377     typedef typename key_container_type_of<Type>::type key_container_type;
0378     typedef typename key_container_type::const_iterator const_iterator;
0379     const_iterator common_lwb_, common_upb_;
0380     if(!Set::common_range(common_lwb_, common_upb_, operand, object))
0381         return;
0382
0383     const_iterator sec_ = common_lwb_;
0384     while(sec_ != common_upb_)
0385         add_intersection(section, object, *sec_++);
0386 }
0387
0388 //------------------------------------------------------------------------------
0389 //- Intersection<ElementMap|ElementSet>
0390 //------------------------------------------------------------------------------
0391 template<class Type>
0392 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0393 operator &= (Type& object, const typename Type::key_type& operand)
0394 {
0395     Type section;
0396     add_intersection(section, object, operand);
0397     object.swap(section);
0398     return object;
0399 }
0400
0401 template<class Type>
0402 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0403 operator & (Type object, const typename Type::key_type& operand)
0404 {
0405     return object &= operand;
0406 }
0407
0408 template<class Type>
0409 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0410 operator & (const typename Type::key_type& operand, Type object)
0411 {
0412     return object &= operand;
0413 }
0414
0415 template<class Type>
0416 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0417 operator &= (Type& object, const typename key_container_type_of<Type>::type& operand)
0418 {
0419     Type section;
0420     add_intersection(section, object, operand);
0421     object.swap(section);
0422     return object;
0423 }
0424
0425 template<class Type>
0426 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0427 operator & (Type object, const Type& operand)
0428 {
0429     return object &= operand;
0430 }
0431 //------------------------------------------------------------------------------
0432
0433 template<class Type, class CoType>
0434 inline typename enable_if<is_associative_element_container<Type>, bool>::type
0435 disjoint(const Type& left, const Type& right)
0436 {
0437     return !intersects(left, right);
0438 }
0439
0440 //==============================================================================
0441 //= Symmetric difference<ElementSet|ElementMap>
0442 //==============================================================================
0443 template<class Type>
0444 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0445 operator ^ (Type object, const typename Type::value_type& operand)
0446 {
0447     return icl::flip(object, operand);
0448 }
0449
0450 template<class Type>
0451 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0452 operator ^ (const typename Type::value_type& operand, Type object)
0453 {
0454     return icl::flip(object, operand);
0455 }
0456
0457 template<class Type>
0458 inline typename enable_if<is_associative_element_container<Type>, Type>::type
0459 operator ^ (Type object, const Type& operand)
0460 {
0461     return object ^= operand;
0462 }
0463
0464
0465 //==============================================================================
0466 //= Manipulation by predicates
0467 //==============================================================================
0468 template<class Type, class Predicate>
0469 typename enable_if<is_associative_element_container<Type>, Type>::type&
0470 erase_if(const Predicate& pred, Type& object)
0471 {
0472     typename Type::iterator it_ = object.begin();
0473     while(it_ != object.end())
0474         if(pred(*it_))
0475             icl::erase(object, it_++);
0476         else ++it_;
0477     return object;
0478 }
0479
0480 template<class Type, class Predicate>
0481 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0482 add_if(const Predicate& pred, Type& object, const Type& src)
0483 {
0484     typename Type::const_iterator it_ = src.begin();
0485     while(it_ != src.end())
0486         if(pred(*it_))
0487             icl::add(object, *it_++);
0488
0489     return object;
0490 }
0491
0492 template<class Type, class Predicate>
0493 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
0494 assign_if(const Predicate& pred, Type& object, const Type& src)
0495 {
0496     icl::clear(object);
0497     return add_if(object, src, pred);
0498 }
0499
0500
0501
0502 }} // namespace boost icl
0503
0504 #endif