Commit | Line | Data |
---|---|---|
d888ccd5 MW |
1 | /* -*-go-*- |
2 | * | |
3 | * Same-fringe solver. | |
4 | */ | |
5 | ||
6 | package main | |
7 | ||
8 | import ( | |
9 | "fmt"; | |
10 | "io"; | |
11 | "os"; | |
12 | ) | |
13 | ||
14 | ///-------------------------------------------------------------------------- | |
15 | /// Utilities. | |
16 | ||
17 | var prog = os.Args[0]; | |
18 | ||
19 | func bail(msg string) { | |
20 | fmt.Fprintf(os.Stderr, "%s: %s\n", prog, msg); | |
21 | os.Exit(1); | |
22 | } | |
23 | ||
24 | ///-------------------------------------------------------------------------- | |
25 | /// Iteration protocol. | |
26 | /// | |
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. | |
30 | ||
31 | // A convenient abbreviation. | |
32 | type any interface {} | |
33 | ||
34 | type Iterable interface { | |
35 | // Simply put the items to the channel CH one at a time. | |
36 | Iterate(ch chan<- any); | |
37 | } | |
38 | ||
39 | // An iterator. | |
40 | type Iterator <-chan any; | |
41 | ||
42 | // Returns an iterator for a given iterable thing. | |
43 | func MakeIterator(it Iterable) Iterator { | |
44 | ch := make(chan any); | |
45 | go func () { | |
46 | it.Iterate(ch); | |
47 | close(ch); | |
48 | } (); | |
49 | return ch; | |
50 | } | |
51 | ||
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) { | |
55 | item := <-it; | |
56 | if closed(it) { return nil, false; } | |
57 | return item, true; | |
58 | } | |
59 | ||
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 { | |
63 | for { | |
64 | a, any_a := ia.Next(); | |
65 | b, any_b := ib.Next(); | |
66 | if !any_a { return !any_b } | |
67 | if a != b { break } | |
68 | } | |
69 | return false; | |
70 | } | |
71 | ||
72 | ///-------------------------------------------------------------------------- | |
73 | /// Node structure. | |
74 | ||
75 | // Just a simple binary tree. | |
76 | type Node struct { | |
77 | data byte; | |
78 | left, right *Node; | |
79 | } | |
80 | ||
81 | // Iteration is easy. Note that recursion is fine here: this is just a | |
82 | // simple function. | |
83 | func (n *Node) Iterate(ch chan<- any) { | |
84 | if n == nil { return } | |
85 | n.left.Iterate(ch); | |
86 | ch <- n.data; | |
87 | n.right.Iterate(ch); | |
88 | } | |
89 | ||
90 | // Parse a tree from a textual description. The syntax is simple: | |
91 | // | |
92 | // tree ::= empty | `(' tree char tree `)' | |
93 | // | |
94 | // where the ambiguity is resolved by declaring that a `(' is a tree if we're | |
95 | // expecting a tree. | |
96 | func ParseTree(s string) *Node { | |
97 | var parse func(int) (*Node, int); | |
98 | n := len(s); | |
99 | i := 0; | |
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") } | |
104 | data := s[i]; | |
105 | right, i := parse(i + 1); | |
106 | if i >= n || s[i] != ')' { bail("missing )") } | |
107 | return &Node { data, left, right }, i + 1; | |
108 | } | |
109 | return nil, i; | |
110 | }; | |
111 | t, i := parse(0); | |
112 | if i < n { bail("trailing junk") } | |
113 | return t; | |
114 | } | |
115 | ||
116 | ///-------------------------------------------------------------------------- | |
117 | /// Main program. | |
118 | ||
119 | func main() { | |
120 | switch len(os.Args) { | |
121 | case 2: | |
122 | t := ParseTree(os.Args[1]); | |
123 | i := MakeIterator(t); | |
124 | for { | |
125 | item, winp := i.Next(); | |
126 | if !winp { break } | |
127 | fmt.Printf("%c", item); | |
128 | } | |
129 | fmt.Printf("\n"); | |
130 | case 3: | |
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"); | |
135 | } else { | |
136 | io.WriteString(os.Stdout, "no match\n"); | |
137 | } | |
138 | default: | |
139 | bail("bad args"); | |
140 | } | |
141 | } | |
142 | ||
143 | ///----- That's all, folks -------------------------------------------------- |