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
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>
19 namespace boost{ namespace icl
22 //==============================================================================
24 //==============================================================================
26 typename enable_if<is_element_container<Type>, std::size_t>::type
27 iterative_size(const Type& object)
33 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
34 size(const Type& object)
36 return icl::iterative_size(object);
40 typename enable_if<is_associative_element_container<Type>, typename Type::size_type>::type
41 cardinality(const Type& object)
43 return icl::iterative_size(object);
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 */
55 typename enable_if<is_associative_element_container<Type>, bool>::type
56 within(const typename Type::key_type& key, const Type& super)
58 return !(super.find(key) == super.end());
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> >,
68 within(const SubT& sub, const SuperT& super)
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;
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))
79 typename SubT::const_iterator sub_ = sub.begin();
80 typename SuperT::const_iterator super_;
81 while(sub_ != sub.end())
83 super_ = super.find(key_value<SubT>(sub_));
84 if(super_ == super.end())
86 else if(!co_equal(sub_, super_, &sub, &super))
94 //------------------------------------------------------------------------------
95 //- bool contains(c T&, c P&) T:{s}|{m} P:{e}|{i} fragment_types|key_types
96 //------------------------------------------------------------------------------
98 typename enable_if<is_associative_element_container<Type>, bool>::type
99 contains(const Type& super, const typename Type::key_type& key)
101 return icl::within(key, super);
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> >,
111 contains(const SuperT& super, const SubT& sub)
113 return icl::within(sub, super);
116 //==============================================================================
117 //= Equivalences and Orderings
118 //==============================================================================
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 :)
125 /** Standard equality, which is lexicographical equality of the sets
126 as sequences, that are given by their Compare order. */
128 inline typename enable_if<is_associative_element_container<Type>, bool>::type
129 operator == (const Type& left, const Type& right)
131 return left.size() == right.size()
132 && std::equal(left.begin(), left.end(), right.begin());
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; }
145 /* Strict weak less ordering which is given by the Compare order */
147 inline typename enable_if<is_associative_element_container<Type>, bool>::type
148 operator < (const Type& left, const Type& right)
150 return std::lexicographical_compare(
151 left.begin(), left.end(), right.begin(), right.end(),
152 typename Type::element_compare()
156 template<class LeftT, class RightT>
157 typename enable_if<is_concept_equivalent<is_element_container,LeftT, RightT>,
159 inclusion_compare(const LeftT& left, const RightT& right)
161 return Set::subset_compare(left, right,
162 left.begin(), left.end(),
163 right.begin(), right.end());
166 //==============================================================================
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)
173 return icl::add(object, operand);
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)
180 return object += operand;
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)
187 return object += operand;
190 template <class Type>
191 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
192 operator += (Type& object, const Type& operand)
194 if(&object == &operand)
197 typename Type::iterator prior_ = object.end();
198 ICL_const_FORALL(typename Type, it_, operand)
199 prior_ = icl::add(object, prior_, *it_);
204 template <class Type>
205 inline typename enable_if<is_associative_element_container<Type>, Type>::type
206 operator + (Type object, const Type& operand)
208 return object += operand;
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)
216 return icl::add(object, operand);
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)
223 return object += operand;
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)
230 return object += operand;
233 template <class Type>
234 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
235 operator |= (Type& object, const Type& operand)
237 return object += operand;
240 template <class Type>
241 inline typename enable_if<is_associative_element_container<Type>, Type>::type
242 operator | (Type object, const Type& operand)
244 return object += operand;
248 //==============================================================================
250 //==============================================================================
251 //------------------------------------------------------------------------------
252 //- V insert(T&, c P&) T:{s}|{m} P:{e}|{b} fragment_type
253 //------------------------------------------------------------------------------
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)
259 return object.insert(operand);
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)
268 return object.insert(prior, operand);
271 //------------------------------------------------------------------------------
272 //- T insert(T&, c T&) T:{s m} map fragment_type
273 //------------------------------------------------------------------------------
275 typename enable_if<is_associative_element_container<Type>, Type>::type&
276 insert(Type& object, const Type& addend)
278 typedef typename Type::iterator iterator;
280 iterator prior_ = object.end();
281 ICL_const_FORALL(typename Type, elem_, addend)
282 icl::insert(object, prior_, *elem_);
288 //==============================================================================
290 //==============================================================================
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)
295 typedef typename Type::size_type size_type;
296 typename Type::iterator it_ = object.find(key_value);
297 if(it_ != object.end())
300 return unit_element<size_type>::value();
302 return identity_element<size_type>::value();
306 typename enable_if<is_associative_element_container<Type>, Type>::type&
307 erase(Type& object, const Type& erasure)
309 ICL_const_FORALL(typename Type, elem_, erasure)
310 icl::erase(object, *elem_);
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)
324 return icl::subtract(object, operand);
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)
331 return object -= operand;
334 template <class Type>
335 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
336 operator -= (Type& object, const Type& subtrahend)
338 ICL_const_FORALL(typename Type, it_, subtrahend)
339 icl::subtract(object, *it_);
344 template <class Type>
345 inline typename enable_if<is_associative_element_container<Type>, Type>::type
346 operator - (Type object, const Type& subtrahend)
348 return object -= subtrahend;
352 //==============================================================================
354 //==============================================================================
355 //------------------------------------------------------------------------------
356 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{e}{e} key_type
357 //------------------------------------------------------------------------------
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)
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_);
369 //------------------------------------------------------------------------------
370 //- void add_intersection(T&, c T&, c P&) T:{s}{m} P:{s}{s} set key_type
371 //------------------------------------------------------------------------------
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)
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))
383 const_iterator sec_ = common_lwb_;
384 while(sec_ != common_upb_)
385 add_intersection(section, object, *sec_++);
388 //------------------------------------------------------------------------------
389 //- Intersection<ElementMap|ElementSet>
390 //------------------------------------------------------------------------------
392 inline typename enable_if<is_associative_element_container<Type>, Type>::type&
393 operator &= (Type& object, const typename Type::key_type& operand)
396 add_intersection(section, object, operand);
397 object.swap(section);
402 inline typename enable_if<is_associative_element_container<Type>, Type>::type
403 operator & (Type object, const typename Type::key_type& operand)
405 return object &= operand;
409 inline typename enable_if<is_associative_element_container<Type>, Type>::type
410 operator & (const typename Type::key_type& operand, Type object)
412 return object &= operand;
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)
420 add_intersection(section, object, operand);
421 object.swap(section);
426 inline typename enable_if<is_associative_element_container<Type>, Type>::type
427 operator & (Type object, const Type& operand)
429 return object &= operand;
431 //------------------------------------------------------------------------------
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)
437 return !intersects(left, right);
440 //==============================================================================
441 //= Symmetric difference<ElementSet|ElementMap>
442 //==============================================================================
444 inline typename enable_if<is_associative_element_container<Type>, Type>::type
445 operator ^ (Type object, const typename Type::value_type& operand)
447 return icl::flip(object, operand);
451 inline typename enable_if<is_associative_element_container<Type>, Type>::type
452 operator ^ (const typename Type::value_type& operand, Type object)
454 return icl::flip(object, operand);
458 inline typename enable_if<is_associative_element_container<Type>, Type>::type
459 operator ^ (Type object, const Type& operand)
461 return object ^= operand;
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)
472 typename Type::iterator it_ = object.begin();
473 while(it_ != object.end())
475 icl::erase(object, it_++);
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)
484 typename Type::const_iterator it_ = src.begin();
485 while(it_ != src.end())
487 icl::add(object, *it_++);
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)
497 return add_if(object, src, pred);
502 }} // namespace boost icl