Mercurial > ~dholland > hg > ag > index.cgi

comparison anagram/support/agbaltree-imp.h @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /**********************************************************
2
3 The AnaGram Class Library
4
5 The AgBalancedTree Class
6 Copyright 1997 Parsifal Software. All Rights Reserved.
7 See the file COPYING for license and usage terms.
8
9 ***********************************************************/
10
11 #ifndef AGBALTREE_IMP_H
12 #define AGBALTREE_IMP_H
13
14 #include "minmax.h"
15
16
17 template <class T>
18 void *AgBalancedTree<T>::Node::operator new(size_t n) {
19 return malloc(n);
20 }
21
22 template <class T>
23 void AgBalancedTree<T>::Node::operator delete(void *p) {
24 free(p);
25 }
26
27 template <class T>
28 AgBalancedTree<T>::Node::Node (const T &t)
29 : left(0), right(0), data(t), count(1)
30 {
31 }
32
33
34 template <class T>
35 AgBalancedTree<T>::~AgBalancedTree() {
36 delete root;
37 }
38
39 template <class T>
40 AgBalancedTree<T>::Node::~Node() {
41 //nodesDeleted++;
42 //LOGV(nodesDeleted);
43 delete left;
44 delete right;
45 }
46
47
48 template <class T>
49 AgBalancedTree<T> &AgBalancedTree<T>::reset() {
50 delete root;
51 root = 0;
52 return *this;
53 }
54
55 template <class T>
56 int AgBalancedTree<T>::operator < (const AgBalancedTree<T> &t) const {
57 int n = min(size(), t.size());
58 int i = 0;
59 while (i < n) {
60 if ((*this)[i] < t[i]) {
61 return 1;
62 }
63 if (t[i] < (*this)[i]) {
64 return 0;
65 }
66 i++;
67 }
68 return size() < t.size();
69 }
70
71 template <class T>
72 void AgBalancedTree<T>::Node::resetCount() {
73 count = 1;
74 if (left) {
75 count += left->count;
76 }
77 if (right) {
78 count += right->count;
79 }
80 }
81
82 template <class T>
83 T &AgBalancedTree<T>::Node::locate(const unsigned x) const {
84 //LOGSECTION("AgBalancedTree<T>::Node::locate");
85 unsigned leftCount = left ? left->count : 0;
86 //LOGV(x) LCV(count) LCV(leftCount);
87 if (x == leftCount) {
88 return (T &) data;
89 }
90 if (x < leftCount) {
91 return left->locate(x);
92 }
93 return right->locate(x - leftCount - 1);
94 }
95
96 template <class T>
97 int AgBalancedTree<T>::compare(const T &x, const T &y) const {
98 if (x < y) {
99 return -1;
100 }
101 return y < x;
102 }
103
104 template <class T>
105 unsigned AgBalancedTree<T>::size() const {
106 return root != 0 ? root->count : 0;
107 }
108
109 template <class T>
110 int AgBalancedTree<T>::includes(const T &t) const {
111 if (root) {
112 return includes(t, root);
113 }
114 else {
115 return 0;
116 }
117 }
118
119 template <class T>
120 int AgBalancedTree<T>::lookup(T &t) const {
121 if (root) {
122 return lookup(t, root);
123 }
124 else {
125 return 0;
126 }
127 }
128
129 template <class T>
130 int AgBalancedTree<T>::insert(const T &t) {
131 if (root) {
132 return insert(t, root);
133 }
134 root = new Node(t);
135 return 0;
136 }
137
138 template <class T>
139 int AgBalancedTree<T>::identify(T &t) {
140 //LOGSECTION("AgBalancedTree::identify");
141 if (root) {
142 return identify(t, root);
143 }
144 root = new Node(t);
145 t = root->data;
146 return 0;
147 }
148
149 template <class T>
150 int AgBalancedTree<T>::identify(T *&t) {
151 if (root) {
152 return identify(t, root);
153 }
154 root = new Node(*t);
155 t = &root->data;
156 return 0;
157 }
158
159 template <class T>
160 int AgBalancedTree<T>::remove(const T &t) {
161 if (root) {
162 return remove(t, root);
163 }
164 else {
165 return 0;
166 }
167 }
168
169 template <class T>
170 int AgBalancedTree<T>::includes(const T &target, AgBalancedTree<T>::Node *node) const {
171 int flag = compare(target, node->data);
172 if (flag == 0) {
173 return 1;
174 }
175 if (flag < 0 && node->left) {
176 return includes(target, node->left);
177 }
178 if (flag > 0 && node->right) {
179 return includes(target, node->right);
180 }
181 return 0;
182 }
183
184 template <class T>
185 int AgBalancedTree<T>::lookup(T &target, AgBalancedTree<T>::Node *node) const {
186 int flag = compare(target, node->data);
187 if (flag == 0) {
188 target = node->data;
189 return 1;
190 }
191 if (flag < 0 && node->left) {
192 return lookup(target, node->left);
193 }
194 if (flag > 0 && node->right) {
195 return lookup(target, node->right);
196 }
197 return 0;
198 }
199
200 template <class T>
201 AgBalancedTree<T> AgBalancedTree<T>::operator + (AgBalancedTree<T> &x) {
202 AgBalancedTree<T> setUnion;
203 int n = size();
204 while (n--) {
205 setUnion.insert((*this)[n]);
206 }
207 n = x.size();
208 while (n--) {
209 setUnion.insert(x[n]);
210 }
211 return setUnion;
212 }
213
214 template <class T>
215 AgBalancedTree<T> AgBalancedTree<T>::operator - (AgBalancedTree<T> &x) {
216 AgBalancedTree<T> difference;
217 int n = size();
218 while (n--) {
219 difference.insert((*this)[n]);
220 }
221 n = x.size();
222 while (n--) {
223 difference.remove(x[n]);
224 }
225 return difference;
226 }
227
228 template <class T>
229 AgBalancedTree<T> AgBalancedTree<T>::operator * (AgBalancedTree<T> &x) {
230 AgBalancedTree<T> intersection;
231 int n = size();
232 while (n--) {
233 T &element = (*this)[n];
234 if (x.includes(element)) {
235 intersection.insert(element);
236 }
237 }
238 return intersection;
239 }
240
241 template <class T>
242 AgBalancedTree<T> &AgBalancedTree<T>::operator *= (AgBalancedTree<T> &x) {
243 int n = size();
244 while (n--) {
245 T &element = (*this)[n];
246 if (!x.includes(element)) {
247 remove(element);
248 }
249 }
250 return *this;
251 }
252
253 template <class T>
254 int AgBalancedTree<T>::insert(const T &target, AgBalancedTree<T>::Node *&node){
255 int flag = compare(target, node->data);
256 if (flag == 0) {
257 return 1;
258 }
259 if (flag < 0 && node->left == 0) {
260 node->left = new Node(target);
261 node->count++;
262 return 0;
263 }
264 if (flag > 0 && node->right == 0) {
265 node->right = new Node(target);
266 node->count++;
267 return 0;
268 }
269
270 if (flag < 0) {
271 if (insert(target, node->left)) {
272 return 1;
273 }
274 node->count++;
275 unsigned newCount = node->left->count;
276 unsigned oldCount = newCount-1;
277 if ((oldCount^newCount) != (oldCount|newCount)) {
278 return 0;
279 }
280 unsigned rightCount = node->right ? node->right->count : 0;
281 if (newCount/2 > rightCount) {
282 rotateRight(node);
283 }
284 }
285 else {
286 if (insert(target, node->right)) {
287 return 1;
288 }
289 node->count++;
290 unsigned newCount = node->right->count;
291 unsigned oldCount = newCount-1;
292 if ((oldCount^newCount) != (oldCount|newCount)) {
293 return 0;
294 }
295 unsigned leftCount = node->left ? node->left->count : 0;
296 if (newCount/2 > leftCount) {
297 rotateLeft(node);
298 }
299 }
300 return 0;
301 }
302
303 template <class T>
304 int AgBalancedTree<T>::identify(T &target, Node *&node) {
305 //LOGSECTION("AgBalancedTree::identify");
306 int flag = compare(target, node->data);
307 if (flag == 0) {
308 target = node->data;
309 return 1;
310 }
311 if (flag < 0 && node->left == 0) {
312 node->left = new Node(target);
313 node->count++;
314 target = node->left->data;
315 return 0;
316 }
317 if (flag > 0 && node->right == 0) {
318 node->right = new Node(target);
319 node->count++;
320 target = node->right->data;
321 return 0;
322 }
323
324 if (flag < 0) {
325 if (identify(target, node->left)) {
326 return 1;
327 }
328 node->count++;
329 unsigned newCount = node->left->count;
330 unsigned oldCount = newCount-1;
331 if ((oldCount^newCount) != (oldCount|newCount)) {
332 return 0;
333 }
334 unsigned rightCount = node->right ? node->right->count : 0;
335 if (newCount/2 > rightCount) {
336 rotateRight(node);
337 }
338 }
339 else {
340 if (identify(target, node->right)) {
341 return 1;
342 }
343 node->count++;
344 unsigned newCount = node->right->count;
345 unsigned oldCount = newCount-1;
346 if ((oldCount^newCount) != (oldCount|newCount)) {
347 return 0;
348 }
349 unsigned leftCount = node->left ? node->left->count : 0;
350 if (newCount/2 > leftCount) {
351 rotateLeft(node);
352 }
353 }
354 return 0;
355 }
356
357 template <class T>
358 int AgBalancedTree<T>::identify(T *&target, AgBalancedTree<T>::Node *&node) {
359 int flag = compare(*target, node->data);
360 if (flag == 0) {
361 target = &node->data;
362 return 1;
363 }
364 if (flag < 0 && node->left == 0) {
365 node->left = new Node(*target);
366 node->count++;
367 target = &node->left->data;
368 return 0;
369 }
370 if (flag > 0 && node->right == 0) {
371 node->right = new Node(*target);
372 node->count++;
373 target = &node->right->data;
374 return 0;
375 }
376
377 if (flag < 0) {
378 if (identify(target, node->left)) {
379 return 1;
380 }
381 node->count++;
382 unsigned newCount = node->left->count;
383 unsigned oldCount = newCount-1;
384 if ((oldCount^newCount) != (oldCount|newCount)) {
385 return 0;
386 }
387 unsigned rightCount = node->right ? node->right->count : 0;
388 if (newCount/2 > rightCount) {
389 rotateRight(node);
390 }
391 }
392 else {
393 if (identify(target, node->right)) {
394 return 1;
395 }
396 node->count++;
397 unsigned newCount = node->right->count;
398 unsigned oldCount = newCount-1;
399 if ((oldCount^newCount) != (oldCount|newCount)) {
400 return 0;
401 }
402 unsigned leftCount = node->left ? node->left->count : 0;
403 if (newCount/2 > leftCount) {
404 rotateLeft(node);
405 }
406 }
407 return 0;
408 }
409
410 template <class T>
411 int AgBalancedTree<T>::remove(const T &target, AgBalancedTree<T>::Node *&node){
412 int flag = compare(target, node->data);
413 if (flag < 0 && node->left) {
414 unsigned oldCount = node->left->count;
415 if (remove(target, node->left) == 0) {
416 return 0;
417 }
418 node->count--;
419 unsigned newCount = oldCount - 1;
420 if ((oldCount^newCount) != (oldCount|newCount)) {
421 return 1;
422 }
423 unsigned rightCount = node->right ? node->right->count : 0;
424 if (rightCount/2 > newCount) {
425 rotateLeft(node);
426 }
427 return 1;
428 }
429 if (flag > 0 && node->right) {
430 unsigned oldCount = node->right->count;
431 if (remove(target, node->right) == 0) {
432 return 0;
433 }
434 node->count--;
435 unsigned newCount = oldCount - 1;
436 if ((oldCount^newCount) != (oldCount|newCount)) {
437 return 1;
438 }
439 unsigned leftCount = node->left ? node->left->count : 0;
440 if (leftCount/2 > newCount) {
441 rotateRight(node);
442 }
443 return 1;
444 }
445
446 if (flag) {
447 return 0;
448 }
449 if (node->count == 1) {
450 delete node;
451 node = 0;
452 return 1;
453 }
454
455 unsigned leftCount = node->left ? node->left->count : 0;
456 unsigned rightCount = node->right ? node->right->count : 0;
457 Node *replacement;
458 if (rightCount > leftCount) {
459 replacement = extractMin(node->right);
460 }
461 else {
462 replacement = extractMax(node->left);
463 }
464 replacement->left = node->left;
465 replacement->right = node->right;
466 node->left = node->right = 0;
467 delete node;
468 replacement->resetCount();
469 node = replacement;
470 return 1;
471 }
472
473 template <class T>
474 void AgBalancedTree<T>::rotateLeft(AgBalancedTree<T>::Node *&node) {
475 Node *nRL = node->right->left;
476 Node *nRR = node->right->right;
477 unsigned leftCount = nRL ? nRL->count : 0;
478 unsigned rightCount = nRR ? nRR->count : 0;
479 if (leftCount < rightCount) {
480 Node *replacement = node->right;
481 Node *orphan = replacement->left;
482
483 replacement->left = node;
484
485 node->right = orphan;
486 node->resetCount();
487
488 node = replacement;
489 node->resetCount();
490 return;
491 }
492 Node *replacement = nRL;
493 Node *leftOrphan = replacement->left;
494 Node *rightOrphan = replacement->right;
495
496 replacement->right = node->right;
497 replacement->right->left = rightOrphan;
498 replacement->right->resetCount();
499
500 replacement->left = node;
501 replacement->left->right = leftOrphan;
502 replacement->left->resetCount();
503
504 node = replacement;
505 node->resetCount();
506 }
507
508 template <class T>
509 void AgBalancedTree<T>::rotateRight(AgBalancedTree<T>::Node *&node) {
510 Node *nLR = node->left->right;
511 Node *nLL = node->left->left;
512 unsigned leftCount = nLL ? nLL->count : 0;
513 unsigned rightCount = nLR ? nLR->count : 0;
514 if (rightCount < leftCount) {
515 Node *replacement = node->left;
516 Node *orphan = replacement->right;
517
518 replacement->right = node;
519
520 node->left = orphan;
521 node->resetCount();
522
523 node = replacement;
524 node->resetCount();
525 return;
526 }
527 Node *replacement = nLR;
528 Node *leftOrphan = replacement->left;
529 Node *rightOrphan = replacement->right;
530
531 replacement->left = node->left;
532 replacement->left->right = leftOrphan;
533 replacement->left->resetCount();
534
535 replacement->right = node;
536 replacement->right->left = rightOrphan;
537 replacement->right->resetCount();
538
539 node = replacement;
540 node->resetCount();
541 }
542
543 template <class T>
544 typename AgBalancedTree<T>::Node *
545 AgBalancedTree<T>::extractMin(typename AgBalancedTree<T>::Node *&node) {
546 Node *result;
547 if (node->left) {
548 unsigned oldCount = node->left->count;
549 result = extractMin(node->left);
550 node->count--;
551 unsigned newCount = oldCount - 1;
552 if ((oldCount^newCount) != (oldCount|newCount)) {
553 return result;
554 }
555 unsigned rightCount = node->right ? node->right->count : 0;
556 if (rightCount/2 > newCount) {
557 rotateLeft(node);
558 }
559 return result;
560 }
561 result = node;
562 node = node->right;
563 return result;
564 }
565
566 template <class T>
567 typename AgBalancedTree<T>::Node *
568 AgBalancedTree<T>::extractMax(typename AgBalancedTree<T>::Node *&node) {
569 Node *result;
570 if (node->right) {
571 unsigned oldCount = node->right->count;
572 result = extractMax(node->right);
573 node->count--;
574 unsigned newCount = oldCount - 1;
575 if ((oldCount^newCount) != (oldCount|newCount)) {
576 return result;
577 }
578 unsigned leftCount = node->left ? node->left->count : 0;
579 if (leftCount/2 > newCount) {
580 rotateRight(node);
581 }
582 return result;
583 }
584 result = node;
585 node = node->left;
586 return result;
587 }
588
589
590 #endif /* AGBALTREE_IMP_H */