chiark - git - mdw - fringe/blob - go-fringe.go

   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 --------------------------------------------------