source: trunk/src/emx/include/Attic/cpp/gen/SplayPQ.ccP@ 18

// This may look like C code, but it is really -*- C++ -*-
/* 
Copyright (C) 1988 Free Software Foundation
    written by Doug Lea ([email protected])

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>.SplayPQ.h"


/* 

 struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
 splay tree algorithms

 All routines use a version of their `simple top-down' splay alg. (p 669)

*/

struct _dummySplayNode
{
  <T>SplayNode*    lt;
  <T>SplayNode*    rt;
  <T>SplayNode*    par;
} _dummy_null;


/*
 traversal primitives
*/


<T>SplayNode* <T>SplayPQ::leftmost()
{
  <T>SplayNode* t = root;
  if (t != 0) while (t->lt != 0) t = t->lt;
  return t;
}

<T>SplayNode* <T>SplayPQ::rightmost()
{
  <T>SplayNode* t = root;
  if (t != 0) while (t->rt != 0) t = t->rt;
  return t;
}

<T>SplayNode* <T>SplayPQ::succ(<T>SplayNode* 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>SplayNode* <T>SplayPQ::pred(<T>SplayNode* 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>SplayPQ::seek(<T&> key)
{
  <T>SplayNode* t = root;
  if (t == 0)
    return 0;

  int comp = <T>CMP(key, t->item);
  if (comp == 0)
    return Pix(t);

  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  <T>SplayNode* l = dummy;
  <T>SplayNode* r = dummy;
  dummy->rt = dummy->lt = dummy->par = 0;

  while (comp != 0)
  {
    if (comp > 0)
    {
      <T>SplayNode* tr = t->rt;
      if (tr == 0)
        break;
      else
      {
        comp = <T>CMP(key, tr->item);
        if (comp <= 0 || tr->rt == 0)
        {
          l->rt = t; t->par = l;
          l = t;
          t = tr;
          if (comp >= 0)
            break;
        }
        else
        {
          if ((t->rt = tr->lt) != 0) t->rt->par = t;
          tr->lt = t; t->par = tr;
          l->rt = tr; tr->par = l;
          l = tr;
          t = tr->rt;
          comp = <T>CMP(key, t->item);
        }
      }
    }
    else
    {
      <T>SplayNode* tl = t->lt;
      if (tl == 0)
        break;
      else
      {
        comp = <T>CMP(key, tl->item);
        if (comp >= 0 || tl->lt == 0)
        {
          r->lt = t; t->par = r;
          r = t;
          t = tl;
          if (comp <= 0)
            break;
        }
        else
        {
          if ((t->lt = tl->rt) != 0) t->lt->par = t;
          tl->rt = t; t->par = tl;
          r->lt = tl; tl->par = r;
          r = tl;
          t = tl->lt;
          comp = <T>CMP(key, t->item);
        }
      }
    }
  }
  if ((r->lt = t->rt) != 0) r->lt->par = r;
  if ((l->rt = t->lt) != 0) l->rt->par = l;
  if ((t->lt = dummy->rt) != 0) t->lt->par = t;
  if ((t->rt = dummy->lt) != 0) t->rt->par = t;
  t->par = 0;
  root = t;
  return (comp == 0) ? Pix(t) : 0;
}


Pix <T>SplayPQ::enq(<T&> item)
{
  ++count;
  <T>SplayNode* newnode = new <T>SplayNode(item);
  <T>SplayNode* t = root;
  if (t == 0)
  {
    root = newnode;
    return Pix(root);
  }

  int comp = <T>CMP(item, t->item);

  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
  <T>SplayNode* l = dummy;
  <T>SplayNode* r = dummy;
  dummy->rt = dummy->lt = dummy->par = 0;
  
  int done = 0;