1*10920Sshannon /*	tree.c	4.1	83/02/11	*/
2*10920Sshannon 
3*10920Sshannon #include "compact.h"
4*10920Sshannon 
5*10920Sshannon 
6*10920Sshannon insert (ch)
7*10920Sshannon int ch;
8*10920Sshannon {
9*10920Sshannon 	register struct node *pp;
10*10920Sshannon 	register int c;
11*10920Sshannon 	union cio d;
12*10920Sshannon 	register struct index *qt, *wt;
13*10920Sshannon 
14*10920Sshannon 	c = ch;
15*10920Sshannon 	wt = NEW;
16*10920Sshannon 	pp = bottom++;
17*10920Sshannon 	bottom -> fath . fp = pp;
18*10920Sshannon 	in [c] . flags = (SEEN | FBIT);
19*10920Sshannon 	d . integ = bottom -> sp [0] . ch = pp -> sp [1] . ch;
20*10920Sshannon 	in [c] . fp = in [d . integ] . fp = pp -> sp [1] . p = wt -> pt = bottom;
21*10920Sshannon 	bottom -> fath . flags = (LLEAF | RLEAF | FBIT);
22*10920Sshannon 	pp -> fath . flags &= ~RLEAF;
23*10920Sshannon 	in [d . integ] . flags = SEEN;
24*10920Sshannon 
25*10920Sshannon 	bottom -> count [0] = pp -> count [1];
26*10920Sshannon 	qt = pp -> top [1];
27*10920Sshannon 	bottom -> top [0] = qt;
28*10920Sshannon 	bottom -> sp [1] . ch = c;
29*10920Sshannon 	bottom -> count [1] = 0;
30*10920Sshannon 	bottom -> top [1] = qt -> next = wt;
31*10920Sshannon 	wt -> next = NULL;
32*10920Sshannon }
33*10920Sshannon 
34*10920Sshannon uptree (ch)
35*10920Sshannon int ch;
36*10920Sshannon {
37*10920Sshannon 	register struct node *r;
38*10920Sshannon 	union treep q, s;
39*10920Sshannon 	int rs, qs, ss, ts;
40*10920Sshannon 	longint rc, qc, sc;
41*10920Sshannon 	struct node *t;
42*10920Sshannon 	register struct index *rt, *qt, *st;
43*10920Sshannon 
44*10920Sshannon 	r = in [ch] . fp;
45*10920Sshannon 	rs = in [ch] . flags & FBIT;
46*10920Sshannon 
47*10920Sshannon 	do {
48*10920Sshannon 		(r -> count [rs])++;
49*10920Sshannon 		rc = r -> count [rs];
50*10920Sshannon 		rt = r -> top [rs];
51*10920Sshannon 
52*10920Sshannon 		for ( ; ; ) {
53*10920Sshannon 			qs = ss = 1 - rs;
54*10920Sshannon 			s . p = r + rs;
55*10920Sshannon 			sc = (s . p) -> count [ss];
56*10920Sshannon 			st = (s . p) -> top [ss];
57*10920Sshannon 
58*10920Sshannon 			if (rs)
59*10920Sshannon 				if (r == bottom) {
60*10920Sshannon 					sc = rc - 2;
61*10920Sshannon 					st = NULL;
62*10920Sshannon 				}
63*10920Sshannon 				else;
64*10920Sshannon 			else if (r == dict) {
65*10920Sshannon 				qc = rc + 1;
66*10920Sshannon 				qt = head;
67*10920Sshannon 				break;
68*10920Sshannon 			}
69*10920Sshannon 
70*10920Sshannon 			q . p = r - qs;
71*10920Sshannon 			qc = (q . p) -> count [qs];
72*10920Sshannon 			qt = (q . p) -> top [qs];
73*10920Sshannon 			if (rc <= qc) break;
74*10920Sshannon 
75*10920Sshannon 			t = qt -> pt;
76*10920Sshannon 			ts = (rc <= t -> count [0] ? 1 : 0);
77*10920Sshannon 
78*10920Sshannon 			/* exchange pointers of (t, ts) and (r, rs) */
79*10920Sshannon 
80*10920Sshannon 			q . ch = t -> sp [ts] . ch;	/*  {					*/
81*10920Sshannon 			s . ch = r -> sp [rs] . ch;	/*  {					*/
82*10920Sshannon 			t -> sp [ts] . ch = s . ch;	/*  {					*/
83*10920Sshannon 			r -> sp [rs] . ch = q . ch;	/*  { change code when Cory gets v. 7	*/
84*10920Sshannon 							/*  {					*/
85*10920Sshannon 			exch (t, ts, q . ch, r, rs);	/*  {					*/
86*10920Sshannon 			exch (r, rs, s . ch, t, ts);	/*  {					*/
87*10920Sshannon 
88*10920Sshannon 			qs = (rs ? RLEAF : LLEAF);
89*10920Sshannon 			ss = (ts ? RLEAF : LLEAF);
90*10920Sshannon 			if (((r -> fath . flags & qs) << rs) ^ ((t -> fath . flags & ss) << ts)) {
91*10920Sshannon 				r -> fath . flags ^= qs;
92*10920Sshannon 				t -> fath . flags ^= ss;
93*10920Sshannon 			}
94*10920Sshannon 
95*10920Sshannon 			(t -> count [ts])++;
96*10920Sshannon 			(r -> count [rs])--;
97*10920Sshannon 			(qt -> pt) += ts;
98*10920Sshannon 			r = t;
99*10920Sshannon 			rs = ts;
100*10920Sshannon 		}
101*10920Sshannon 
102*10920Sshannon 		if (rc == qc) {
103*10920Sshannon 			r -> top [rs] = qt;
104*10920Sshannon 			if (rc > sc + 1) {
105*10920Sshannon 				qt -> next = st;
106*10920Sshannon 
107*10920Sshannon 				/* dispose of rt */
108*10920Sshannon 
109*10920Sshannon 				rt -> next = flist;
110*10920Sshannon 				flist = rt;
111*10920Sshannon 			}
112*10920Sshannon 			else st -> pt = s . p;
113*10920Sshannon 		}
114*10920Sshannon 
115*10920Sshannon 		else if (rc == sc + 1) {
116*10920Sshannon 
117*10920Sshannon 			/* create new index at rt */
118*10920Sshannon 
119*10920Sshannon 			rt = NEW;
120*10920Sshannon 			rt -> next = st;
121*10920Sshannon 			rt -> pt = r;
122*10920Sshannon 			qt -> next = rt;
123*10920Sshannon 			if (st) st -> pt = s . p;
124*10920Sshannon 			r -> top [rs] = rt;
125*10920Sshannon 		}
126*10920Sshannon 
127*10920Sshannon 		rs = r -> fath . flags & FBIT;
128*10920Sshannon 		r = r -> fath . fp;
129*10920Sshannon 
130*10920Sshannon 	} while (r);
131*10920Sshannon 	dirp = head -> next;
132*10920Sshannon 	dirq = dirp -> next;
133*10920Sshannon }
134*10920Sshannon 
135*10920Sshannon exch (v, vs, x, w, ws)
136*10920Sshannon struct node *v, *w;
137*10920Sshannon union treep x;
138*10920Sshannon int vs, ws;
139*10920Sshannon {
140*10920Sshannon 
141*10920Sshannon 	if (v -> fath . flags & (vs ? RLEAF : LLEAF)) {
142*10920Sshannon 		in [x . ch] . fp = w;
143*10920Sshannon 		in [x . ch] . flags &= ~01;
144*10920Sshannon 		if (ws) in [x . ch] . flags |= ws;
145*10920Sshannon 	}
146*10920Sshannon 	else {
147*10920Sshannon 		(x . p) -> fath . fp = w;
148*10920Sshannon 		(x . p) -> fath . flags &= ~01;
149*10920Sshannon 		if (ws) (x . p) -> fath . flags |= ws;
150*10920Sshannon 	}
151*10920Sshannon }
152