algorithms in c code.txt

This file contains the code from "Algorithms in C, Third Edition, Parts 1-4," by Robert Sedgewick,

-----
link joinLR(link a, link b)
  { 
    if (b == z) return a;
    b = partR(b, 0); b->l = a; 
    return b;
  }
link deleteR(link h, Key v)
  { link x; Key t = key(h->item);
    if (h == z) return z; 
    if (less(v, t)) h->l = deleteR(h->l, v);
    if (less(t, v)) h->r = deleteR(h->r, v);
    if (eq(v, t)) 
      { x = h; h = joinLR(h->l, h->r); free(x); }
    return h;
  }
void STdelete(Key v)
  { head = deleteR(head, v); }
-----
link STjoin(link a, link b)
  { 
    if (b == z) return a;
    if (a == z) return b;
    b = STinsert(b, a->item); 
    b->l = STjoin(a->l, b->l); 
    b->r = STjoin(a->r, b->r); 
    free(a);    
    return b;
  }
-----

----------
CHAPTER 13. Balanced Trees
-----
link balanceR(link h)
  { 
    if (h->N < 2) return h;
    h = partR(h, h->N/2);
    h->l = balanceR(h->l); 
    h->r = balanceR(h->r);
    return h;
  }
-----
link insertR(link h, Item item)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if (rand()< RAND_MAX/(h->N+1)) 
      return insertT(h, item);
    if less(v, t) h->l = insertR(h->l, item);
             else h->r = insertR(h->r, item);
    (h->N)++; return h;
  }
void STinsert(Item item)
  { head = insertR(head, item); }
-----
link STjoinR(link a, link b)
  { 
    if (a == z) return b;
    b = STinsert(b, a->rec); 
    b->l = STjoin(a->l, b->l); 
    b->r = STjoin(a->r, b->r); 
    fixN(b); free(a);
    return b;
  }
link STjoin(link a, link b)
  { 
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         STjoinR(a, b);
    else STjoinR(b, a);
  }
-----
link joinLR(link a, link b)
  { 
    if (a == z) return b;
    if (b == z) return a;
    if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
         { a->r = joinLR(a->r, b); return a; }
    else { b->l = joinLR(a, b->l); return b; }
  }
-----
link splay(link h, Item item)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1);  
    if (less(v, key(h->item))) 
      { 
        if (hl == z) return NEW(item, z, h, h->N+1);
        if (less(v, key(hl->item))) 
          { hll = splay(hll, item); h = rotR(h); }
        else 
          { hlr = splay(hlr, item); hl = rotL(hl); }
        return rotR(h); 
      }
    else
      { 
        if (hr == z) return NEW(item, h, z, h->N+1);
        if (less(key(hr->item), v)) 
          { hrr = splay(hrr, item); h = rotL(h); }
        else 
          { hrl = splay(hrl, item); hr = rotR(hr); }
        return rotL(h);
      }
  }
void STinsert(Item item)
  { head = splay(head, item); }
-----
link RBinsert(link h, Item item, int sw)
  { Key v = key(item);
    if (h == z) return NEW(item, z, z, 1, 1);  
    if ((hl->red) && (hr->red)) 
      { h->red = 1; hl->red = 0; hr->red = 0; }
    if (less(v, key(h->item))) 
      { 
        hl = RBinsert(hl, item, 0); 
        if (h->red && hl->red && sw) h = rotR(h); 
        if (hl->red && hll->red) 
          { h = rotR(h); h->red = 0; hr->red = 1; }
      }
    else
      { 
        hr = RBinsert(hr, item, 1); 
        if (h->red && hr->red && !sw) h = rotL(h); 
        if (hr->red && hrr->red) 
          { h = rotL(h); h->red = 0; hl->red = 1; }
      }
    fixN(h); return h;
  }
void STinsert(Item item)
  { head = RBinsert(head, item, 0); head->red = 0; }
-----
Item searchR(link t, Key v, int k)
  { 
    if (eq(v, key(t->item))) return t->item;
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k == 0) return NULLitem;
        return searchR(t, v, k-1); 
      }
    return searchR(t->next[k], v, k);
  }
Item STsearch(Key v)
  { return searchR(head, v, lgN); }
-----
typedef struct STnode* link;
struct STnode { Item item; link* next; int sz; };
static link head, z;
static int N, lgN;
link NEW(Item item, int k)      
  { int i; link x = malloc(sizeof *x);
    x->next = malloc(k*sizeof(link));
    x->item = item; x->sz = k;
    for (i = 0; i < k; i++) x->next[i] = z;
    return x;                         
  }                                   
void STinit(int max) 
  { 
    N = 0; lgN = 0; 
    z = NEW(NULLitem, 0); 
    head = NEW(NULLitem, lgNmax); 
  }
-----
int randX()
  { int i, j, t = rand();
    for (i = 1, j = 2; i < lgNmax; i++, j += j)
      if (t > RAND_MAX/j) break;
    if (i > lgN) lgN = i;
    return i;
  }
void insertR(link t, link x, int k)
  { Key v = key(x->item); 
    if (less(v, key(t->next[k]->item))) 
      { 
        if (k < x->sz)
          { x->next[k] = t->next[k]; 
            t->next[k] = x; }
        if (k == 0) return;
        insertR(t, x, k-1); return;
      }
    insertR(t->next[k], x, k);
  }
void STinsert(Key v)
  { insertR(head, NEW(v, randX()), lgN); N++; }
-----
void deleteR(link t, Key v, int k)
  { link x = t->next[k];
    if (!less(key(x->item), v)) 
      { 
        if (eq(v, key(x->item)))
          { t->next[k] = x->next[k]; }
        if (k == 0) { free(x); return; }
        deleteR(t, v, k-1); return;
      }
    deleteR(t->next[k], v, k);
  }
void STdelete(Key v)
  { deleteR(head, v, lgN); N--; }

----------
CHAPTER 14. Hashing
-----
int hash(char *v, int M)
  { int h = 0, a = 127;
    for (; *v != '\0'; v++) 
      h = (a*h + *v) % M;
    return h;
  }
-----
int hashU(char *v, int M)
  { int h, a = 31415, b = 27183;
    for (h = 0; *v != '\0'; v++, a = a*b % (M-1)) 
        h = (a*h + *v) % M;
    return h;
  }
-----
static link *heads, z;
static int N, M;
void STinit(int max) 
  { int i;
    N = 0; M = max/5;
    heads = malloc(M*sizeof(link));
    z = NEW(NULLitem, NULL);
    for (i = 0; i < M; i++) heads[i] = z; 
  }
Item STsearch(Key v)
  { return searchR(heads[hash(v, M)], v); }
void STinsert(Item item)
  { int i = hash(key(item), M);
    heads[i] = NEW(item, heads[i]); N++; }
void STdelete(Item item)
  { int i = hash(key(item), M);
    heads[i] = deleteR(heads[i], item); }
-----
#include <stdlib.h>
#include "Item.h"
#define null(A) (key(st[A]) == key(NULLitem))
static int N, M;
static Item *st;
void STinit(int max)
  { int i; 
    N = 0; M = 2*max;
    st = malloc(M*sizeof(Item));
    for (i = 0; i < M; i++) st[i] = NULLitem; 
  }
int STcount() { return N; }
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    while (!null(i)) i = (i+1) % M;
    st[i] = item; N++;
  }
Item STsearch(Key v)
  { int i = hash(v, M);
    while (!null(i))
      if eq(v, key(st[i])) return st[i]; 
      else i = (i+1) % M;
    return NULLitem;
  }
-----
void STdelete(Item item)
  { int j, i = hash(key(item), M); Item v;
    while (!null(i))
      if eq(key(item), key(st[i])) break; 
      else i = (i+1) % M;
    if (null(i)) return;
    st[i] = NULLitem; N--;
    for (j = i+1; !null(j); j = (j+1) % M, N--)
      { v = st[j]; st[j] = NULLitem; STinsert(v); }
  }
-----
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    int k = hashtwo(v, M);
    while (!null(i)) i = (i+k) % M;
    st[i] = item; N++;
  }
Item STsearch(Key v)
  { int i = hash(v, M);
    int k = hashtwo(v, M);
    while (!null(i))
      if eq(v, key(st[i])) return st[i]; 
      else i = (i+k) % M;
    return NULLitem;
  }
-----
void expand();
void STinsert(Item item)
  { Key v = key(item);
    int i = hash(v, M);
    while (!null(i)) i = (i+1) % M;
    st[i] = item; 
    if (N++ > M/2) expand();
  }
void expand()
  { int i; Item *t = st;
    init(M+M);
    for (i = 0; i < M/2; i++) 
      if (key(t[i]) != key(NULLitem)) 
        STinsert(t[i]); 
    free(t);
  }

----------
CHAPTER 15. Radix Search
-----
Item searchR(link h, Key v, int w)
  { Key t = key(h->item);
    if (h == z) return NULLitem;
    if eq(v, t) return h->item;
    if (digit(v, w) == 0)
         return searchR(h->l, v, w+1);
    else return searchR(h->r, v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
-----
#define leaf(A) ((h->l == z) && (h->r == z))
Item searchR(link h, Key v, int w)
  { Key t = key(h->item);
    if (h == z) return NULLitem;
    if (leaf(h))
      return eq(v, t) ? h->item : NULLitem;
    if (digit(v, w) == 0)
         return searchR(h->l, v, w+1);
    else return searchR(h->r, v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
-----
void STinit()
  { head = (z = NEW(NULLitem, 0, 0, 0)); }
link split(link p, link q, int w)
  { link t = NEW(NULLitem, z, z, 2);
    switch(digit(p->item, w)*2 + digit(q->item, w))
      {
        case 0: t->l = split(p, q, w+1); break;
        case 1: t->l = p; t->r = q; break;
        case 2: t->r = p; t->l = q; break;
        case 3: t->r = split(p, q, w+1); break;
      }
    return t;
  }
link insertR(link h, Item item, int w)
  { Key v = key(item), t = key(h->item);
    if (h == z) return NEW(item, z, z, 1);
    if (leaf(h))
      { return split(NEW(item, z, z, 1), h, w); }
    if (digit(v, w) == 0)
         h->l = insertR(h->l, item, w+1);
    else h->r = insertR(h->r, item, w+1);
    return h;
  }
void STinsert(Item item)
  { head = insertR(head, item, 0); }
-----
Item searchR(link h, Key v, int w)
  { 
    if (h->bit <= w) return h->item;
    if (digit(v, h->bit) == 0)
         return searchR(h->l, v, h->bit);
    else return searchR(h->r, v, h->bit);
  }
Item STsearch(Key v) 
  { Item t = searchR(head->l, v, -1); 
    return eq(v, key(t)) ? t : NULLitem; 
  } 
-----
void STinit()
  { head = NEW(NULLitem, 0, 0, -1); 
    head->l = head; head->r = head; }
link insertR(link h, Item item, int w, link p)
  { link x; Key v = key(item);
    if ((h->bit >= w) || (h->bit <= p->bit))
      { 
        x = NEW(item, 0, 0, w);
        x->l = digit(v, x->bit) ? h : x;
        x->r = digit(v, x->bit) ? x : h;
        return x; 
      }
    if (digit(v, h->bit) == 0)
         h->l = insertR(h->l, item, w, h);
    else h->r = insertR(h->r, item, w, h);
    return h;
  }
void STinsert(Item item)
  { int i;
    Key v = key(item); 
    Key t = key(searchR(head->l, v, -1));
    if (v == t) return;
    for (i = 0; digit(v, i) == digit(t, i); i++) ;
    head->l = insertR(head->l, item, i, head);
  }
-----
void sortR(link h, void (*visit)(Item), int w)
  { 
    if (h->bit <= w) { visit(h->item); return; }
    sortR(h->l, visit, h->bit);
    sortR(h->r, visit, h->bit);
  }
void STsort(void (*visit)(Item))
  { sortR(head->l, visit, -1); } 
-----
typedef struct STnode *link;
struct STnode { link next[R]; };
static link head;
void STinit() { head = NULL; }
link NEW()
  { int i;
    link x = malloc(sizeof *x); 
    for (i = 0; i < R; i++) x->next[i] = NULL;
    return x;
  }
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem;
    if (i == NULLdigit) return v;
    return searchR(h->next[i], v, w+1);
  }
Item STsearch(Key v) 
  { return searchR(head, v, 0); } 
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) h = NEW();
    if (i == NULLdigit) return h;
    h->next[i] = insertR(h->next[i], v, w+1);
    return h;
  }
void STinsert(Item item)
  { head = insertR(head, item, 0); N++; }
-----
typedef struct STnode* link;
struct STnode { Item item; int d; link l, m, r; };
static link head;
void STinit() { head = NULL; }
link NEW(int d)
  { link x = malloc(sizeof *x); 
    x->d = d; x->l = NULL; x->m = NULL; x->r = NULL;
    return x;
  }
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem; 
    if (i == NULLdigit) return v;
    if (i < h->d) return searchR(h->l, v, w);
    if (i == h->d) return searchR(h->m, v, w+1);
    if (i > h->d) return searchR(h->r, v, w);
  }
Item STsearch( Key v)
  { return searchR(head, v, 0); }
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) h = NEW(i); 
    if (i == NULLdigit) return h;
    if (i < h->d) h->l = insertR(h->l, v, w);
    if (i == h->d) h->m = insertR(h->m, v, w+1);
    if (i > h->d) h->r = insertR(h->r, v, w);
    return h;
  }
void STinsert(Key key)
  { head = insertR(head, key, 0); }
-----
char word[maxW];
void matchR(link h, char *v, int i)
  { 
    if (h == z) return; 
    if ((*v == '\0') && (h->d == '\0')) 
      { word[i] = h->d; printf("%s ", word); }
    if ((*v == '*') || (*v == h->d)) 
      { word[i] = h->d; matchR(h->m, v+1, i+1); }
    if ((*v == '*') || (*v < h->d)) 
      matchR(h->l, v, i);
    if ((*v == '*') || (*v > h->d)) 
      matchR(h->r, v, i);
  }
void STmatch(char *v)
  { matchR(head, v, 0); }
-----
#define internal(A) ((A->d) != NULLdigit)
link NEWx(link h, int d)
  { link x = malloc(sizeof *x); 
    x->item = NULLitem; x->d = d;
    x->l = NULL; x->m = h; x->r = NULL;
    return x;
  }
link split(link p, link q, int w)
  { int pd = digit(p->item, w), 
        qd = digit(q->item, w);
    link t = NEW(NULLitem, qd);
    if (pd < qd) { t->m = q; t->l = NEWx(p, pd); }
    if (pd == qd) { t->m = split(p, q, w+1); }
    if (pd > qd) { t->m = q; t->r = NEWx(p, pd); }
    return t;
  }
link insertR(link h, Item item, int w)
  { Key v = key(item);
    int i = digit(v, w);
    if (h == NULL) 
      return NEWx(NEW(item, NULLdigit), i);
    if (!internal(h))
      return split(NEW(item, NULLdigit), h, w); 
    if (i < h->d) h->l = insertR(h->l, v, w);
    if (i == h->d) h->m = insertR(h-