A range is a view into a collection. Ranges are typically mutable (though the individual elements may be immutable), so you can advance their position with popFront, but collections may be immutable. Here, we'll implement a stack data structure that exposes ranges to inspect it.
First, let's implement our stack type. A stack is a data type that fundamentally only needs two operations: push and pop. You push data on to the stack, and then pop data off in reverse order to which it was pushed. Popped data is removed from the stack. If we push 1 and then 2, we should pop 2 then 1. Popping from an empty stack is an error.
It is possible to use a built-in array directly as a stack, using slicing and the append operator (a ~ b), but this is woefully inefficient. Instead, we'll use a static buffer that can grow, if necessary, with a companion position variable. We can slice into a statically sized buffer to get started, and if this proves to be too small, we can simply grow the length. This allows the runtime to be reallocated as required on the garbage collected memory heap—a somewhat slow but infrequent step. Otherwise, the code is pretty straightforward as shown:
struct Stack(T, size_t expectedMaxSize = 32) {
T[expectedMaxSize] initialBuffer;
T[] buffer;
size_t currentPosition;
bool isEmpty() { return currentPosition == 0; }
void push(T item) {
// initialization
if(buffer is null) buffer = initialBuffer[];
// growth if needed
if(currentPosition == buffer.length) buffer.length += 64;
// the actual push operation
buffer[currentPosition++] = item;
}
T pop() {
if(currentPosition == 0)
throw new Exception("Empty stack cannot pop.");
return buffer[--currentPosition];
}
}Our stack can be used as shown:
Stack!int stack; stack.push(1); stack.push(2); writeln(stack.pop()); // prints 2 writeln(stack.pop()); // prints 1 assert(stack.isEmpty()); // passes, we've used all the data
Now, let's look at how to put a range interface on it.
Let's put a range interface on a collection by executing the following steps:
- Write a range by using the data members of your collection to implement the range primitives you can write efficiently. The range can use private members, but since it is part of the public interface, be careful not to break encapsulation and expose something you don't want to commit to.
- Try to avoid modifying the original data. A data member that keeps the current position will be useful. For our stack, we'll take a slice into the stack buffer and keep this private so that our implementation details don't leak out.
- Make the range's constructor private. The code for the viewing range is as follows:
struct StackView(T) { // we'll start with the data members and constructors that peek into the collection private const(T)[] data; // our read-only view into the data private this(const(T)[] data) { this.data = data; } // and our range primitives @property bool empty() const { return data.length == 0; } @property const(T) front() const { return data[$ - 1]; // the stack pops backwards in the array } void popFront() { data = data[0 .. $ - 1]; } } - Add a method to the collection that returns the range. The method should have a relevant name for the kind of range it returns. Inside our
Stackstruct, add the following code:@property auto view() const { return StackView!T(buffer[0 .. currentPosition]); }
Whenever possible, a range should operate independently of a collection. Ranges provide their own interface and keep track of their own position. Thus, typically, ranges and collections are two separate types, but they are located in the same module so that the range can take advantage of the collection's private implementation for maximum efficiency.
The name of the method the collection provides to return a range can be anything. Here, we're using view because the range lets us look into the data, nothing more. The analogous range methods on std.stdio.File are called byLine and byChunk, as they iterate over the file by lines and chunks, respectively. A collection may have multiple ranges that work with it in different ways.
If it is impossible to advance a range without modifying the underlying collection or stream, you may still provide a range interface. For example, the ranges on a file must read more data from the file to get the next lines. This is a necessary cost in that situation. Additional stream-based functions, such as seeking, are not exposed in the range. While, in theory, using file seeking and buffering, File.byLine could provide primitives such as save or bidirectionality, in practice, these would break the efficiency guarantees of the range interface and thus are not exposed. Stream or collection-specific functions are implemented on their native type.
With a different implementation of Stack, we may have been forced to use the primitive pop instead of view into its internal buffer. This would have been acceptable, but not ideal since pop modifies the underlying data as you look through it.