// file tree-tools.choc
// author : E. Duris
// date : 24.04.97

class Tree { The corresponding Java code

// Constructor (production) declarations

case Tip (int);
case Fork (Tree, Tree);

// Attributes and methods declarations

// BIRD constructs an homomorphic tree with all leaves
// at the minimal leaf value in the input tree

Tree bird
{

int hmin;
int min;
Tree result;

case Tip (x) :

this.min = x;
this.result = Tip(this.hmin);

case Fork (left, right) :

this.min = (left.min > right.min) ? right.min : left.min ;
this.result= Fork(left.result,right.result);
left.hmin = this.hmin;
right.hmin = this.hmin;

case bird :

this.hmin = this.min;
return this.result;

} // end bird

// FLATTEN builds a list with the input tree leaves (here, from left to right)

List flatten
{

List h;
List result;

case Tip (x) :

this.result = Cons(x,this.h);

case Fork (left, right) :

right.h = this.h;
left.h = right.result;
this.result = left.result;

case flatten :

this.h = Nil;
return this.result;

} // end flatten

// MIRROR constructs the homomorphic tree with leaves in reverse order

Tree mirror
{

List result;

case Tip (x) :

this.result = Tip(x);

case Fork (left, right) :

this.result = Fork(right.result,left.result);

case mirror :

return this.result;

} // end mirror

// Method SIGMA : construct the homomorphic tree with
// added (accumulated) leaves, from left to right

Tree sigma
{

int acc;
int h;
Tree result;

case Tip (x) :

this.acc = this.h + x;
this.result = Tip(this.h + x);

case Fork (left, right) :

left.h = this.h;
right.h = left.acc;
this.acc = right.acc;
this.result = Fork(left.result,right.result);

case mirror :

this.h = 0;
return this.result;

} // end sigma

} // end class tree