icl/detail/set_algo.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2007-2010: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004 Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
0005 +------------------------------------------------------------------------------+
0006    Distributed under the Boost Software License, Version 1.0.
0007       (See accompanying file LICENCE.txt or copy at
0008            http://www.boost.org/LICENSE_1_0.txt)
0009 +-----------------------------------------------------------------------------*/
0010 #ifndef BOOST_ICL_SET_ALGO_HPP_JOFA_990225
0011 #define BOOST_ICL_SET_ALGO_HPP_JOFA_990225
0012
0013 #include <boost/type_traits/remove_const.hpp>
0014 #include <boost/icl/detail/notate.hpp>
0015 #include <boost/icl/concept/container.hpp>
0016 #include <boost/icl/concept/set_value.hpp>
0017 #include <boost/icl/concept/map_value.hpp>
0018
0019
0020 namespace boost{namespace icl
0021 {
0022
0023 namespace Set
0024 {
0025
0026 template<class ObjectT, class ConstObjectT, class IteratorT>
0027 bool common_range(IteratorT& lwb, IteratorT& upb, ObjectT& x1, const ConstObjectT& x2)
0028 {
0029     // lwb and upb are iterators of x1 marking the lower and upper bound of
0030     // the common range of x1 and x2.
0031     typedef typename ConstObjectT::const_iterator ConstObject_iterator;
0032     // ObjectT may be const or non const.
0033     typedef typename remove_const<ObjectT>::type  PureObjectT;
0034
0035     lwb = x1.end();
0036     upb = x1.end();
0037
0038     if(icl::is_empty(x1) || icl::is_empty(x2))
0039         return false;
0040
0041     IteratorT x1_fst_ = x1.begin();
0042     IteratorT x1_lst_ = x1.end(); x1_lst_--;
0043
0044     ConstObject_iterator x2_fst_ = x2.begin();
0045     ConstObject_iterator x2_lst_ = x2.end(); x2_lst_--;
0046
0047     typename ObjectT::key_compare key_less;
0048     if(key_less(icl::key_value< PureObjectT>(x1_lst_),
0049                 icl::key_value<ConstObjectT>(x2_fst_))) // {x1}   {x2}
0050         return false;
0051     if(key_less(icl::key_value<ConstObjectT>(x2_lst_),
0052                 icl::key_value< PureObjectT>(x1_fst_))) // {x2}   {x1}
0053         return false;
0054
0055     // We do have a common range
0056     lwb = x1.lower_bound(icl::key_value<ConstObjectT>(x2_fst_));
0057     upb = x1.upper_bound(icl::key_value<ConstObjectT>(x2_lst_));
0058
0059     return true;
0060 }
0061
0062
0063 /** Function template <tt>contained_in</tt> implements the subset relation.
0064 <tt>contained_in(sub, super)</tt> is true if <tt>sub</tt> is contained in <tt>super</tt> */
0065 template<class SetType>
0066 inline bool within(const SetType& sub, const SetType& super)
0067 {
0068     if(&super == &sub)                   return true;
0069     if(icl::is_empty(sub))               return true;
0070     if(icl::is_empty(super))             return false;
0071
0072     typename SetType::const_iterator common_lwb_, common_upb_;
0073     if(!common_range(common_lwb_, common_upb_, sub, super))
0074         return false;
0075
0076     typename SetType::const_iterator sub_ = common_lwb_, super_;
0077     while(sub_ != common_upb_)
0078     {
0079         super_ = super.find(*sub_++);
0080         if(super_ == super.end())
0081             return false;
0082     }
0083     return true;
0084 }
0085
0086 template<class SetType>
0087 bool intersects(const SetType& left, const SetType& right)
0088 {
0089     typename SetType::const_iterator common_lwb_right_, common_upb_right_;
0090     if(!common_range(common_lwb_right_, common_upb_right_, right, left))
0091         return false;
0092
0093     typename SetType::const_iterator right_ = common_lwb_right_, found_;
0094     while(right_ != common_upb_right_)
0095     {
0096         found_ = left.find(*right_++);
0097         if(found_ != left.end())
0098             return true; // found a common element
0099     }
0100     // found no common element
0101     return false;
0102 }
0103
0104
0105 #ifdef BOOST_MSVC
0106 #pragma warning(push)
0107 #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'
0108 #endif                        // I do guarantee here that I am using the parameters correctly :)
0109
0110 /** Function template <tt>lexicographical_equal</tt> implements
0111     lexicographical equality. */
0112 template<class SetType>
0113 inline bool lexicographical_equal(const SetType& left, const SetType& right)
0114 {
0115     if(&left == &right)
0116         return true;
0117     else return left.iterative_size() == right.iterative_size()
0118              && std::equal(left.begin(), left.end(), right.begin());
0119 }
0120
0121 #ifdef BOOST_MSVC
0122 #pragma warning(pop)
0123 #endif
0124
0125
0126 } // namespace Set
0127
0128 }} // namespace icl boost
0129
0130 #endif
0131