icl/detail/interval_subset_comparer.hpp

0001 /*-----------------------------------------------------------------------------+
0002 Copyright (c) 2008-2009: Joachim Faulhaber
0003 +------------------------------------------------------------------------------+
0004    Distributed under the Boost Software License, Version 1.0.
0005       (See accompanying file LICENCE.txt or copy at
0006            http://www.boost.org/LICENSE_1_0.txt)
0007 +-----------------------------------------------------------------------------*/
0008 #ifndef BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
0009 #define BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
0010
0011 #include <boost/icl/type_traits/is_map.hpp>
0012 #include <boost/icl/detail/notate.hpp>
0013 #include <boost/icl/detail/relation_state.hpp>
0014 #include <boost/icl/type_traits/identity_element.hpp>
0015 #include <boost/icl/type_traits/is_concept_equivalent.hpp>
0016 #include <boost/icl/type_traits/is_interval_container.hpp>
0017 #include <boost/icl/type_traits/is_set.hpp>
0018 #include <boost/icl/concept/interval_set_value.hpp>
0019
0020 namespace boost{namespace icl
0021 {
0022
0023 #ifdef BOOST_MSVC
0024 #pragma warning(push)
0025 #pragma warning(disable:4127) // conditional expression is constant
0026 #endif
0027
0028 namespace Interval_Set
0029 {
0030
0031 //------------------------------------------------------------------------------
0032 template<class LeftT, class RightT>
0033 struct settic_codomain_compare
0034 {
0035     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0036     {
0037         return inclusion_compare( icl::co_value<LeftT>(left_),
0038                                  icl::co_value<RightT>(right_));
0039     }
0040 };
0041
0042 template<class LeftT, class RightT>
0043 struct atomic_codomain_compare
0044 {
0045     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0046     {
0047         if(icl::co_value<LeftT>(left_) == icl::co_value<RightT>(right_))
0048             return inclusion::equal;
0049         else
0050             return inclusion::unrelated;
0051     }
0052 };
0053
0054 template<class LeftT, class RightT>
0055 struct empty_codomain_compare
0056 {
0057     static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator)
0058     {
0059         return inclusion::equal;
0060     }
0061 };
0062
0063 template<class LeftT, class RightT>
0064 struct map_codomain_compare
0065 {
0066     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
0067     {
0068         using namespace boost::mpl;
0069         typedef typename LeftT::codomain_type  LeftCodomainT;
0070         typedef typename RightT::codomain_type RightCodomainT;
0071
0072         return
0073             if_<
0074                 bool_<is_concept_equivalent<is_set,LeftCodomainT,
0075                                                    RightCodomainT>::value>,
0076                 settic_codomain_compare<LeftT,RightT>,
0077                 atomic_codomain_compare<LeftT,RightT>
0078             >
0079             ::type::apply(left_, right_);
0080     }
0081 };
0082
0083
0084 //------------------------------------------------------------------------------
0085 template<class LeftT, class RightT>
0086 class subset_comparer
0087 {
0088 private:
0089     subset_comparer& operator = (const subset_comparer&);
0090 public:
0091     typedef typename LeftT::const_iterator  LeftIterT;
0092     typedef typename RightT::const_iterator RightIterT;
0093
0094     BOOST_STATIC_CONSTANT(bool,
0095         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
0096
0097
0098     subset_comparer(const LeftT&      left,
0099                     const RightT&     right,
0100                     const LeftIterT&  left_end,
0101                     const RightIterT& right_end)
0102         : _left(left), _right(right),
0103           _left_end(left_end), _right_end(right_end), _result(equal)
0104     {}
0105
0106     enum{nextboth, nextleft, nextright, stop};
0107
0108     enum
0109     {
0110         unrelated  = inclusion::unrelated,
0111         subset     = inclusion::subset,     // left is_subset_of   right
0112         superset   = inclusion::superset,   // left is_superset_of right
0113         equal      = inclusion::equal       // equal = subset | superset
0114     };
0115
0116     int result()const{ return _result; }
0117
0118
0119     int co_compare(LeftIterT& left, RightIterT& right)
0120     {
0121         using namespace boost::mpl;
0122
0123         return
0124             if_<
0125                 bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
0126                 map_codomain_compare<LeftT,RightT>,
0127                 empty_codomain_compare<LeftT,RightT>
0128             >
0129             ::type::apply(left,right);
0130     }
0131
0132     int restrict_result(int state) { return _result &= state; }
0133
0134     int proceed(LeftIterT& left, RightIterT& right)
0135     {
0136         if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
0137         {   // left  ..)
0138             // right .....)
0139             _prior_left = left;
0140             ++left;
0141             return nextleft;
0142         }
0143         else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
0144         {   // left  .....)
0145             // right ..)
0146             _prior_right = right;
0147             ++right;
0148             return nextright;
0149         }
0150         else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
0151         {   // left  ..)
0152             // right ..)
0153             ++left;
0154             ++right;
0155             return nextboth;
0156         }
0157     }
0158
0159     int next_both(LeftIterT& left, RightIterT& right)
0160     {
0161         if(left == _left_end && right == _right_end)
0162             return stop;
0163         else if(left == _left_end)
0164         {   // left: ....end    left could be subset
0165             // right:....[..
0166             restrict_result(subset);
0167             return stop;
0168         }
0169         else if(right == _right_end)
0170         {   // left: ....[..    left could be superset
0171             // right:....end
0172             restrict_result(superset);
0173             return stop;
0174         }
0175         else if(exclusive_less(key_value<LeftT>(left), key_value<RightT>(right)))
0176         {   // left: [..) . . .[---)      left could be superset
0177             // right:           [..)....  if [---) exists
0178             restrict_result(superset);
0179             if(unrelated == _result)
0180                 return stop;
0181             else
0182             {
0183                 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
0184                 if(joint_ == _left.end())
0185                 {
0186                     _result = unrelated;
0187                     return stop;
0188                 }
0189                 else
0190                 {
0191                     left = joint_;
0192                     return nextboth;
0193                 }
0194             }
0195         }
0196         else if(exclusive_less(key_value<RightT>(right), key_value<LeftT>(left)))
0197         {   // left:             [..  left could be subset
0198             // right:....) . . .[---) if [---) exists
0199             restrict_result(subset);
0200             if(unrelated == _result)
0201                 return stop;
0202             else
0203             {
0204                 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
0205                 if(joint_ == _right.end())
0206                 {
0207                     _result = unrelated;
0208                     return stop;
0209                 }
0210                 else
0211                 {
0212                     right = joint_;
0213                     return nextboth;
0214                 }
0215             }
0216         }
0217
0218         // left and right have intervals with nonempty intersection:
0219         if(_compare_codomain)
0220             if(unrelated == restrict_result(co_compare(left,right)))
0221                 return stop;
0222
0223         // examine left borders only. Right borders are checked in proceed
0224         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
0225         {   // left: ....[...     left could be superset
0226             // right:....   [..
0227             if(unrelated == restrict_result(superset))
0228                 return stop;
0229         }
0230         else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
0231         {   // left: ....   [..   left can be subset
0232             // right:....[...
0233             if(unrelated == restrict_result(subset))
0234                 return stop;
0235         }
0236         //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
0237             // left: ....[..   both can be equal
0238             // right:....[..
0239             // nothing to do: proceed
0240
0241         return proceed(left, right);
0242     }
0243
0244     int next_left(LeftIterT& left, RightIterT& right)
0245     {
0246         if(left == _left_end)
0247         {   // left: ..)end    left could be subset
0248             // right:......)
0249             restrict_result(subset);
0250             return stop;
0251         }
0252         else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
0253         {   // left: ..)   [..
0254             // right:.........)
0255             if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
0256             {   //   ..)   [..   left could be subset
0257                 //   ..........)
0258                 if(unrelated == restrict_result(subset))
0259                     return stop;
0260             }
0261             //else   ..)   [...
0262             //          [..
0263             if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
0264                 if(unrelated == restrict_result(co_compare(left,right)))
0265                     return stop;
0266         }
0267         else
0268         {   // left: ..)[..  left could be subset
0269             // right:.......)
0270             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
0271                 if(unrelated == restrict_result(co_compare(left,right)))
0272                     return stop;
0273         }
0274
0275         return proceed(left, right);
0276     }
0277
0278
0279     int next_right(LeftIterT& left, RightIterT& right)
0280     {
0281         if(right == _right_end)
0282         {   // left: ......)    left could be superset
0283             // right:..)end
0284             restrict_result(superset);
0285             return stop;
0286         }
0287         else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
0288         {   // left: .........)
0289             // right:..)   [..
0290             if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
0291             {   //       [....)  left could be superset
0292                 //   ..)   [..
0293                 if(unrelated == restrict_result(superset))
0294                     return stop;
0295             }
0296             //else       [....)
0297             //   ..)   [..
0298             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
0299                 if(unrelated == restrict_result(co_compare(left,right)))
0300                     return stop;
0301         }
0302         else
0303         {
0304             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
0305                 if(unrelated == restrict_result(co_compare(left,right)))
0306                     return stop;
0307         }
0308
0309         return proceed(left, right);
0310     }
0311
0312 private:
0313     const LeftT&  _left;
0314     const RightT& _right;
0315     LeftIterT     _left_end;
0316     RightIterT    _right_end;
0317     LeftIterT     _prior_left;
0318     RightIterT    _prior_right;
0319     int           _result;
0320 };
0321
0322
0323
0324
0325
0326 //------------------------------------------------------------------------------
0327 // Subset/superset comparison on ranges of two interval container
0328 //------------------------------------------------------------------------------
0329 template<class LeftT, class RightT>
0330 int subset_compare
0331 (
0332     const LeftT& left,   //sub
0333     const RightT& right, //super
0334     typename LeftT::const_iterator  left_begin,
0335     typename LeftT::const_iterator  left_end,
0336     typename RightT::const_iterator right_begin,
0337     typename RightT::const_iterator right_end
0338 )
0339 {
0340     typedef subset_comparer<LeftT,RightT> Step;
0341     Step step(left, right, left_end, right_end);
0342
0343     typename LeftT::const_iterator  left_  = left_begin;
0344     typename RightT::const_iterator right_ = right_begin;
0345
0346     int state = Step::nextboth;
0347     while(state != Step::stop)
0348     {
0349         switch(state){
0350         case Step::nextboth:    state = step.next_both(left_, right_);  break;
0351         case Step::nextleft:    state = step.next_left(left_, right_);  break;
0352         case Step::nextright:   state = step.next_right(left_, right_); break;
0353         }
0354     }
0355     return step.result();
0356 }
0357
0358
0359 } // namespace Interval_Set
0360
0361 #ifdef BOOST_MSVC
0362 #pragma warning(pop)
0363 #endif
0364
0365 }} // namespace icl boost
0366
0367 #endif
0368