mdw@git.distorted.org.uk Git - 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, anyp := <-it;
  56         return item, anyp;
  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 {
  63                 a, any_a := ia.Next();
  64                 b, any_b := ib.Next();
  65                 if !any_a { return !any_b }
  66                 if a != b { break }
  67         }
  68         return false;
  69 }
  70
  71 ///--------------------------------------------------------------------------
  72 /// Node structure.
  73
  74 // Just a simple binary tree.
  75 type Node struct {
  76         data byte;
  77         left, right *Node;
  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 }
  84         n.left.Iterate(ch);
  85         ch <- n.data;
  86         n.right.Iterate(ch);
  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 {
  96         var parse func(int) (*Node, int);
  97         n := len(s);
  98         i := 0;
  99         parse = func(i int) (*Node, int) {
 100                 if i < n && s[i] == '(' {
 101                         left, i := parse(i + 1);
 102                         if i >= n { bail("no data") }
 103                         data := s[i];
 104                         right, i := parse(i + 1);
 105                         if i >= n || s[i] != ')' { bail("missing )") }
 106                         return &Node { data, left, right }, i + 1;
 107                 }
 108                 return nil, i;
 109         };
 110         t, i := parse(0);
 111         if i < n { bail("trailing junk") }
 112         return t;
 113 }
 114
 115 ///--------------------------------------------------------------------------
 116 /// Main program.
 117
 118 func main() {
 119         switch len(os.Args) {
 120         case 2:
 121                 t := ParseTree(os.Args[1]);
 122                 i := MakeIterator(t);
 123                 for {
 124                         item, winp := i.Next();
 125                         if !winp { break }
 126                         fmt.Printf("%c", item);
 127                 }
 128                 fmt.Printf("\n");
 129         case 3:
 130                 ia := MakeIterator(ParseTree(os.Args[1]));
 131                 ib := MakeIterator(ParseTree(os.Args[2]));
 132                 if SameIterators(ia, ib) {
 133                         io.WriteString(os.Stdout, "match\n");
 134                 } else {
 135                         io.WriteString(os.Stdout, "no match\n");
 136                 }
 137         default:
 138                 bail("bad args");
 139         }
 140 }
 141
 142 ///----- That's all, folks --------------------------------------------------