/*
 * This code is from "Algorithms in C, Third Edition,"
 * by Robert Sedgewick, Addison Wesley Longman, 1998.
 * (Com pequenas alteracoes).
 */
#include <stdlib.h>
#include "Item.h"
typedef struct STnode* link;
struct STnode { Item item; link l, r; int N; };
static link head, z;
link NEW(Item item, link l, link r, int N)
  { link x = malloc(sizeof *x); 
    x->item = item; x->l = l; x->r = r; x->N = N;
    return x;
  }
void STinit()
  { head = (z = NEW(NULLitem, 0, 0, 0)); }
int STcount() { return head->N; }
Item searchR(link h, Key v)
  { Key t;
    if (h == z) return NULLitem;
    t = key(h->item);
    if eq(v, t) return h->item;
    if less(v, t) return searchR(h->l, v);
             else return searchR(h->r, v);
  }
Item STsearch(Key v) 
  { return searchR(head, v); } 
link insertR(link h, Item item)
  { Key v = key(item), t; 
    if (h == z) return NEW(item, z, z, 1);
    t = key(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); }

void print_in_orderR(link h)
{
  if (h!=z) {
    print_in_orderR(h->l);
    ITEMshow(h->item);
    print_in_orderR(h->r);
  }
}

void STshow_all()
{
  print_in_orderR(head);
}