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