Ranges

[Derek Parnell]

Steve Teale (steve.teale at britseyeview.com) wrote:
>> What is a range? 

In my case, I understand templates but that in itself doesn't help me
understand Andrei's concept of ranges. Just using English as a guide
doesn't really help either because a "range" is not an "iterator" in
English.

So I'd describe a range more along the lines of ...

A Range is a data construct that has a set of zero or more discrete
elements and can be used to iterate over its elements. There are a few
varieties of ranges: InputRange, OutputRange, ForwardRange,
BidirectionalRange and RandomAccessRange.

InputRange
----------
With this range, iteration can only occur in one direction, from first to
last element. 
As a minimum requirement it must implement methods that ...
  1) Provide a function that returns if there are any elements (remaining)
to iterator over. That function must be called 'empty()'.
  2) Provide a function that returns the current first element in the set.
Calling this when 'empty()' returns true will throw an exception. That
function must be called 'front()'. 
  3) Provide a function that moves an internal 'cursor' to the element
following the current first element in the set, such that it becomes the
new current first element. Calling this when 'empty()' returns true will
throw an exception. That function must be called 'popFront()'.

(I assume that the initial call to front() before calling popFront() will
return the absolute first element in the set, but this doesn't seem to be
documented.)

OutputRange
-----------
This is an InputRange with the extra capability of being able to add
elements to the range.
In addition to the InputRange methods, it must also provide a method that
adds a new element to the range, such that it becomes the current element.
That method must be called 'put(E)' where 'E' is the new element.

ForwardRange
------------
This is an InputRange with the extra capability of being able checkpoint
the current first 'cursor' position simply by copying the range. When you
copy an plain InputRange the copied range starts again from the absolute
first element, but a copied ForwardRange starts at whatever was the current
first element in the source range.

(I'm not sure why Birectional ranges are not allowed to be checkpointed)

BidirectionalRange
------------------
This is a ForwardRange that also allows iteration in the opposite
direction.
In addition to the ForwardRange methods it must also ...
 1) Provide a function that returns the current last element in the set.
Calling this when 'empty()' returns true will throw an exception. This must
be called 'back()'. 
 2) Provide a function that moves an internal 'cursor' to the element that
precedes the current last element in the set, such that it becomes the new
current last element. Calling this when 'empty()' returns true will throw
an exception. That function must be called 'popBack()'.

(I assume that the initial call to back() before calling popBack() will
return the absolute last element in the set, but this doesn't seem to be
documented.)


RandomAccessRange
-----------------
This is either a BidirectionalRange or any Range in which 'empty()' always
returns false (an infinite range).
It must provide a method that will return the Nth element of the set. That
function must be called 'opIndex(N)' where 'N' is a non-negative integer
that represents a zero-based index into the set. Thus opIndex(0) returns
the first element, opIndex(1) returns the 2nd element, etc ...

(I assume that for finite Ranges if 'N' is not a valid index that the Range
will throw an exception, but this doesn't seem to be documented.)


Now I admit that these are not method names I would have choosen, as I
would have preferred names more like ... isEmpty(), getFront(),
moveForwards(), getBack(), moveBackwards(), getElement(N), addElement(E),
but the bikeshed gods have more wisdom than me ... and not that I'm
complaining of course.

-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell