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_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
Chris@16: #define BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
Chris@16: 
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/is_concept_equivalent.hpp>
Chris@16: #include <boost/icl/type_traits/is_interval_container.hpp>
Chris@16: #include <boost/icl/type_traits/is_set.hpp>
Chris@16: #include <boost/icl/concept/interval_set_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 Interval_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( icl::co_value<LeftT>(left_), 
Chris@16:                                  icl::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(icl::co_value<LeftT>(left_) == icl::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: 
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, nextleft, nextright, 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: 
Chris@16:     int co_compare(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         using namespace boost::mpl;
Chris@16: 
Chris@16:         return  
Chris@16:             if_<
Chris@16:                 bool_<is_concept_equivalent<is_interval_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 proceed(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
Chris@16:         {   // left  ..)  
Chris@16:             // right .....)
Chris@16:             _prior_left = left;
Chris@16:             ++left;
Chris@16:             return nextleft;
Chris@16:         }
Chris@16:         else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
Chris@16:         {   // left  .....)
Chris@16:             // right ..)
Chris@16:             _prior_right = right;
Chris@16:             ++right;
Chris@16:             return nextright;
Chris@16:         }
Chris@16:         else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
Chris@16:         {   // left  ..)
Chris@16:             // right ..)
Chris@16:             ++left; 
Chris@16:             ++right;    
Chris@16:             return nextboth;
Chris@16:         }
Chris@16:     }
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:         {   // left: ....end    left could be subset
Chris@16:             // right:....[..
Chris@16:             restrict_result(subset);
Chris@16:             return stop;
Chris@16:         }
Chris@16:         else if(right == _right_end)
Chris@16:         {   // left: ....[..    left could be superset
Chris@16:             // right:....end
Chris@16:             restrict_result(superset);
Chris@16:             return stop;
Chris@16:         }
Chris@16:         else if(exclusive_less(key_value<LeftT>(left), key_value<RightT>(right)))
Chris@16:         {   // left: [..) . . .[---)      left could be superset
Chris@16:             // right:           [..)....  if [---) 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:                 {
Chris@16:                     _result = unrelated;
Chris@16:                     return stop;
Chris@16:                 }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     left = joint_;
Chris@16:                     return nextboth;
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16:         else if(exclusive_less(key_value<RightT>(right), key_value<LeftT>(left)))
Chris@16:         {   // left:             [..  left could be subset
Chris@16:             // right:....) . . .[---) if [---) 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:                 {
Chris@16:                     _result = unrelated;
Chris@16:                     return stop;
Chris@16:                 }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     right = joint_;
Chris@16:                     return nextboth;
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // left and right have intervals with nonempty intersection:
Chris@16:         if(_compare_codomain)
Chris@16:             if(unrelated == restrict_result(co_compare(left,right)))
Chris@16:                 return stop;
Chris@16: 
Chris@16:         // examine left borders only. Right borders are checked in proceed
Chris@16:         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
Chris@16:         {   // left: ....[...     left could be superset
Chris@16:             // right:....   [..
Chris@16:             if(unrelated == restrict_result(superset))
Chris@16:                 return stop;
Chris@16:         }
Chris@16:         else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
Chris@16:         {   // left: ....   [..   left can be subset
Chris@16:             // right:....[...
Chris@16:             if(unrelated == restrict_result(subset))
Chris@16:                 return stop;
Chris@16:         }
Chris@16:         //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
Chris@16:             // left: ....[..   both can be equal
Chris@16:             // right:....[..
Chris@16:             // nothing to do: proceed
Chris@16: 
Chris@16:         return proceed(left, right);
Chris@16:     }
Chris@16: 
Chris@16:     int next_left(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         if(left == _left_end)
Chris@16:         {   // left: ..)end    left could be subset
Chris@16:             // right:......)
Chris@16:             restrict_result(subset);
Chris@16:             return stop;            
Chris@16:         }
Chris@16:         else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
Chris@16:         {   // left: ..)   [..
Chris@16:             // right:.........)
Chris@16:             if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
Chris@16:             {   //   ..)   [..   left could be subset
Chris@16:                 //   ..........)
Chris@16:                 if(unrelated == restrict_result(subset))
Chris@16:                     return stop;            
Chris@16:             }
Chris@16:             //else   ..)   [...
Chris@16:             //          [..
Chris@16:             if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
Chris@16:                 if(unrelated == restrict_result(co_compare(left,right)))
Chris@16:                     return stop;
Chris@16:         }
Chris@16:         else
Chris@16:         {   // left: ..)[..  left could be subset
Chris@16:             // right:.......)
Chris@16:             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
Chris@16:                 if(unrelated == restrict_result(co_compare(left,right)))
Chris@16:                     return stop;
Chris@16:         }
Chris@16: 
Chris@16:         return proceed(left, right);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     int next_right(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         if(right == _right_end)
Chris@16:         {   // left: ......)    left could be superset
Chris@16:             // right:..)end
Chris@16:             restrict_result(superset);
Chris@16:             return stop;            
Chris@16:         }
Chris@16:         else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
Chris@16:         {   // left: .........)
Chris@16:             // right:..)   [..
Chris@16:             if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
Chris@16:             {   //       [....)  left could be superset
Chris@16:                 //   ..)   [..
Chris@16:                 if(unrelated == restrict_result(superset))
Chris@16:                     return stop;            
Chris@16:             }
Chris@16:             //else       [....)
Chris@16:             //   ..)   [..
Chris@16:             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
Chris@16:                 if(unrelated == restrict_result(co_compare(left,right)))
Chris@16:                     return stop;
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
Chris@16:                 if(unrelated == restrict_result(co_compare(left,right)))
Chris@16:                     return stop;
Chris@16:         }
Chris@16: 
Chris@16:         return proceed(left, right);
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:     LeftIterT     _prior_left;
Chris@16:     RightIterT    _prior_right;
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:     {
Chris@16:         switch(state){
Chris@16:         case Step::nextboth:    state = step.next_both(left_, right_);  break;
Chris@16:         case Step::nextleft:    state = step.next_left(left_, right_);  break;
Chris@16:         case Step::nextright:   state = step.next_right(left_, right_); break;
Chris@16:         }
Chris@16:     }
Chris@16:     return step.result();
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: } // namespace Interval_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: