home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
NeXTSTEP 3.2 (Developer)
/
NS_dev_3.2.iso
/
NextDeveloper
/
Headers
/
g++
/
gen
/
BSTSet.ccP
< prev
next >
Wrap
Text File
|
1993-06-29
|
7KB
|
379 lines
// 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 the GNU C++ Library. This library is free
software; you can redistribute it and/or modify it under the terms of
the GNU Library General Public License as published by the Free
Software Foundation; either version 2 of the License, or (at your
option) any later version. This library is distributed in the hope
that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
PURPOSE. See the GNU Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifdef __GNUG__
#pragma implementation
#endif
#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);
}
}
}
// linear-time, zero space overhead binary tree rebalancing from
// Stout & Warren, ``Tree rebalancing in linear space and time''
// CACM, Sept, 1986, p902.
void <T>BSTSet::balance()
{
if (count <= 2) return; // don't bother --
// also we assume non-null root, below
// make re-attaching the root easy via trickery
struct _fake_node { _fake_node *lt, *rt, *par; } fake_root;
fake_root.rt = (_fake_node*)root;
fake_root.par = 0;
<T>BSTNode* pseudo_root = (<T>BSTNode*)&fake_root;
// phase 1: tree-to-vine
<T>BSTNode* vine_tail = pseudo_root;
<T>BSTNode* remainder = root;
while (remainder != 0)
{
if (remainder->lt == 0)
{
vine_tail = remainder;
remainder = remainder->rt;
}
else
{
<T>BSTNode* tmp = remainder->lt;
remainder->lt = tmp->rt;
if (remainder->lt != 0) remainder->lt->par = remainder;
tmp->rt = remainder;
remainder->par = tmp;
vine_tail->rt = remainder = tmp;
}
}
// phase 2: vine-to-tree
// Uses the slightly simpler version adapted from
// Day ``Balancing a binary tree'' Computer Journal, Nov. 1976,
// since it's not generally important whether the `stray' leaves are
// on the left or on the right.
unsigned int spines = count - 1;
while (spines > 1)
{
int compressions = spines >> 1; // compress every other node
spines -= compressions + 1; // halve for next time
<T>BSTNode* scanner = pseudo_root;
while (compressions-- > 0)
{
<T>BSTNode* child = scanner->rt;
<T>BSTNode* grandchild = child->rt;
scanner->rt = grandchild;
grandchild->par = scanner;
child->rt = grandchild->lt;
if (child->rt != 0) child->rt->par = child;
grandchild->lt = child;
child->par = grandchild;
scanner = grandchild;
}
}
root = pseudo_root->rt;
root->par = 0;
}
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;
}