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