2.24. Iterator

Iterators are objects which can traverse over a sequence without knowing the details of the sequence’s implementation.

The Iterator type is defined as follows:

iterator_type ::= iterator < type >

iterator<int>           // iterates over integer
iterator<const Foo&>    // iterates over Foo by reference

Iterators can be moved, but not copied or cloned.

Iterators can be created via the each function from a range, static array, or dynamic array. each functions are unsafe because the iterator does not capture its arguments:

unsafe {
    var it <- each ( [1,2,3,4] )
}

The most straightforward way to traverse an iterator is with a for loop:

for ( x in it ) {             // iterates over contents of 'it'
    print("x = {x}\n")
}

For the reference iterator, the for loop will provide a reference variable:

var t = fixed_array(1,2,3,4)
for ( x in t ) {        // x is int&
    x ++                // increases values inside t
}

Iterators can be created from lambdas (see Lambda) or generators (see Generator).

Calling delete on an iterator will make it sequence out and free its memory:

var it <- each_enum(Numbers one)
delete it                           // safe to delete

var it <- each_enum(Numbers one)
for ( x in it ) {
    print("x = {x}\n")
}
delete it                           // its always safe to delete sequenced out iterator

Loops and iteration functions do it automatically.

2.24.1. builtin iterators

Table keys and values iterators can be obtained via the keys and values functions:

var tab <- { "one"=>1, "two"=>2 }
for ( k,v in keys(tab),values(tab) ) {  // keys(tab) is iterator<string>
    print("{k} => {v}\n")               // values(tab) is iterator<int&>
}

It is possible to iterate over each character of the string via the each function:

unsafe {
    for ( ch in each("hello,world!") ) {   // string iterator is iterator<int>
        print("ch = {ch}\n")
    }
}

It is possible to iterate over each element of an enumeration via the each_enum function:

enum Numbers {
    one
    two
    ten = 10
}

for ( x in each_enum(Numbers.one) ) {       // argument is any value from said enumeration
    print("x = {x}\n")
}

2.24.2. builtin iteration functions

The empty function checks if an iterator is null or already sequenced out:

unsafe {
    var it <- each ( fixed_array(1,2,3,4) )
    for ( x in it ) {
        print("x = {x}\n")
    }
    verify(empty(it))           // iterator is sequenced out
}

More complicated iteration patterns may require the next function:

var x : int
while ( next(it,x) ) {       // this is semantically equivalent to the `for x in it`
    print("x = {x}\n")
}

Next can only operate on copyable types.

2.24.3. low level builtin iteration functions

_builtin_iterator_first, _builtin_iterator_next, and _builtin_iterator_close address the regular lifecycle of the iterator. A semantic equivalent of the for loop can be explicitly written using these operations:

var it <- each(range(0,10))
var i : int
var pi : void?
unsafe {
    pi = reinterpret<void?> ( addr(i) )
}
if ( _builtin_iterator_first(it,pi) ) {
    print("i = {i}\n")
    while ( _builtin_iterator_next(it,pi) ) {
        print("i = {i}\n")
    }
    _builtin_iterator_close(it,pi)
}

_builtin_iterator_iterate is one function to rule them all. It acts like all 3 functions above. On a non-empty iterator it starts with ‘first’, then proceeds to call next until the sequence is exhausted. Once the iterator is sequenced out, it calls close:

var it <- each(range(0,10))
var i : int
var pi : void?
unsafe {
    pi = reinterpret<void?> ( addr(i) )
}
while ( _builtin_iterator_iterate(it,pi) ) {     // this is equivalent to the example above
    print("i = {i}\n")
}

2.24.4. next implementation details

The function next is implemented as follows:

def next ( it:iterator<auto(TT)>; var value : TT& ) : bool {
    static_if (!typeinfo can_copy(type<TT>)) {
        concept_assert(false, "requires type
         which can be copied")
    } static_elif (typeinfo is_ref_value(type<TT>)) {
        var pValue : TT - & ?
        unsafe {
            if ( _builtin_iterator_iterate(it, addr(pValue)) ) {
                value = *pValue
                return true
            } else {
                return false
            }
        }
    } else {
        unsafe {
            return _builtin_iterator_iterate(it, addr(value))
        }
    }

It is important to notice that builtin iteration functions accept pointers instead of references.