/* searchtree.q: generic search tree data structure (11-07-1993, revised
   03-02-2002 AG) */

/* This file is part of the trees.q sample script. */

public type SearchTree;

/* interface operations */

public members T, insert T X, delete T X, member T X;

/* Generic operations on search trees (see bintree.q and avltree.q for
   examples of concrete subtypes): union, diff and intersect compute
   the union, difference and intersection of two search trees, subeq
   determines whether all elements of one tree are contained in another.
   These operations apply to all subtypes of SearchTree, and you can also
   mix argument types. The result type of union, diff and intersect
   is the type of the first argument. */

public union T1 T2, diff T1 T2, intersect T1 T2, subeq T1 T2;

union	  T1:SearchTree T2:SearchTree	= foldl insert T1 (members T2);
diff	  T1:SearchTree T2:SearchTree	= foldl delete T1 (members T2);
intersect T1:SearchTree T2:SearchTree	= diff T1 (diff T1 T2);
subeq	  T1:SearchTree T2:SearchTree	= all (member T2) (members T1);