Backward Iterators

[me22]

Since Dean is looking for some activity, I thought I'd raise a
question I thought up while pondering Alexandrescu's ranges:

Why are there no BackwardIterators?

For instance, reverse_copy currently is spec'ed as reverse_copy(Bidi,
Bidi, Output), where it would clearly work as reverse_copy(Backward,
Backward, Output). Similarly, copy_backward(Bidi, Bidi, Bidi) has a
far higher concept weight than its forward version, copy(Input, Input,
Output). (In fact, both would prefer a BackwardInputIterator.)

Where would this be useful? I would like to make a general trie, but
the only cheap kind of iterator for the stored sequences would be
BackwardIterators (which would follow parent pointers in the trie).

Thoughts?
~ Scott

[Dean Michael Berris]

Hi Scott!

It's been a while. :D

On Tue, Dec 15, 2009 at 3:13 AM, me22 <me2...@gmail.com> wrote:
> Since Dean is looking for some activity, I thought I'd raise a
> question I thought up while pondering Alexandrescu's ranges:
>
> Why are there no BackwardIterators?
>

What is the difference between a BackwardIterator and a
ForwardIterator derived from a ReversedRange (in the Boost.Range
sense)?

> For instance, reverse_copy currently is spec'ed as reverse_copy(Bidi,
> Bidi, Output), where it would clearly work as reverse_copy(Backward,
> Backward, Output).  Similarly, copy_backward(Bidi, Bidi, Bidi) has a
> far higher concept weight than its forward version, copy(Input, Input,
> Output).  (In fact, both would prefer a BackwardInputIterator.)
>

Have you read Stepanov & McJones' Elements of Programming? If let's
say you have a Range concept which had sentinels that marked the
"before the start" and "past the end", then an algorithm like 'copy'
would look like this:

template <class InputRange, class OutputRange>
requires WriteableForwardRange<OutputRange>
&& ForwardTraversable<InputRange>
OutputRange copy (InputRange input, OutputRange output) {
while (!empty(input)) push(output, front_pop(input));
return output;
}

In this case all you need to do is create a reversed input range from
the container that would start from the "past-end" sentinel and every
time you front_pop, your range would shrink by one.

> Where would this be useful?  I would like to make a general trie, but
> the only cheap kind of iterator for the stored sequences would be
> BackwardIterators (which would follow parent pointers in the trie).
>

If you support the sentinel-based Range concept I describe (along with
Alexandrescu's assertion that ranges are the primitive) this can
definitely be done. It would be interesting to see an STL implemented
in Range primites instead of Iterators. ;)

I hope this makes sense. :D

--
Dean Michael Berris
blog.cplusplus-soup.com | twitter.com/mikhailberis
linkedin.com/in/mikhailberis | facebook.com/dean.berris | deanberris.com

[me22]

2009/12/14 Dean Michael Berris <mikhai...@gmail.com>:

>
> What is the difference between a BackwardIterator and a
> ForwardIterator derived from a ReversedRange (in the Boost.Range
> sense)?
>

A BackwardIterator provides operator-- instead of operator++.

In the Alexandrescu sense, ignoring the OnePass ranges (which I've
always hated):

interface SillyRange {
bool empty();
}

interface ForwardRange : SillyRange {
Ref<T> front();
void popFront();
}

interface BackwardRange : SillyRange{
Ref<T> front();
void popFront();
}

interface BidirectionalRange : ForwardRange, BackwardRange {
}

(Compare to http://www.informit.com/articles/printerfriendly.aspx?p=1407357 )

>
> Have you read Stepanov & McJones' Elements of Programming?

It's in a box behind me, waiting for the holidays :P

I wouldn't be surprised if they've thought all this through already...

>
> In this case all you need to do is create a reversed input range from
> the container that would start from the "past-end" sentinel and every
> time you front_pop, your range would shrink by one.
>

But that's the type of the range you reversed to get a ForwardTraversable range?

>
> If you support the sentinel-based Range concept I describe (along with
> Alexandrescu's assertion that ranges are the primitive) this can
> definitely be done. It would be interesting to see an STL implemented

> in Range primitives instead of Iterators. ;)
>

I've started on one, actually, though I'm calling the primitives
"Views" and "Streams" instead of "Ranges", since I disagree on some of
the choices for fundamental operations and think that C++ has a better
way of handling OnePass ranges than requiring all ranges to have
reference semantics by default.

But that's another story.

>
> I hope this makes sense. :D
>

I'm thinking I wasn't clear enough.

Suppose I make a trie class that I can use something like this:

trie<char> tc;
tc.insert(cstring_range("hello"));
tc.insert(cstring_range("hey"));
auto x = tc.front(); // x is a trie_range<char>, essentially

Now I have to implement that trie_range somehow. If I have a pointer
to the 'e' node in the trie, I can't know how to go forward -- to 'l'
or 'y' -- but going backwards I obviously go to the 'h' node by
following the parent pointer. That means it can't be a
BidirectionalRange, the only kind that std::reverse_iterator, boost's
ReversedRange, and Alexandrescu's Retro<> are designed to use.

So I could certainly return a ForwardRange, but that's conceptually
backwards from what was inserted in the first place.

string s{x};
assert(s == "olleh");

I want a trie_range to be a BackwardRange such that the code above
doesn't even compile*. If people don't mind getting it out backwards,
they could reverse the backward range:

string s{reverse(x)};
assert(s == "olleh");

Or, if they just need to compare with things:

string s = "hello";
assert(equal(s.all(), reverse(x)));
assert(equal_backward(reverse(s.all()), x));

At the same time, things like deque or list can have constructors from
both Forward and Backward ranges:

deque<char> d{x};

Or construction could be done explicitly:

list<char> lc = ...;
reverse_copy(x, front_inserter(lc));

Does that make more sense?

Also, here's a follow-up issue to ponder:

Alexandrescu has pointed out that infinite ranges are perfectly
plausible. The range of Natural numbers {0, 1, 2, 3, ...} is an
obvious well-behaved candidate, as it can trivially provide both a
random-access popFront(n) and an op[](i). What if you reverse it,
though? popBack(n) is a simple thing to provide, but how would
op[](i) work? It'll have to call op[](f(i)), so f must be an
involution in order for reverse(reverse(x)) to be the same as x, but
which involution? Retro<> uses size()-i, but that obviously doesn't
work with infinite ranges.

The only nice one I can come up with is the bitwise 2's complement**.
That means, though, that every backward range would have to allow
v[-1] === v.back(), and that op[]'s parameter becomes fundamentally
signed, whereas currently it's unsigned. Does that mean that op[] is
a bad fundamental operation for random-access?

~ Scott

* string and vector could, of course, have constructors from
BackwardRanges that also provide a size.

** The twos-complement op[] works particularly nicely with an infinite
bidirectional range of integers {0, 1, 2, 3, ..., -4, -3, -2, -1},
where op[](i) == i. Note that that's the same identity as there was
with naturals, just there it only worked for non-negative numbers.

[Dean Michael Berris]

On Tue, Dec 15, 2009 at 7:23 AM, me22 <me2...@gmail.com> wrote:
>
> 2009/12/14 Dean Michael Berris <mikhai...@gmail.com>:
> >
> > What is the difference between a BackwardIterator and a
> > ForwardIterator derived from a ReversedRange (in the Boost.Range
> > sense)?
> >
>
> A BackwardIterator provides operator-- instead of operator++.
>

Hmmm... That's not a big fundamental difference.

> In the Alexandrescu sense, ignoring the OnePass ranges (which I've
> always hated):
>
> interface SillyRange {
>   bool empty();
> }
>
> interface ForwardRange : SillyRange {
>   Ref<T> front();
>   void popFront();
> }
>
> interface BackwardRange : SillyRange{
>   Ref<T> front();
>   void popFront();
> }
>
> interface BidirectionalRange : ForwardRange, BackwardRange {
> }
>
> (Compare to http://www.informit.com/articles/printerfriendly.aspx?p=1407357 )
>

This doesn't look like C++ to me -- this is in D?

> >
> > Have you read Stepanov & McJones' Elements of Programming?
>
> It's in a box behind me, waiting for the holidays :P

Great read. It will make your holidays worth reading. Although you
might want to keep a math reference book close by. :D

>
> I wouldn't be surprised if they've thought all this through already...
>

Actually, they present a means of dealing with non-linear data
structure traversal using half-open ranges still made up of Iterators.
They present a means of traversing a binary tree with parent links too
using a different definition of Iterator concepts from what the
current STL has.

> >
> > In this case all you need to do is create a reversed input range from
> > the container that would start from the "past-end" sentinel and every
> > time you front_pop, your range would shrink by one.
> >
>
> But that's the type of the range you reversed to get a ForwardTraversable range?
>

If you have sentinels to mark your data structure bounds and use that
to implement the reverse operation (assuming you actually have optimal
storage to store just one direction links -- in tries, you'd have the
parent link) then you can provably traverse the data structure using
normal forward traversal algorithms -- but your range should implement
the reverse internally. Something like:

container c;
auto r = reverse(c.all());

Then you can apply the normal forward traversal on the range just like
you will any other range that can be traversed in one direction. That
immediately makes your range usable in other algorithms without
creating a special type of Iterator or Range.

> >
> > If you support the sentinel-based Range concept I describe (along with
> > Alexandrescu's assertion that ranges are the primitive) this can
> > definitely be done. It would be interesting to see an STL implemented
> > in Range primitives instead of Iterators. ;)
> >
>
> I've started on one, actually, though I'm calling the primitives
> "Views" and "Streams" instead of "Ranges", since I disagree on some of
> the choices for fundamental operations and think that C++ has a better
> way of handling OnePass ranges than requiring all ranges to have
> reference semantics by default.
>
> But that's another story.
>

That'd be an interesting story indeed. I've been thinking about a
Boost.Proto based expression template means of representing and
dealing with lazy ranges. Basically something that allow constructs
like this (ala Boost.Spirit):

auto r = c.all() | (_1 % 2 == 0);

And eventually more complex constructs. In the meantime I'm
concentrating on cpp-netlib and memcache++ because some current
projects need both those libraries. Maybe later we can talk more about
implementing a range-based generic algorithms library. :)

> >
> > I hope this makes sense. :D
> >
>
> I'm thinking I wasn't clear enough.
>
> Suppose I make a trie class that I can use something like this:
>
>    trie<char> tc;
>    tc.insert(cstring_range("hello"));
>    tc.insert(cstring_range("hey"));
>    auto x = tc.front(); // x is a trie_range<char>, essentially
>
> Now I have to implement that trie_range somehow.  If I have a pointer
> to the 'e' node in the trie, I can't know how to go forward -- to 'l'
> or 'y' -- but going backwards I obviously go to the 'h' node by
> following the parent pointer.  That means it can't be a
> BidirectionalRange, the only kind that std::reverse_iterator, boost's
> ReversedRange, and Alexandrescu's Retro<> are designed to use.
>
> So I could certainly return a ForwardRange, but that's conceptually
> backwards from what was inserted in the first place.
>
>    string s{x};
>    assert(s == "olleh");
>

What if by default your ForwardRange from the trie data structure is
reversed? It models the ForwardRange semantics, but the traversal is
only one-direction (or moving forward).

> I want a trie_range to be a BackwardRange such that the code above
> doesn't even compile*.  If people don't mind getting it out backwards,
> they could reverse the backward range:
>
>    string s{reverse(x)};
>    assert(s == "olleh");
>
> Or, if they just need to compare with things:
>
>    string s = "hello";
>    assert(equal(s.all(), reverse(x)));
>    assert(equal_backward(reverse(s.all()), x));
>
> At the same time, things like deque or list can have constructors from
> both Forward and Backward ranges:
>
>    deque<char> d{x};
>
> Or construction could be done explicitly:
>
>    list<char> lc = ...;
>    reverse_copy(x, front_inserter(lc));
>
> Does that make more sense?
>

I still don't see why you need the BackwardRange when you already have
a ForwardRange. I just don't think there's any value to an analog when
if I'm reading what you're explaining correctly, conceptually:

BackwardRange = ForwardRange<Reversed<Range> >

Except for operator-- instead of operator++, I don't see any real
difference worth highlighting.

> Also, here's a follow-up issue to ponder:
>
> Alexandrescu has pointed out that infinite ranges are perfectly
> plausible.

Indeed they are. :)

> The range of Natural numbers {0, 1, 2, 3, ...} is an
> obvious well-behaved candidate, as it can trivially provide both a
> random-access popFront(n) and an op[](i).  What if you reverse it,
> though?  popBack(n) is a simple thing to provide, but how would
> op[](i) work?  It'll have to call op[](f(i)), so f must be an
> involution in order for reverse(reverse(x)) to be the same as x, but
> which involution?  Retro<> uses size()-i, but that obviously doesn't
> work with infinite ranges.
>

Hold on.

Given:
r = [0 .. infinity)
popBack(range) -> range' , where size(range') = size(range) - 1 and
front(range') == front(range)
Then:
popBack(r) -> r
Proof:
Because size(r) = infinity
and infinity - 1 == infinity
and front(r) == front(popBack(r)) == 0
QED

I don't see why popBack has to do anything to an infinite ForwardRange. ;)

> The only nice one I can come up with is the bitwise 2's complement**.
> That means, though, that every backward range would have to allow
> v[-1] === v.back(), and that op[]'s parameter becomes fundamentally
> signed, whereas currently it's unsigned.  Does that mean that op[] is
> a bad fundamental operation for random-access?
>

Not really; operator[](I i) is just fine because:

* the type 'I' determines the limit of the accessible random-accessible element
* granted that operator[] can be approximated for a RandomAccess
range using successive succession (or front-popping) then the
short-hand is merited for semantics sake
* I don't see why offset-addressing is funamentally different from
successive range shrinking from one end (i.e., from the start element
or start sentinel).

Now if you intend to support circular data structures or "closed ring"
ranges, then it would be a lot simpler -- but that makes your range
finite, which means normal finite range operations will apply. ;)

> ~ Scott
>
> * string and vector could, of course, have constructors from
> BackwardRanges that also provide a size.

I still don't see why ForwardRange<Reversed<Range> > wouldn't work for
your use case still.

>
> ** The twos-complement op[] works particularly nicely with an infinite
> bidirectional range of  integers {0, 1, 2, 3, ..., -4, -3, -2, -1},
> where op[](i) == i.  Note that that's the same identity as there was
> with naturals, just there it only worked for non-negative numbers.
>

Then you can use the mod-trick to find out the correct offset in the
case of regular ring functions -- of course only if you know the exact
finite bounds of the "infinite" range. So long as you have an offset,
having a ring structure allows you to traverse your co-domain space
without getting "lost".

HTH

[me22]

2009/12/14 Dean Michael Berris <mikhai...@gmail.com>:
> On Tue, Dec 15, 2009 at 7:23 AM, me22 <me2...@gmail.com> wrote:
>>
>> A BackwardIterator provides operator-- instead of operator++.
>>
>
> Hmmm... That's not a big fundamental difference.
>

I agree -- with just one range it's a completely pointless
distinction. (Except for the fact that I think reverse should be an
involution on forward ranges too, which means that the intermediate
type should have a concept too, even if it's just
CanBeReversedToGetAForwardRangeRange.)

If you have 2 ranges that are supposed to represent the same sequence
of elements (but aren't over the same storage), though, then it makes
sense for the primary "direction" of one to be the opposite of the
other's.

>>
>> (Compare to http://www.informit.com/articles/printerfriendly.aspx?p=1407357 )
>>
>
> This doesn't look like C++ to me -- this is in D?
>

He refers to it as "CDJ#++" -- it's a pseudocode.

>
> If you have sentinels to mark your data structure bounds and use that
> to implement the reverse operation (assuming you actually have optimal
> storage to store just one direction links -- in tries, you'd have the
> parent link)

I do have a parent link, but I want to traverse the paths from root to
specific nodes, since those are the "sequences" stored in the trie. I
have optimal storage for that path backwards -- the parent links --
but not forwards, since that would require an oracle to tell me which
child pointer to take at each step.

> then you can provably traverse the data structure using normal
> forward traversal algorithms -- but your range should implement
> the reverse internally. Something like:
>
>  container c;
>  auto r = reverse(c.all());
>
> Then you can apply the normal forward traversal on the range just like
> you will any other range that can be traversed in one direction. That
> immediately makes your range usable in other algorithms without
> creating a special type of Iterator or Range.
>

> [...]

>
> I still don't see why you need the BackwardRange when you already have
> a ForwardRange. I just don't think there's any value to an analog when
> if I'm reading what you're explaining correctly, conceptually:
>
>  BackwardRange = ForwardRange<Reversed<Range> >
>
> Except for operator-- instead of operator++, I don't see any real
> difference worth highlighting.
>

Ah, ok. I get what you've been saying, now.

I suppose my complaint is then, "Why not have a concept for
SomethingThatIfYouPassItToReverseGivesYouAForwardRange?"

Right now I can't pass it to reverse_copy, since that demands a
BidirectionalRange, not a ForwardRange<Reversed<Range> >.

I suppose calling it a ForwardRange<Reversed<Range> > is sufficient,
but why shouldn't they be more orthogonal? Alexandrescu points out
that infiniteness means that RandomAccessRange is a refinement of
ForwardRange, not BidirectionalRange, and I think a similar
observation is valid for BidirectionalRange.

Why shouldn't Bidi be defined like this?

BidirectionalRange<Range> = And< ForwardRange<Range>,
BackwardRange<Range> >

You're right; it only has something to do with a reversed infinite ForwardRange.

reverse(r).popBack() === r.popFront()

So when you do the same thing with operator[]:

reverse(r)[i] === r[f(i)], for some appropriate involution f

But using the idea of your proof, when r is [0, inf),

reverse(r)[0] === reverse(r)[1] === ...

So the only useful definition of [] means it needs to take a negative number.

If you take the infinite range of Naturals, ℕ = (0, 1, 2, ...), then I
doubt anyone would complain about this (other than abuse of notation):

∀ i ∈ ℕ, ℕ[i] = i.

So extending that by letting it "overflow" infinity (thanks to some
more notation abuse), we get all the integers, ℤ = (0, 1, 2, 3, ...,
-4, -3, -2, -1), and can keep an analogous property:

∀ i ∈ ℤ, ℤ[i] = i.

That suggests that the involution of choice is the twos-complement:

reverse(r)[i] === r[~i]

Which seems pleasing to me, since already in C++03, for a signed integer i:

v.begin() + i == v.end() + ~i

(Assuming its magnitude is appropriately small.)

>  * I don't see why offset-addressing is fundamentally different from

> successive range shrinking from one end (i.e., from the start element
> or start sentinel).
>

Yup; there's no fundamental reason for operator[] to be a fundamental one, since

r[i] === (t = r, t.pop_front(i), t.front())

But what if, instead, rr = (-inf, -1], so there are no *_front functions?

rr[i] === (t = r, t.pop_back(f(i)), t.back())

(Which is just a different perspective on what I said above.)

Hoping he made more sense this time,
~ Scott

[Dean Michael Berris]

On Tue, Dec 15, 2009 at 10:00 AM, me22 <me2...@gmail.com> wrote:
> 2009/12/14 Dean Michael Berris <mikhai...@gmail.com>:
>> On Tue, Dec 15, 2009 at 7:23 AM, me22 <me2...@gmail.com> wrote:
>>>
>>> A BackwardIterator provides operator-- instead of operator++.
>>>
>>
>> Hmmm... That's not a big fundamental difference.
>>
>
> I agree -- with just one range it's a completely pointless
> distinction.  (Except for the fact that I think reverse should be an
> involution on forward ranges too, which means that the intermediate
> type should have a concept too, even if it's just
> CanBeReversedToGetAForwardRangeRange.)
>

I think reverse would only make sense on a Range if the range is
finite though. This is what I mean by having sentinels in the range
implementation which allows you to modify the range from either
direction (which pre-supposes a Bidirectional Range).

> If you have 2 ranges that are supposed to represent the same sequence
> of elements (but aren't over the same storage), though, then it makes
> sense for the primary "direction" of one to be the opposite of the
> other's.
>

But the Range concept that I have in my mind has nothing to do with
storage -- just the representation of a range of values. Now whether
your range returns rvalues instead of references (which I would
personally prefer, because you really can simulate lvalue references
with first-class objects with the (additional?) cost of storing a
pointer instead of the actual value aka a reference proxy) is
completely a different matter altogether. ;)

>>>
>>> (Compare to http://www.informit.com/articles/printerfriendly.aspx?p=1407357 )
>>>
>>
>> This doesn't look like C++ to me -- this is in D?
>>
>
> He refers to it as "CDJ#++" -- it's a pseudocode.
>

Ah, alright. :) I have yet to completely drink the Alexandrescu
Kool-Aid on this whole range as primitive business though. I don't
also see why you need the STL to be implemented in other programming
languages too. :D

>>
>> If you have sentinels to mark your data structure bounds and use that
>> to implement the reverse operation (assuming you actually have optimal
>> storage to store just one direction links -- in tries, you'd have the
>> parent link)
>
> I do have a parent link, but I want to traverse the paths from root to
> specific nodes, since those are the "sequences" stored in the trie.  I
> have optimal storage for that path backwards -- the parent links --
> but not forwards, since that would require an oracle to tell me which
> child pointer to take at each step.
>

Yes, but if you consider your Range to represent a state machine (or a
permutation machine) instead of just representing values in the trie,
then you may have an optimal (read, logarithmic time) implementation
of a forward traversal of the "permutations" or "traversals" of your
trie. This means for a trie:

h - e ---- l - l - o
\ \
a - y p

You can then have a range that represents intermediate traversals. For
instance, a range 'r' that starts at the root of the trie will
represent just 'h'. If you move forward, you then get as the next
element of the range the concatenation of 'h' and a pre-determined
traversal of the trie, for instance 'ha', then next element is 'hay',
next is 'he', 'hel', 'help', 'hell', 'hello'.

Then what you get is a range of ranges instead of a "flattened" view
of your data structure. You can do away with storing the concatenated
range too and just yield the most recent element in the traversal
(when accessing range.front) just taking note the traversal algorithm
state as you go shrinking the range *from one direction*. If you used
sentinels you can make that range a BidirectionalRange.

It helps if you think about non-linear coordinate structures
represented using iterators. What you'll find is for example on a
binary tree that you want to traverse using a single iterator (let me
get away from ranges for a while):

a
b c

You then have a projection of the 2-dimensional coordinate structure
on-to a 1-dimensional coordinate structure using a state-ful iterator;
just like the way you "flatten" a binary tree is to traverse it using
any one of the available traversal algorithms (pre-, in-, post-).
However that would mean your traversal algorithm is embedded in the
iterator, and keeps state on an incremental basis -- which is really
the "trick" or "approach" that Stepanov and McJones present in their
book.

>> then you can provably traverse the data structure using normal
>> forward traversal algorithms -- but your range should implement
>> the reverse internally. Something like:
>>
>>  container c;
>>  auto r = reverse(c.all());
>>
>> Then you can apply the normal forward traversal on the range just like
>> you will any other range that can be traversed in one direction. That
>> immediately makes your range usable in other algorithms without
>> creating a special type of Iterator or Range.
>>
>> [...]
>>
>> I still don't see why you need the BackwardRange when you already have
>> a ForwardRange. I just don't think there's any value to an analog when
>> if I'm reading what you're explaining correctly, conceptually:
>>
>>  BackwardRange = ForwardRange<Reversed<Range> >
>>
>> Except for operator-- instead of operator++, I don't see any real
>> difference worth highlighting.
>>
>
> Ah, ok.  I get what you've been saying, now.
>
> I suppose my complaint is then, "Why not have a concept for
> SomethingThatIfYouPassItToReverseGivesYouAForwardRange?"
>
> Right now I can't pass it to reverse_copy, since that demands a
> BidirectionalRange, not a ForwardRange<Reversed<Range> >.
>

Actually, you should still be able to do that. Let me explain a little.

ForwardRange<Reversed<Range> > can still model a BidirectionalRange
using a concept map. Take note that it requires Range to be Finite.
This happens because you can theoretically already deduce that a Range
that is Reversed implies that it can be traversed from either
direction. And since reverse(...) is reversed by another call to
reverse (yeah, pun not intended) then it already makes your
Reversed<Range> a BidirectionalRange. You can then lift this to
"override" the "ForwardRange" constraint but only for the specific
case.

This means all you need to do is map a ForwardRange<Reversed<Range> >
to adapt it to be conceptually equivalent to a BidirectionalRange only
because it's proven that only a Finite Range can be Reverse<>'d.

> I suppose calling it a ForwardRange<Reversed<Range> > is sufficient,
> but why shouldn't they be more orthogonal?  Alexandrescu points out
> that infiniteness means that RandomAccessRange is a refinement of
> ForwardRange, not BidirectionalRange, and I think a similar
> observation is valid for BidirectionalRange.
>
> Why shouldn't Bidi be defined like this?
>
>    BidirectionalRange<Range> = And< ForwardRange<Range>,
>                                     BackwardRange<Range> >
>

Because BackwardRange can already be modeled as
ForwardRange<Reverse<Range> >. ;) Also because it implies that Range
is already finite for it to be reversible.

>>
>> Hold on.
>>
>> Given:
>>  r = [0 .. infinity)
>>  popBack(range) -> range' , where size(range') = size(range) - 1 and
>> front(range') == front(range)
>> Then:
>>  popBack(r) -> r
>> Proof:
>>  Because size(r) = infinity
>>  and infinity - 1 == infinity
>>  and front(r) == front(popBack(r)) == 0
>>  QED
>>
>> I don't see why popBack has to do anything to an infinite ForwardRange. ;)
>>
>
> You're right; it only has something to do with a reversed infinite ForwardRange.
>

But that doesn't make sense. You can't really reverse an infinite
range, because you don't know the "other end" from which to start
from.

>    reverse(r).popBack() === r.popFront()
>
> So when you do the same thing with operator[]:
>
>    reverse(r)[i] === r[f(i)], for some appropriate involution f
>
> But using the idea of your proof, when r is [0, inf),
>
>    reverse(r)[0] === reverse(r)[1] === ...
>
> So the only useful definition of [] means it needs to take a negative number.
>

But you're forgetting that [0..infinity) cannot be reversed to become
[infinity..-1) and still model ForwardRange. If infinity means real
infinity and not some machine-induced storage bound, then you're out
of luck. But if you want to model all the numbers representable by a
given bounded integral type, then this is what you call a Group, and
from there you can definitely implement reverse(...).

> If you take the infinite range of Naturals, ℕ = (0, 1, 2, ...), then I
> doubt anyone would complain about this (other than abuse of notation):
>
>    ∀ i ∈ ℕ, ℕ[i] = i.
>
> So extending that by letting it "overflow" infinity (thanks to some
> more notation abuse), we get all the integers, ℤ = (0, 1, 2, 3, ...,
> -4, -3, -2, -1), and can keep an analogous property:
>
>    ∀ i ∈ ℤ, ℤ[i] = i.
>

Although that's not mathematically sound, there's really no way (using
Euclidean geometry and flat 1-d numerical domain spaces) for you to
"wrap around infinity". Unless you're dealing with hyper-parabolic
mathematical number spaces, in which case you may have to throw out
all the notions of infinity you may have in the Euclidean sense. ;)

> That suggests that the involution of choice is the twos-complement:
>
>    reverse(r)[i] === r[~i]
>
> Which seems pleasing to me, since already in C++03, for a signed integer i:
>
>    v.begin() + i == v.end() + ~i
>
> (Assuming its magnitude is appropriately small.)
>

Here, it also assumes that v is finite. ;)

>>  * I don't see why offset-addressing is fundamentally different from
>> successive range shrinking from one end (i.e., from the start element
>> or start sentinel).
>>
>
> Yup; there's no fundamental reason for operator[] to be a fundamental one, since
>
>    r[i] === (t = r, t.pop_front(i), t.front())
>
> But what if, instead, rr = (-inf, -1], so there are no *_front functions?
>
>    rr[i] === (t = r, t.pop_back(f(i)), t.back())
>
> (Which is just a different perspective on what I said above.)
>
> Hoping he made more sense this time,

Ah, so you want to be able to turn a ForwardRange<Range> where
FrontBoundedInifiniteRange<Range> into a BackwardRange<Range> where
front() is not defined. There may be some merit to that though but
only for ForwardRange<Range> where FrontBoundedInfiniteRange<Range>.

Now I think I understand the motivation for a
BackwardRange/BackwardIterator, and I must say thinking about it more,
there would be some merit to that. Now to implement that
FrontBoundedInfiniteRange Concept... :D

[me22]

2009/12/15 Dean Michael Berris <mikhai...@gmail.com>:

>
> I think reverse would only make sense on a Range if the range is
> finite though. This is what I mean by having sentinels in the range
> implementation which allows you to modify the range from either
> direction (which pre-supposes a Bidirectional Range).
>

See, I dislike pre-supposing a Bidirectional Range.

>> If you have 2 ranges that are supposed to represent the same sequence
>> of elements (but aren't over the same storage), though, then it makes
>> sense for the primary "direction" of one to be the opposite of the
>> other's.
>>
>
> But the Range concept that I have in my mind has nothing to do with
> storage -- just the representation of a range of values. Now whether
> your range returns rvalues instead of references (which I would
> personally prefer, because you really can simulate lvalue references
> with first-class objects with the (additional?) cost of storing a
> pointer instead of the actual value aka a reference proxy) is
> completely a different matter altogether. ;)
>

So to phrase it as "a range of values", I want to have the range of
values {0, 1, 2, 3, 4} be equivalent to the range of values {4, 3, 2,
1, 0} by specifying that their directions are opposite.

>
> I don't also see why you need the STL to be implemented in
> other programming languages too. :D
>

I think it's important for missionaries :P

>
> Yes, but if you consider your Range to represent a state machine (or a
> permutation machine) instead of just representing values in the trie,
> then you may have an optimal (read, logarithmic time) implementation
> of a forward traversal of the "permutations" or "traversals" of your
> trie.
>

Yes; that's a pre-order traversal iterator over the trie, essentially.

>
> You then have a projection of the 2-dimensional coordinate structure
> on-to a 1-dimensional coordinate structure using a state-ful iterator;
> just like the way you "flatten" a binary tree is to traverse it using
> any one of the available traversal algorithms (pre-, in-, post-).
> However that would mean your traversal algorithm is embedded in the
> iterator, and keeps state on an incremental basis -- which is really
> the "trick" or "approach" that Stepanov and McJones present in their
> book.
>

I get how to iterate over the whole tree; that's not a problem. The
problem is in iterating a *specific path* in the tree.

Consider something like a set<string> ss, but implemented internally as a trie.

trie_set<string>::iterator is the pre-order traversal iterator you
mention. But its value_type should be a pair of iterators allowing
you to iterate the path from the root to the current node in the
traversal, and there's no reason that those iterators should store all
the state needed for the pre-order traversal, since one pointer that
walks to the root is plenty (and iterators means you have one pointer
in each, which is one reason Alexandresu likes ranges as a primitive,
btw).

I can't walk the pointer a step down from the root in O(1) without
knowing the whole path a priori, taking O(m) space.

>
> ForwardRange<Reversed<Range> > can still model a BidirectionalRange
> using a concept map.
>

As mentioned, while that's clever, I can't model a BidirectionalRange.

>
> Because BackwardRange can already be modeled as
> ForwardRange<Reverse<Range> >. ;) Also because it implies that Range
> is already finite for it to be reversible.
>

Except it can't, because you just said that
ForwardRange<Reverse<Range> > is a BidirectionalRange, which has more
requirements than a BackwardRange.

>
> But you're forgetting that [0..infinity) cannot be reversed to become
> [infinity..-1) and still model ForwardRange.

That's my complaint. Why should it have to model a ForwardRange?

>
> Although that's not mathematically sound, there's really no way (using
> Euclidean geometry and flat 1-d numerical domain spaces) for you to
> "wrap around infinity". Unless you're dealing with hyper-parabolic
> mathematical number spaces, in which case you may have to throw out
> all the notions of infinity you may have in the Euclidean sense. ;)
>

I know it's not rigorous to say it, but I think it's an acceptable
analogy in the same sense that the Cauchy Principal Value of
Integral(-inf, inf, x, dx) is 0 even though the integral isn't
"really" defined.

Z_1 = (0, -1)
Z_2 = (0, 1, -2, -1)
Z_3 = (0, 1, 2, 3, -4, -3, -2, -1)
...
Z_N = (0, 1, ..., 2**(N-1)-1, -2**(N-1), ..., -2, -1)
...
Z_inf = Z = (0, 1, 2, 3, ..., inf, -inf, ..., -2, -1)

>
> Here, it also assumes that v is finite. ;)
>

Yes.

>
> Ah, so you want to be able to turn a ForwardRange<Range> where
> FrontBoundedInifiniteRange<Range> into a BackwardRange<Range> where
> front() is not defined. There may be some merit to that though but
> only for ForwardRange<Range> where FrontBoundedInfiniteRange<Range>.
>
> Now I think I understand the motivation for a
> BackwardRange/BackwardIterator, and I must say thinking about it more,
> there would be some merit to that. Now to implement that
> FrontBoundedInfiniteRange Concept... :D
>

Yay! I finally made sense :)

Why only for infinite, though? What if you want to use an slist as
the internal storage for the std::stack template?

I'd immediately think of writing a revered_container wrapper, so I
could say std::stack<T, reversed_container<slist<T> > >. What concept
does reversed_container<std::slist<T> >::iterator satisfy?

(Which leads into my favourite reason that ranges should be the
primitive: A container is just a range that owns its elements. A
std::deque<T> *is* a perfectly acceptable range of rvalues; It just
happens to be a touch expensive to copy.)

~ Scott

[Dean Michael Berris]

On Wed, Dec 16, 2009 at 12:12 AM, me22 <me2...@gmail.com> wrote:
> 2009/12/15 Dean Michael Berris <mikhai...@gmail.com>:
>>
>> I think reverse would only make sense on a Range if the range is
>> finite though. This is what I mean by having sentinels in the range
>> implementation which allows you to modify the range from either
>> direction (which pre-supposes a Bidirectional Range).
>>
>
> See, I dislike pre-supposing a Bidirectional Range.
>

Right, I think I see the rationale for that but only for certain cases
where BidirectionalRange would impose an overhead in the
implementation. Otherwise I don't see what is wrong with a
BidirectionalRange per se, just as long as a range can be modified
from either end.

>>> If you have 2 ranges that are supposed to represent the same sequence
>>> of elements (but aren't over the same storage), though, then it makes
>>> sense for the primary "direction" of one to be the opposite of the
>>> other's.
>>>
>>
>> But the Range concept that I have in my mind has nothing to do with
>> storage -- just the representation of a range of values. Now whether
>> your range returns rvalues instead of references (which I would
>> personally prefer, because you really can simulate lvalue references
>> with first-class objects with the (additional?) cost of storing a
>> pointer instead of the actual value aka a reference proxy) is
>> completely a different matter altogether. ;)
>>
>
> So to phrase it as "a range of values", I want to have the range of
> values {0, 1, 2, 3, 4} be equivalent to the range of values {4, 3, 2,
> 1, 0} by specifying that their directions are opposite.
>

Right, {0, 1, 2, 3, 4} is equivalent to reverse({4, 3, 2, 1, 0}) as
long as equivalent does not imply storage/address equivalence. :)

>>
>> I don't also see why you need the STL to be implemented in
>> other programming languages too. :D
>>
>
> I think it's important for missionaries :P
>

LOL. I don't know about that, the STL seems perfectly fine to stay
just within C++ though IMO. ;)

>
> I get how to iterate over the whole tree; that's not a problem.  The
> problem is in iterating a *specific path* in the tree.
>

What stops you from encoding the specific path as a permutation or a
traversal of the same existing data structure?

> Consider something like a set<string> ss, but implemented internally as a trie.
>
> trie_set<string>::iterator is the pre-order traversal iterator you
> mention.  But its value_type should be a pair of iterators allowing
> you to iterate the path from the root to the current node in the
> traversal, and there's no reason that those iterators should store all
> the state needed for the pre-order traversal, since one pointer that
> walks to the root is plenty (and iterators means you have one pointer
> in each, which is one reason Alexandresu likes ranges as a primitive,
> btw).
>
> I can't walk the pointer a step down from the root in O(1) without
> knowing the whole path a priori, taking O(m) space.
>

Right, but is you have a permutation range or a range of all possible
traversals of a data structure (still a Finite Range) then each
traversal can be represented as a value in that range. Did I just get
an epiphany there? :D

BTW I agree with why life would be so much simpler with the range as a
primitive. My gripe with it is the disconnect between how the
underlying lower level computer works (indexing using a pointer,
single point in memory with a size, no built-in low-level support for
bounded memory areas with metadata, etc.) and how it's going to be
really hard for compilers to "optimize out" or abstract much of the
data that makes Iterators so attractive in the first place. Unless you
come up with a deliberately optimized "expression template" based
approach to dealing with Ranges to get the same performance and
optimization hints that just Iterators can give you, I'm holding out
on the range as a primitive.

Note that conceptually, I like it. Implementation-wise, it's going to
be a nightmare to optimize unless you go full functional and lazy on
ranges which to say the least can overwhelm both library implementors
and users. Also I think it gives compiler vendors the shivers thinking
about better complex template metaprogramming support in their
compilers.

>
>>
>> ForwardRange<Reversed<Range> > can still model a BidirectionalRange
>> using a concept map.
>>
>
> As mentioned, while that's clever, I can't model a BidirectionalRange.
>

Even with sentinels and/or permutation/traversal ranges?

>>
>> Because BackwardRange can already be modeled as
>> ForwardRange<Reverse<Range> >. ;) Also because it implies that Range
>> is already finite for it to be reversible.
>>
>
> Except it can't, because you just said that
> ForwardRange<Reverse<Range> > is a BidirectionalRange, which has more
> requirements than a BackwardRange.
>

It *can* be adapted to become a BidirectionalRange using concept maps
IIRC. I may be wrong though.

>>
>> But you're forgetting that [0..infinity) cannot be reversed to become
>> [infinity..-1) and still model ForwardRange.
>
> That's my complaint.  Why should it have to model a ForwardRange?
>

Because, for it to be useful with any algorithm that supports forward
traversal, it would have to model a ForwardRange. Unless you also
create a family of algorithms that deal with backward traversal in
which case you throw away the utility of having reverse_* algorithms.

If you were starting from a clean slate, I would say create reversible
ranges instead and have a single algorithm that accepts a
LinearTraversableRange. There should be a trait instead that says what
direction a range can be modified. That is the option compared to
having things like:

reverse_copy(...)
backward_copy(...)
forward_copy(...)
copy(...) // which would imply forward_copy and would be superfluous

Does that make sense?

>>
>> Although that's not mathematically sound, there's really no way (using
>> Euclidean geometry and flat 1-d numerical domain spaces) for you to
>> "wrap around infinity". Unless you're dealing with hyper-parabolic
>> mathematical number spaces, in which case you may have to throw out
>> all the notions of infinity you may have in the Euclidean sense. ;)
>>
>
> I know it's not rigorous to say it, but I think it's an acceptable
> analogy in the same sense that the Cauchy Principal Value of
> Integral(-inf, inf, x, dx) is 0 even though the integral isn't
> "really" defined.
>
> Z_1 = (0, -1)
> Z_2 = (0, 1, -2, -1)
> Z_3 = (0, 1, 2, 3, -4, -3, -2, -1)
> ...
> Z_N = (0, 1, ..., 2**(N-1)-1, -2**(N-1), ..., -2, -1)
> ...
> Z_inf = Z = (0, 1, 2, 3, ..., inf, -inf, ..., -2, -1)
>

But here you'd be dealing with limits and limit theory -- of course
it's completely plausible to "represent" infinite ranges in memory in
the mathematical sense. How you deal with these infinite ranges as
they are infinite that requires any sort of bounded algorithms
actually breaks the mathematical purity of the term "infinite". Note
that integration implies higher order operations on primitives that do
rely on infinity and yet still again you're at the realm of limits and
limit theory.

You can approximate in the numerical sense and unless you're doing
symoblic analysis on the integral of a function over a defined domain
and range (even those that are infinite in the mathematical sense) you
end up with mathematically impure implementations on binary digital
computers.

But, of course, that'd be an off-topic discussion IMO, and is way beyond C++. :D

>>
>> Here, it also assumes that v is finite. ;)
>>
>
> Yes.
>

Which helps a lot. :D

>>
>> Ah, so you want to be able to turn a ForwardRange<Range> where
>> FrontBoundedInifiniteRange<Range> into a BackwardRange<Range> where
>> front() is not defined. There may be some merit to that though but
>> only for ForwardRange<Range> where FrontBoundedInfiniteRange<Range>.
>>
>> Now I think I understand the motivation for a
>> BackwardRange/BackwardIterator, and I must say thinking about it more,
>> there would be some merit to that. Now to implement that
>> FrontBoundedInfiniteRange Concept... :D
>>
>
> Yay!  I finally made sense :)
>
> Why only for infinite, though?  What if you want to use an slist as
> the internal storage for the std::stack template?
>
> I'd immediately think of writing a revered_container wrapper, so I
> could say std::stack<T, reversed_container<slist<T> > >.  What concept
> does reversed_container<std::slist<T> >::iterator satisfy?
>

This supposes you still deal with Iterators. ;) And the answer would
be of course the BackwardIterator. :D Then your problem becomes
std::stack needing to support that and then you're going to be stuck
with the STL that doesn't support the BackwardIterator.

If you dealt with Ranges of course, then reversed_container<slist<T>
>::all() yields a ForwardRange<Reversed<Range> > -- of course
Reversed<Range> should have an optimal pop_front(...) implementation,
that just forwards to Range's pop_back(...) implementation, and
front(...) implementation that just forwards to Range's back(...)
implementation. The more I think about this the more I'd like to work
on that TMP-heavy expression-template based range processing library.

Maybe when I get paid to do that kind of work I just might do that. ;)

> (Which leads into my favourite reason that ranges should be the
> primitive: A container is just a range that owns its elements.  A
> std::deque<T> *is* a perfectly acceptable range of rvalues; It just
> happens to be a touch expensive to copy.)
>

Right, unless you have a copy-on-write std::dequeue<T> proxy that you
pass around instead of an actual std::dequeue<T> -- which is not
thread-safe and can kill cache locality.

I like Range as a primitive too, still am not sold on the performance
implications of any practically imperative implementation precisely
because of reasons you cite above. :)

[me22]

2009/12/15 Dean Michael Berris <mikhai...@gmail.com>:
>

> Right, I think I see the rationale for that but only for certain cases
> where BidirectionalRange would impose an overhead in the
> implementation.
>

Which are not unheard-of. Singly-linked lists, PRNGs, ...

>
> Right, {0, 1, 2, 3, 4} is equivalent to reverse({4, 3, 2, 1, 0}) as
> long as equivalent does not imply storage/address equivalence. :)
>

Which is why I specified it the first time, only for you to complain
that whether it returns lvaues or rvalues is insignificant :|

>
> What stops you from encoding the specific path as a permutation or a
> traversal of the same existing data structure?
>

Encoding the path in a manner that's usable for "forward" traversal
takes linear space, at which point I might as well just build and
return a string instead of the range.

>
> Note that conceptually, I like it. Implementation-wise, it's going to
> be a nightmare to optimize unless you go full functional and lazy on
> ranges which to say the least can overwhelm both library implementors
> and users. Also I think it gives compiler vendors the shivers thinking
> about better complex template metaprogramming support in their
> compilers.
>

Fair enough. Guess I'll have to see how the efficiency comes out.

>
> If you were starting from a clean slate, I would say create reversible
> ranges instead and have a single algorithm that accepts a
> LinearTraversableRange. There should be a trait instead that says what
> direction a range can be modified. That is the option compared to
> having things like:
>
>  reverse_copy(...)
>  backward_copy(...)
>  forward_copy(...)
>  copy(...) // which would imply forward_copy and would be superfluous
>
> Does that make sense?
>

Yup.

reverse_copy(ForwardRange, BackwardRange)
reverse_copy(BackwardRange, ForwardRange)

For instance, with appropriate handling of (BidiRange, BidiRange),
which matches both.

>
> If you dealt with Ranges of course, then reversed_container<slist<T>
>>::all() yields a ForwardRange<Reversed<Range> > -- of course
> Reversed<Range> should have an optimal pop_front(...) implementation,
> that just forwards to Range's pop_back(...) implementation, and
> front(...) implementation that just forwards to Range's back(...)
> implementation.
>

Exactly -- and neither of those is a BidiRange.

>
> Right, unless you have a copy-on-write std::dequeue<T> proxy that you
> pass around instead of an actual std::dequeue<T> -- which is not
> thread-safe and can kill cache locality.
>
> I like Range as a primitive too, still am not sold on the performance
> implications of any practically imperative implementation precisely
> because of reasons you cite above. :)
>

I just thought of this, so I haven't really considered the downsides,
but what if you move all the ranges by default instead of copying
them? Seems like a great way of handling one-pass ranges, since you
neatly avoid their current complete lack of referential transparency.
Then the way to know a multi-pass range is by its copy constructor.

container.all() returns an rvalue to a non-owning range, which is
passable, but you could also pass std::move(container) as the range if
you don't care about losing its contents.

Hmm...