ceph/src/boost/boost/icl/detail/element_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_ELEMENT_COMPARER_HPP_JOFA_090202
   9 #define BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202
  10
  11 #include <boost/mpl/and.hpp>
  12 #include <boost/icl/type_traits/is_map.hpp>
  13 #include <boost/icl/detail/notate.hpp>
  14 #include <boost/icl/type_traits/identity_element.hpp>
  15
  16 namespace boost{namespace icl
  17 {
  18
  19 namespace Interval_Set
  20 {
  21
  22 template<class LeftT, class RightT>
  23 class element_comparer
  24 {
  25 public:
  26     typedef typename LeftT::const_iterator  LeftIterT;
  27     typedef typename RightT::const_iterator RightIterT;
  28
  29     BOOST_STATIC_CONSTANT(bool,
  30         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
  31
  32     element_comparer(const LeftT&      left,
  33                      const RightT&     right,
  34                      const LeftIterT&  left_end,
  35                      const RightIterT& right_end)
  36         : _left(left), _right(right),
  37           _left_end(left_end), _right_end(right_end), _result(equal)
  38     {}
  39
  40     enum{nextboth, nextleft, nextright, stop};
  41
  42     enum
  43     {
  44         less    = comparison::less,
  45         equal   = comparison::equal,
  46         greater = comparison::greater
  47     };
  48
  49     int result()const{ return _result; }
  50
  51     bool covalues_are_equal(LeftIterT& left, RightIterT& right)
  52     {
  53         if(co_value<LeftT>(left) < co_value<RightT>(right))
  54             _result = less;
  55         if(co_value<RightT>(right) < co_value<LeftT>(left))
  56             _result = greater;
  57         return _result == equal;
  58     }
  59
  60     int proceed(LeftIterT& left, RightIterT& right)
  61     {
  62         if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
  63         {
  64             _prior_left = left;
  65             ++left;
  66             return nextleft;
  67         }
  68         else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
  69         {
  70             _prior_right = right;
  71             ++right;
  72             return nextright;
  73         }
  74         else
  75         {
  76             ++left;
  77             ++right;
  78             return nextboth;
  79         }
  80     }
  81
  82     int next_both(LeftIterT& left, RightIterT& right)
  83     {
  84         if(left == _left_end)
  85         {
  86             _result = (right == _right_end) ? equal : less;
  87             return stop;
  88         }
  89
  90         // left != _left_end
  91         if(right == _right_end)
  92         {
  93             _result = greater;
  94             return stop;
  95         }
  96
  97         // The starting intervals have to begin equally
  98         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
  99         {   // left: same A... = sameA...
 100             // right:same  B.. = sameB...
 101             _result = less;
 102             return stop;
 103         }
 104
 105         if(lower_less(key_value<LeftT>(right), key_value<RightT>(left)))
 106         {   // left: same  B.. = sameB...
 107             // right:same A... = sameA...
 108             _result = greater;
 109             return stop;
 110         }
 111
 112         if(_compare_codomain && !covalues_are_equal(left, right))
 113             return stop;
 114
 115         return proceed(left, right);
 116     }
 117
 118     int next_left(LeftIterT& left, RightIterT& right)
 119     {
 120         if(left == _left_end)
 121         {   // left: same
 122             // right:sameA...
 123             _result = less;
 124             return stop;
 125         }
 126
 127         if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left)))
 128         {   // left: same B = sameB...
 129             // right:sameA  = sameA...
 130             _result = greater;
 131             return stop;
 132         }
 133
 134         if(_compare_codomain && !covalues_are_equal(left, right))
 135             return stop;
 136
 137         return proceed(left, right);
 138     }
 139
 140     int next_right(LeftIterT& left, RightIterT& right)
 141     {
 142         if(right == _right_end)
 143         {   // left: sameA...
 144             // right:same
 145             _result = greater;
 146             return stop;
 147         }
 148
 149         if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right)))
 150         {
 151             // left: sameA... = sameA...
 152             // right:same B.. = sameB...
 153             _result = less;
 154             return stop;
 155         }
 156
 157         if(_compare_codomain && !covalues_are_equal(left, right))
 158             return stop;
 159
 160         return proceed(left, right);
 161     }
 162
 163 private:
 164     const LeftT&  _left;
 165     const RightT& _right;
 166     LeftIterT     _left_end;
 167     RightIterT    _right_end;
 168     LeftIterT     _prior_left;
 169     RightIterT    _prior_right;
 170     int           _result;
 171 };
 172
 173
 174
 175 template<class LeftT, class RightT>
 176 int element_compare
 177 (
 178     const LeftT& left,   //sub
 179     const RightT& right, //super
 180     typename LeftT::const_iterator  left_begin,
 181     typename LeftT::const_iterator  left_end,
 182     typename RightT::const_iterator right_begin,
 183     typename RightT::const_iterator right_end
 184 )
 185 {
 186     typedef element_comparer<LeftT,RightT> Step;
 187     Step step(left, right, left_end, right_end);
 188
 189     typename LeftT::const_iterator  left_  = left_begin;
 190     typename RightT::const_iterator right_ = right_begin;
 191
 192     int state = Step::nextboth;
 193     while(state != Step::stop)
 194     {
 195         switch(state){
 196         case Step::nextboth:  state = step.next_both (left_, right_); break;
 197         case Step::nextleft:  state = step.next_left (left_, right_); break;
 198         case Step::nextright: state = step.next_right(left_, right_); break;
 199         }
 200     }
 201     return step.result();
 202 }
 203
 204
 205 } // namespace Interval_Set
 206
 207 }} // namespace icl boost
 208
 209 #endif
 210