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_ELEMENT_COMPARER_HPP_JOFA_090202
Chris@16: #define BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202
Chris@16: 
Chris@16: #include <boost/mpl/and.hpp>
Chris@16: #include <boost/icl/type_traits/is_map.hpp>
Chris@16: #include <boost/icl/detail/notate.hpp>
Chris@16: #include <boost/icl/type_traits/identity_element.hpp>
Chris@16: 
Chris@16: namespace boost{namespace icl
Chris@16: {
Chris@16: 
Chris@16: namespace Interval_Set
Chris@16: {
Chris@16: 
Chris@16: template<class LeftT, class RightT>
Chris@16: class element_comparer
Chris@16: {
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:     element_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:         less    = comparison::less, 
Chris@16:         equal   = comparison::equal, 
Chris@16:         greater = comparison::greater
Chris@16:     };
Chris@16: 
Chris@16:     int result()const{ return _result; }
Chris@16: 
Chris@16:     bool covalues_are_equal(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         if(co_value<LeftT>(left) < co_value<RightT>(right))
Chris@16:             _result = less;
Chris@16:         if(co_value<RightT>(right) < co_value<LeftT>(left))
Chris@16:             _result = greater;
Chris@16:         return _result == equal;
Chris@16:     }
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:         {
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:         {
Chris@16:             _prior_right = right;
Chris@16:             ++right;
Chris@16:             return nextright;
Chris@16:         }
Chris@16:         else
Chris@16:         {
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)
Chris@16:         {
Chris@16:             _result = (right == _right_end) ? equal : less;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         // left != _left_end
Chris@16:         if(right == _right_end)
Chris@16:         {
Chris@16:             _result = greater;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         // The starting intervals have to begin equally
Chris@16:         if(lower_less(key_value<LeftT>(left), key_value<RightT>(right)))
Chris@16:         {   // left: same A... = sameA...
Chris@16:             // right:same  B.. = sameB...
Chris@16:             _result = less;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(lower_less(key_value<LeftT>(right), key_value<RightT>(left)))
Chris@16:         {   // left: same  B.. = sameB...
Chris@16:             // right:same A... = sameA...
Chris@16:             _result = greater;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(_compare_codomain && !covalues_are_equal(left, right))
Chris@16:             return stop;
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: same
Chris@16:             // right:sameA...
Chris@16:             _result = less;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left)))
Chris@16:         {   // left: same B = sameB...
Chris@16:             // right:sameA  = sameA...
Chris@16:             _result = greater;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(_compare_codomain && !covalues_are_equal(left, right))
Chris@16:             return stop;
Chris@16: 
Chris@16:         return proceed(left, right);
Chris@16:     }
Chris@16: 
Chris@16:     int next_right(LeftIterT& left, RightIterT& right)
Chris@16:     {
Chris@16:         if(right == _right_end)
Chris@16:         {   // left: sameA...
Chris@16:             // right:same
Chris@16:             _result = greater;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right)))
Chris@16:         {
Chris@16:             // left: sameA... = sameA...
Chris@16:             // right:same B.. = sameB...
Chris@16:             _result = less;
Chris@16:             return stop;
Chris@16:         }
Chris@16: 
Chris@16:         if(_compare_codomain && !covalues_are_equal(left, right))
Chris@16:             return stop;
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: template<class LeftT, class RightT>
Chris@16: int element_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 element_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: }} // namespace icl boost
Chris@16: 
Chris@16: #endif 
Chris@16: