This file contains (part of) the code from "Algorithms in C, Third Edition,
Parts 1-4," by Robert Sedgewick, and is covered under the copyright
and warranty notices in that book. Permission is granted for this
code to be used for educational purposes in association with the text,
and for other uses not covered by copyright laws, provided that
the following notice is included with the code:

 	"This code is from "Algorithms in C, Third Edition,"
	by Robert Sedgewick, Addison Wesley Longman, 1998."

Commercial uses of this code require the explicit written
permission of the publisher. Send your request for permission,
stating clearly what code you would like to use, and in what
specific way, to: aw.cse@aw.com

CHAPTER 4. Abstract Data Types
-----
void STACKinit(int);
 int STACKempty();
void STACKpush(Item);
Item STACKpop();
-----
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
  { char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == '+')
          STACKpush(STACKpop()+STACKpop());
        if (a[i] == '*')
          STACKpush(STACKpop()*STACKpop());
        if ((a[i] >= '0') && (a[i] <= '9')) 
          STACKpush(0);
        while ((a[i] >= '0') && (a[i] <= '9')) 
          STACKpush(10*STACKpop() + (a[i++]-'0')); 
      }
    printf("%d \n", STACKpop());
  }       
-----
#include <stdio.h>
#include <string.h>
#include "Item.h"
#include "STACK.h"
main(int argc, char *argv[])
  { char *a = argv[1]; int i, N = strlen(a);
    STACKinit(N);
    for (i = 0; i < N; i++)
      {
        if (a[i] == ')')
          printf("%c ", STACKpop()); 
        if ((a[i] == '+') || (a[i] == '*')) 
          STACKpush(a[i]);
        if ((a[i] >= '0') && (a[i] <= '9')) 
          printf("%c ", a[i]); 
      }
    printf("\n");
  }       
-----
#include <stdlib.h>
#include "Item.h"
#include "STACK.h"
static Item *s;
static int N;
void STACKinit(int maxN)
  { s = malloc(maxN*sizeof(Item)); N = 0; }
int STACKempty()
  { return N == 0; }
void STACKpush(Item item)
  { s[N++] = item; }
Item STACKpop()
  { return s[--N]; }

-----
#include <stdlib.h>
#include "Item.h"
typedef struct STACKnode* link;
struct STACKnode { Item item; link next; };
static link head;
link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
void STACKinit(int maxN) 
  { head = NULL; }
int STACKempty()
  { return head == NULL; }
STACKpush(Item item)
  { head = NEW(item, head); }
Item STACKpop()
  { Item item = head->item;
    link t = head->next; 
    free(head); head = t;
    return item;
  }
-----
void UFinit(int);
 int UFfind(int, int);
 int UFunion(int, int);
-----
#include <stdio.h>
#include "UF.h"
main(int argc, char *argv[])
  { int p, q, N = atoi(argv[1]);
    UFinit(N);
    while (scanf("%d %d", &p, &q) == 2)
      if (!UFfind(p, q)) 
        { UFunion(p, q); printf(" %d %d\n", p, q); }
 }
-----
#include <stdlib.h>
#include "UF.h"
static int *id, *sz;
void UFinit(int N)
  { int i;
    id = malloc(N*sizeof(int)); 
    sz = malloc(N*sizeof(int)); 
    for (i = 0; i < N; i++) 
      { id[i] = i; sz[i] = 1; }
  }
int find(int x)
  { int i = x; 
    while (i != id[i]) i = id[i]; return i; }
int UFfind(int p, int q)
  { return (find(p) == find(q)); }
int UFunion(int p, int q)
  { int i = find(p), j = find(q);
    if (i == j) return;
    if (sz[i] < sz[j])
         { id[i] = j; sz[j] += sz[i]; }
    else { id[j] = i; sz[i] += sz[j]; }
  }
-----
void QUEUEinit(int);
 int QUEUEempty();
void QUEUEput(Item);
Item QUEUEget();
-----
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
static link head, tail;
link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
void QUEUEinit(int maxN) 
  { head = NULL; }
int QUEUEempty()
  { return head == NULL; }
QUEUEput(Item item)
  { 
    if (head == NULL)
      { head = (tail = NEW(item, head)); return; }
    tail->next = NEW(item, tail->next); 
    tail = tail->next;
  }
Item QUEUEget()
  { Item item = head->item;
    link t = head->next; 
    free(head); head = t;
    return item;
  }
-----
#include <stdlib.h>
#include "Item.h"
static Item *q;
static int N, head, tail;
void QUEUEinit(int maxN)
  { q = malloc((maxN+1)*sizeof(Item)); 
    N = maxN+1; head = N; tail = 0; }
int QUEUEempty()
  { return head % N == tail; }
void QUEUEput(Item item)
  { q[tail++] = item; tail = tail % N; }
Item QUEUEget()
  { head = head % N; return q[head++]; }

-----
#include <stdlib.h>
static int *s, *t;
static int N;
void STACKinit(int maxN)
  { int i;
    s = malloc(maxN*sizeof(int)); 
    t = malloc(maxN*sizeof(int)); 
    for (i = 0; i < maxN; i++) t[i] = 0;
    N = 0; 
  }
int STACKempty()
  { return !N; }
void STACKpush(int item)
  { 
    if (t[item] == 1) return;
    s[N++] = item; t[item] = 1;
  }
int STACKpop()
  { N--; t[s[N]] = 0; return s[N]; }
-----
#include <stdio.h>
#include <math.h>
#include "COMPLEX.h"
#define PI 3.141592625
main(int argc, char *argv[])
  { int i, j, N = atoi(argv[1]);
    Complex t, x;
    printf("%dth complex roots of unity\n", N);
    for (i = 0; i < N; i++)
      { float r = 2.0*PI*i/N;
        t = COMPLEXinit(cos(r), sin(r));
        printf("%2d %6.3f %6.3f ", i, Re(t), Im(t));
        for (x = t, j = 0; j < N-1; j++)
          x = COMPLEXmult(t, x);
        printf("%6.3f %6.3f\n", Re(x), Im(x));
      }
 }
-----
typedef struct { float Re; float Im; } Complex;
Complex COMPLEXinit(float, float);
  float Re(Complex);
  float Im(Complex);
Complex COMPLEXmult(Complex, Complex);
-----
#include "COMPLEX.h"
Complex COMPLEXinit(float Re, float Im)
  { Complex t; t.Re = Re; t.Im = Im; return t; }
float Re(Complex z)
  { return z.Re; }
float Im(Complex z)
  { return z.Im; }
Complex COMPLEXmult(Complex a, Complex b)
  { Complex t; 
    t.Re = a.Re*b.Re - a.Im*b.Im; 
    t.Im = a.Re*b.Im + a.Im*b.Re; 
    return t; 
  }
-----
typedef struct complex *Complex;
Complex COMPLEXinit(float, float);
  float Re(Complex);
  float Im(Complex);
Complex COMPLEXmult(Complex, Complex);
-----
#include <stdlib.h>
#include "COMPLEX.h"
struct complex { float Re; float Im; };
Complex COMPLEXinit(float Re, float Im)
  { Complex t = malloc(sizeof *t); 
    t->Re = Re; t->Im = Im; 
    return t; 
  }
float Re(Complex z)
  { return z->Re; }
float Im(Complex z)
  { return z->Im; }
Complex COMPLEXmult(Complex a, Complex b)
  { 
    return COMPLEXinit(Re(a)*Re(b) - Im(a)*Im(b),  
                       Re(a)*Im(b) + Im(a)*Re(b));
  }

-----
typedef struct queue *Q;
void QUEUEdump(Q);
   Q QUEUEinit(int maxN);
 int QUEUEempty(Q);
void QUEUEput(Q, Item);
Item QUEUEget(Q);
-----
#include <stdio.h>
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
#define M 10
main(int argc, char *argv[])
  { int i, j, N = atoi(argv[1]); 
    Q queues[M]; 
    for (i = 0; i < M; i++) 
      queues[i] = QUEUEinit(N);
    for (i = 0; i < N; i++)
      QUEUEput(queues[rand() % M], j);
    for (i = 0; i < M; i++, printf("\n"))
      for (j = 0; !QUEUEempty(queues[i]); j++) 
        printf("%3d ", QUEUEget(queues[i]));
  }
-----
#include <stdlib.h>
#include "Item.h"
#include "QUEUE.h"
typedef struct QUEUEnode* link;
struct QUEUEnode { Item item; link next; };
struct queue { link head; link tail; };
link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
Q QUEUEinit(int maxN) 
  { Q q = malloc(sizeof *q); 
    q->head = NULL; q->tail = NULL; 
    return q;
  }
int QUEUEempty(Q q)
  { return q->head == NULL; }
void QUEUEput(Q q, Item item)
  { 
    if (q->head == NULL)
      { q->tail = NEW(item, q->head)
        q->head = q->tail; return; }
    q->tail->next = NEW(item, q->tail->next); 
    q->tail = q->tail->next;
  }
Item QUEUEget(Q q)
  { Item item = q->head->item;
    link t = q->head->next;
    free(q->head); q->head = t;
    return item;
  }
----
#include <stdio.h>
#include <stdlib.h>
#include "POLY.h"
main(int argc, char *argv[])
  { int N = atoi(argv[1]); float p = atof(argv[2]);
    Poly t, x; int i, j;
    printf("Binomial coefficients\n");
    t = POLYadd(POLYterm(1, 1), POLYterm(1, 0));
    for (i = 0, x = t; i < N; i++)
      { x = POLYmult(t, x); showPOLY(x); }
    printf("%f\n", POLYeval(x, p));
 }
-----
typedef struct poly *Poly;
 void showPOLY(Poly);
 Poly POLYterm(int, int);
 Poly POLYadd(Poly, Poly);
 Poly POLYmult(Poly, Poly);
float POLYeval(Poly, float);
-----
#include <stdlib.h>
#include "POLY.h"
struct poly { int N; int *a; };
Poly POLYterm(int coeff, int exp)
  { int i; Poly t = malloc(sizeof *t);
    t->a = malloc((exp+1)*sizeof(int));
    t->N = exp+1; t->a[exp] = coeff;
    for (i = 0; i < exp; i++) t->a[i] = 0;    
    return t;
  }    
Poly POLYadd(Poly p, Poly q)
  { int i; Poly t;
    if (p->N < q->N) { t = p; p = q; q = t; }
    for (i = 0; i < q->N; i++) p->a[i] += q->a[i];
    return p;
  }
Poly POLYmult(Poly p, Poly q)
  { int i, j;
    Poly t = POLYterm(0, (p->N-1)+(q->N-1));
    for (i = 0; i < p->N; i++) 
      for (j = 0; j < q->N; j++) 
        t->a[i+j] += p->a[i]*q->a[j];
    return t;
  }
float POLYeval(Poly p, float x)
  { int i; double t = 0.0;
    for (i = p->N-1; i >= 0; i--) 
      t = t*x + p->a[i];
    return t;
  }

----------