Oberon || Library || Module Index || Search Engine || Definition || Module


Ulm's Oberon Library:
Iterators


NAME

Iterators - sequential access of data structures

SYNOPSIS

TYPE Reference = Objects.Object; Mode = SHORTINT;
TYPE Iterator = POINTER TO IteratorRec;
TYPE IteratorRec = RECORD (Services.ObjectRec) END;
TYPE IteratorProc = PROCEDURE (it: Iterator; ref: Reference; mode: Mode);


PROCEDURE Create(VAR it: Iterator; itproc: IteratorProc; ref: Reference; mode: Mode); PROCEDURE CreateQuickIterator(VAR it: Iterator; itproc: IteratorProc; ref: Reference; mode: Mode);

PROCEDURE Yield(it: Iterator; object: Objects.Object); PROCEDURE Get(it: Iterator; VAR object: Objects.Object) : BOOLEAN;

DESCRIPTION

Iterators offers a convenient interface for iterators and is based on coroutines. An iterator allows to access a complex data structure sequentially object for object. Once an iterator has been created, there is only one pass through all objects. I.e. it is not possible to rewind an iterator.

Two parties belong to an iterator: a producer and a consumer. The producer examines all objects of a data structure and ``produces'' them by Yield. The consumer retrieves these objects by Get. The consumer is free to ``consume'' all objects (i.e. until Get returns FALSE) or to stop calling Get at any time. For this reason, the producer cannot be sure to be continued after calling Yield.

Create creates an iterator and is usually called by the module which owns the data structure which is to be visited. itproc is a procedure which will be called by a newly created coroutine. In contrast to ordinary coroutine procedures, itproc is free to execute RETURN which causes a subsequent Get to return FALSE. ref and mode will be passed to itproc and not interpreted by Iterators. ref is intended to be a reference to the data structure and mode may be convenient to specify directions or keys.

Alternatively, an iterator can be created using CreateQuickIterator that does not cause a coroutine to be created. Instead, the first invocation of Get causes all available objects to be generated. This is useful for small sequences or in cases where no significant computational overhead is required in generating the objects.

EXAMPLE

A binary tree is given on the producer side. IterateTree would remain private while CreateIterator may be exported.
(* excerpt of module Trees *)

CONST
   preorder = 0; inorder = 1; postorder = 2;
TYPE
   Tree = POINTER TO TreeRec;
   TreeRec =
      RECORD
         (Objects.ObjectRec)
         object: Objects.Object;
         left, right: Tree;
      END;

PROCEDURE IterateTree(it: Iterators.Iterator;
                      ref: Objects.Object;
                      mode: SHORTINT);
BEGIN
   IF ref = NIL THEN RETURN END;
   WITH ref: Tree DO
      IF mode = preorder THEN
         Iterators.Yield(it, ref.object);
      END;
      IterateTree(it, ref.left, mode);
      IF mode = inorder THEN
         Iterators.Yield(it, ref.object);
      END;
      IterateTree(it, ref.right, mode);
      IF mode = postorder THEN
         Iterators.Yield(it, ref.object);
      END;
   END;
END IterateTree;

PROCEDURE CreateIterator(VAR it: Iterator; tree: Tree; order: SHORTINT);
BEGIN
   Iterators.Create(it, IterateTree, tree, order);
END CreateIterator;

A consumer is easily written. After creating an iterator by Trees.CreateIterator, a tree may be examined by Iterators.Get:

   VAR
      iterator: Iterators.Iterator;
      tree: Trees.Tree;
      object: Objects.Object;

(* ... *)

Trees.CreateIterator(iterator, tree, Trees.inorder);
WHILE Iterators.Get(iterator, object) DO
   (* examine object *)
END;

SEE ALSO

RemoteIterators
supports import and export of iterators

Edited by: borchert, last change: 2005/08/25, revision: 1.3, converted to HTML: 2005/08/25

Oberon || Library || Module Index || Search Engine || Definition || Module