14 ///--------------------------------------------------------------------------
17 var prog = os.Args[0];
19 func bail(msg string) {
20 fmt.Fprintf(os.Stderr, "%s: %s\n", prog, msg);
24 ///--------------------------------------------------------------------------
25 /// Iteration protocol.
27 /// A data type implements the iteration protocol by providing a method which
28 /// simply writes its consistuent elements to a provided channel. The
29 /// iteration machinery runs this method in a separate goroutine.
31 // A convenient abbreviation.
34 type Iterable interface {
35 // Simply put the items to the channel CH one at a time.
36 Iterate(ch chan<- any);
40 type Iterator <-chan any;
42 // Returns an iterator for a given iterable thing.
43 func MakeIterator(it Iterable) Iterator {
52 // Returns the next item from an iterator IT. If there is indeed an item
53 // available, return it and true; otherwise return nil and false.
54 func (it Iterator) Next() (any, bool) {
56 if closed(it) { return nil, false; }
60 // Answer whether the iterators return the same items in the same order.
61 // Equality is determined using `=='. Maybe we'll do better some day.
62 func SameIterators(ia, ib Iterator) bool {
64 a, any_a := ia.Next();
65 b, any_b := ib.Next();
66 if !any_a { return !any_b }
72 ///--------------------------------------------------------------------------
75 // Just a simple binary tree.
81 // Iteration is easy. Note that recursion is fine here: this is just a
83 func (n *Node) Iterate(ch chan<- any) {
84 if n == nil { return }
90 // Parse a tree from a textual description. The syntax is simple:
92 // tree ::= empty | `(' tree char tree `)'
94 // where the ambiguity is resolved by declaring that a `(' is a tree if we're
96 func ParseTree(s string) *Node {
97 var parse func(int) (*Node, int);
100 parse = func(i int) (*Node, int) {
101 if i < n && s[i] == '(' {
102 left, i := parse(i + 1);
103 if i >= n { bail("no data") }
105 right, i := parse(i + 1);
106 if i >= n || s[i] != ')' { bail("missing )") }
107 return &Node { data, left, right }, i + 1;
112 if i < n { bail("trailing junk") }
116 ///--------------------------------------------------------------------------
120 switch len(os.Args) {
122 t := ParseTree(os.Args[1]);
123 i := MakeIterator(t);
125 item, winp := i.Next();
127 fmt.Printf("%c", item);
131 ia := MakeIterator(ParseTree(os.Args[1]));
132 ib := MakeIterator(ParseTree(os.Args[2]));
133 if SameIterators(ia, ib) {
134 io.WriteString(os.Stdout, "match\n");
136 io.WriteString(os.Stdout, "no match\n");
143 ///----- That's all, folks --------------------------------------------------