Steve Teale ([email protected]) 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
