ceph/src/boost/libs/icl/include/boost/icl/detail/interval_subset_comparer.hpp

   1 /*-----------------------------------------------------------------------------+
   2 Copyright (c) 2008-2009: Joachim Faulhaber
   3 +------------------------------------------------------------------------------+
   4    Distributed under the Boost Software License, Version 1.0.
   5       (See accompanying file LICENCE.txt or copy at
   6            http://www.boost.org/LICENSE_1_0.txt)
   7 +-----------------------------------------------------------------------------*/
   8 #ifndef BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
   9 #define BOOST_ICL_INTERVAL_SUBSET_COMPARER_HPP_JOFA_090827
  10
  11 #include <boost/icl/type_traits/is_map.hpp>
  12 #include <boost/icl/detail/notate.hpp>
  13 #include <boost/icl/detail/relation_state.hpp>
  14 #include <boost/icl/type_traits/identity_element.hpp>
  15 #include <boost/icl/type_traits/is_concept_equivalent.hpp>
  16 #include <boost/icl/type_traits/is_interval_container.hpp>
  17 #include <boost/icl/type_traits/is_set.hpp>
  18 #include <boost/icl/concept/interval_set_value.hpp>
  19
  20 namespace boost{namespace icl
  21 {
  22
  23 #ifdef BOOST_MSVC
  24 #pragma warning(push)
  25 #pragma warning(disable:4127) // conditional expression is constant
  26 #endif
  27
  28 namespace Interval_Set
  29 {
  30
  31 //------------------------------------------------------------------------------
  32 template<class LeftT, class RightT>
  33 struct settic_codomain_compare
  34 {
  35     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  36     {
  37         return inclusion_compare( icl::co_value<LeftT>(left_),
  38                                  icl::co_value<RightT>(right_));
  39     }
  40 };
  41
  42 template<class LeftT, class RightT>
  43 struct atomic_codomain_compare
  44 {
  45     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  46     {
  47         if(icl::co_value<LeftT>(left_) == icl::co_value<RightT>(right_))
  48             return inclusion::equal;
  49         else
  50             return inclusion::unrelated;
  51     }
  52 };
  53
  54 template<class LeftT, class RightT>
  55 struct empty_codomain_compare
  56 {
  57     static int apply(typename LeftT::const_iterator&, typename RightT::const_iterator)
  58     {
  59         return inclusion::equal;
  60     }
  61 };
  62
  63 template<class LeftT, class RightT>
  64 struct map_codomain_compare
  65 {
  66     static int apply(typename LeftT::const_iterator& left_, typename RightT::const_iterator& right_)
  67     {
  68         using namespace boost::mpl;
  69         typedef typename LeftT::codomain_type  LeftCodomainT;
  70         typedef typename RightT::codomain_type RightCodomainT;
  71
  72         return
  73             if_<
  74                 bool_<is_concept_equivalent<is_set,LeftCodomainT,
  75                                                    RightCodomainT>::value>,
  76                 settic_codomain_compare<LeftT,RightT>,
  77                 atomic_codomain_compare<LeftT,RightT>
  78             >
  79             ::type::apply(left_, right_);
  80     }
  81 };
  82
  83
  84 //------------------------------------------------------------------------------
  85 template<class LeftT, class RightT>
  86 class subset_comparer
  87 {
  88 private:
  89     subset_comparer& operator = (const subset_comparer&);
  90 public:
  91     typedef typename LeftT::const_iterator  LeftIterT;
  92     typedef typename RightT::const_iterator RightIterT;
  93
  94     BOOST_STATIC_CONSTANT(bool,
  95         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
  96
  97
  98     subset_comparer(const LeftT&      left,
  99                     const RightT&     right,
 100                     const LeftIterT&  left_end,
 101                     const RightIterT& right_end)
 102         : _left(left), _right(right),
 103           _left_end(left_end), _right_end(right_end), _result(equal)
 104     {}
 105
 106     enum{nextboth, nextleft, nextright, stop};
 107
 108     enum
 109     {
 110         unrelated  = inclusion::unrelated,
 111         subset     = inclusion::subset,     // left is_subset_of   right
 112         superset   = inclusion::superset,   // left is_superset_of right
 113         equal      = inclusion::equal       // equal = subset | superset
 114     };
 115
 116     int result()const{ return _result; }
 117
 118
 119     int co_compare(LeftIterT& left, RightIterT& right)
 120     {
 121         using namespace boost::mpl;
 122
 123         return
 124             if_<
 125                 bool_<is_concept_equivalent<is_interval_map,LeftT,RightT>::value>,
 126                 map_codomain_compare<LeftT,RightT>,
 127                 empty_codomain_compare<LeftT,RightT>
 128             >
 129             ::type::apply(left,right);
 130     }
 131
 132     int restrict_result(int state) { return _result &= state; }
 133
 134     int proceed(LeftIterT& left, RightIterT& right)
 135     {
 136         if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
 137         {   // left  ..)
 138             // right .....)
 139             _prior_left = left;
 140             ++left;
 141             return nextleft;
 142         }
 143         else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
 144         {   // left  .....)
 145             // right ..)
 146             _prior_right = right;
 147             ++right;
 148             return nextright;
 149         }
 150         else//key_value<LeftT>(left).upper_equal(key_value<RightT>(right))
 151         {   // left  ..)
 152             // right ..)
 153             ++left;
 154             ++right;
 155             return nextboth;
 156         }
 157     }
 158
 159     int next_both(LeftIterT& left, RightIterT& right)
 160     {
 161         if(left == _left_end && right == _right_end)
 162             return stop;
 163         else if(left == _left_end)
 164         {   // left: ....end    left could be subset
 165             // right:....[..
 166             restrict_result(subset);
 167             return stop;
 168         }
 169         else if(right == _right_end)
 170         {   // left: ....[..    left could be superset
 171             // right:....end
 172             restrict_result(superset);
 173             return stop;
 174         }
 175         else if(exclusive_less(key_value<LeftT>(left), key_value<RightT>(right)))
 176         {   // left: [..) . . .[---)      left could be superset
 177             // right:           [..)....  if [---) exists
 178             restrict_result(superset);
 179             if(unrelated == _result)
 180                 return stop;
 181             else
 182             {
 183                 LeftIterT joint_ = _left.lower_bound(key_value<RightT>(right));
 184                 if(joint_ == _left.end())
 185                 {
 186                     _result = unrelated;
 187                     return stop;
 188                 }
 189                 else
 190                 {
 191                     left = joint_;
 192                     return nextboth;
 193                 }
 194             }
 195         }
 196         else if(exclusive_less(key_value<RightT>(right), key_value<LeftT>(left)))
 197         {   // left:             [..  left could be subset
 198             // right:....) . . .[---) if [---) exists
 199             restrict_result(subset);
 200             if(unrelated == _result)
 201                 return stop;
 202             else
 203             {
 204                 RightIterT joint_ = _right.lower_bound(key_value<LeftT>(left));
 205                 if(joint_ == _right.end())
 206                 {
 207                     _result = unrelated;
 208                     return stop;
 209                 }
 210                 else
 211                 {
 212                     right = joint_;
 213                     return nextboth;
 214                 }
 215             }
 216         }
 217
 218         // left and right have intervals with nonempty intersection:
 219         if(_compare_codomain)
 220             if(unrelated == restrict_result(co_compare(left,right)))
 221                 return stop;
 222
 223         // examine left borders only. Right borders are checked in proceed
 224         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
 225         {   // left: ....[...     left could be superset
 226             // right:....   [..
 227             if(unrelated == restrict_result(superset))
 228                 return stop;
 229         }
 230         else if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
 231         {   // left: ....   [..   left can be subset
 232             // right:....[...
 233             if(unrelated == restrict_result(subset))
 234                 return stop;
 235         }
 236         //else key_value<LeftT>(right).lower_equal(key_value<RightT>(left))
 237             // left: ....[..   both can be equal
 238             // right:....[..
 239             // nothing to do: proceed
 240
 241         return proceed(left, right);
 242     }
 243
 244     int next_left(LeftIterT& left, RightIterT& right)
 245     {
 246         if(left == _left_end)
 247         {   // left: ..)end    left could be subset
 248             // right:......)
 249             restrict_result(subset);
 250             return stop;
 251         }
 252         else if(!touches(key_value<LeftT>(_prior_left), key_value<LeftT>(left)))
 253         {   // left: ..)   [..
 254             // right:.........)
 255             if(lower_less(key_value<RightT>(right), key_value<LeftT>(left)))
 256             {   //   ..)   [..   left could be subset
 257                 //   ..........)
 258                 if(unrelated == restrict_result(subset))
 259                     return stop;
 260             }
 261             //else   ..)   [...
 262             //          [..
 263             if(_compare_codomain && intersects(key_value<LeftT>(left),key_value<RightT>(right)) )
 264                 if(unrelated == restrict_result(co_compare(left,right)))
 265                     return stop;
 266         }
 267         else
 268         {   // left: ..)[..  left could be subset
 269             // right:.......)
 270             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
 271                 if(unrelated == restrict_result(co_compare(left,right)))
 272                     return stop;
 273         }
 274
 275         return proceed(left, right);
 276     }
 277
 278
 279     int next_right(LeftIterT& left, RightIterT& right)
 280     {
 281         if(right == _right_end)
 282         {   // left: ......)    left could be superset
 283             // right:..)end
 284             restrict_result(superset);
 285             return stop;
 286         }
 287         else if(!touches(key_value<RightT>(_prior_right), key_value<RightT>(right)))
 288         {   // left: .........)
 289             // right:..)   [..
 290             if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
 291             {   //       [....)  left could be superset
 292                 //   ..)   [..
 293                 if(unrelated == restrict_result(superset))
 294                     return stop;
 295             }
 296             //else       [....)
 297             //   ..)   [..
 298             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
 299                 if(unrelated == restrict_result(co_compare(left,right)))
 300                     return stop;
 301         }
 302         else
 303         {
 304             if(_compare_codomain && intersects(key_value<LeftT>(left), key_value<RightT>(right)) )
 305                 if(unrelated == restrict_result(co_compare(left,right)))
 306                     return stop;
 307         }
 308
 309         return proceed(left, right);
 310     }
 311
 312 private:
 313     const LeftT&  _left;
 314     const RightT& _right;
 315     LeftIterT     _left_end;
 316     RightIterT    _right_end;
 317     LeftIterT     _prior_left;
 318     RightIterT    _prior_right;
 319     int           _result;
 320 };
 321
 322
 323
 324
 325
 326 //------------------------------------------------------------------------------
 327 // Subset/superset comparison on ranges of two interval container
 328 //------------------------------------------------------------------------------
 329 template<class LeftT, class RightT>
 330 int subset_compare
 331 (
 332     const LeftT& left,   //sub
 333     const RightT& right, //super
 334     typename LeftT::const_iterator  left_begin,
 335     typename LeftT::const_iterator  left_end,
 336     typename RightT::const_iterator right_begin,
 337     typename RightT::const_iterator right_end
 338 )
 339 {
 340     typedef subset_comparer<LeftT,RightT> Step;
 341     Step step(left, right, left_end, right_end);
 342
 343     typename LeftT::const_iterator  left_  = left_begin;
 344     typename RightT::const_iterator right_ = right_begin;
 345
 346     int state = Step::nextboth;
 347     while(state != Step::stop)
 348     {
 349         switch(state){
 350         case Step::nextboth:    state = step.next_both(left_, right_);  break;
 351         case Step::nextleft:    state = step.next_left(left_, right_);  break;
 352         case Step::nextright:   state = step.next_right(left_, right_); break;
 353         }
 354     }
 355     return step.result();
 356 }
 357
 358
 359 } // namespace Interval_Set
 360
 361 #ifdef BOOST_MSVC
 362 #pragma warning(pop)
 363 #endif
 364
 365 }} // namespace icl boost
 366
 367 #endif
 368