← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WTF/wtf/AVLTree.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/WTF/wtf/AVLTree.h
 
1
/*
 
2
 * Copyright (C) 2008 Apple Inc. All rights reserved.
 
3
 *
 
4
 * Based on Abstract AVL Tree Template v1.5 by Walt Karas
 
5
 * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
 
6
 *
 
7
 * Redistribution and use in source and binary forms, with or without
 
8
 * modification, are permitted provided that the following conditions
 
9
 * are met:
 
10
 *
 
11
 * 1.  Redistributions of source code must retain the above copyright
 
12
 *     notice, this list of conditions and the following disclaimer.
 
13
 * 2.  Redistributions in binary form must reproduce the above copyright
 
14
 *     notice, this list of conditions and the following disclaimer in the
 
15
 *     documentation and/or other materials provided with the distribution.
 
16
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 
17
 *     its contributors may be used to endorse or promote products derived
 
18
 *     from this software without specific prior written permission.
 
19
 *
 
20
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 
21
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 
22
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 
23
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 
24
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 
25
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 
26
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 
27
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
28
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
29
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
30
 */
 
31
 
 
32
#ifndef AVL_TREE_H_
 
33
#define AVL_TREE_H_
 
34
 
 
35
#include <wtf/Assertions.h>
 
36
#include <wtf/FixedArray.h>
 
37
 
 
38
namespace WTF {
 
39
 
 
40
// Here is the reference class for BSet.
 
41
//
 
42
// class BSet
 
43
//   {
 
44
//   public:
 
45
//
 
46
//     class ANY_bitref
 
47
//       {
 
48
//       public:
 
49
//         operator bool ();
 
50
//         void operator = (bool b);
 
51
//       };
 
52
//
 
53
//     // Does not have to initialize bits.
 
54
//     BSet();
 
55
//
 
56
//     // Must return a valid value for index when 0 <= index < maxDepth
 
57
//     ANY_bitref operator [] (unsigned index);
 
58
//
 
59
//     // Set all bits to 1.
 
60
//     void set();
 
61
//
 
62
//     // Set all bits to 0.
 
63
//     void reset();
 
64
//   };
 
65
 
 
66
template<unsigned maxDepth>
 
67
class AVLTreeDefaultBSet {
 
68
public:
 
69
    bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; }
 
70
    void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
 
71
    void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
 
72
 
 
73
private:
 
74
    FixedArray<bool, maxDepth> m_data;
 
75
};
 
76
 
 
77
// How to determine maxDepth:
 
78
// d  Minimum number of nodes
 
79
// 2  2
 
80
// 3  4
 
81
// 4  7
 
82
// 5  12
 
83
// 6  20
 
84
// 7  33
 
85
// 8  54
 
86
// 9  88
 
87
// 10 143
 
88
// 11 232
 
89
// 12 376
 
90
// 13 609
 
91
// 14 986
 
92
// 15 1,596
 
93
// 16 2,583
 
94
// 17 4,180
 
95
// 18 6,764
 
96
// 19 10,945
 
97
// 20 17,710
 
98
// 21 28,656
 
99
// 22 46,367
 
100
// 23 75,024
 
101
// 24 121,392
 
102
// 25 196,417
 
103
// 26 317,810
 
104
// 27 514,228
 
105
// 28 832,039
 
106
// 29 1,346,268
 
107
// 30 2,178,308
 
108
// 31 3,524,577
 
109
// 32 5,702,886
 
110
// 33 9,227,464
 
111
// 34 14,930,351
 
112
// 35 24,157,816
 
113
// 36 39,088,168
 
114
// 37 63,245,985
 
115
// 38 102,334,154
 
116
// 39 165,580,140
 
117
// 40 267,914,295
 
118
// 41 433,494,436
 
119
// 42 701,408,732
 
120
// 43 1,134,903,169
 
121
// 44 1,836,311,902
 
122
// 45 2,971,215,072
 
123
//
 
124
// E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28.
 
125
// You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000.
 
126
 
 
127
template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> >
 
128
class AVLTree {
 
129
public:
 
130
 
 
131
    typedef typename Abstractor::key key;
 
132
    typedef typename Abstractor::handle handle;
 
133
    typedef typename Abstractor::size size;
 
134
 
 
135
    enum SearchType {
 
136
        EQUAL = 1,
 
137
        LESS = 2,
 
138
        GREATER = 4,
 
139
        LESS_EQUAL = EQUAL | LESS,
 
140
        GREATER_EQUAL = EQUAL | GREATER
 
141
    };
 
142
 
 
143
 
 
144
    Abstractor& abstractor() { return abs; }
 
145
 
 
146
    inline handle insert(handle h);
 
147
 
 
148
    inline handle search(key k, SearchType st = EQUAL);
 
149
    inline handle search_least();
 
150
    inline handle search_greatest();
 
151
 
 
152
    inline handle remove(key k);
 
153
 
 
154
    inline handle subst(handle new_node);
 
155
 
 
156
    void purge() { abs.root = null(); }
 
157
 
 
158
    bool is_empty() { return abs.root == null(); }
 
159
 
 
160
    AVLTree() { abs.root = null(); }
 
161
 
 
162
    class Iterator {
 
163
    public:
 
164
 
 
165
        // Initialize depth to invalid value, to indicate iterator is
 
166
        // invalid.   (Depth is zero-base.)
 
167
        Iterator() { depth = ~0U; }
 
168
 
 
169
        void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
 
170
        {
 
171
            // Mask of high bit in an int.
 
172
            const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
 
173
 
 
174
            // Save the tree that we're going to iterate through in a
 
175
            // member variable.
 
176
            tree_ = &tree;
 
177
 
 
178
            int cmp, target_cmp;
 
179
            handle h = tree_->abs.root;
 
180
            unsigned d = 0;
 
181
 
 
182
            depth = ~0U;
 
183
 
 
184
            if (h == null())
 
185
              // Tree is empty.
 
186
              return;
 
187
 
 
188
            if (st & LESS)
 
189
              // Key can be greater than key of starting node.
 
190
              target_cmp = 1;
 
191
            else if (st & GREATER)
 
192
              // Key can be less than key of starting node.
 
193
              target_cmp = -1;
 
194
            else
 
195
              // Key must be same as key of starting node.
 
196
              target_cmp = 0;
 
197
 
 
198
            for (;;) {
 
199
                cmp = cmp_k_n(k, h);
 
200
                if (cmp == 0) {
 
201
                    if (st & EQUAL) {
 
202
                        // Equal node was sought and found as starting node.
 
203
                        depth = d;
 
204
                        break;
 
205
                    }
 
206
                    cmp = -target_cmp;
 
207
                } else if (target_cmp != 0) {
 
208
                    if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
 
209
                        // cmp and target_cmp are both negative or both positive.
 
210
                        depth = d;
 
211
                    }
 
212
                }
 
213
                h = cmp < 0 ? get_lt(h) : get_gt(h);
 
214
                if (h == null())
 
215
                    break;
 
216
                branch[d] = cmp > 0;
 
217
                path_h[d++] = h;
 
218
            }
 
219
        }
 
220
 
 
221
        void start_iter_least(AVLTree &tree)
 
222
        {
 
223
            tree_ = &tree;
 
224
 
 
225
            handle h = tree_->abs.root;
 
226
 
 
227
            depth = ~0U;
 
228
 
 
229
            branch.reset();
 
230
 
 
231
            while (h != null()) {
 
232
                if (depth != ~0U)
 
233
                    path_h[depth] = h;
 
234
                depth++;
 
235
                h = get_lt(h);
 
236
            }
 
237
        }
 
238
 
 
239
        void start_iter_greatest(AVLTree &tree)
 
240
        {
 
241
            tree_ = &tree;
 
242
 
 
243
            handle h = tree_->abs.root;
 
244
 
 
245
            depth = ~0U;
 
246
 
 
247
            branch.set();
 
248
 
 
249
            while (h != null()) {
 
250
                if (depth != ~0U)
 
251
                    path_h[depth] = h;
 
252
                depth++;
 
253
                h = get_gt(h);
 
254
            }
 
255
        }
 
256
 
 
257
        handle operator*()
 
258
        {
 
259
            if (depth == ~0U)
 
260
                return null();
 
261
 
 
262
            return depth == 0 ? tree_->abs.root : path_h[depth - 1];
 
263
        }
 
264
 
 
265
        void operator++()
 
266
        {
 
267
            if (depth != ~0U) {
 
268
                handle h = get_gt(**this);
 
269
                if (h == null()) {
 
270
                    do {
 
271
                        if (depth == 0) {
 
272
                            depth = ~0U;
 
273
                            break;
 
274
                        }
 
275
                        depth--;
 
276
                    } while (branch[depth]);
 
277
                } else {
 
278
                    branch[depth] = true;
 
279
                    path_h[depth++] = h;
 
280
                    for (;;) {
 
281
                        h = get_lt(h);
 
282
                        if (h == null())
 
283
                            break;
 
284
                        branch[depth] = false;
 
285
                        path_h[depth++] = h;
 
286
                    }
 
287
                }
 
288
            }
 
289
        }
 
290
 
 
291
        void operator--()
 
292
        {
 
293
            if (depth != ~0U) {
 
294
                handle h = get_lt(**this);
 
295
                if (h == null())
 
296
                    do {
 
297
                        if (depth == 0) {
 
298
                            depth = ~0U;
 
299
                            break;
 
300
                        }
 
301
                        depth--;
 
302
                    } while (!branch[depth]);
 
303
                else {
 
304
                    branch[depth] = false;
 
305
                    path_h[depth++] = h;
 
306
                    for (;;) {
 
307
                        h = get_gt(h);
 
308
                        if (h == null())
 
309
                            break;
 
310
                        branch[depth] = true;
 
311
                        path_h[depth++] = h;
 
312
                    }
 
313
                }
 
314
            }
 
315
        }
 
316
 
 
317
        void operator++(int) { ++(*this); }
 
318
        void operator--(int) { --(*this); }
 
319
 
 
320
    protected:
 
321
 
 
322
        // Tree being iterated over.
 
323
        AVLTree *tree_;
 
324
 
 
325
        // Records a path into the tree.  If branch[n] is true, indicates
 
326
        // take greater branch from the nth node in the path, otherwise
 
327
        // take the less branch.  branch[0] gives branch from root, and
 
328
        // so on.
 
329
        BSet branch;
 
330
 
 
331
        // Zero-based depth of path into tree.
 
332
        unsigned depth;
 
333
 
 
334
        // Handles of nodes in path from root to current node (returned by *).
 
335
        handle path_h[maxDepth - 1];
 
336
 
 
337
        int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
 
338
        int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
 
339
        handle get_lt(handle h) { return tree_->abs.get_less(h); }
 
340
        handle get_gt(handle h) { return tree_->abs.get_greater(h); }
 
341
        handle null() { return tree_->abs.null(); }
 
342
    };
 
343
 
 
344
    template<typename fwd_iter>
 
345
    bool build(fwd_iter p, size num_nodes)
 
346
    {
 
347
        if (num_nodes == 0) {
 
348
            abs.root = null();
 
349
            return true;
 
350
        }
 
351
 
 
352
        // Gives path to subtree being built.  If branch[N] is false, branch
 
353
        // less from the node at depth N, if true branch greater.
 
354
        BSet branch;
 
355
 
 
356
        // If rem[N] is true, then for the current subtree at depth N, it's
 
357
        // greater subtree has one more node than it's less subtree.
 
358
        BSet rem;
 
359
 
 
360
            // Depth of root node of current subtree.
 
361
        unsigned depth = 0;
 
362
 
 
363
            // Number of nodes in current subtree.
 
364
        size num_sub = num_nodes;
 
365
 
 
366
        // The algorithm relies on a stack of nodes whose less subtree has
 
367
        // been built, but whose right subtree has not yet been built.  The
 
368
        // stack is implemented as linked list.  The nodes are linked
 
369
        // together by having the "greater" handle of a node set to the
 
370
        // next node in the list.  "less_parent" is the handle of the first
 
371
        // node in the list.
 
372
        handle less_parent = null();
 
373
 
 
374
        // h is root of current subtree, child is one of its children.
 
375
        handle h, child;
 
376
 
 
377
        for (;;) {
 
378
            while (num_sub > 2) {
 
379
                // Subtract one for root of subtree.
 
380
                num_sub--;
 
381
                rem[depth] = !!(num_sub & 1);
 
382
                branch[depth++] = false;
 
383
                num_sub >>= 1;
 
384
            }
 
385
 
 
386
            if (num_sub == 2) {
 
387
                // Build a subtree with two nodes, slanting to greater.
 
388
                // I arbitrarily chose to always have the extra node in the
 
389
                // greater subtree when there is an odd number of nodes to
 
390
                // split between the two subtrees.
 
391
 
 
392
                h = *p;
 
393
                p++;
 
394
                child = *p;
 
395
                p++;
 
396
                set_lt(child, null());
 
397
                set_gt(child, null());
 
398
                set_bf(child, 0);
 
399
                set_gt(h, child);
 
400
                set_lt(h, null());
 
401
                set_bf(h, 1);
 
402
            } else { // num_sub == 1
 
403
                // Build a subtree with one node.
 
404
 
 
405
                h = *p;
 
406
                p++;
 
407
                set_lt(h, null());
 
408
                set_gt(h, null());
 
409
                set_bf(h, 0);
 
410
            }
 
411
 
 
412
            while (depth) {
 
413
                depth--;
 
414
                if (!branch[depth])
 
415
                    // We've completed a less subtree.
 
416
                    break;
 
417
 
 
418
                // We've completed a greater subtree, so attach it to
 
419
                // its parent (that is less than it).  We pop the parent
 
420
                // off the stack of less parents.
 
421
                child = h;
 
422
                h = less_parent;
 
423
                less_parent = get_gt(h);
 
424
                set_gt(h, child);
 
425
                // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
 
426
                num_sub <<= 1;
 
427
                num_sub += 1 - rem[depth];
 
428
                if (num_sub & (num_sub - 1))
 
429
                    // num_sub is not a power of 2
 
430
                    set_bf(h, 0);
 
431
                else
 
432
                    // num_sub is a power of 2
 
433
                    set_bf(h, 1);
 
434
            }
 
435
 
 
436
            if (num_sub == num_nodes)
 
437
                // We've completed the full tree.
 
438
                break;
 
439
 
 
440
            // The subtree we've completed is the less subtree of the
 
441
            // next node in the sequence.
 
442
 
 
443
            child = h;
 
444
            h = *p;
 
445
            p++;
 
446
            set_lt(h, child);
 
447
 
 
448
            // Put h into stack of less parents.
 
449
            set_gt(h, less_parent);
 
450
            less_parent = h;
 
451
 
 
452
            // Proceed to creating greater than subtree of h.
 
453
            branch[depth] = true;
 
454
            num_sub += rem[depth++];
 
455
 
 
456
        } // end for (;;)
 
457
 
 
458
        abs.root = h;
 
459
 
 
460
        return true;
 
461
    }
 
462
 
 
463
protected:
 
464
 
 
465
    friend class Iterator;
 
466
 
 
467
    // Create a class whose sole purpose is to take advantage of
 
468
    // the "empty member" optimization.
 
469
    struct abs_plus_root : public Abstractor {
 
470
        // The handle of the root element in the AVL tree.
 
471
        handle root;
 
472
    };
 
473
 
 
474
    abs_plus_root abs;
 
475
 
 
476
 
 
477
    handle get_lt(handle h) { return abs.get_less(h); }
 
478
    void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
 
479
 
 
480
    handle get_gt(handle h) { return abs.get_greater(h); }
 
481
    void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
 
482
 
 
483
    int get_bf(handle h) { return abs.get_balance_factor(h); }
 
484
    void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
 
485
 
 
486
    int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
 
487
    int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
 
488
 
 
489
    handle null() { return abs.null(); }
 
490
 
 
491
private:
 
492
 
 
493
    // Balances subtree, returns handle of root node of subtree
 
494
    // after balancing.
 
495
    handle balance(handle bal_h)
 
496
    {
 
497
        handle deep_h;
 
498
 
 
499
        // Either the "greater than" or the "less than" subtree of
 
500
        // this node has to be 2 levels deeper (or else it wouldn't
 
501
        // need balancing).
 
502
 
 
503
        if (get_bf(bal_h) > 0) {
 
504
            // "Greater than" subtree is deeper.
 
505
 
 
506
            deep_h = get_gt(bal_h);
 
507
 
 
508
            if (get_bf(deep_h) < 0) {
 
509
                handle old_h = bal_h;
 
510
                bal_h = get_lt(deep_h);
 
511
 
 
512
                set_gt(old_h, get_lt(bal_h));
 
513
                set_lt(deep_h, get_gt(bal_h));
 
514
                set_lt(bal_h, old_h);
 
515
                set_gt(bal_h, deep_h);
 
516
 
 
517
                int bf = get_bf(bal_h);
 
518
                if (bf != 0) {
 
519
                    if (bf > 0) {
 
520
                        set_bf(old_h, -1);
 
521
                        set_bf(deep_h, 0);
 
522
                    } else {
 
523
                        set_bf(deep_h, 1);
 
524
                        set_bf(old_h, 0);
 
525
                    }
 
526
                    set_bf(bal_h, 0);
 
527
                } else {
 
528
                    set_bf(old_h, 0);
 
529
                    set_bf(deep_h, 0);
 
530
                }
 
531
            } else {
 
532
                set_gt(bal_h, get_lt(deep_h));
 
533
                set_lt(deep_h, bal_h);
 
534
                if (get_bf(deep_h) == 0) {
 
535
                    set_bf(deep_h, -1);
 
536
                    set_bf(bal_h, 1);
 
537
                } else {
 
538
                    set_bf(deep_h, 0);
 
539
                    set_bf(bal_h, 0);
 
540
                }
 
541
                bal_h = deep_h;
 
542
            }
 
543
        } else {
 
544
            // "Less than" subtree is deeper.
 
545
 
 
546
            deep_h = get_lt(bal_h);
 
547
 
 
548
            if (get_bf(deep_h) > 0) {
 
549
                handle old_h = bal_h;
 
550
                bal_h = get_gt(deep_h);
 
551
                set_lt(old_h, get_gt(bal_h));
 
552
                set_gt(deep_h, get_lt(bal_h));
 
553
                set_gt(bal_h, old_h);
 
554
                set_lt(bal_h, deep_h);
 
555
 
 
556
                int bf = get_bf(bal_h);
 
557
                if (bf != 0) {
 
558
                    if (bf < 0) {
 
559
                        set_bf(old_h, 1);
 
560
                        set_bf(deep_h, 0);
 
561
                    } else {
 
562
                        set_bf(deep_h, -1);
 
563
                        set_bf(old_h, 0);
 
564
                    }
 
565
                    set_bf(bal_h, 0);
 
566
                } else {
 
567
                    set_bf(old_h, 0);
 
568
                    set_bf(deep_h, 0);
 
569
                }
 
570
            } else {
 
571
                set_lt(bal_h, get_gt(deep_h));
 
572
                set_gt(deep_h, bal_h);
 
573
                if (get_bf(deep_h) == 0) {
 
574
                    set_bf(deep_h, 1);
 
575
                    set_bf(bal_h, -1);
 
576
                } else {
 
577
                    set_bf(deep_h, 0);
 
578
                    set_bf(bal_h, 0);
 
579
                }
 
580
                bal_h = deep_h;
 
581
            }
 
582
        }
 
583
 
 
584
        return bal_h;
 
585
    }
 
586
 
 
587
};
 
588
 
 
589
template <class Abstractor, unsigned maxDepth, class BSet>
 
590
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
591
AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
 
592
{
 
593
    set_lt(h, null());
 
594
    set_gt(h, null());
 
595
    set_bf(h, 0);
 
596
 
 
597
    if (abs.root == null())
 
598
        abs.root = h;
 
599
    else {
 
600
        // Last unbalanced node encountered in search for insertion point.
 
601
        handle unbal = null();
 
602
        // Parent of last unbalanced node.
 
603
        handle parent_unbal = null();
 
604
        // Balance factor of last unbalanced node.
 
605
        int unbal_bf;
 
606
 
 
607
        // Zero-based depth in tree.
 
608
        unsigned depth = 0, unbal_depth = 0;
 
609
 
 
610
        // Records a path into the tree.  If branch[n] is true, indicates
 
611
        // take greater branch from the nth node in the path, otherwise
 
612
        // take the less branch.  branch[0] gives branch from root, and
 
613
        // so on.
 
614
        BSet branch;
 
615
 
 
616
        handle hh = abs.root;
 
617
        handle parent = null();
 
618
        int cmp;
 
619
 
 
620
        do {
 
621
            if (get_bf(hh) != 0) {
 
622
                unbal = hh;
 
623
                parent_unbal = parent;
 
624
                unbal_depth = depth;
 
625
            }
 
626
            cmp = cmp_n_n(h, hh);
 
627
            if (cmp == 0)
 
628
                // Duplicate key.
 
629
                return hh;
 
630
            parent = hh;
 
631
            hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
 
632
            branch[depth++] = cmp > 0;
 
633
        } while (hh != null());
 
634
 
 
635
        //  Add node to insert as leaf of tree.
 
636
        if (cmp < 0)
 
637
            set_lt(parent, h);
 
638
        else
 
639
            set_gt(parent, h);
 
640
 
 
641
        depth = unbal_depth;
 
642
 
 
643
        if (unbal == null())
 
644
            hh = abs.root;
 
645
        else {
 
646
            cmp = branch[depth++] ? 1 : -1;
 
647
            unbal_bf = get_bf(unbal);
 
648
            if (cmp < 0)
 
649
                unbal_bf--;
 
650
            else  // cmp > 0
 
651
                unbal_bf++;
 
652
            hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
 
653
            if ((unbal_bf != -2) && (unbal_bf != 2)) {
 
654
                // No rebalancing of tree is necessary.
 
655
                set_bf(unbal, unbal_bf);
 
656
                unbal = null();
 
657
            }
 
658
        }
 
659
 
 
660
        if (hh != null())
 
661
            while (h != hh) {
 
662
                cmp = branch[depth++] ? 1 : -1;
 
663
                if (cmp < 0) {
 
664
                    set_bf(hh, -1);
 
665
                    hh = get_lt(hh);
 
666
                } else { // cmp > 0
 
667
                    set_bf(hh, 1);
 
668
                    hh = get_gt(hh);
 
669
                }
 
670
            }
 
671
 
 
672
        if (unbal != null()) {
 
673
            unbal = balance(unbal);
 
674
            if (parent_unbal == null())
 
675
                abs.root = unbal;
 
676
            else {
 
677
                depth = unbal_depth - 1;
 
678
                cmp = branch[depth] ? 1 : -1;
 
679
                if (cmp < 0)
 
680
                    set_lt(parent_unbal, unbal);
 
681
                else  // cmp > 0
 
682
                    set_gt(parent_unbal, unbal);
 
683
            }
 
684
        }
 
685
    }
 
686
 
 
687
    return h;
 
688
}
 
689
 
 
690
template <class Abstractor, unsigned maxDepth, class BSet>
 
691
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
692
AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
 
693
{
 
694
    const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
 
695
 
 
696
    int cmp, target_cmp;
 
697
    handle match_h = null();
 
698
    handle h = abs.root;
 
699
 
 
700
    if (st & LESS)
 
701
        target_cmp = 1;
 
702
    else if (st & GREATER)
 
703
        target_cmp = -1;
 
704
    else
 
705
        target_cmp = 0;
 
706
 
 
707
    while (h != null()) {
 
708
        cmp = cmp_k_n(k, h);
 
709
        if (cmp == 0) {
 
710
            if (st & EQUAL) {
 
711
                match_h = h;
 
712
                break;
 
713
            }
 
714
            cmp = -target_cmp;
 
715
        } else if (target_cmp != 0)
 
716
            if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
 
717
                // cmp and target_cmp are both positive or both negative.
 
718
                match_h = h;
 
719
        h = cmp < 0 ? get_lt(h) : get_gt(h);
 
720
    }
 
721
 
 
722
    return match_h;
 
723
}
 
724
 
 
725
template <class Abstractor, unsigned maxDepth, class BSet>
 
726
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
727
AVLTree<Abstractor, maxDepth, BSet>::search_least()
 
728
{
 
729
    handle h = abs.root, parent = null();
 
730
 
 
731
    while (h != null()) {
 
732
        parent = h;
 
733
        h = get_lt(h);
 
734
    }
 
735
 
 
736
    return parent;
 
737
}
 
738
 
 
739
template <class Abstractor, unsigned maxDepth, class BSet>
 
740
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
741
AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
 
742
{
 
743
    handle h = abs.root, parent = null();
 
744
 
 
745
    while (h != null()) {
 
746
        parent = h;
 
747
        h = get_gt(h);
 
748
    }
 
749
 
 
750
    return parent;
 
751
}
 
752
 
 
753
template <class Abstractor, unsigned maxDepth, class BSet>
 
754
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
755
AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
 
756
{
 
757
    // Zero-based depth in tree.
 
758
    unsigned depth = 0, rm_depth;
 
759
 
 
760
    // Records a path into the tree.  If branch[n] is true, indicates
 
761
    // take greater branch from the nth node in the path, otherwise
 
762
    // take the less branch.  branch[0] gives branch from root, and
 
763
    // so on.
 
764
    BSet branch;
 
765
 
 
766
    handle h = abs.root;
 
767
    handle parent = null(), child;
 
768
    int cmp, cmp_shortened_sub_with_path = 0;
 
769
 
 
770
    for (;;) {
 
771
        if (h == null())
 
772
            // No node in tree with given key.
 
773
            return null();
 
774
        cmp = cmp_k_n(k, h);
 
775
        if (cmp == 0)
 
776
            // Found node to remove.
 
777
            break;
 
778
        parent = h;
 
779
        h = cmp < 0 ? get_lt(h) : get_gt(h);
 
780
        branch[depth++] = cmp > 0;
 
781
        cmp_shortened_sub_with_path = cmp;
 
782
    }
 
783
    handle rm = h;
 
784
    handle parent_rm = parent;
 
785
    rm_depth = depth;
 
786
 
 
787
    // If the node to remove is not a leaf node, we need to get a
 
788
    // leaf node, or a node with a single leaf as its child, to put
 
789
    // in the place of the node to remove.  We will get the greatest
 
790
    // node in the less subtree (of the node to remove), or the least
 
791
    // node in the greater subtree.  We take the leaf node from the
 
792
    // deeper subtree, if there is one.
 
793
 
 
794
    if (get_bf(h) < 0) {
 
795
        child = get_lt(h);
 
796
        branch[depth] = false;
 
797
        cmp = -1;
 
798
    } else {
 
799
        child = get_gt(h);
 
800
        branch[depth] = true;
 
801
        cmp = 1;
 
802
    }
 
803
    depth++;
 
804
 
 
805
    if (child != null()) {
 
806
        cmp = -cmp;
 
807
        do {
 
808
            parent = h;
 
809
            h = child;
 
810
            if (cmp < 0) {
 
811
                child = get_lt(h);
 
812
                branch[depth] = false;
 
813
            } else {
 
814
                child = get_gt(h);
 
815
                branch[depth] = true;
 
816
            }
 
817
            depth++;
 
818
        } while (child != null());
 
819
 
 
820
        if (parent == rm)
 
821
            // Only went through do loop once.  Deleted node will be replaced
 
822
            // in the tree structure by one of its immediate children.
 
823
            cmp_shortened_sub_with_path = -cmp;
 
824
        else
 
825
            cmp_shortened_sub_with_path = cmp;
 
826
 
 
827
        // Get the handle of the opposite child, which may not be null.
 
828
        child = cmp > 0 ? get_lt(h) : get_gt(h);
 
829
    }
 
830
 
 
831
    if (parent == null())
 
832
        // There were only 1 or 2 nodes in this tree.
 
833
        abs.root = child;
 
834
    else if (cmp_shortened_sub_with_path < 0)
 
835
        set_lt(parent, child);
 
836
    else
 
837
        set_gt(parent, child);
 
838
 
 
839
    // "path" is the parent of the subtree being eliminated or reduced
 
840
    // from a depth of 2 to 1.  If "path" is the node to be removed, we
 
841
    // set path to the node we're about to poke into the position of the
 
842
    // node to be removed.
 
843
    handle path = parent == rm ? h : parent;
 
844
 
 
845
    if (h != rm) {
 
846
        // Poke in the replacement for the node to be removed.
 
847
        set_lt(h, get_lt(rm));
 
848
        set_gt(h, get_gt(rm));
 
849
        set_bf(h, get_bf(rm));
 
850
        if (parent_rm == null())
 
851
            abs.root = h;
 
852
        else {
 
853
            depth = rm_depth - 1;
 
854
            if (branch[depth])
 
855
                set_gt(parent_rm, h);
 
856
            else
 
857
                set_lt(parent_rm, h);
 
858
        }
 
859
    }
 
860
 
 
861
    if (path != null()) {
 
862
        // Create a temporary linked list from the parent of the path node
 
863
        // to the root node.
 
864
        h = abs.root;
 
865
        parent = null();
 
866
        depth = 0;
 
867
        while (h != path) {
 
868
            if (branch[depth++]) {
 
869
                child = get_gt(h);
 
870
                set_gt(h, parent);
 
871
            } else {
 
872
                child = get_lt(h);
 
873
                set_lt(h, parent);
 
874
            }
 
875
            parent = h;
 
876
            h = child;
 
877
        }
 
878
 
 
879
        // Climb from the path node to the root node using the linked
 
880
        // list, restoring the tree structure and rebalancing as necessary.
 
881
        bool reduced_depth = true;
 
882
        int bf;
 
883
        cmp = cmp_shortened_sub_with_path;
 
884
        for (;;) {
 
885
            if (reduced_depth) {
 
886
                bf = get_bf(h);
 
887
                if (cmp < 0)
 
888
                    bf++;
 
889
                else  // cmp > 0
 
890
                    bf--;
 
891
                if ((bf == -2) || (bf == 2)) {
 
892
                    h = balance(h);
 
893
                    bf = get_bf(h);
 
894
                } else
 
895
                    set_bf(h, bf);
 
896
                reduced_depth = (bf == 0);
 
897
            }
 
898
            if (parent == null())
 
899
                break;
 
900
            child = h;
 
901
            h = parent;
 
902
            cmp = branch[--depth] ? 1 : -1;
 
903
            if (cmp < 0)    {
 
904
                parent = get_lt(h);
 
905
                set_lt(h, child);
 
906
            } else {
 
907
                parent = get_gt(h);
 
908
                set_gt(h, child);
 
909
            }
 
910
        }
 
911
        abs.root = h;
 
912
    }
 
913
 
 
914
    return rm;
 
915
}
 
916
 
 
917
template <class Abstractor, unsigned maxDepth, class BSet>
 
918
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
 
919
AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
 
920
{
 
921
    handle h = abs.root;
 
922
    handle parent = null();
 
923
    int cmp, last_cmp;
 
924
 
 
925
    /* Search for node already in tree with same key. */
 
926
    for (;;) {
 
927
        if (h == null())
 
928
            /* No node in tree with same key as new node. */
 
929
            return null();
 
930
        cmp = cmp_n_n(new_node, h);
 
931
        if (cmp == 0)
 
932
            /* Found the node to substitute new one for. */
 
933
            break;
 
934
        last_cmp = cmp;
 
935
        parent = h;
 
936
        h = cmp < 0 ? get_lt(h) : get_gt(h);
 
937
    }
 
938
 
 
939
    /* Copy tree housekeeping fields from node in tree to new node. */
 
940
    set_lt(new_node, get_lt(h));
 
941
    set_gt(new_node, get_gt(h));
 
942
    set_bf(new_node, get_bf(h));
 
943
 
 
944
    if (parent == null())
 
945
        /* New node is also new root. */
 
946
        abs.root = new_node;
 
947
    else {
 
948
        /* Make parent point to new node. */
 
949
        if (last_cmp < 0)
 
950
            set_lt(parent, new_node);
 
951
        else
 
952
            set_gt(parent, new_node);
 
953
    }
 
954
 
 
955
    return h;
 
956
}
 
957
 
 
958
}
 
959
 
 
960
#endif