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