/*-----------------------------------------------------------------------------+ | |
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 | |