couple of really noob questions (ranges, toString)

[Jonathan M Davis]

On Monday 01 November 2010 19:21:27 spir wrote:
> On Mon, 1 Nov 2010 18:47:38 -0700
> 
> Jonathan M Davis <jmdavisProg at gmx.com> wrote:
> > The best place to start learning about ranges is probably here:
> > http://www.informit.com/articles/article.aspx?p=1407357
> > 
> > front, popFront(), and empty make perfect sense as they are and work
> > quite well. hasNext() and next() have the serious drawback of mixing
> > iterating through the range and getting an element in it. It's one of
> > the serious flaws in Java's iterators. It's far better to have getting
> > the current or front element be separate from moving or  popping the
> > next one.
> 
> Thank for the pointer.
> Note That I know exactly nothing of Java. In fact, I used this scheme and
> those names spontaneously to implement traversal of custom structs in
> Oberon (that has no such notion). There's a point I don't understand in
> your argument: "...the serious drawback of mixing iterating through the
> range and getting an element in it". Isn't this precisely what popFront()
> does, stepping and returning an element? Or is "pop" in "popFront"
> misleading? (I've followed your pointer, but the site is so designed that
> the article is spread over 15 pages!) To move forward without popping,
> you'd need a kind of step() method that just follows the next pointer;
> really complementary to front(). Or is there something I misunderstand?
> But since typical use is iteration, does it make sense to separate
> stepping and reading? I now realise that my previous comment on the method
> trio vs my point of view is wrong; the functionality is the same, done the
> same way, only naming reveals a different pov: next() is popFront() seen
> differently, hasNext() is !empty().

In C++, iterators are effectively pointers. ++ increments, -- decrements, and * 
dereferences the element that it currently points to. The same goes for C#, 
except that they didn't overload * to get the current element but rather used a 
property function (Current IIRC, but I haven't used C# in a while). In both 
cases, accessing the current element does not move the iterator. Moving the 
iterator is completely separate from accessing what it points to.

In Java, on the other hand, they have hasNext(), hasPrev(), next(), and 
previous(), and the iterator doesn't point _at_ a particular element but rather 
_between_ them. So, hasNext() and hasPrevious() return a bool telling you 
whether there is a next or previous element respectively. next() returns the 
next element and moves the iterator whereas previous() returns the previous 
iterator and moves the iterator backwards. It means that you have to save the 
element every time that you access the next one rather than being able to use 
the iterator to get it again. It also makes it essentially impossible (or 
extremely ugly) to try and designate a range of any kind with iterators, since 
they don't actually point _at_ elements at using iterators alters them. Of 
course, Java didn't end up using iterators in a fashion that algorithms could be 
used for them (like C++ did), but it would be a pain even if you tried due to 
the lack of separation between moving an iterator and accessing what it refers 
to.

D uses ranges, which are at their most basic a pair of iterators but which are 
far more flexible than that, since you don't have to actually use iterators for 
their implementation. Things like infinite ranges become possible, which aren't 
really doable in the same way with iterators. They also completely avoid the 
issues related to passing iterators in the wrong order or which point to 
different containers.

There are various types of ranges, each with a set of functions that they must 
have, but the most basic is an InputIterator which has front, popFront(), and 
empty. front gives the first element in the range without altering the range. 
popFront() pops the first element from the range, making the next elment (if any) 
the first element in the range. popFront() is void and does not return what it 
pops. empty indicates whether there are any more elements left in the range. 
Using front when a range is empty will generally result in an exception being 
thrown, because there is no first element in the range.

The term "pop" does _not_ mean that an element is returned but that it is 
removed from the range. This is true for pretty much anything that uses a pop 
function in any language - stacks, lists, etc. It _is_ true that many 
implementations choose to have pop return the element which is popped, but 
that's an implementation detail. The term pop merely indicates that an element 
is removed from an end of a range or container.

- Jonathan M Davis