Iterators are an extremely useful tool for iterating and generating values from arbitrary data structures through a common interface.
This section covers the various ways to create iterators. Currently, the library contains built-in support for creating iterators from ranges, arrays, structs, strings, and common data structures.
To create an iterator, you should use the Iterator constructor function. Passing an array, struct, or string to this constructor will cause it to intelligently decide what sort of iterator you need.
An array iterator can be created simply using the Iterator constructor:
var iter = new Iterator(["A", "B", "C", "D"]);Alternatively, you can pass an instance of ArrayReader to specifically target arrays if you know your data structure will always be an array:
var reader = new ArrayReader(["A", "B", "C", "D"]);
var iter = new Iterator(reader);Much like array iterators, you should create a string iterator by using the Iterator constructor:
var iter = new Iterator("hello world");This will create an iterator which generates individual characters of the string. This is the same as creating an iterator from an instance of the CharacterReader struct:
var reader = new CharacterReader("hello world");
var iter = new Iterator(reader);Alternatively, you can use a different string iterator by passing in an instance of the WordReader struct:
var reader = new WordReader("hello world", " ");
var iter = new Iterator(reader);This variant will produce an iterator which generates slices of a string separated by some delimiter; in this case, the delimiter was " ".
Unfortunately, due to how data structures are implemented in GML, the Iterator constructor does not have enough information to correctly create an iterator from data structures. Therefore, you should also pass the ds_type_* of the data structure you intend to use:
var list = ds_list_create();
ds_list_add(list, 1, 2, 3);
var iter = new Iterator(list, ds_type_list);Alternatively, you can pass an instance of the corresponding reader struct. The following table details the ds_type_* and its corresponding reader struct:
| Type | Reader |
|---|---|
ds_type_grid |
GridReader |
ds_type_list |
ListReader |
ds_type_queue |
QueueReader |
ds_type_stack |
StackReader |
ds_type_priority |
PriorityQueueReader |
ds_type_map |
MapReader |
There is a little more work to creating an iterator from a struct. Your struct must contain a __next__ member which tells you the next item to return. The following iterator will count up from 1:
var struct = {
count : 0,
__next__ : function() {
count += 1;
return count;
}
}
var iter = new Iterator(struct);This approach is also compatible with structs created using constructor functions:
function Vec3(_x, _y, _z) constructor {
x = _x;
y = _y;
z = _z;
__next__ = function() {
static i = 0;
i += 1;
switch (i) {
case 1:
return x;
case 2:
return y;
case 3:
i = 0;
return z;
}
}
}
var vec3 = new Vec3(3, 12, 0);
var iter = new Iterator(vec3);This iterator will iterate over the three (x, y, and z) values of a Vec3.
Some of the previous examples of iterators are infinite because they have no well-defined end state. To create an iterator which does end, you must return undefined in that case. As an example:
var struct = {
count : 0,
__next__ : function() {
count += 1;
if (count <= 10) {
return count;
} else {
// end of iterator
return undefined;
}
}
}
var iter = new Iterator(struct);This iterator only counts up to ten, since in the case that count > 10, the iterator returns undefined. This signals the end of the iterator.
A useful built-in iterator constructor is range. The range function will create a new (potentially infinite) iterator over the supplied range. For example, range(1, 10) will return a new iterator which generates values 1 to 10 inclusive.
An additional, optional argument can be passed to the range function to decide the step of the range; that is, the value to increment each element of the range by. The default step is 1.
Another useful built-in iterator constructor is iterate. The iterate function will create an infinite iterator where each subsequent value generated is the result of applying a function to the previous value, starting at some initial value. For example, the following code will create an iterator over the function y = 2x by multiplying the previous value by 2 each iteration:
function pow2(_n) {
return _n * 2;
}
var iter = iterate(pow2, 1); // start at 1An auxiliary iterator which was included in this library was the file iterator. This iterator acts as a wrapper for the file_text_* functions, except it gives you the benefit of iterators. This iterator can be created by supplying an instance of the FileReader struct:
var file = file_text_open("./test.txt");
var reader = new FileReader(file);
var iter = new Iterator(reader);This section details basic operations you can perform on iterators to generate values.
Once you have an iterator, you can start generating values using next and peek.
The next method will return the next generated value and advance the iterator:
var iter = new Iterator(["A", "B", "C", "D"]);
var a = iter.next(); // holds "A"
var b = iter.next(); // holds "B"
var c = iter.next(); // holds "C"The peek function will return the next generated value, but will not advance the iterator.
var iter = new Iterator(["A", "B", "C", "D"]);
var a_peeked = iter.peek(); // holds "A"
var a = iter.next(); // holds "A"
var b = iter.next(); // holds "B"If you require your iterator to be converted into a collection, such as an array or a ds_list, then this is possible with the collect method. To collect an iterator into an array, simply call the method out-right:
var iter = range(1, 5);
var array = iter.collect(); // holds [1, 2, 3, 4, 5]Howeverm, if you want to convert the iterator into an alternative data structure, such as a ds_list or a ds_stack, you should pass the ds_type_ as a parameter. For example, to collect an iterator into a stack:
var iter = new Iterator(["A", "B", "C"]);
var stack = iter.collect(ds_type_stack);Currently, the only supported built-in collections are: arrays, ds_type_list, ds_type_queue, and ds_type_stack.
If you need to an easy way to display the contents of an iterator, then you can use the toString method:
var iter = range(1, 3);
var str = iter.toString(); // holds "[1, 2, 3]"Alternatively, you can use the built-in string function directly:
var iter = range(1, 3);
var str = string(iter); // holds "[1, 2, 3]"The main idea of iterators is to help generalise iteration, right? This library contains two important methods for iterating through iterators called forEach and fold.
The forEach method takes a procedure f as a parameter and calls it for every element of the iterator:
var iter = new Iterator([1, "a", false]);
iter.forEach(function(_x) {
show_message(_x); // prints 1
// "a"
// false
});Alternatively, the fold method captures the concept of applying some binary operation to all elements of the iterator. Let's say you have an array of strings ["hello", " ", "world"]. To concatenate these together we could use the + operator like so:
var array = ["hello", " ", "world"];
var hello_world = array[0] + array[1] + array[2];This idea of applying + over and over again is what fold achieves. Therefore, the previous section of code can be reduced to:
var array = ["hello", " ", "world"];
var iter = new Iterator(array);
var hello_world = iter.fold("", function(_left, _right) {
return _left + _right;
});Of course, this is a very basic case. But now imagine you have an array which is 100 values long, or an array which you don't know the size of, it becomes a lot trickier to add all items in that array together. That is why fold is so useful; it abstracts away the boilerplate of for loops and accumulators.
This section picks up the pace, and details additional operations which can be used to modify and process iterators.
As you might have noticed, unlike typical data structures, iterators can be infinite in size. This can make them very powerful for handling nested data structures and cyclic references.
All of this is achieved through lazy evaluation (also known as call-by-need). This means that new values are only ever generated when they are absolutely required. If you only care about the first 10 elements of an infinite iterator, then the remaining values will never be created.
Iterators can be stacked with multiple operations with barely any overhead or complexity from using raw arrays. Some examples of operations are zip, map, and concat.
The zip method takes a second iterator as an argument, and returns a new iterator which generate pairs of values that correspond to the generated values of each iterator:
var iter = new Iterator("hello");
iter.zip(new Iterator("world"));
var array = iter.collect(); // holds [["w", "h"], ["o", "e"], ["r", "l"], ["l", "l"], ["d", "o"]]The map method takes a function as an argument, and returns a new iterator which applies that function to each generated value of the previous iterator:
var iter = range(1, infinity);
iter.map(function(_x) { return _x * _x });
iter.take(4);
var array = iter.collect(); // holds [1, 4, 9, 16]The take method accepts a number n as an argument, and will produce a new iterator which will only generate up to that number of values:
var iter = range(1, 5);
iter.take(3);
var array = iter.collect(); // holds [1, 2, 3]The drop method takes a number n as an argument, and will produce a new iterator which will skip that number of values:
var iter = range(2, 8);
iter.drop(2); // drops [2, 3]
iter.take(3);
var array = iter.collect(); // holds [4, 5, 6]