Re: [boost] [odeint] Iterator semantics

Subject: Re: [boost] [odeint] Iterator semantics
From: Karsten Ahnert (karsten.ahnert_at_[hidden])
Date: 2012-08-10 09:19:15

>>>>> So you are checking for overlap. This looks good and I think 
>>>>> it should work.
>>>> 
>>>> If I'm understanding correctly what you're saying, making two 
>>>> iterators equal if their underlying time ranges overlap would 
>>>> be "evil." Your equality operator would not be transitive, and 
>>>> thus not an equivalence relation, and therefore you would not 
>>>> have implemented a conforming iterator, and you'd have no
>>>> right to expect an algorithm that works on iterators to work
>>>> on yours.
>>> 
[snip]

> 
> I think already found a solution. The end iterator is marked as end
> (it has a flag m_end). Then, two iterators are equal if theirs flags
> are equal, or if the flags is not equal the time of the first
> iterator must be smaller then the time of the end iterator:
> 
> bool equal( iterator other ) const { if( m_end == other.m_end )
> return true; else { return ( m_end ) ? ( other.m_time < m_time ) : (
> m_time < other.m_time ); } }
> 
> This iterator is a single pass iterator, for example it is similar
> to the istream_iterator.

I analyzed the problem once more and it turned out that the iterator is
not transitive. The problem is the following: a range consist of a begin
and an end iterator. The end iterator is flagged as end is not
dereferencable and can not be incremented. When two iterator of the same
type (end-end, begin-begin) are compared to each other they are equal
(neither of both should be incremented). If iterators of different types
are compared it is checked that the time of the begin iterator is
greater then the time of the end iterator. The violation of transitivity
might now occur if two end iterators and one begin iterator are
compared. The two end iterators are always equal, which is not true for
the comparison of the begin iterator with the end iterators.

I tried to find different solutions but it is difficult since one is
more or less always checking for overlap. On the other hand I wonder if
the requirement of transitivity can be relaxed in this case. I can not
imagine an algorithm where the above situation might occur. The iterator
is a single pass iterator which limits the number of possible
algorithms. Furthermore the violation can only appear if two end
iterators are used. This is not the case for all algorithms in the
standard and Boost.Range.

Any ideas or comments? Is it really necessary to require transitivity?