]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*-----------------------------------------------------------------------------+ |
2 | Copyright (c) 2007-2010: Joachim Faulhaber | |
3 | +------------------------------------------------------------------------------+ | |
4 | Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin | |
5 | +------------------------------------------------------------------------------+ | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENCE.txt or copy at | |
8 | http://www.boost.org/LICENSE_1_0.txt) | |
9 | +-----------------------------------------------------------------------------*/ | |
10 | #ifndef BOOST_ICL_SET_ALGO_HPP_JOFA_990225 | |
11 | #define BOOST_ICL_SET_ALGO_HPP_JOFA_990225 | |
12 | ||
13 | #include <boost/type_traits/remove_const.hpp> | |
14 | #include <boost/icl/detail/notate.hpp> | |
15 | #include <boost/icl/concept/container.hpp> | |
16 | #include <boost/icl/concept/set_value.hpp> | |
17 | #include <boost/icl/concept/map_value.hpp> | |
18 | ||
19 | ||
20 | namespace boost{namespace icl | |
21 | { | |
22 | ||
23 | namespace Set | |
24 | { | |
25 | ||
26 | template<class ObjectT, class ConstObjectT, class IteratorT> | |
27 | bool common_range(IteratorT& lwb, IteratorT& upb, ObjectT& x1, const ConstObjectT& x2) | |
28 | { | |
29 | // lwb and upb are iterators of x1 marking the lower and upper bound of | |
30 | // the common range of x1 and x2. | |
31 | typedef typename ConstObjectT::const_iterator ConstObject_iterator; | |
32 | // ObjectT may be const or non const. | |
33 | typedef typename remove_const<ObjectT>::type PureObjectT; | |
34 | ||
35 | lwb = x1.end(); | |
36 | upb = x1.end(); | |
37 | ||
38 | if(icl::is_empty(x1) || icl::is_empty(x2)) | |
39 | return false; | |
40 | ||
41 | IteratorT x1_fst_ = x1.begin(); | |
42 | IteratorT x1_lst_ = x1.end(); x1_lst_--; | |
43 | ||
44 | ConstObject_iterator x2_fst_ = x2.begin(); | |
45 | ConstObject_iterator x2_lst_ = x2.end(); x2_lst_--; | |
46 | ||
47 | typename ObjectT::key_compare key_less; | |
48 | if(key_less(icl::key_value< PureObjectT>(x1_lst_), | |
49 | icl::key_value<ConstObjectT>(x2_fst_))) // {x1} {x2} | |
50 | return false; | |
51 | if(key_less(icl::key_value<ConstObjectT>(x2_lst_), | |
52 | icl::key_value< PureObjectT>(x1_fst_))) // {x2} {x1} | |
53 | return false; | |
54 | ||
55 | // We do have a common range | |
56 | lwb = x1.lower_bound(icl::key_value<ConstObjectT>(x2_fst_)); | |
57 | upb = x1.upper_bound(icl::key_value<ConstObjectT>(x2_lst_)); | |
58 | ||
59 | return true; | |
60 | } | |
61 | ||
62 | ||
63 | /** Function template <tt>contained_in</tt> implements the subset relation. | |
64 | <tt>contained_in(sub, super)</tt> is true if <tt>sub</tt> is contained in <tt>super</tt> */ | |
65 | template<class SetType> | |
66 | inline bool within(const SetType& sub, const SetType& super) | |
67 | { | |
68 | if(&super == &sub) return true; | |
69 | if(icl::is_empty(sub)) return true; | |
70 | if(icl::is_empty(super)) return false; | |
71 | ||
72 | typename SetType::const_iterator common_lwb_, common_upb_; | |
73 | if(!common_range(common_lwb_, common_upb_, sub, super)) | |
74 | return false; | |
75 | ||
76 | typename SetType::const_iterator sub_ = common_lwb_, super_; | |
77 | while(sub_ != common_upb_) | |
78 | { | |
79 | super_ = super.find(*sub_++); | |
80 | if(super_ == super.end()) | |
81 | return false; | |
82 | } | |
83 | return true; | |
84 | } | |
85 | ||
86 | template<class SetType> | |
87 | bool intersects(const SetType& left, const SetType& right) | |
88 | { | |
89 | typename SetType::const_iterator common_lwb_right_, common_upb_right_; | |
90 | if(!common_range(common_lwb_right_, common_upb_right_, right, left)) | |
91 | return false; | |
92 | ||
93 | typename SetType::const_iterator right_ = common_lwb_right_, found_; | |
94 | while(right_ != common_upb_right_) | |
95 | { | |
96 | found_ = left.find(*right_++); | |
97 | if(found_ != left.end()) | |
98 | return true; // found a common element | |
99 | } | |
100 | // found no common element | |
101 | return false; | |
102 | } | |
103 | ||
104 | ||
105 | #ifdef BOOST_MSVC | |
106 | #pragma warning(push) | |
107 | #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' | |
108 | #endif // I do guarantee here that I am using the parameters correctly :) | |
109 | ||
110 | /** Function template <tt>lexicographical_equal</tt> implements | |
111 | lexicographical equality. */ | |
112 | template<class SetType> | |
113 | inline bool lexicographical_equal(const SetType& left, const SetType& right) | |
114 | { | |
115 | if(&left == &right) | |
116 | return true; | |
117 | else return left.iterative_size() == right.iterative_size() | |
118 | && std::equal(left.begin(), left.end(), right.begin()); | |
119 | } | |
120 | ||
121 | #ifdef BOOST_MSVC | |
122 | #pragma warning(pop) | |
123 | #endif | |
124 | ||
125 | ||
126 | } // namespace Set | |
127 | ||
128 | }} // namespace icl boost | |
129 | ||
130 | #endif | |
131 |