home *** CD-ROM | disk | FTP | other *** search
- // This may look like C code, but it is really -*- C++ -*-
- /*
- Copyright (C) 1988 Free Software Foundation
- written by Doug Lea (dl@rocky.oswego.edu)
-
- This file is part of GNU CC.
-
- GNU CC is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY. No author or distributor
- accepts responsibility to anyone for the consequences of using it
- or for whether it serves any particular purpose or works at all,
- unless he says so in writing. Refer to the GNU CC General Public
- License for full details.
-
- Everyone is granted permission to copy, modify and redistribute
- GNU CC, but only under the conditions described in the
- GNU CC General Public License. A copy of this license is
- supposed to have been given to you along with GNU CC so you
- can know your rights and responsibilities. It should be in a
- file named COPYING. Among other things, the copyright notice
- and this notice must be preserved on all copies.
- */
-
- #include <stream.h>
- #include <assert.h>
- #include "<T><U>AVLAssoc.h"
-
-
- // error handling
-
-
- void default_<T><U>AVLAssoc_error_handler(char* msg)
- {
- cerr << "Fatal <T><U>AVLAssoc error. " << msg << "\n";
- exit(1);
- }
-
- one_arg_error_handler_t <T><U>AVLAssoc_error_handler = default_<T><U>AVLAssoc_error_handler;
-
- one_arg_error_handler_t set_<T><U>AVLAssoc_error_handler(one_arg_error_handler_t f)
- {
- one_arg_error_handler_t old = <T><U>AVLAssoc_error_handler;
- <T><U>AVLAssoc_error_handler = f;
- return old;
- }
-
- void <T><U>AVLAssoc::error(const char* msg)
- {
- (*<T><U>AVLAssoc_error_handler)(msg);
- }
-
-
- /*
- constants & inlines for maintaining balance & thread status in tree nodes
- */
-
- #define AVLBALANCEMASK 3
- #define AVLBALANCED 0
- #define AVLLEFTHEAVY 1
- #define AVLRIGHTHEAVY 2
-
- #define LTHREADBIT 4
- #define RTHREADBIT 8
-
-
- static inline int bf(<T><U>AVLAssocNode* t)
- {
- return t->stat & AVLBALANCEMASK;
- }
-
- static inline void set_bf(<T><U>AVLAssocNode* t, int b)
- {
- t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
- }
-
-
- static inline int rthread(<T><U>AVLAssocNode* t)
- {
- return t->stat & RTHREADBIT;
- }
-
- static inline void set_rthread(<T><U>AVLAssocNode* t, int b)
- {
- if (b)
- t->stat |= RTHREADBIT;
- else
- t->stat &= ~RTHREADBIT;
- }
-
- static inline int lthread(<T><U>AVLAssocNode* t)
- {
- return t->stat & LTHREADBIT;
- }
-
- static inline void set_lthread(<T><U>AVLAssocNode* t, int b)
- {
- if (b)
- t->stat |= LTHREADBIT;
- else
- t->stat &= ~LTHREADBIT;
- }
-
- /*
- traversal primitives
- */
-
-
- <T><U>AVLAssocNode* <T><U>AVLAssoc::leftmost()
- {
- <T><U>AVLAssocNode* t = root;
- if (t != 0) while (t->lt != 0) t = t->lt;
- return t;
- }
-
- <T><U>AVLAssocNode* <T><U>AVLAssoc::rightmost()
- {
- <T><U>AVLAssocNode* t = root;
- if (t != 0) while (t->rt != 0) t = t->rt;
- return t;
- }
-
- <T><U>AVLAssocNode* <T><U>AVLAssoc::succ(<T><U>AVLAssocNode* t)
- {
- <T><U>AVLAssocNode* r = t->rt;
- if (!rthread(t)) while (!lthread(r)) r = r->lt;
- return r;
- }
-
- <T><U>AVLAssocNode* <T><U>AVLAssoc::pred(<T><U>AVLAssocNode* t)
- {
- <T><U>AVLAssocNode* l = t->lt;
- if (!lthread(t)) while (!rthread(l)) l = l->rt;
- return l;
- }
-
-
- int <T><U>AVLAssoc::contains(<T&> key)
- {
- <T><U>AVLAssocNode* t = root;
- if (t == 0)
- return 0;
- for (;;)
- {
- int comp = key_key_cmp(key, t->key);
- if (comp == 0)
- return 1;
- else if (comp < 0)
- {
- if (lthread(t))
- return 0;
- else
- t = t->lt;
- }
- else if (rthread(t))
- return 0;
- else
- t = t->rt;
- }
- }
-
-
- /*
- The combination of threads and AVL bits make adding & deleting
- interesting, but very awkward.
-
- We use the following statics to avoid passing them around recursively
- */
-
- static int _need_rebalancing; // to send back balance info from rec. calls
- static <T>* _target_item; // add/del target
- static <T><U>AVLAssocNode* _target_node; // found or inserted node
- static <T><U>AVLAssocNode* _mark_for_deletion; // must put off
- // actualling killing
- // deleted nodes in _del
- static <T><U>AVLAssocNode** _hold_nodes; // used for rebuilding trees
- static int _max_hold_index; // # elements-1 in _hold_nodes
-
- void <T><U>AVLAssoc:: _add(<T><U>AVLAssocNode*& t)
- {
- int cmp = key_key_cmp(*_target_item, t->key);
- if (cmp == 0)
- {
- _target_node = t;
- return;
- }
- else if (cmp < 0)
- {
- if (lthread(t))
- {
- ++cnt;
- <T><U>AVLAssocNode* q = new <T><U>AVLAssocNode(*_target_item);
- set_lthread(q, 1);
- set_rthread(q, 1);
- q->lt = t->lt;
- q->rt = t;
- t->lt = q;
- set_lthread(t, 0);
- _target_node = q;
- _need_rebalancing = 1;
- }
- else
- _add(t->lt);
- if (_need_rebalancing)
- {
- switch(bf(t))
- {
- case AVLRIGHTHEAVY:
- set_bf(t, AVLBALANCED);
- _need_rebalancing = 0;
- return;
- case AVLBALANCED:
- set_bf(t, AVLLEFTHEAVY);
- return;
- case AVLLEFTHEAVY:
- <T><U>AVLAssocNode* l = t->lt;
- if (bf(l) == AVLLEFTHEAVY)
- {
- if (rthread(l))
- t->lt = l;
- else
- t->lt = l->rt;
- set_lthread(t, rthread(l));
- l->rt = t;
- set_rthread(l, 0);
- set_bf(t, AVLBALANCED);
- set_bf(l, AVLBALANCED);
- t = l;
- _need_rebalancing = 0;
- }
- else
- {
- <T><U>AVLAssocNode* r = l->rt;
- set_rthread(l, lthread(r));
- if (lthread(r))
- l->rt = r;
- else
- l->rt = r->lt;
- r->lt = l;
- set_lthread(r, 0);
- set_lthread(t, rthread(r));
- if (rthread(r))
- t->lt = r;
- else
- t->lt = r->rt;
- r->rt = t;
- set_rthread(r, 0);
- if (bf(r) == AVLLEFTHEAVY)
- set_bf(t, AVLRIGHTHEAVY);
- else
- set_bf(t, AVLBALANCED);
- if (bf(r) == AVLRIGHTHEAVY)
- set_bf(l, AVLLEFTHEAVY);
- else
- set_bf(l, AVLBALANCED);
- set_bf(r, AVLBALANCED);
- t = r;
- _need_rebalancing = 0;
- return;
- }
- }
- }
- }
- else
- {
- if (rthread(t))
- {
- ++cnt;
- <T><U>AVLAssocNode* q = new <T><U>AVLAssocNode(*_target_item);
- set_rthread(t, 0);
- set_lthread(q, 1);
- set_rthread(q, 1);
- q->lt = t;
- q->rt = t->rt;
- t->rt = q;
- _target_node = q;
- _need_rebalancing = 1;
- }
- else
- _add(t->rt);
- if (_need_rebalancing)
- {
- switch(bf(t))
- {
- case AVLLEFTHEAVY:
- set_bf(t, AVLBALANCED);
- _need_rebalancing = 0;
- return;
- case AVLBALANCED:
- set_bf(t, AVLRIGHTHEAVY);
- return;
- case AVLRIGHTHEAVY:
- <T><U>AVLAssocNode* r = t->rt;
- if (bf(r) == AVLRIGHTHEAVY)
- {
- if (lthread(r))
- t->rt = r;
- else
- t->rt = r->lt;
- set_rthread(t, lthread(r));
- r->lt = t;
- set_lthread(r, 0);
- set_bf(t, AVLBALANCED);
- set_bf(r, AVLBALANCED);
- t = r;
- _need_rebalancing = 0;
- }
- else
- {
- <T><U>AVLAssocNode* l = r->lt;
- set_lthread(r, rthread(l));
- if (rthread(l))
- r->lt = l;
- else
- r->lt = l->rt;
- l->rt = r;
- set_rthread(l, 0);
- set_rthread(t, lthread(l));
- if (lthread(l))
- t->rt = l;
- else
- t->rt = l->lt;
- l->lt = t;
- set_lthread(l, 0);
- if (bf(l) == AVLRIGHTHEAVY)
- set_bf(t, AVLLEFTHEAVY);
- else
- set_bf(t, AVLBALANCED);
- if (bf(l) == AVLLEFTHEAVY)
- set_bf(r, AVLRIGHTHEAVY);
- else
- set_bf(r, AVLBALANCED);
- set_bf(l, AVLBALANCED);
- t = l;
- _need_rebalancing = 0;
- return;
- }
- }
- }
- }
- }
-
- <U>& <T><U>AVLAssoc::operator [] (<T&> item)
- {
- if (root == 0)
- {
- ++cnt;
- root = new <T><U>AVLAssocNode(item);
- set_rthread(root, 1);
- set_lthread(root, 1);
- return root->cont;
- }
- else
- {
- _target_item = &item;
- _need_rebalancing = 0;
- _add(root);
- return _target_node->cont;
- }
- }
-
-
- void <T><U>AVLAssoc::_del(<T><U>AVLAssocNode* par, <T><U>AVLAssocNode*& t)
- {
- int comp = key_key_cmp(*_target_item, t->key);
- if (comp == 0)
- {
- if (lthread(t) && rthread(t))
- {
- _mark_for_deletion = t;
- if (t == par->lt)
- {
- set_lthread(par, 1);
- par->lt = t->lt;
- }
- else
- {
- set_rthread(par, 1);
- par->rt = t->rt;
- }
- _need_rebalancing = 1;
- return;
- }
- else if (lthread(t))
- {
- _mark_for_deletion = t;
- <T><U>AVLAssocNode* s = succ(t);
- if (s != 0 && lthread(s))
- s->lt = t->lt;
- t = t->rt;
- _need_rebalancing = 1;
- return;
- }
- else if (rthread(t))
- {
- _mark_for_deletion = t;
- <T><U>AVLAssocNode* p = pred(t);
- if (p != 0 && rthread(p))
- p->rt = t->rt;
- t = t->lt;
- _need_rebalancing = 1;
- return;
- }
- else // replace item & find someone deletable
- {
- <T><U>AVLAssocNode* p = pred(t);
- t->key = p->key;
- t->cont = p->cont;
- _target_item = &p->key;
- comp = -1; // fall through below to left
- }
- }
-
- if (comp < 0)
- {
- if (lthread(t))
- return;
- _del(t, t->lt);
- if (!_need_rebalancing)
- return;
- switch (bf(t))
- {
- case AVLLEFTHEAVY:
- set_bf(t, AVLBALANCED);
- return;
- case AVLBALANCED:
- set_bf(t, AVLRIGHTHEAVY);
- _need_rebalancing = 0;
- return;
- case AVLRIGHTHEAVY:
- <T><U>AVLAssocNode* r = t->rt;
- switch (bf(r))
- {
- case AVLBALANCED:
- if (lthread(r))
- t->rt = r;
- else
- t->rt = r->lt;
- set_rthread(t, lthread(r));
- r->lt = t;
- set_lthread(r, 0);
- set_bf(t, AVLRIGHTHEAVY);
- set_bf(r, AVLLEFTHEAVY);
- _need_rebalancing = 0;
- t = r;
- return;
- case AVLRIGHTHEAVY:
- if (lthread(r))
- t->rt = r;
- else
- t->rt = r->lt;
- set_rthread(t, lthread(r));
- r->lt = t;
- set_lthread(r, 0);
- set_bf(t, AVLBALANCED);
- set_bf(r, AVLBALANCED);
- t = r;
- return;
- case AVLLEFTHEAVY:
- <T><U>AVLAssocNode* l = r->lt;
- set_lthread(r, rthread(l));
- if (rthread(l))
- r->lt = l;
- else
- r->lt = l->rt;
- l->rt = r;
- set_rthread(l, 0);
- set_rthread(t, lthread(l));
- if (lthread(l))
- t->rt = l;
- else
- t->rt = l->lt;
- l->lt = t;
- set_lthread(l, 0);
- if (bf(l) == AVLRIGHTHEAVY)
- set_bf(t, AVLLEFTHEAVY);
- else
- set_bf(t, AVLBALANCED);
- if (bf(l) == AVLLEFTHEAVY)
- set_bf(r, AVLRIGHTHEAVY);
- else
- set_bf(r, AVLBALANCED);
- set_bf(l, AVLBALANCED);
- t = l;
- return;
- }
- }
- }
- else
- {
- if (rthread(t))
- return;
- _del(t, t->rt);
- if (!_need_rebalancing)
- return;
- switch (bf(t))
- {
- case AVLRIGHTHEAVY:
- set_bf(t, AVLBALANCED);
- return;
- case AVLBALANCED:
- set_bf(t, AVLLEFTHEAVY);
- _need_rebalancing = 0;
- return;
- case AVLLEFTHEAVY:
- <T><U>AVLAssocNode* l = t->lt;
- switch (bf(l))
- {
- case AVLBALANCED:
- if (rthread(l))
- t->lt = l;
- else
- t->lt = l->rt;
- set_lthread(t, rthread(l));
- l->rt = t;
- set_rthread(l, 0);
- set_bf(t, AVLLEFTHEAVY);
- set_bf(l, AVLRIGHTHEAVY);
- _need_rebalancing = 0;
- t = l;
- return;
- case AVLLEFTHEAVY:
- if (rthread(l))
- t->lt = l;
- else
- t->lt = l->rt;
- set_lthread(t, rthread(l));
- l->rt = t;
- set_rthread(l, 0);
- set_bf(t, AVLBALANCED);
- set_bf(l, AVLBALANCED);
- t = l;
- return;
- case AVLRIGHTHEAVY:
- <T><U>AVLAssocNode* r = l->rt;
- set_rthread(l, lthread(r));
- if (lthread(r))
- l->rt = r;
- else
- l->rt = r->lt;
- r->lt = l;
- set_lthread(r, 0);
- set_lthread(t, rthread(r));
- if (rthread(r))
- t->lt = r;
- else
- t->lt = r->rt;
- r->rt = t;
- set_rthread(r, 0);
- if (bf(r) == AVLLEFTHEAVY)
- set_bf(t, AVLRIGHTHEAVY);
- else
- set_bf(t, AVLBALANCED);
- if (bf(r) == AVLRIGHTHEAVY)
- set_bf(l, AVLLEFTHEAVY);
- else
- set_bf(l, AVLBALANCED);
- set_bf(r, AVLBALANCED);
- t = r;
- return;
- }
- }
- }
- }
-
-
- int <T><U>AVLAssoc::del(<T&> key)
- {
- _need_rebalancing = 0;
- _mark_for_deletion = 0;
- _target_item = &key;
- _del(root, root);
- if (_mark_for_deletion)
- {
- delete(_mark_for_deletion);
- --cnt;
- return 1;
- }
- else
- return 0;
- }
-
- // build an ordered array of pointers to tree nodes back into a tree
- // we know that at least one element exists
-
- static <T><U>AVLAssocNode* _do_treeify(int lo, int hi, int& h)
- {
- int lh, rh;
- int mid = (lo + hi) / 2;
- <T><U>AVLAssocNode* t = _hold_nodes[mid];
- if (lo > mid - 1)
- {
- set_lthread(t, 1);
- if (mid == 0)
- t->lt = 0;
- else
- t->lt = _hold_nodes[mid-1];
- lh = 0;
- }
- else
- {
- set_lthread(t, 0);
- t->lt = _do_treeify(lo, mid-1, lh);
- }
- if (hi < mid + 1)
- {
- set_rthread(t, 1);
- if (mid == _max_hold_index)
- t->rt = 0;
- else
- t->rt = _hold_nodes[mid+1];
- rh = 0;
- }
- else
- {
- set_rthread(t, 0);
- t->rt = _do_treeify(mid+1, hi, rh);
- }
- if (lh == rh)
- {
- set_bf(t, AVLBALANCED);
- h = lh + 1;
- }
- else if (lh == rh - 1)
- {
- set_bf(t, AVLRIGHTHEAVY);
- h = rh + 1;
- }
- else if (rh == lh - 1)
- {
- set_bf(t, AVLLEFTHEAVY);
- h = lh + 1;
- }
- else // can't happen
- abort();
-
- return t;
- }
-
- static <T><U>AVLAssocNode* _treeify(int n)
- {
- <T><U>AVLAssocNode* t;
- if (n == 0)
- t = 0;
- else
- {
- int b;
- _max_hold_index = n-1;
- t = _do_treeify(0, _max_hold_index, b);
- }
- delete _hold_nodes;
- return t;
- }
-
-
- void <T><U>AVLAssoc::_kill(<T><U>AVLAssocNode* t)
- {
- if (t != 0)
- {
- if (!lthread(t)) _kill(t->lt);
- if (!rthread(t)) _kill(t->rt);
- delete t;
- }
- }
-
-
- <T><U>AVLAssoc::<T><U>AVLAssoc(<T><U>AVLAssoc& b)
- {
- if ((cnt = b.cnt) == 0)
- {
- root = 0;
- }
- else
- {
- _hold_nodes = new <T><U>AVLAssocNodePtr [cnt];
- <T><U>AVLAssocNode* t = b.leftmost();
- int i = 0;
- while (t != 0)
- {
- _hold_nodes[i++] = new <T><U>AVLAssocNode(t->key, t->cont);
- t = b.succ(t);
- }
- root = _treeify(cnt);
- }
- }
-
- <T><U>AVLAssoc& <T><U>AVLAssoc:: operator = (<T><U>AVLAssoc& b)
- {
- if (b.root != root)
- {
- clear();
- if ((cnt = b.cnt) == 0)
- root = 0;
- else
- {
- _hold_nodes = new <T><U>AVLAssocNodePtr [cnt];
- <T><U>AVLAssocNode* t = b.leftmost();
- int i = 0;
- while (t != 0)
- {
- _hold_nodes[i++] = new <T><U>AVLAssocNode(t->key, t->cont);
- t = b.succ(t);
- }
- root = _treeify(cnt);
- }
- }
- }
-
-