go-fringe.go: Language change: `closed' function on channels has gone.

[fringe] / c-fringe.c

/* -*-c-*-
 *
 * Prosaic C implementation of a `same-fringe' solver.
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

/*----- Utilities ---------------------------------------------------------*/

static const char *progname = "?";

/* Mournfully announce an error and quit. */
static void bail(const char *m)
  { fprintf(stderr, "%s: %s\n", progname, m); exit(EXIT_FAILURE); }

/*----- Our node structure ------------------------------------------------*/

struct node {
  struct node *left;
  struct node *right;
  int data;
};

/* Make a new node and return it. */
static struct node *makenode(int data, struct node *left, struct node *right)
{
  struct node *n = malloc(sizeof(*n));

  if (!n) bail("no memory");
  n->data = data; n->left = left; n->right = right;
  return (n);
}

/* Free node N and its subtrees. */
static void freetree(struct node *n)
  { if (n) { freetree(n->left); freetree(n->right); free(n); } }

/* Recursive parser, used by `parsetree': read from string, updating `*p' as
 * we go.
 */
static struct node *rparsetree(const char **p)
{
  struct node *left, *right;
  int data;

  switch (**p) {
    case '(':
      (*p)++;
      left = rparsetree(p);
      data = *(*p)++;
      if (!data) bail("no data");
      right = rparsetree(p);
      if (**p != ')') bail("missing )");
      (*p)++;
      return (makenode(data, left, right));
    default:
      return (0);
  }
}

/* Parse a tree description from the string `p'.
 *
 * The syntax is as follows.
 *
 *	tree ::= empty | `(' tree char tree `)'
 *
 * where the ambiguity is resolved by always treating `(' as starting a tree
 * if a tree is expected.
 */
static struct node *parsetree(const char *p)
{
  struct node *n = rparsetree(&p);

  if (*p) bail("trailing junk");
  return (n);
}

/*----- Iteration ---------------------------------------------------------*/

struct nodeiter {
#define MAXDEPTH 64
  struct node *stack[MAXDEPTH];
  int sp;
};

/* Helper for `nextnode' and `iternodes'.  If N is not null, push it onto
 * NI's stack, and then do the same for N's left child.
 */
static void pushnodes(struct nodeiter *ni, struct node *n)
{
  int sp = ni->sp;

  while (n) {
    assert(sp < MAXDEPTH);
    ni->stack[sp++] = n;
    n = n->left;
  }
  ni->sp = sp;
}

/* Return the next node in order for the tree being traversed by NI, or null
 * if all nodes are exhausted.
 */
static struct node *nextnode(struct nodeiter *ni)
{
  struct node *n;

  if (!ni->sp)
    return (0);
  else {
    n = ni->stack[--ni->sp];
    pushnodes(ni, n->right);
    return (n);
  }
}

/* Initialize NI as an iterator iterating over the tree headed by N. */
static void iternodes(struct nodeiter *ni, struct node *n)
  { ni->sp = 0; pushnodes(ni, n); }

/*------ Fringe operations ------------------------------------------------*/

/* Print the characters stored in the tree headed by N to stdout, in
 * order. */
static void printfringe(struct node *n)
{
  struct nodeiter ni;

  for (iternodes(&ni, n); (n = nextnode(&ni)) != 0; )
    putchar(n->data);
  putchar('\n');
}

/* Return nonzero if traversing the trees headed by N and NN respectively
 * yields the same items in the same order.
 */
static int samefringep(struct node *n, struct node *nn)
{
  struct nodeiter ni, nni;

  iternodes(&ni, n); iternodes(&nni, nn);
  for (;;) {
    n = nextnode(&ni); nn = nextnode(&nni);
    if (!n) return (!nn);
    else if (!nn) return (0);
    else if (n->data != nn->data) return (0);
  }
}

/*----- Main program ------------------------------------------------------*/

int main(int argc, char *argv[])
{
  struct node *n, *nn;

  progname = argv[0];
  switch (argc) {
    case 2:
      n = parsetree(argv[1]);
      printfringe(n);
      freetree(n);
      break;
    case 3:
      n = parsetree(argv[1]); nn = parsetree(argv[2]);
      printf("%s\n", samefringep(n, nn) ? "match" : "no match");
      freetree(n); freetree(nn);
      break;
    default:
      bail("bad args");
      break;
  }
  return (0);
}

/*----- That's all, folks -------------------------------------------------*/