icl/detail/element_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_ELEMENT_COMPARER_HPP_JOFA_090202
0009 #define BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202
0010
0011 #include <boost/mpl/and.hpp>
0012 #include <boost/icl/type_traits/is_map.hpp>
0013 #include <boost/icl/detail/notate.hpp>
0014 #include <boost/icl/type_traits/identity_element.hpp>
0015
0016 namespace boost{namespace icl
0017 {
0018
0019 namespace Interval_Set
0020 {
0021
0022 template<class LeftT, class RightT>
0023 class element_comparer
0024 {
0025 public:
0026     typedef typename LeftT::const_iterator  LeftIterT;
0027     typedef typename RightT::const_iterator RightIterT;
0028
0029     BOOST_STATIC_CONSTANT(bool,
0030         _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value));
0031
0032     element_comparer(const LeftT&      left,
0033                      const RightT&     right,
0034                      const LeftIterT&  left_end,
0035                      const RightIterT& right_end)
0036         : _left(left), _right(right),
0037           _left_end(left_end), _right_end(right_end), _result(equal)
0038     {}
0039
0040     enum{nextboth, nextleft, nextright, stop};
0041
0042     enum
0043     {
0044         less    = comparison::less,
0045         equal   = comparison::equal,
0046         greater = comparison::greater
0047     };
0048
0049     int result()const{ return _result; }
0050
0051     bool covalues_are_equal(LeftIterT& left, RightIterT& right)
0052     {
0053         if(co_value<LeftT>(left) < co_value<RightT>(right))
0054             _result = less;
0055         if(co_value<RightT>(right) < co_value<LeftT>(left))
0056             _result = greater;
0057         return _result == equal;
0058     }
0059
0060     int proceed(LeftIterT& left, RightIterT& right)
0061     {
0062         if(upper_less(key_value<LeftT>(left), key_value<RightT>(right)))
0063         {
0064             _prior_left = left;
0065             ++left;
0066             return nextleft;
0067         }
0068         else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left)))
0069         {
0070             _prior_right = right;
0071             ++right;
0072             return nextright;
0073         }
0074         else
0075         {
0076             ++left;
0077             ++right;
0078             return nextboth;
0079         }
0080     }
0081
0082     int next_both(LeftIterT& left, RightIterT& right)
0083     {
0084         if(left == _left_end)
0085         {
0086             _result = (right == _right_end) ? equal : less;
0087             return stop;
0088         }
0089
0090         // left != _left_end
0091         if(right == _right_end)
0092         {
0093             _result = greater;
0094             return stop;
0095         }
0096
0097         // The starting intervals have to begin equally
0098         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
0099         {   // left: same A... = sameA...
0100             // right:same  B.. = sameB...
0101             _result = less;
0102             return stop;
0103         }
0104
0105         if(lower_less(key_value<LeftT>(right), key_value<RightT>(left)))
0106         {   // left: same  B.. = sameB...
0107             // right:same A... = sameA...
0108             _result = greater;
0109             return stop;
0110         }
0111
0112         if(_compare_codomain && !covalues_are_equal(left, right))
0113             return stop;
0114
0115         return proceed(left, right);
0116     }
0117
0118     int next_left(LeftIterT& left, RightIterT& right)
0119     {
0120         if(left == _left_end)
0121         {   // left: same
0122             // right:sameA...
0123             _result = less;
0124             return stop;
0125         }
0126
0127         if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left)))
0128         {   // left: same B = sameB...
0129             // right:sameA  = sameA...
0130             _result = greater;
0131             return stop;
0132         }
0133
0134         if(_compare_codomain && !covalues_are_equal(left, right))
0135             return stop;
0136
0137         return proceed(left, right);
0138     }
0139
0140     int next_right(LeftIterT& left, RightIterT& right)
0141     {
0142         if(right == _right_end)
0143         {   // left: sameA...
0144             // right:same
0145             _result = greater;
0146             return stop;
0147         }
0148
0149         if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right)))
0150         {
0151             // left: sameA... = sameA...
0152             // right:same B.. = sameB...
0153             _result = less;
0154             return stop;
0155         }
0156
0157         if(_compare_codomain && !covalues_are_equal(left, right))
0158             return stop;
0159
0160         return proceed(left, right);
0161     }
0162
0163 private:
0164     const LeftT&  _left;
0165     const RightT& _right;
0166     LeftIterT     _left_end;
0167     RightIterT    _right_end;
0168     LeftIterT     _prior_left;
0169     RightIterT    _prior_right;
0170     int           _result;
0171 };
0172
0173
0174
0175 template<class LeftT, class RightT>
0176 int element_compare
0177 (
0178     const LeftT& left,   //sub
0179     const RightT& right, //super
0180     typename LeftT::const_iterator  left_begin,
0181     typename LeftT::const_iterator  left_end,
0182     typename RightT::const_iterator right_begin,
0183     typename RightT::const_iterator right_end
0184 )
0185 {
0186     typedef element_comparer<LeftT,RightT> Step;
0187     Step step(left, right, left_end, right_end);
0188
0189     typename LeftT::const_iterator  left_  = left_begin;
0190     typename RightT::const_iterator right_ = right_begin;
0191
0192     int state = Step::nextboth;
0193     while(state != Step::stop)
0194     {
0195         switch(state){
0196         case Step::nextboth:  state = step.next_both (left_, right_); break;
0197         case Step::nextleft:  state = step.next_left (left_, right_); break;
0198         case Step::nextright: state = step.next_right(left_, right_); break;
0199         }
0200     }
0201     return step.result();
0202 }
0203
0204
0205 } // namespace Interval_Set
0206
0207 }} // namespace icl boost
0208
0209 #endif
0210