/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * Wildly edited.  Is it correct?
 */
#include <stdlib.h>
#include "Item.h"
#include "ST.h"

typedef struct STnode* link;
struct STnode { Item item; link next; };
static link head, z;
static int N;
static link NEW(Item item, link next)      
  { link x = malloc(sizeof *x);
    x->item = item; x->next = next;     
    return x;                         
  }                                   
void STinit(int max) 
{
  N = 0;
  head = (z = NEW(NULLitem, NULL));
  head->next = z;
}

int STcount() { return N; }

link searchR(link t, Key v)
  { 
    if (t->next == z) return t;
    if (less(key(t->next->item), v))
      return searchR(t->next, v);
    return t;
  }

Item STsearch(Key v)
{
  link t = searchR(head, v);
  if (t->next == z) return NULLitem;
  if (eq(key(t->next->item), v))
    return t->next->item;
  return NULLitem;
}

void STinsert(Item item)
{
  link t = searchR(head, key(item));
  if ((t->next != z) && eq(key(t->next->item), key(item)))
    return;
  t->next = NEW(item, t->next);
  N++;
}

void STsort(void (*visit)(Item))
{
  link t = head;

  while (t->next!=z) {
    t = t->next;
    visit(t->item);
  }
}