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