PPP Exercises: Iterations in Trees

Extend the module 'tree' of the exercise Libraries and Modules with the functions 'create' and 'elements'. Implementing the function 'elements' you may use the module 'iter'. However you should consider that an implementation of your own, which doesn't use 'iter', might be more efficient. So if you feel fit enough by now, go ahead and try on your own, i.e. using only the type 'IterRep.T'.

 
interface Tree
import
  :Iter
export
  T(E <:Ok) <:Ok

  error :Exception end
  
  mkLeaf(E <:Ok  e :E) :T(E)
  (* Make a leaf node with element 'e'. *)
  
  mkNode(E <:Ok  left, right :T(E)) :T(E)
  (* Make an inner node with two subtrees 'left' & 'right'. *) 

  isLeaf(E <:Ok  t :T(E)) :Bool
  (* Return 'true' if 't' is a leaf, otherwise 'false'. *)

  getValue(E <:Ok  t :T(E)) :E
  (* Return the value of a leaf.
     Raise error if 't' is a node. *)

  getLeft, getRight(E <:Ok  t :T(E)) :T(E)
  (* Return left or right subtree of node 't'.
     Raise error if 't' is a leaf. *)

(* >>>> new *)

  create(E <:Ok  from :Iter.T(E)) :T(E)
  (* Create a tree from the iteration 'from'. *)
  
  elements(E <:Ok  t :T(E)) :Iter.T(E)
  (* Return an iteration over the elements of the tree 't'. *) 

(* new <<<< *)
  
end;

Test your module with this code:

import tree iter print fmt;
let fromIter = iter.enum of 1 2 3 4 5 6 7 end
let aTree = tree.create(fromIter)
let toIter = tree.elements(aTree);
let var x = toIter
while not(x.empty()) do
   print.int(x.get()) print.ln()
   x := x.rest()
end;
print.iter(toIter fmt.int);

Ulrike Steffens, 1994