12.4 Access Functions

Export of DataStream

generator: % -> Generator T

Usage

T == Integer;
l: List T := [2,3,5,7,11,0];
s: DataStream T := stream generator l;
nonzeros: List T := [x for x in s while x > 0];

Description

Generate all elements of the stream.

This function always returns a generator that gives infinitely many elements. generator(x) is equivalent to the following code.

generate for i in 0.. repeat yield x.i;

Remarks

Note that g := generator(new()) does not give the empty generator, but rather a runtime error if g is asked for an element.

407aexports: DataStream 392a+   (386)  404a  410
generator: % -> Generator T;

Uses Generator 617.
407bimplementation: DataStream 392b+   (386)  404b  411
generator(x: %): Generator T == generate for i in 0.. repeat yield x.i;

Uses Generator 617.

Export of DataStream

elements: (%, startFromIndex: MachineInteger == 0) -> Generator T

Usage

s: DataStream Integer := stream 4;
g1: Generator Integer := generator s;
l1: List Integer := [i for i in g1 for k in 0..9];
assert(l1 = [4,4,4,4,4,4,4,4,4,4]);

g2: Generator Integer := elements s;
l2: List Integer := [i for i in g2 for k in 0..9];
assert(l2 = [4]);

t: DataStream Integer := stream generator [2,3,5,7,11];
g3: Generator Integer := elements(t, 2);
l3: List Integer := [i for i in g3 for k in 0..9];
assert(l3 = [5,7,11]);

g4: Generator Integer := elements(t, 10);
l4: List Integer := [i for i in g4 for k in 0..9];
assert(l4 = [11]);

Description

Generate all elements of the stream until the last elements repeats.

This function returns a generator that generates elements until the stream is known to be constant. It starts from the index in s that is given as a second argument.

The function elements is the inverse of stream in the sense that

h := elements(stream(g))

is basically a copy of the original generator g. But note that g is consumed and the cache of the stream stream(g) is filled while extracting elements from h.

Similarly, r := stream(elements(s)) is a copy of the stream s. But again, while elements are extracted from r, also the number of computed elements of s might change.

Calling r := stream(elements(s, 1)) creates a stream that is like the orignal s, but without the head element.

Remarks

It is no problem to access (and thus internally modify) the stream s while iterating over elements(s). For example, the following code correctly generates 6 elements.

g: Generator Integer := generator [1,2,3,4,5,6];
s: DataStream Integer := stream g;
a: List Integer := empty;
b: List Integer := empty;
for i in 0.. for x in elements s repeat {
  a := cons(x, a);
  b := cons(s.(2*i), b);
}

The values of a and b are [6,5,4,3,2,1] and [6,6,6,5,3,1], respectively.

See also

generator, constant?

410exports: DataStream 392a+   (386)  407a  412
elements: (%, startFromIndex: MachineInteger == 0) -> Generator T;

Uses Generator 617 and MachineInteger 67.
411implementation: DataStream 392b+   (386)  407b  413a
elements(x: %, startFromIndex: MachineInteger == 0): Generator T == generate {
        assert(startFromIndex >= 0);
        for i in startFromIndex.. repeat {
                z := x.i;
                if constant? x and i >= #x then {
                        if startFromIndex >= #x then yield z;
                        break;
                }
                yield z;
        }
}

Uses Generator 617 and MachineInteger 67.

Export of DataStream

apply: (%, MachineInteger) -> T

Usage

T == Integer;
l: List T := [2,3,5,7,11,0];
s: DataStream T := stream generator l;
x := s.3;
y := apply(s, 0);

Description

Access an entry of the stream.

A DataStream models an infinite object of the form

(s0,s1,s2,s3,...)
(172)
with si T for all i = 0,1,. The call apply(s, i) or s.i returns si.
412exports: DataStream 392a+   (386)  410  416
apply: (%, MachineInteger) -> T;

Uses MachineInteger 67.

If in apply(s, i) the parameter i #s and the stream s is not known to be constant, then new elements must be computed from the internally stored generator of s. During that process, the internal array must grow. For that we use the following resize! function. After its execution the cache corresponding to x must have room for sz entries (0,1,sz1).

413aimplementation: DataStream 392b+   (386)  411  413b
local resize!(x: %, sz: I): () == {
        assert(sz > 0);
        Xsize := X.size;
        sz <= Xsize => return; -- there is already enough room
        zero? Xsize => {-- reserve space for non-empty array
                X.cache := new sz;
                X.size := sz;
        }
        m := max(sz, 2*Xsize);
        X.cache := resize!(X.cache, Xsize, m);
        X.size := m;
}

Uses I 47.
ToDo 64
rhx 52 24-Aug-2006: Introduce a StreamException for the case

g: Generator T == generate {};
s: DataStream T == stream g;
t: T := s.0;  -- exception here

413bimplementation: DataStream 392b+   (386)  413a  418c
apply(x: %, i: I): T == {
        implementation: DataStream: apply: special cases 414a
        implementation: DataStream: apply: compute entries 414b
        X.cache.i;
}

Uses I 47.

In case the i-th entry has already been computed, we simply take it from the cache. If we know a stream x is eventually constant, then we can simply return the constant value by accessing the cache at index #x 1.

414aimplementation: DataStream: apply: special cases 414a  (413b)
assert(i >= 0);
n := #x;
i < n => data(x).i; -- here (n > 0 and not empty? X.cache)
constant? x => data(x).(prev n);

Here we know that the element we want to return, is not yet computed. So first we make room so that the element with index i can be stored into the cache.

414bimplementation: DataStream: apply: compute entries 414b  (413b)  414c
resize!(x, next i); -- make room for a.i

Now we fill the cache with all the elements up to the i-th.

414cimplementation: DataStream: apply: compute entries 414b+   (413b)  414b
a: PrimitiveArray T := X.cache; -- array of already computed elements
n: I := X.numberOfElements; -- number of computed elements in a
g: Generator T := X.gen;
while n <= i for t in g repeat { -- note the order of iterators!!!
        a.n := t;
        n := next n;
        X.numberOfElements := n;
}
zero? n => throw GeneratorException; -- no element provided
n := prev n; -- make e equal to the last computed index
-- now it could be that g is exhausted before e=i
if n < i then {X.constant? := true; i := n}

Uses Generator 617, GeneratorException 619b, and I 47.