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
iterative_size(const Type & object)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
size(const Type & object)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
cardinality(const Type & object)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
within(const typename Type::key_type & key,const Type & super)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
within(const SubT & sub,const SuperT & super)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
contains(const Type & super,const typename Type::key_type & key)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
contains(const SuperT & super,const SubT & sub)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
operator ==(const Type & left,const Type & right)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
is_element_equal(const Type & left,const Type & right)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
operator <(const Type & left,const Type & right)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
inclusion_compare(const LeftT & left,const RightT & right)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&
operator +=(Type & object,const typename Type::value_type & operand)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
operator +(Type object,const typename Type::value_type & operand)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
operator +(const typename Type::value_type & operand,Type object)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&
operator +=(Type & object,const Type & operand)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
operator +(Type object,const Type & operand)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&
operator |=(Type & object,const typename Type::value_type & operand)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
operator |(Type object,const typename Type::value_type & operand)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
operator |(const typename Type::value_type & operand,Type object)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&
operator |=(Type & object,const Type & operand)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
operator |(Type object,const Type & operand)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
insert(Type & object,const typename Type::value_type & operand)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
insert(Type & object,typename Type::iterator prior,const typename Type::value_type & operand)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&
insert(Type & object,const Type & addend)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
erase(Type & object,const typename Type::key_type & key_value)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&
erase(Type & object,const Type & erasure)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&
operator -=(Type & object,const typename Type::value_type & operand)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
operator -(Type object,const typename Type::value_type & operand)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&
operator -=(Type & object,const Type & subtrahend)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
operator -(Type object,const Type & subtrahend)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
add_intersection(Type & section,const Type & object,const typename Type::key_type & operand)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
add_intersection(Type & section,const Type & object,const typename key_container_type_of<Type>::type & operand)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&
operator &=(Type & object,const typename Type::key_type & operand)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
operator &(Type object,const typename Type::key_type & operand)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
operator &(const typename Type::key_type & operand,Type object)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&
operator &=(Type & object,const typename key_container_type_of<Type>::type & operand)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
operator &(Type object,const Type & operand)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
disjoint(const Type & left,const Type & right)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
operator ^(Type object,const typename Type::value_type & operand)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
operator ^(const typename Type::value_type & operand,Type object)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
operator ^(Type object,const Type & operand)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&
erase_if(const Predicate & pred,Type & object)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&
add_if(const Predicate & pred,Type & object,const Type & src)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&
assign_if(const Predicate & pred,Type & object,const Type & src)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