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 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->m, v, w+1);
    if (i > h->d) h->r = insertR(h->r, v, w);
    return h;
  }
void STinsert(Key key)
  { int i = digit(key, 0);
    heads[i] = insertR(heads[i], key, 1); 
  }
-----
Item searchR(link h, Key v, int w)
  { int i = digit(v, w);
    if (h == NULL) return NULLitem; 
    if (internal(h))
      {
        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);
      }
    if eq(v, key(h->item)) return h->item;
    return NULLitem;
  }
Item STsearch(Key v)
  { return searchR(heads[digit(v, 0)], v, 1); }
-----
typedef struct STnode* link;
struct STnode { Item item; link l, m, r; };
static link head;
#define z NULL
void STinit() { head = z; }
link NEW(char *v)
  { link x = malloc(sizeof *x); 
    x->item = v; x->l = z; x->m = z; x->r = z;
    return x;
  }
Item searchR(link h, char *v)
  { char *t;
    if (h == z) return NULLitem; 
    if (*v == '\0') return h->item;
    if (*v < *(h->item)) searchR(h->l, v);
    if (*v > *(h->item)) searchR(h->r, v);
    if (*v == *(h->item)) t = searchR(h->m, v+1);
    return null(t) ? t : v;
  }
Item STsearch(char *v)
  { char *t = searchR(head, v); 
    if (eq(v, t)) return t;
    return NULLitem;
  }
link insertR(link h, char *v)
  { 
    if (h == z) h = NEW(v); 
    if ((*v ==  *(h->item)) && (*v != '\0'))
      h->m = insertR(h->m, v+1);
    if (h == z) h = NEW(v); 
    if (*v < *(h->item)) h->l = insertR(h->l, v);
    if (*v > *(h->item)) h->r = insertR(h->r, v);
    return h;
  }
void STinsert(char *v)
  { head = insertR(head, v); }

----------