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