"werasm" <w_erasm@telkomsa.net> writes:

> - Are there iterator concepts modelling this kind of iterator? I can
> see some disadvantages, such as algorithms storing and incrementing a
> valid bidirectional iterator, expecting the algorithm to end when it
> reaches the end - therefore we would need a specialised container.

A legal forward (and therefore a bidirectional) iterator is not
allowed to visit the same object (as distinguished by its address)
twice when traversing a range.

  21.4/1:

  --- If a and b are both dereferenceable, then a == b if and only if
      *a and *b are the same object.

Your circular iterator can only be an input iterator (or use some new
iterator concepts for classification,
e.g. http://boost.org/libs/iterator/doc/index.html#new-style-iterators

HTH,

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

werasm wrote:
> Hi all,
>
> I recently had a problem where I found that writing an iterator adaptor
> that would wrap (to the beginning) when incremented to the end, would
> make my solution more efficient (instead of rotating) and copying into
> a new sequence. Something like this:
>
> CircularIter& operator++()
> { // preincrement
>   myIter_.operator++(); //Call underlying preincrement
>
>   if( myIter_ == mySeq_.end() )
>   {
>     myIter_ = mySeq.begin();
>   }
>   return (*this);
> }
>
> This would have allowed me to, for example, do the following (this
> applies for more than one container type, but for now I'll use list).
>
> typedef std::pair<float, float> AngleWeightPair;
> typedef std::list< AngleWeightPair > AngleWeightPairLst;
>
> Items in the list are sorted according to angle (degrees) in ascending
> order. Now I would want search from a minimum angle, clockwise (so to
> speak) to a maximum angle (excluding all other angles) for the position
> representing the smalles weight. Something like below:
>
> float getMinWeight( float angleIn )
> {
>   static const float halfSearchWindow( 23.f );
>   //TrimToRange returns a value from 0-360 degrees
>   const float minAngle( TrimToRange( angleIn-halfSearchWindow ) );
>
>   ClosestMatch minAngleMatch(
>     for_each( angleSeq_.begin(), angleSeq_.end(),
> ClosestMatch(angleSeq_, minAngle) ) );
>
>   const float maxAngle( TrimToRange( angleIn+halfSearchWindow ) );
>   ClosestMatch maxAngleMatch(
>     for_each( angleSeq_.begin(), angleSeq_.end(),
> ClosestMatch(angleSeq_, maxAngle) ) );
>   //[1] NOTE!!!! minAngleMatch may represent 359   , and maxAngleMatch
> 30   .
>   return for_each( minAngleMatch.pos(), maxAngleMatch.pos(),
> FindMinWeight() ).get();
> }
>
> The functor ClosestMatch always stores a valid iterator representing
> the position which differs from the incoming angle the least.
> FindMinWeight stores the value of the weight (second item) that is the
> least in the range.
>
> Now my observation:
> [1] This won't work, as we don't know whether minAngleMatch.pos is in
> actual fact before or after maxAngleMatch.pos - we could have known
> this if we had random access iterators, but this would cause tedious
> code - if min after max, copy from min to end, then from begin to
> max...
>
> If we had an iterator that was allowed to increment passed the end
> (terminating upon reaching itself only - considering itself as the end
> of the range), we would have breezed through this excersize. Now we
> need to, in the case of using a list as container, perform rotation and
> all kinds of funny exercises to solve this problem.
>
> - Are there iterator concepts modelling this kind of iterator? I can
> see some disadvantages, such as algorithms storing and incrementing a
> valid bidirectional iterator, expecting the algorithm to end when it
> reaches the end - therefore we would need a specialised container.
>
> - Are there C++ containers modelling this concept (of not having an end
> - circular)?
>
> - Are they considering this kind of concept for standards to come? If
> not, why not etc. :-)

I once put some effort into designing a circular list container. My
design goals were to meet the standard's applicable iterator and
container requirements, and to match the design of std::list as closely
as possible, while retaining circularity. You could iterate around the
circle as many times as you wished. It turned out to be quite feasible,
but I ran into one key issue: it had the property that begin() was
always equal to end(). The standard says that if a container is
empty,then begin()==end(). I haven't been able to find any place where
it says the converse: that if begin()==end(), then the container is
empty. Therefore, as far as the container requirements are concerned,
that's not a problem.

To be honest, I should mention that Valentin Bonnard claims that the
standard implies the converse in many different locations, but failed
to identify those locations. See
<http://groups.google.com/group/comp.std.c++/tree/browse_frm/thread/1c7a494914ced167/771d644a04c9b50c?rnum=1&hl=en&_done=%2Fgroup%2Fcomp.std.c%2B%2B%2Fbrowse_frm%2Fthread%2F1c7a494914ced167%2F56a324c579f07b13%3Flnk%3Dst%26q%3D%26rnum%3D1%26hl%3Den%26#doc_010c40a1a45b074c>

However, as a practical matter virtually every algorithm ever written
to take an iterator range assumes that [i,j) defines an empty range if
i==j. I figured out a way around that problem, by using a heavy
iterator. That iterator would contain a reference named 'parent' to the
container it came from, and a signed integer called winding_number. A
function named equal() compares two iterators based solely on what
element of the list they point at; operator==(i,j) is overloaded to
evaluate equal(i,j) && i.winding_number == j.winding_number.

Each time one of these iterators was iterated through the point where
equal(&self,parent.begin()) in the forward direction, it would
increment winding_number ; each time it was iterated past that point in
the reverse direction, it would decrement winding_number. end()
returned an iterator identical to begin(), except that if the circular
list was non-empty, end().winding_number==1, while
begin().winding_number==0.

This design violates the requirement that i==j if and only if *i and *j
refer to the same object. However, as a practical matter, that should
not be a problem so long as you never pass an iterator range to an
algorithm that winds more than one full time around the circular list.

I've never tested this design - I've never even fully implemented it;
but it should work. As I remember it, there were some tricky details
when defining splice(), though I don't remember what they were.


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

David Abrahams wrote:
> "werasm" <w_erasm@telkomsa.net> writes:

>
> A legal forward (and therefore a bidirectional) iterator is not
> allowed to visit the same object (as distinguished by its address)
> twice when traversing a range.

Yes, but for the purpose of the traversing (or performing an algorithm)
on a (sorted) sequence, the iterator only needs to consider itself as
an end to meet this requirement (doing this the same object will not be
visited more than once.

1) It would have a physical beginning - this could remain constant once
the sequence is established  - at construction only (therefore require
default constructor for items).
2) It would have a physical end - which could remain constant.
3) (--end() ) would refer to the last item.
4) (--begin() ) would also refer to the last item.
5) (++end() ) == (begin())
6) Iterators can actually never be invalidated (one needn't be that
strict though, but the idea is that the container would have a fixed
size).

A Circular buffer (boost) could suffice, apart from the fact that one
cannot increment past the end or decrement past the beginning. I
suppose the iterators used for this sequence will fall into a unique
category, yes.

>
>   21.4/1:
>
>   --- If a and b are both dereferenceable, then a == b if and only if
>       *a and *b are the same object.

Still applies...

>
> Your circular iterator can only be an input iterator (or use some new
> iterator concepts for classification,

Yes. I have looked at whether any of those iterators represented what I
was looking for. Is (*(++end()) ) valid for the "Incrementable Iterator
concept"?

A good example I can think of is a range of angle (mentioned
previously) where I would like to perform an algo on this part of the
sequence (indicate by square brackets):

{ 0,1,2,3 ] ,4,5,6,7,8,9....355,356,  [357,358,359}

Typically conventional iterators an containers don't give one this
ability, which is my problem. I do also realise that writing an
iterator adaptor that has this ability for a conventional container
would be dangerous, as algorithms may store and increment iterators
internally - the internal iterators for a conventional container would
give UB when incremented for this case (as you know).

I hope the example gives you some clarity - thanks for response.

Werner

> e.g. http://boost.org/libs/iterator/doc/index.html#new-style-iterators
>
> HTH,
>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

David Abrahams wrote:
> "werasm" <w_erasm@telkomsa.net> writes:
>
> > - Are there iterator concepts modelling this kind of iterator? I can
> > see some disadvantages, such as algorithms storing and incrementing a
> > valid bidirectional iterator, expecting the algorithm to end when it
> > reaches the end - therefore we would need a specialised container.
>
> A legal forward (and therefore a bidirectional) iterator is not
> allowed to visit the same object (as distinguished by its address)
> twice when traversing a range.
>
>   21.4/1:
>
>   --- If a and b are both dereferenceable, then a == b if and only if
>       *a and *b are the same object.

A circular iterator would simply "wrap around" to a previous value, so
there would never be more than one iterator value per element in the
container. So the above condition would still hold.

Essentially for a circular iterator, the following pair of statements
would hold true for iterators: a and b:

     a == b
     a == b  + n;

where n is the number of elements in the circular container. All of the
other random access iterator requirements would still be met. The only
anomaly would be that there would always be in every circular container
one iterator i for which the following was true:

    i > i++;

Although counter-intuitive, I see no reason why such an iterator would
be non-conforming.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

werasm wrote:

> //Now we search the entire sequence...
> find_if( someIter, someIter, predicate );

Sorry, somewhat flawed thinking over here as algo would terminated
before it started. For this case one could use a counter that
decrements each time the iterator comparison is equal - when the
counter becoms zero, the algo terminates. This could be ideal for
performing algorithms on ranges past the end (wrapping, so to speak).
As mentioned, it does violate the requirement that i==j if and only if
*i and *j refer to the same object, though.

Regards,

Werner

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kuyper@wizard.net wrote:

> I once put some effort into designing a circular list container. My
> design goals were to meet the standard's applicable iterator and
> container requirements, and to match the design of std::list as closely
> as possible, while retaining circularity. You could iterate around the
> circle as many times as you wished. It turned out to be quite feasible,
> but I ran into one key issue: it had the property that begin() was
> always equal to end(). The standard says that if a container is
> empty,then begin()==end(). I haven't been able to find any place where
> it says the converse: that if begin()==end(), then the container is
> empty. Therefore, as far as the container requirements are concerned,
> that's not a problem.

The fact that one is iterating from an item to itself (so to speak)
does not mean that the iterator refers to the physical beginning of the
container, and that the applicable iterator is also considered to be
the end. The container can still have a physical beginning and an end
(depicting its normal range). For this reason, what the standard says
may still hold - for the converse as well.

> However, as a practical matter virtually every algorithm ever written
> to take an iterator range assumes that [i,j) defines an empty range if
> i==j.

Yes, this prohibits one from searching the entire range, as the
algorithm would end immediately (As I now realize...sorry Dave :-).

> I figured out a way around that problem, by using a heavy
> iterator. That iterator would contain a reference named 'parent' to the
> container it came from, and a signed integer called winding_number. A
> function named equal() compares two iterators based solely on what
> element of the list they point at; operator==(i,j) is overloaded to
> evaluate equal(i,j) && i.winding_number == j.winding_number.

Yes, although when traversing the entire sequence, one would typically
traverse from beginning to end. The possibility of traversing to
oneself must be possible for consistency though, therefore:

//T just a placeholder...
void foo( T v1 )
{
  //Winding count of first would be zero.
  my_list<T>::iterator first( find( myList.begin(), myList.end(), v1 );
  int windingCount(1);
  my_list<T>::iterator last( first, windingCount );
  //Now we perform algo on range [first, last);
  for_each( first, last, ... );
}

This type of thing would certainly be conveniant for ranges where the
natural thing would be to search past the end (angle example). The only
problem that I see, is that one still needs to know where first is in
relation to second (before or after). This need not be a problem (but
requires care - see example:

//We don't know how v1 and v2 relates (which one comes first)
void foo( T v1, T v2 )
{
  {
  my_list<T>::iterator first( find( myList.begin(), myList.end(), v1 )
);
  my_list<T>::iterator last( find( myList.begin(), myList.end(), v2 )
);

  //Now we perform algo on range [first, last);
  for_each( first, last, ... );
  //...Oops, was last behind first - what was its windingcount,
  // would it terminate?
  }

  {
  //but this would work
  my_list<T>::iterator first( find( myList.begin(), myList.end(), v1 )
);
  //One indicating winding count, the returned value being relative to
  // first - this would work great!
  my_list<T>::iterator last( find( first, my_list<T>::iterator( first,
1) , v2 ) );

  //Now we perform algo on range [first, last) - no problem...
  for_each( first, last, ... );
  }
}

> This design violates the requirement that i==j if and only if *i and *j
> refer to the same object.

Afraid so. Is the requirement perhaps too restrictive?

Something else came to my mind suddenly - how about an isEqualCount
that decrements? Everytime a comparison is equal, one is subtracted,
when the isEqualCount becomes zero, i==j and algo terminates. This
would make things easier. Now we don't need to know the relative
positions anymore.

int isEqualCount( 1 );

my_list<T>::iterator j( i, isEqualCount);

find( i, j, value );

Terminates when isEqualCount is zero and (*i == *j) .


Kind regards,

Werner

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

David Abrahams ha scritto:
> "werasm" <w_erasm@telkomsa.net> writes:
>
>> - Are there iterator concepts modelling this kind of iterator? I can
>> see some disadvantages, such as algorithms storing and incrementing a
>> valid bidirectional iterator, expecting the algorithm to end when it
>> reaches the end - therefore we would need a specialised container.
>
> A legal forward (and therefore a bidirectional) iterator is not
> allowed to visit the same object (as distinguished by its address)
> twice when traversing a range.
>
>   21.4/1:
>
>   --- If a and b are both dereferenceable, then a == b if and only if
>       *a and *b are the same object.
>
> Your circular iterator can only be an input iterator (or use some new
> iterator concepts for classification,
> e.g. http://boost.org/libs/iterator/doc/index.html#new-style-iterators
>

Using kuyper's "winding_number" idea, it should be quite easy to design
some kind of iterator adaptor that would implements some kind of
circular traversal. Let's forget the current standard and focus on the
new iterator concept proposal: how would such iterator classify?

First of all, in order for the circular iterator to make sense, we need
the "base" iterator to provide at least forward traversal. Let's assume
that.

If I understand the proposal enough, there wouldn't be any problem with
the traversal of the circular-ized iterator, in the sense that it would
provide the same traversal as the original. We don't actually need a
"circular traversal iterator" concept.

No problem with being a readable iterator, because the requirement "If a
== b then *a is equivalent to *b" is satisfied.

The only thing that goes wrong is about the Writable requirement. If
fact we could have a != b yet *a could refer to the same object as *b
(that would be the case when two iterators points to same object while
having different winding_number).

So our iterator would fit the framework nicely, but it won't be
Writable... Well... yet it looks like being writable, isn't it?

What if we relaxed the "Writable" concept? Do we really need the "a == b
if and only if *a is the same object as *b" requirement? In a few cases,
the requirement is actually not necessary in its full strength. For
example, std::fill is said to require a Writable iterator. In fact I
can't see any problem in feeding it a "relaxed-Writable" iterator
provided the one-to-one requirement is valid at least for each iterator
*in the given range*.

So what about removing the one-to-one requirement from the Writable
concept and making it a precondition about the range of the algorithms?

Hope it make sense,

Ganesh

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hi all,

I recently had a problem where I found that writing an iterator adaptor
that would wrap (to the beginning) when incremented to the end, would
make my solution more efficient (instead of rotating) and copying into
a new sequence. Something like this:

CircularIter& operator++()
{ // preincrement
  myIter_.operator++(); //Call underlying preincrement

  if( myIter_ == mySeq_.end() )
  {
    myIter_ = mySeq.begin();
  }
  return (*this);
}

This would have allowed me to, for example, do the following (this
applies for more than one container type, but for now I'll use list).

typedef std::pair<float, float> AngleWeightPair;
typedef std::list< AngleWeightPair > AngleWeightPairLst;

Items in the list are sorted according to angle (degrees) in ascending
order. Now I would want search from a minimum angle, clockwise (so to
speak) to a maximum angle (excluding all other angles) for the position
representing the smalles weight. Something like below:

float getMinWeight( float angleIn )
{
  static const float halfSearchWindow( 23.f );
  //TrimToRange returns a value from 0-360 degrees
  const float minAngle( TrimToRange( angleIn-halfSearchWindow ) );

  ClosestMatch minAngleMatch(
    for_each( angleSeq_.begin(), angleSeq_.end(),
ClosestMatch(angleSeq_, minAngle) ) );

  const float maxAngle( TrimToRange( angleIn+halfSearchWindow ) );
  ClosestMatch maxAngleMatch(
    for_each( angleSeq_.begin(), angleSeq_.end(),
ClosestMatch(angleSeq_, maxAngle) ) );
  //[1] NOTE!!!! minAngleMatch may represent 359   , and maxAngleMatch
30   .
  return for_each( minAngleMatch.pos(), maxAngleMatch.pos(),
FindMinWeight() ).get();
}

The functor ClosestMatch always stores a valid iterator representing
the position which differs from the incoming angle the least.
FindMinWeight stores the value of the weight (second item) that is the
least in the range.

Now my observation:
[1] This won't work, as we don't know whether minAngleMatch.pos is in
actual fact before or after maxAngleMatch.pos - we could have known
this if we had random access iterators, but this would cause tedious
code - if min after max, copy from min to end, then from begin to
max...

If we had an iterator that was allowed to increment passed the end
(terminating upon reaching itself only - considering itself as the end
of the range), we would have breezed through this excersize. Now we
need to, in the case of using a list as container, perform rotation and
all kinds of funny exercises to solve this problem.

- Are there iterator concepts modelling this kind of iterator? I can
see some disadvantages, such as algorithms storing and incrementing a
valid bidirectional iterator, expecting the algorithm to end when it
reaches the end - therefore we would need a specialised container.

- Are there C++ containers modelling this concept (of not having an end
- circular)?

- Are they considering this kind of concept for standards to come? If
not, why not etc. :-)

Kind regards,

Werner


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

werasm wrote:
> Hi all,
>
> I recently had a problem where I found that writing an iterator adaptor
> that would wrap (to the beginning) when incremented to the end, would
> make my solution more efficient (instead of rotating) and copying into
> a new sequence. Something like this:
>
> CircularIter& operator++()
> { // preincrement
>   myIter_.operator++(); //Call underlying preincrement
>
>   if( myIter_ == mySeq_.end() )
>   {
>     myIter_ = mySeq.begin();
>   }
>   return (*this);
> }
>
.
> - Are there C++ containers modelling this concept (of not having an end
> - circular)?
>
> - Are they considering this kind of concept for standards to come? If
> not, why not etc. :-)

It sounds very much like you are describing a circular buffer - a type
of buffer that tends to minimize copying operations when reading and
writing large amounts of data. See
http://en.wikipedia.org/wiki/Circular_buffer.

There is indeed a C++ implementation of a STL-compliant circular buffer
that appears to be ready for a formal boost review. See
http://boost.cvs.sourceforge.net/*checkout*/boost-sandbox/boost-sandbox/libs/circular_buffer/doc/circular_buffer.html.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:

> It sounds very much like you are describing a circular buffer - a type
> of buffer that tends to minimize copying operations when reading and
> writing large amounts of data. See
> http://en.wikipedia.org/wiki/Circular_buffer.

I'm aware of this concept.

>
> There is indeed a C++ implementation of a STL-compliant circular buffer
> that appears to be ready for a formal boost review. See

Unfortunately it has the following caveat - Quote:

"While internals of a circular_buffer are circular, iterators are not.
Iterators of a circular_buffer are only valid for the range [begin(),
end()] . E.g. iterators (begin() - 1) and (end() + 1) are invalid."

This would still mean that incrementing an iterator past the end is not
valid. One would want to know (in a circular buffer) where the logical
end is (IMHO) for performing algorithms with half-open ranges, but you
would like to be able to increment passed the end (effectively wrap)
for cases like the one I've mentioned. To prevent an algorithm from not
terminating, an iterator could then use itself as the end.

Example (assuming random access):

// We don't know whether someIter - 50 is before
// begin() or not, and we don't care...
find_if( someIter, someIter - 50, predicate ); //or ...

//Now we search the entire sequence...
find_if( someIter, someIter, predicate );

End remains end, and begin remains begin, but as the container is
circular, searching over the limits does not matter - handy for the
following sequence (angles).

[0...359]

What if I'm interested in performing algo on range [350...10], now I
can't use conventional iterators, and need to write (more) tedious
code...

Regards,

Werner

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]