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 "<T>.BSTSet.h"
-
-
- /*
- traversal primitives
- */
-
-
- <T>BSTNode* <T>BSTSet::leftmost()
- {
- <T>BSTNode* t = root;
- if (t != 0) while (t->lt != 0) t = t->lt;
- return t;
- }
-
- <T>BSTNode* <T>BSTSet::rightmost()
- {
- <T>BSTNode* t = root;
- if (t != 0) while (t->rt != 0) t = t->rt;
- return t;
- }
-
- <T>BSTNode* <T>BSTSet::succ(<T>BSTNode* t)
- {
- if (t == 0)
- return 0;
- if (t->rt != 0)
- {
- t = t->rt;
- while (t->lt != 0) t = t->lt;
- return t;
- }
- else
- {
- for (;;)
- {
- if (t->par == 0 || t == t->par->lt)
- return t->par;
- else
- t = t->par;
- }
- }
- }
-
- <T>BSTNode* <T>BSTSet::pred(<T>BSTNode* t)
- {
- if (t == 0)
- return 0;
- else if (t->lt != 0)
- {
- t = t->lt;
- while (t->rt != 0) t = t->rt;
- return t;
- }
- else
- {
- for (;;)
- {
- if (t->par == 0 || t == t->par->rt)
- return t->par;
- else
- t = t->par;
- }
- }
- }
-
-
- Pix <T>BSTSet::seek(<T&> key)
- {
- <T>BSTNode* t = root;
- for (;;)
- {
- if (t == 0)
- return 0;
- int comp = <T>CMP(key, t->item);
- if (comp == 0)
- return Pix(t);
- else if (comp < 0)
- t = t->lt;
- else
- t = t->rt;
- }
- }
-
-
- Pix <T>BSTSet::add(<T&> item)
- {
- if (root == 0)
- {
- ++count;
- root = new <T>BSTNode(item);
- return Pix(root);
- }
-
- <T>BSTNode* t = root;
- <T>BSTNode* p = root;
- int comp;
- for (;;)
- {
- if (t == 0)
- {
- ++count;
- t = new <T>BSTNode(item);
- if (comp > 0)
- p->lt = t;
- else
- p->rt = t;
- t->par = p;
- return Pix(t);
- }
- p = t;
- comp = <T>CMP(t->item, item);
- if (comp == 0)
- return Pix(t);
- else if (comp > 0)
- t = t->lt;
- else
- t = t->rt;
- }
- }
-
-
- void <T>BSTSet::del(<T&> key)
- {
- <T>BSTNode* t = root;
- <T>BSTNode* p = root;
- int comp;
- for (;;)
- {
- if (t == 0)
- return;
- comp = <T>CMP(key, t->item);
- if (comp == 0)
- {
- --count;
- <T>BSTNode* repl;
- if (t->lt == 0)
- repl = t->rt;
- else if (t->rt == 0)
- repl = t->lt;
- else
- {
- <T>BSTNode* prepl = t;
- repl = t->lt;
- while (repl->rt != 0)
- {
- prepl = repl;
- repl = repl->rt;
- }
- if (prepl != t)
- {
- prepl->rt = repl->lt;
- if (prepl->rt != 0) prepl->rt->par = prepl;
- repl->lt = t->lt;
- if (repl->lt != 0) repl->lt->par = repl;
- }
- repl->rt = t->rt;
- if (repl->rt != 0) repl->rt->par = repl;
- }
- if (t == root)
- {
- root = repl;
- if (repl != 0) repl->par = 0;
- }
- else
- {
- if (t == p->lt)
- p->lt = repl;
- else
- p->rt = repl;
- if (repl != 0) repl->par = p;
- }
- delete t;
- return;
- }
- p = t;
- if (comp < 0)
- t = t->lt;
- else
- t = t->rt;
- }
- }
-
-
- void <T>BSTSet::_kill(<T>BSTNode* t)
- {
- if (t != 0)
- {
- _kill(t->lt);
- _kill(t->rt);
- delete t;
- }
- }
-
- <T>BSTNode* <T>BSTSet::_copy(<T>BSTNode* t)
- {
- if (t == 0)
- return 0;
- else
- {
- <T>BSTNode* u = new <T>BSTNode(t->item, _copy(t->lt), _copy(t->rt));
- if (u->lt != 0) u->lt->par = u;
- if (u->rt != 0) u->rt->par = u;
- return u;
- }
- }
-
-
- int <T>BSTSet::operator == (<T>BSTSet& y)
- {
- if (count != y.count)
- return 0;
- else
- {
- <T>BSTNode* t = leftmost();
- <T>BSTNode* u = y.leftmost();
- for (;;)
- {
- if (t == 0)
- return 1;
- else if (!<T>EQ(t->item, u->item))
- return 0;
- else
- {
- t = succ(t);
- u = y.succ(u);
- }
- }
- }
- }
-
- int <T>BSTSet::operator <= (<T>BSTSet& y)
- {
- if (count > y.count)
- return 0;
- else
- {
- <T>BSTNode* t = leftmost();
- <T>BSTNode* u = y.leftmost();
- for (;;)
- {
- if (t == 0)
- return 1;
- else if (u == 0)
- return 0;
- int cmp = <T>CMP(t->item, u->item);
- if (cmp == 0)
- {
- t = succ(t);
- u = y.succ(u);
- }
- else if (cmp < 0)
- return 0;
- else
- u = y.succ(u);
- }
- }
- }
-
-
- int <T>BSTSet::OK()
- {
- int v = 1;
- if (root == 0)
- v = count == 0;
- else
- {
- int n = 1;
- <T>BSTNode* trail = leftmost();
- <T>BSTNode* t = succ(trail);
- while (t != 0)
- {
- ++n;
- v &= <T>CMP(trail->item, t->item) < 0;
- trail = t;
- t = succ(t);
- }
- v &= n == count;
- }
- if (!v) error("invariant failure");
- return v;
- }
-