juno-machine/src/Egraph.i3


 Copyright (C) 1992, Digital Equipment Corporation                         
 All rights reserved.                                                      
 See the file COPYRIGHT for a full description.                            
                                                                           
 Last modified on Fri Mar 26 16:05:52 PST 1993 by heydon                   

An Egraph.T is a node of an oriented, directed graph in which every node has out-degree 0 or 2 and on which there is an equivalence relation.

INTERFACE Egraph;

IMPORT Equiv;

TYPE
  T <: Public;
  Public = Equiv.T OBJECT
    car, cdr: T := NIL;
  METHODS
    init(): T;
  END;

END Egraph.
NEW(Egraph.T, car := a, cdr := b).init() returns a new node in its own equivalence class with children initialized to the values a and b. For any existing node x, x.init().find() = x. However, the node x' = x.init() is not necessarily in its own equivalence class; there may be other existing elements y such that y.find() = x'.

The car and cdr fields are READONLY after initialization.