"Fossies" - the Fresh Open Source Software Archive 
Member "ncc-2.8/dbstree.h" (9 Jul 2006, 5999 Bytes) of package /linux/privat/old/ncc-2.8.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 /******************************************************************************
2 Dynamic Binary Search Tree.
3 Check dbstree.tex for info.
4 ******************************************************************************/
5
6 #include <alloca.h>
7 #ifndef HAVE_DBSTREE
8 #define HAVE_DBSTREE
9
10 #define DBS_MAGIC 32
11 extern char *StrDup (char*);
12
13 #define TX template<class dbsNode>
14
15 template<class dbsNode> class dbsTree
16 {
17 dbsNode **FoundSlot;
18 int FoundDepth;
19 void tree_to_array (dbsNode*);
20 void walk_tree (dbsNode*, void (*)(dbsNode*));
21 void walk_tree_io (dbsNode*, void (*)(dbsNode*));
22 void walk_tree_d (dbsNode*, void (*)(dbsNode*));
23 public:
24 dbsNode *root;
25 int nnodes;
26 dbsTree ();
27 void dbsBalance ();
28 dbsNode* dbsFind ();
29 void dbsRemove (dbsNode*);
30 void copytree (void (*)(dbsNode*));
31 void foreach (void (*)(dbsNode*));
32 void deltree (void (*)(dbsNode*));
33 dbsNode* parentOf (dbsNode*);
34 void addself (dbsNode*);
35 };
36
37 #define DBS_STRQUERY dbsNodeStr::Query
38
39 class dbsNodeStr
40 {
41 public:
42 int compare (dbsNodeStr*);
43 int compare ();
44 dbsNodeStr ();
45 char *Name;
46 ~dbsNodeStr ();
47
48 static char *Query;
49 };
50
51 TX dbsTree<dbsNode>::dbsTree ()
52 {
53 nnodes = 0;
54 root = NULL;
55 FoundSlot = NULL;
56 }
57
58 /*
59 * Balancing a binary tree. This happens whenever the height reaches 32.
60 */
61 TX void dbsTree<dbsNode>::tree_to_array (dbsNode *n)
62 {
63 if (n->less) tree_to_array (n->less);
64 *FoundSlot++ = n;
65 if (n->more) tree_to_array (n->more);
66 }
67
68 TX void dbsTree<dbsNode>::dbsBalance () // O(n)
69 {
70 dbsNode **npp;
71 unsigned long long i, j, k, D, Y, k2, k3;
72
73 if (!root) return;
74
75 npp = FoundSlot = (dbsNode**) alloca (sizeof (dbsNode*) * nnodes);
76 tree_to_array (root);
77
78 root = npp [nnodes / 2];
79 for (D = nnodes + 1, i = 4; i <= D; i *= 2)
80 for (j = 2; j < i; j += 4)
81 {
82 k3 = nnodes * j / i;
83 npp [k3]->less = npp [nnodes * (j - 1) / i],
84 npp [k3]->more = npp [nnodes * (j + 1) / i];
85 }
86 k = nnodes + 1 - (Y = i / 2);
87 if (k == 0)
88 {
89 for (i /=2, j = 1; j < i; j += 2)
90 k3 = nnodes * j / i,
91 npp [k3]->less = npp [k3]->more = NULL;
92 return;
93 }
94
95 for (j = 2; j < i; j += 4)
96 {
97 k3 = nnodes * j / i;
98 D = (k2 = (j - 1) * nnodes / i) * Y % nnodes;
99 if (D >= k || D == 0)
100 npp [k3]->less = NULL;
101 else
102 {
103 npp [k3]->less = npp [k2];
104 npp [k2]->less = npp [k2]->more = NULL;
105 }
106 D = (k2 = (j + 1) * nnodes / i) * Y % nnodes;
107 if (D >= k || D == 0)
108 npp [k3]->more = NULL;
109 else
110 {
111 npp [k3]->more = npp [k2];
112 npp [k2]->less = npp [k2]->more = NULL;
113 }
114 }
115
116 dbsNode *np;
117 for (np = root; np->less; np = np->less);
118
119 np->less = npp [0];
120 npp [0]->less = npp [0]->more = NULL;
121 }
122
123 TX void dbsTree<dbsNode>::addself (dbsNode *t)
124 {
125 t->less = t->more = 0;
126 *FoundSlot = t;
127 ++nnodes;
128
129 if (FoundDepth >= DBS_MAGIC)
130 dbsBalance ();
131 FoundSlot = NULL; // Bug traper
132 }
133
134 /*
135 */
136 TX void dbsTree<dbsNode>::dbsRemove (dbsNode *t) // O(log n)
137 {
138 dbsNode *np, *nl, *nr, *nlp, *nrp;
139 int isroot;
140 unsigned int i, j;
141
142 isroot = (np = parentOf (t)) == NULL;
143
144 --nnodes;
145
146 if (!(t->less && t->more))
147 {
148 if (isroot)
149 root = (t->less) ? t->less : t->more;
150 else
151 if (np->less == t)
152 np->less = (t->less) ? t->less : t->more;
153 else
154 np->more = (t->less) ? t->less : t->more;
155 return;
156 }
157
158 for (i = 0, nlp = NULL, nl = t->less; nl->more; i++)
159 nlp = nl, nl = nl->more;
160 for (j = 0, nrp = NULL, nr = t->more; nr->less; j++)
161 nrp = nr, nr = nr->less;
162
163 if (i >= j) // the smallest from bigger ones
164 {
165 if (isroot) root = nl;
166 else
167 if (np->less == t) np->less = nl;
168 else np->more = nl;
169 if (nlp)
170 {
171 nlp->more = nl->less;
172 nl->less = t->less;
173 }
174 nl->more = t->more;
175 }
176 else // Mirror situation
177 {
178 if (isroot) root = nr;
179 else
180 if (np->less == t) np->less = nr;
181 else np->more = nr;
182 if (nrp)
183 {
184 nrp->less = nr->more;
185 nr->more = t->more;
186 }
187 nr->less = t->less;
188 }
189 }
190
191 TX dbsNode *dbsTree<dbsNode>::parentOf (dbsNode *t) // O(log n)
192 {
193 dbsNode *np;
194
195 if ((np = root) == t)
196 return NULL;
197
198 while (np)
199 if (t->compare (np) < 0)
200 if (np->less == t) break;
201 else np = np->less;
202 else
203 if (np->more == t) break;
204 else np = np->more;
205
206 assert (np);
207
208 return np;
209 }
210
211 TX dbsNode *dbsTree<dbsNode>::dbsFind () // O (log n)
212 {
213 dbsNode *d;
214 int i;
215
216 FoundDepth = 0;
217
218 if (!(d = root)) {
219 FoundSlot = &root;
220 return NULL;
221 }
222
223 ++FoundDepth;
224
225 for (;; ++FoundDepth) {
226 if ((i = d->compare ()) == 0) {
227 FoundSlot = NULL;
228 return d;
229 }
230 if (i < 0)
231 if (d->more) d = d->more;
232 else {
233 FoundSlot = &d->more;
234 return NULL;
235 }
236 else
237 if (d->less) d = d->less;
238 else {
239 FoundSlot = &d->less;
240 return NULL;
241 }
242 }
243 }
244
245 /*
246 * Moving in the tree.
247 * If we want for every node of the tree: foreach () O(n)
248 * To copy the tree - preorder: copytree () O(n)
249 * Safe to node deletion (but no dbsRemove, just
250 * root=NULL, cnt=0) - postorder: deltree () O(n)
251 * To a specific index: operator [i] O(n) ...(n/16)
252 * But for every node with operator[] total is ... n^2 CAREFUL!
253 * Inorder next/prev dbsNext, dbsPrev: O(log n)
254 * For a scroller area Use dbsNext, dbsPrev and keep a sample node
255 * if the tree is modified, reget the sample node from operator [].
256 *
257 */
258
259 TX void dbsTree<dbsNode>::walk_tree (dbsNode *n, void (*foo)(dbsNode*))
260 {
261 foo (n);
262 if (n->less) walk_tree (n->less, foo);
263 if (n->more) walk_tree (n->more, foo);
264 }
265 TX void dbsTree<dbsNode>::walk_tree_io (dbsNode *n, void (*foo)(dbsNode*))
266 {
267 if (n->less) walk_tree_io (n->less, foo);
268 foo (n);
269 if (n->more) walk_tree_io (n->more, foo);
270 }
271 TX void dbsTree<dbsNode>::walk_tree_d (dbsNode *n, void (*foo)(dbsNode*))
272 {
273 if (n->less) walk_tree_d (n->less, foo);
274 if (n->more) walk_tree_d (n->more, foo);
275 foo (n);
276 }
277
278
279 TX void dbsTree<dbsNode>::copytree (void (*f)(dbsNode*))
280 {
281 if (root) walk_tree (root, f);
282 }
283
284 TX void dbsTree<dbsNode>::foreach (void (*f)(dbsNode*))
285 {
286 if (root) walk_tree_io (root, f);
287 }
288
289 TX void dbsTree<dbsNode>::deltree (void (*f)(dbsNode*))
290 {
291 if (root) walk_tree_d (root, f);
292 }
293 /*
294 * Indexed by inorder access
295 */
296
297 #endif