--* From postmaster%watson.vnet.ibm.com@yktvmv.watson.ibm.com  Tue Jul  5 09:16:18 1994
--* Received: from yktvmv-ob.watson.ibm.com by asharp.watson.ibm.com (AIX 3.2/UCB 5.64/930311)
--*           id AA24499; Tue, 5 Jul 1994 09:16:18 -0400
--* Received: from watson.vnet.ibm.com by yktvmv.watson.ibm.com (IBM VM SMTP V2R3)
--*    with BSMTP id 2737; Tue, 05 Jul 94 09:16:20 EDT
--* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0"
--*           id <A.JENKS.NOTE.VAGENT2.6473.Jul.05.09:16:19.-0400>
--*           for asbugs@watson; Tue, 05 Jul 94 09:16:20 -0400
--* Received: from YKTVMV by watson.vnet.ibm.com with "VAGENT.V1.0"
--*           id 6469; Tue, 5 Jul 1994 09:16:19 EDT
--* Received: from leonardo.watson.ibm.com by yktvmv.watson.ibm.com
--*    (IBM VM SMTP V2R3) with TCP; Tue, 05 Jul 94 09:16:19 EDT
--* Received: by leonardo.watson.ibm.com (AIX 3.2/UCB 5.64/920123)
--*           id AA23109; Tue, 5 Jul 1994 09:11:34 -0400
--* Date: Tue, 5 Jul 1994 09:11:34 -0400
--* From: jenks@leonardo.watson.ibm.com
--* X-External-Networks: yes
--* Message-Id: <9407051311.AA23109@leonardo.watson.ibm.com>
--* To: asbugs@watson.ibm.com
--* Subject: [3] asharp -ginterp xtree.as => [/u/jenks/dimacs94/ex.pm/xtree.as][?]

--@ Fixed  by:  PI   Tue Aug 2 15:05:33 EDT 1994 
--@ Tested by:  NotNeeded 
--@ Summary:    Not a bug. Wrong use of Tuple domain. 


--> testint
--> testrun
#include "aslib.as"

Xtree(S: BasicType): BasicType with {
	empty: %;
	tree:  S  -> %;
        tree:  (S, List %) -> %;
        bracket: Tuple Union(S,%) -> %;
        leaf?: % -> Boolean;
	empty?: % -> Boolean;
        generator: % -> Generator S;
	node:   % -> S;
        child: (%, Integer) -> %;
        preorder: % -> Generator S
} == add {
	Rep ==> Record(node: S, args: List %);
	import from Rep;
        import from List %;
	tree(s: S): % == per [s, nil];
	tree(s: S, l: List %): % == per [s, l];
	empty: % == nil$Pointer pretend %;
	sample: % == empty;
	empty?(t: %): Boolean == nil?(t pretend Pointer)$Pointer;
        leaf? (t: %): Boolean == empty? ((rep t).args);
        node(t: %): S == (rep t) . node;

        child(t: %, n: Integer): % == {
		empty? t => error "Taking a part of a non-empty tree";
                n <= 0   => error "child must take a positive index";
                apply((rep t) . args, n pretend SingleInteger)
        }

        bracket(tup: Tuple Union(S, %)): % == {
          u: List Tuple Union(S, %) := [tup];
          root := {
            first u case S => first u;
            error "first element must be a scalar"
          }
          branches := {
            acc: List % := nil;
            for x in rest u repeat {
              y: % := {
                x case S => tree x;
                x
              }
              acc := cons(x,acc);
            }
            reverse acc
          }
          tree(root, branches)
        }

        generator(l: %): Generator S == generate {
                yield l . node;
                for x in l . args repeat yield x
        }

	(t1: %) = (t2: %): Boolean == {
		import from S;
		empty? t1 and  empty? t2 => true;
		empty? t1 or   empty? t2 => false;
		(rep t1).node = (rep t2).node and (rep t1).args = (rep t2).args
	}

        preorder(t: %) : Generator S == generate { not empty? t => {
                yield node t;
                for branch in (rep t).args repeat
                   for val in preorder branch repeat yield val
        }}

	(outp: TextWriter) << (t: %): TextWriter == {
		import from String;
		import from S;
		empty? t => outp << "empty";
                leaf? t  => outp << (rep t) . node;
                outp << "[" << (rep t) . node;
                for x in (rep t) . args repeat outp << ", " << x;
                outp << "]"
	}
}

-- Testing your solution
f(): () == {
        import from String;
        import from TextWriter;
        import from Xtree(String);
        import from List(Xtree(String));
        t := tree "a";
        print << "The tree is " << t;
--        t := tree("*", [tree("+", [tree "a",tree "b"]),
--                                      tree("-", [tree "c",tree "d"])]);
        print << "The tree is " << t;
        print << "Preorder: ";
        for s in preorder t repeat print << s << " ";
        print << newline;

}

f();