| /*-----------------------------------------------------------------------------+ |
| Copyright (c) 2008-2009: Joachim Faulhaber |
| +------------------------------------------------------------------------------+ |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENCE.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| +-----------------------------------------------------------------------------*/ |
| #ifndef BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202 |
| #define BOOST_ICL_ELEMENT_COMPARER_HPP_JOFA_090202 |
| |
| #include <boost/mpl/and.hpp> |
| #include <boost/icl/type_traits/is_map.hpp> |
| #include <boost/icl/detail/notate.hpp> |
| #include <boost/icl/type_traits/identity_element.hpp> |
| |
| namespace boost{namespace icl |
| { |
| |
| namespace Interval_Set |
| { |
| |
| template<class LeftT, class RightT> |
| class element_comparer |
| { |
| public: |
| typedef typename LeftT::const_iterator LeftIterT; |
| typedef typename RightT::const_iterator RightIterT; |
| |
| BOOST_STATIC_CONSTANT(bool, |
| _compare_codomain = (mpl::and_<is_map<LeftT>, is_map<RightT> >::value)); |
| |
| element_comparer(const LeftT& left, |
| const RightT& right, |
| const LeftIterT& left_end, |
| const RightIterT& right_end) |
| : _left(left), _right(right), |
| _left_end(left_end), _right_end(right_end), _result(equal) |
| {} |
| |
| enum{nextboth, nextleft, nextright, stop}; |
| |
| enum |
| { |
| less = comparison::less, |
| equal = comparison::equal, |
| greater = comparison::greater |
| }; |
| |
| int result()const{ return _result; } |
| |
| bool covalues_are_equal(LeftIterT& left, RightIterT& right) |
| { |
| if(co_value<LeftT>(left) < co_value<RightT>(right)) |
| _result = less; |
| if(co_value<RightT>(right) < co_value<LeftT>(left)) |
| _result = greater; |
| return _result == equal; |
| } |
| |
| int proceed(LeftIterT& left, RightIterT& right) |
| { |
| if(upper_less(key_value<LeftT>(left), key_value<RightT>(right))) |
| { |
| _prior_left = left; |
| ++left; |
| return nextleft; |
| } |
| else if(upper_less(key_value<RightT>(right), key_value<LeftT>(left))) |
| { |
| _prior_right = right; |
| ++right; |
| return nextright; |
| } |
| else |
| { |
| ++left; |
| ++right; |
| return nextboth; |
| } |
| } |
| |
| int next_both(LeftIterT& left, RightIterT& right) |
| { |
| if(left == _left_end) |
| { |
| _result = (right == _right_end) ? equal : less; |
| return stop; |
| } |
| |
| // left != _left_end |
| if(right == _right_end) |
| { |
| _result = greater; |
| return stop; |
| } |
| |
| // The starting intervals have to begin equally |
| if(lower_less(key_value<LeftT>(left), key_value<RightT>(right))) |
| { // left: same A... = sameA... |
| // right:same B.. = sameB... |
| _result = less; |
| return stop; |
| } |
| |
| if(lower_less(key_value<LeftT>(right), key_value<RightT>(left))) |
| { // left: same B.. = sameB... |
| // right:same A... = sameA... |
| _result = greater; |
| return stop; |
| } |
| |
| if(_compare_codomain && !covalues_are_equal(left, right)) |
| return stop; |
| |
| return proceed(left, right); |
| } |
| |
| int next_left(LeftIterT& left, RightIterT& right) |
| { |
| if(left == _left_end) |
| { // left: same |
| // right:sameA... |
| _result = less; |
| return stop; |
| } |
| |
| if(!key_value<LeftT>(_prior_left).touches(key_value<LeftT>(left))) |
| { // left: same B = sameB... |
| // right:sameA = sameA... |
| _result = greater; |
| return stop; |
| } |
| |
| if(_compare_codomain && !covalues_are_equal(left, right)) |
| return stop; |
| |
| return proceed(left, right); |
| } |
| |
| int next_right(LeftIterT& left, RightIterT& right) |
| { |
| if(right == _right_end) |
| { // left: sameA... |
| // right:same |
| _result = greater; |
| return stop; |
| } |
| |
| if(!key_value<RightT>(_prior_right).touches(key_value<RightT>(right))) |
| { |
| // left: sameA... = sameA... |
| // right:same B.. = sameB... |
| _result = less; |
| return stop; |
| } |
| |
| if(_compare_codomain && !covalues_are_equal(left, right)) |
| return stop; |
| |
| return proceed(left, right); |
| } |
| |
| private: |
| const LeftT& _left; |
| const RightT& _right; |
| LeftIterT _left_end; |
| RightIterT _right_end; |
| LeftIterT _prior_left; |
| RightIterT _prior_right; |
| int _result; |
| }; |
| |
| |
| |
| template<class LeftT, class RightT> |
| int element_compare |
| ( |
| const LeftT& left, //sub |
| const RightT& right, //super |
| typename LeftT::const_iterator left_begin, |
| typename LeftT::const_iterator left_end, |
| typename RightT::const_iterator right_begin, |
| typename RightT::const_iterator right_end |
| ) |
| { |
| typedef element_comparer<LeftT,RightT> Step; |
| Step step(left, right, left_end, right_end); |
| |
| typename LeftT::const_iterator left_ = left_begin; |
| typename RightT::const_iterator right_ = right_begin; |
| |
| int state = Step::nextboth; |
| while(state != Step::stop) |
| { |
| switch(state){ |
| case Step::nextboth: state = step.next_both (left_, right_); break; |
| case Step::nextleft: state = step.next_left (left_, right_); break; |
| case Step::nextright: state = step.next_right(left_, right_); break; |
| } |
| } |
| return step.result(); |
| } |
| |
| |
| } // namespace Interval_Set |
| |
| }} // namespace icl boost |
| |
| #endif |
| |