| /*-----------------------------------------------------------------------------+ |
| Copyright (c) 2008-2009: Joachim Faulhaber |
| +------------------------------------------------------------------------------+ |
| 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_SUBSET_COMPARER_HPP_JOFA_090202 |
| #define BOOST_ICL_SUBSET_COMPARER_HPP_JOFA_090202 |
| |
| #include <boost/mpl/and.hpp> |
| #include <boost/icl/type_traits/is_map.hpp> |
| #include <boost/icl/detail/notate.hpp> |
| #include <boost/icl/detail/relation_state.hpp> |
| #include <boost/icl/type_traits/identity_element.hpp> |
| #include <boost/icl/type_traits/codomain_type_of.hpp> |
| #include <boost/icl/type_traits/is_concept_equivalent.hpp> |
| #include <boost/icl/type_traits/is_element_container.hpp> |
| #include <boost/icl/concept/interval_set_value.hpp> |
| #include <boost/icl/concept/map_value.hpp> |
| |
| namespace boost{namespace icl |
| { |
| |
| #ifdef BOOST_MSVC |
| #pragma warning(push) |
| #pragma warning(disable:4127) // conditional expression is constant |
| #endif |
| |
| namespace Set |
| { |
| |
| //------------------------------------------------------------------------------ |
| template<class LeftT, class RightT> |
| struct settic_codomain_compare |
| { |
| static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_) |
| { |
| return inclusion_compare( co_value<LeftT>(left_), |
| co_value<RightT>(right_)); |
| } |
| }; |
| |
| template<class LeftT, class RightT> |
| struct atomic_codomain_compare |
| { |
| static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_) |
| { |
| if(co_value<LeftT>(left_) == co_value<RightT>(right_)) |
| return inclusion::equal; |
| else |
| return inclusion::unrelated; |
| } |
| }; |
| |
| template<class LeftT, class RightT> |
| struct empty_codomain_compare |
| { |
| static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator&) |
| { |
| return inclusion::equal; |
| } |
| }; |
| |
| template<class LeftT, class RightT> |
| struct map_codomain_compare |
| { |
| static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_) |
| { |
| using namespace boost::mpl; |
| typedef typename LeftT::codomain_type LeftCodomainT; |
| typedef typename RightT::codomain_type RightCodomainT; |
| |
| return |
| if_< |
| bool_<is_concept_equivalent<is_set,LeftCodomainT, |
| RightCodomainT>::value>, |
| settic_codomain_compare<LeftT,RightT>, |
| atomic_codomain_compare<LeftT,RightT> |
| > |
| ::type::apply(left_, right_); |
| } |
| }; |
| |
| |
| //------------------------------------------------------------------------------ |
| template<class LeftT, class RightT> |
| class subset_comparer |
| { |
| private: |
| subset_comparer& operator = (const subset_comparer&); |
| public: |
| typedef typename LeftT::const_iterator LeftIterT; |
| typedef typename RightT::const_iterator RightIterT; |
| |
| BOOST_STATIC_CONSTANT(bool, |
| _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value)); |
| |
| subset_comparer(const LeftT& left, |
| const RightT& right, |
| const LeftIterT& left_end, |
| const RightIterT& right_end) |
| : _left(left), _right(right), |
| _left_end(left_end), _right_end(right_end), _result(equal) |
| {} |
| |
| enum{nextboth, stop}; |
| |
| enum |
| { |
| unrelated = inclusion::unrelated, |
| subset = inclusion::subset, // left is_subset_of right |
| superset = inclusion::superset, // left is_superset_of right |
| equal = inclusion::equal // equal = subset | superset |
| }; |
| |
| int result()const{ return _result; } |
| |
| int co_compare(LeftIterT& left, RightIterT& right) |
| { |
| using namespace boost::mpl; |
| typedef typename codomain_type_of<LeftT>::type LeftCodomainT; |
| typedef typename codomain_type_of<RightT>::type RightCodomainT; |
| |
| return |
| if_< |
| bool_<is_concept_equivalent<is_element_map,LeftT,RightT>::value>, |
| map_codomain_compare<LeftT,RightT>, |
| empty_codomain_compare<LeftT,RightT> |
| > |
| ::type::apply(left,right); |
| } |
| |
| int restrict_result(int state) { return _result &= state; } |
| |
| int next_both(LeftIterT& left, RightIterT& right) |
| { |
| if(left == _left_end && right == _right_end) |
| return stop; |
| else if(left == _left_end) |
| { |
| restrict_result(subset); |
| return stop; |
| } |
| else if(right == _right_end) |
| { |
| restrict_result(superset); |
| return stop; |
| } |
| else if(typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(right))) |
| { // left: *left . . *joint_ left could be superset |
| // right: *right ... if joint_ exists |
| restrict_result(superset); |
| if(unrelated == _result) |
| return stop; |
| else |
| { |
| LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right)); |
| if( joint_ == _left.end() |
| || typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(joint_))) |
| { |
| _result = unrelated; |
| return stop; |
| } |
| else |
| left = joint_; |
| } |
| } |
| else if(typename LeftT::key_compare()(key_value<RightT>(right), key_value<LeftT>(left))) |
| { // left: *left left could be subset |
| // right:*right . . .*joint_ if *joint_ exists |
| restrict_result(subset); |
| if(unrelated == _result) |
| return stop; |
| else |
| { |
| RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left)); |
| if( joint_ == _right.end() |
| || typename LeftT::key_compare()(key_value<LeftT>(left), key_value<RightT>(joint_))) |
| { |
| _result = unrelated; |
| return stop; |
| } |
| else |
| right = joint_; |
| } |
| } |
| |
| // left =key= right |
| if(_compare_codomain) |
| if(unrelated == restrict_result(co_compare(left,right))) |
| return stop; |
| |
| ++left; |
| ++right; |
| return nextboth; |
| } |
| |
| private: |
| const LeftT& _left; |
| const RightT& _right; |
| LeftIterT _left_end; |
| RightIterT _right_end; |
| int _result; |
| }; |
| |
| |
| |
| |
| |
| //------------------------------------------------------------------------------ |
| // Subset/superset comparison on ranges of two interval container |
| //------------------------------------------------------------------------------ |
| template<class LeftT, class RightT> |
| int subset_compare |
| ( |
| const LeftT& left, //sub |
| const RightT& right, //super |
| typename LeftT::const_iterator left_begin, |
| typename LeftT::const_iterator left_end, |
| typename RightT::const_iterator right_begin, |
| typename RightT::const_iterator right_end |
| ) |
| { |
| typedef subset_comparer<LeftT,RightT> Step; |
| Step step(left, right, left_end, right_end); |
| |
| typename LeftT::const_iterator left_ = left_begin; |
| typename RightT::const_iterator right_ = right_begin; |
| |
| int state = Step::nextboth; |
| while(state != Step::stop) |
| state = step.next_both(left_, right_); |
| |
| return step.result(); |
| } |
| |
| template<class LeftT, class RightT> |
| int subset_compare(const LeftT& left, const RightT& right) |
| { |
| return subset_compare |
| ( |
| left, right, |
| left.begin(), left.end(), |
| right.begin(), right.end() |
| ); |
| } |
| |
| |
| } // namespace Set |
| |
| #ifdef BOOST_MSVC |
| #pragma warning(pop) |
| #endif |
| |
| }} // namespace icl boost |
| |
| #endif |
| |