Re: [boost] Ranges

From: Richard Peters (R.A.Peters_at_[hidden])
Date: 2002-02-10 13:29:57

----- Original Message -----
From: "David Abrahams" <david.abrahams_at_[hidden]>
> ----- Original Message -----
> From: "Richard Peters" <R.A.Peters_at_[hidden]>
> >
> Your aim, AFAICS, is to make iterator ranges. Mine was to make generalized
> half-open ranges. Since iterator ranges are just a subset of generalized
> ranges, it seems like a win to shoot for the generalized model.

Yes, I realize that difference in our aims now. My aim is to provide a way
to coveniently work with
ranges of iterators, and easily make ranges from containers. I'd like to end
up with the possibility of doing for_each(SomeVector, ...)
I'd love to see if there is a mid-way between iterator ranges and general
(half-open?) ranges. Shall we name them iterator_range and value_range while
discussing, to make the distinction where necessary?
On a sidenote, IMHO iterator_ranges are more important _to the stl_ because
all algorithms work with two iterators where they actually mean a range.

Ok, so we'd like to make a general half-open class. Let's start all over. I
see two options here:
- Make an iterator_range and make it work with values too. This could be
done by loading a counting_iterator or some other sort of iterator that can
hold any valuetype into the iterators. If the iterator is not traversable,
some functions like size() would not be present, but that doesn't matter.
- Make a value_range and make it work with iterators. In that case, the
valuetype is iterator, and there would be functions like size() that assume
the valuetype is an iterator.

In the case of the value_range, you could store the value in
counting_iterators, so that you can iterator over the range.

My preference is to make an iterator_range:
If you only need to store values specifying [begin, end), you can fill in a
counting_iterator or something like that, and not use functions that
traverse through the range.
An iterator doesn't necessarily traverse through ranges. They are used that
way, but we could see iterators as just pointing at/holding values. Seen in
that way, a iterator_range is a range pointing out the two boundary values.
And there we have iterator_range being a value_range.

I see a problem with starting out with value_ranges. Suppose: -we have a
value_range, specifing the range [0, 5). -we have generalised the
value_range so that it support some iterator operations. -we have a
value_range, holding two iterators, the two iterators specify the range [0,
5). [--end suppose] Then, we want to copy both ranges to a destination. They
both hold [0, 5) so you'd expect that copy works on both. However, either
copy dereferences the valuetype, then it can copy the value_range holding
the iterators, but it can't copy the value_range holding just the values, or
copy doesn't derefernce the valuetype, in that case copy works on the
value_range holding the values, but it doesn't work on the value_range
holding the iterators.

I see a problem with starting out with iterator_range, but this time I have
a solution. Suppose -we want a range of floating point values, [0, 5). -we
have two members begin() and end(), begin() returns an iterator holding the
float 0, end() returns an iterator holding the float 5. -we have two members
of iterator_range, front() return *begin() and back() returning
*prior(end()). [--end suppose] Then, what does back() return? normally, it
would return 4. In floating point types, however, 4.5 would still be in [0,
5). What we actually want is to make back() returning *end(). Why? We
actually have the range [0, 5] where the last value isn't in the range.
Implementations that know this, query the back() and keep in mind that this
value doesn't belong to the range, but everything less does.
Possible solution: In half open ranges, we can not guarantee that
*prior(end()) is the last value. We can guarantee however, that when end()
is dereferenceable, that *end() is the least upper bound of the range. We
could change the behaviour of back() in the following way: reference
back(bool Open = true) { return *(end() - (difference_type)Open);
Implementations of algorithms can now specify: -I want an open range, -I
want an open range where end() is dereferenceable, -I want a closed range.
The first case is the most common one, just calls back(). The second and
third one call back(false), where the second one takes into account that the
value actually doesn't belong to the range. Front() could be modified the
same way, then we have the choice of treating the iterator_range as closed,
open, half-open or half-closed.

Value_range doesn't have this problem, because you can already just access
the first and last value. It's up to implementations to treat this as
closed, open, half-open or half-closed.

I hope your favorite is still to first make a value_range and to make that
one work with iterators. That would mean we have a more thorough research of
both possibilities and we'll end up with a better solution :)

---
Richard Peters
Eindhoven University of Technology