head	1.2;
access;
symbols
	perseant-exfatfs-base-20250801:1.2
	perseant-exfatfs-base-20240630:1.2
	cjep_sun2x:1.2.0.44
	cjep_sun2x-base:1.2
	cjep_staticlib_x-base1:1.2
	cjep_staticlib_x:1.2.0.42
	cjep_staticlib_x-base:1.2
	phil-wifi-20200421:1.2
	phil-wifi-20200411:1.2
	phil-wifi-20200406:1.2
	pgoyette-compat-merge-20190127:1.2
	pgoyette-compat-20190127:1.2
	pgoyette-compat-20190118:1.2
	pgoyette-compat-1226:1.2
	pgoyette-compat-1126:1.2
	pgoyette-compat-1020:1.2
	pgoyette-compat-0930:1.2
	pgoyette-compat-0906:1.2
	pgoyette-compat-0728:1.2
	pgoyette-compat-0625:1.2
	pgoyette-compat-0521:1.2
	pgoyette-compat-0502:1.2
	pgoyette-compat-0422:1.2
	pgoyette-compat-0415:1.2
	pgoyette-compat-0407:1.2
	pgoyette-compat-0330:1.2
	pgoyette-compat-0322:1.2
	pgoyette-compat-0315:1.2
	pgoyette-compat:1.2.0.40
	pgoyette-compat-base:1.2
	perseant-stdc-iso10646:1.2.0.38
	perseant-stdc-iso10646-base:1.2
	prg-localcount2-base3:1.2
	prg-localcount2-base2:1.2
	prg-localcount2-base1:1.2
	prg-localcount2:1.2.0.36
	prg-localcount2-base:1.2
	pgoyette-localcount-20170426:1.2
	bouyer-socketcan-base1:1.2
	pgoyette-localcount-20170320:1.2
	bouyer-socketcan:1.2.0.34
	bouyer-socketcan-base:1.2
	pgoyette-localcount-20170107:1.2
	pgoyette-localcount-20161104:1.2
	localcount-20160914:1.2
	pgoyette-localcount-20160806:1.2
	pgoyette-localcount-20160726:1.2
	pgoyette-localcount:1.2.0.32
	pgoyette-localcount-base:1.2
	netbsd-5-2-3-RELEASE:1.2
	netbsd-5-1-5-RELEASE:1.2
	yamt-pagecache-base9:1.2
	yamt-pagecache-tag8:1.2
	tls-earlyentropy:1.2.0.28
	tls-earlyentropy-base:1.2
	riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.2
	riastradh-drm2-base3:1.2
	netbsd-5-2-2-RELEASE:1.2
	netbsd-5-1-4-RELEASE:1.2
	netbsd-5-2-1-RELEASE:1.2
	netbsd-5-1-3-RELEASE:1.2
	agc-symver:1.2.0.30
	agc-symver-base:1.2
	tls-maxphys-base:1.2
	yamt-pagecache-base8:1.2
	netbsd-5-2:1.2.0.26
	yamt-pagecache-base7:1.2
	netbsd-5-2-RELEASE:1.2
	netbsd-5-2-RC1:1.2
	yamt-pagecache-base6:1.2
	yamt-pagecache-base5:1.2
	yamt-pagecache-base4:1.2
	netbsd-5-1-2-RELEASE:1.2
	netbsd-5-1-1-RELEASE:1.2
	yamt-pagecache-base3:1.2
	yamt-pagecache-base2:1.2
	yamt-pagecache:1.2.0.24
	yamt-pagecache-base:1.2
	bouyer-quota2-nbase:1.2
	bouyer-quota2:1.2.0.22
	bouyer-quota2-base:1.2
	matt-nb5-pq3:1.2.0.20
	matt-nb5-pq3-base:1.2
	netbsd-5-1:1.2.0.18
	netbsd-5-1-RELEASE:1.2
	netbsd-5-1-RC4:1.2
	netbsd-5-1-RC3:1.2
	netbsd-5-1-RC2:1.2
	netbsd-5-1-RC1:1.2
	netbsd-5-0-2-RELEASE:1.2
	netbsd-5-0-1-RELEASE:1.2
	jym-xensuspend-nbase:1.2
	netbsd-5-0:1.2.0.16
	netbsd-5-0-RELEASE:1.2
	netbsd-5-0-RC4:1.2
	netbsd-5-0-RC3:1.2
	netbsd-5-0-RC2:1.2
	jym-xensuspend:1.2.0.14
	jym-xensuspend-base:1.2
	netbsd-5-0-RC1:1.2
	netbsd-5:1.2.0.12
	netbsd-5-base:1.2
	mjf-devfs2:1.2.0.10
	mjf-devfs2-base:1.2
	yamt-pf42-base4:1.2
	yamt-pf42-base3:1.2
	hpcarm-cleanup-nbase:1.2
	yamt-pf42-base2:1.2
	yamt-pf42:1.2.0.8
	yamt-pf42-base:1.2
	keiichi-mipv6:1.2.0.6
	keiichi-mipv6-base:1.2
	cube-autoconf:1.2.0.4
	cube-autoconf-base:1.2
	hpcarm-cleanup:1.2.0.2
	hpcarm-cleanup-base:1.2
	netbsd-1-3-PATCH003:1.1.1.1
	netbsd-1-3-PATCH003-CANDIDATE2:1.1.1.1
	netbsd-1-3-PATCH003-CANDIDATE1:1.1.1.1
	netbsd-1-3-PATCH003-CANDIDATE0:1.1.1.1
	netbsd-1-3-PATCH002:1.1.1.1
	netbsd-1-3-PATCH001:1.1.1.1
	netbsd-1-3-RELEASE:1.1.1.1
	netbsd-1-3-BETA:1.1.1.1
	netbsd-1-3:1.1.1.1.0.2
	netbsd-1-3-base:1.1.1.1
	netbsd-1-2-PATCH001:1.1.1.1
	libg++-2-7-2:1.1.1.1
	netbsd-1-2-RELEASE:1.1.1.1
	netbsd-1-2-BETA:1.1.1.1
	netbsd-1-2-base:1.1.1.1
	netbsd-1-2:1.1.1.1.0.4
	libg++-2-7-1:1.1.1.1
	FSF:1.1.1;
locks; strict;
comment	@# @;


1.2
date	98.12.12.23.50.47;	author tv;	state dead;
branches;
next	1.1;

1.1
date	96.03.09.00.00.59;	author phil;	state Exp;
branches
	1.1.1.1;
next	;

1.1.1.1
date	96.03.09.00.00.59;	author phil;	state Exp;
branches;
next	;


desc
@@


1.2
log
@GC old gcc 2.7.2.2.
@
text
@// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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;
  for (;;)
  {
    int comp = <T>CMP(t->item, item);
    if (comp == 0)
      return Pix(t);
    else if (comp > 0)
      t = t->lt;
    else
      t = t->rt;
    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;
  }
}


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;
}
@


1.1
log
@Initial revision
@
text
@@


1.1.1.1
log
@Import of libg++-2.7.1.
@
text
@@