#ifndef lint
static char sccsid[] = "@(#)tree.c	4.3 (Berkeley) 08/25/84";
#endif

#include "compact.h"

insert (ch)
	int ch;
{
	register struct node *pp;
	register int c;
	union cio d;
	register struct index *qt, *wt;

	c = ch;
	wt = NEW;
	pp = bottom++;
	bottom->fath.fp = pp;
	in[c].flags = (SEEN | FBIT);
	d.integ = bottom->sp[0].ch = pp->sp[1].ch;
	in[c].fp = in[d.integ].fp = pp->sp[1].p = wt->pt = bottom;
	bottom->fath.flags = (LLEAF | RLEAF | FBIT);
	pp->fath.flags &= ~RLEAF;
	in[d.integ].flags = SEEN;

	bottom->count[0] = pp->count[1];
	qt = pp->top[1];
	bottom->top[0] = qt;
	bottom->sp[1].ch = c;
	bottom->count[1] = 0;
	bottom->top[1] = qt->next = wt;
	wt->next = NULL;
}

uptree (ch)
	int ch;
{
	register struct node *r;
	union treep q, s;
	int rs, qs, ss, ts;
	longint rc, qc, sc;
	struct node *t;
	register struct index *rt, *qt, *st;

	r = in[ch].fp;
	rs = in[ch].flags & FBIT;

	do {
		rc = ++r->count[rs];
		rt = r->top[rs];
		for (;;) {
			qs = ss = 1 - rs;
			s.p = r + rs;
			sc = s.p->count[ss];
			st = s.p->top[ss];
	
			if (rs) {
				if (r == bottom) {
					sc = rc - 2;
					st = NULL;
				}
			} else {
				if (r == dict) {
					qc = rc + 1;
					qt = head;
					break;
				}
			}
			q.p = r - qs;
			qc = q.p->count[qs];
			qt = q.p->top[qs];
			if (rc <= qc)
				break;

			t = qt->pt;
			ts = (rc <= t->count[0]);

			/* exchange pointers of (t, ts) and (r, rs) */
			q.ch = t->sp[ts].ch;
			s.ch = r->sp[rs].ch;
			t->sp[ts].ch = s.ch;
			r->sp[rs].ch = q.ch;
			exch(t, ts, q.ch, r, rs);
			exch(r, rs, s.ch, t, ts);

			qs = (rs ? RLEAF : LLEAF);
			ss = (ts ? RLEAF : LLEAF);
			if (((r->fath.flags & qs) << rs) ^ ((t->fath.flags & ss) << ts)) {
				r->fath.flags ^= qs;
				t->fath.flags ^= ss;
			}

			t->count[ts]++;
			r->count[rs]--;
			qt->pt += ts;
			r = t;
			rs = ts;
		}

		if (rc == qc) {
			r->top[rs] = qt;
			if (rc > sc + 1) {
				qt->next = st;
				/* dispose of rt */
				rt->next = flist;
				flist = rt;
			} else
				st->pt = s.p;
		} else if (rc == sc + 1) {
			/* create new index at rt */
			rt = NEW;
			rt->next = st;
			rt->pt = r;
			qt->next = rt;
			if (st)
				st->pt = s.p;
			r->top[rs] = rt;
		}
		rs = r->fath.flags & FBIT;
		r = r->fath.fp;
	} while (r);
	dirp = head->next;
	dirq = dirp->next;
}

exch(v, vs, x, w, ws)
	struct node *v, *w;
	union treep x;
	int vs, ws;
{

	if (v->fath.flags & (vs ? RLEAF : LLEAF)) {
		in[x.ch].fp = w;
		in[x.ch].flags &= ~01;
		if (ws)
			in[x.ch].flags |= ws;
	} else {
		x.p->fath.fp = w;
		x.p->fath.flags &= ~01;
		if (ws)
			x.p->fath.flags |= ws;
	}
}