// 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.
struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
All routines use a version of their `simple top-down' splay alg. (p 669)
<T>SplayNode* <T>SplayPQ::leftmost()
if (t != 0) while (t->lt != 0) t = t->lt;
<T>SplayNode* <T>SplayPQ::rightmost()
if (t != 0) while (t->rt != 0) t = t->rt;
<T>SplayNode* <T>SplayPQ::succ(<T>SplayNode* t)
while (t->lt != 0) t = t->lt;
if (t->par == 0 || t == t->par->lt)
<T>SplayNode* <T>SplayPQ::pred(<T>SplayNode* t)
while (t->rt != 0) t = t->rt;
if (t->par == 0 || t == t->par->rt)
Pix <T>SplayPQ::seek(<T&> key)
int comp = <T>CMP(key, t->item);
<T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
dummy->rt = dummy->lt = dummy->par = 0;
<T>SplayNode* tr = t->rt;
comp = <T>CMP(key, tr->item);
if (comp <= 0 || tr->rt == 0)
if ((t->rt = tr->lt) != 0) t->rt->par = t;
comp = <T>CMP(key, t->item);
<T>SplayNode* tl = t->lt;
comp = <T>CMP(key, tl->item);
if (comp >= 0 || tl->lt == 0)
if ((t->lt = tl->rt) != 0) t->lt->par = t;
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;
return (comp == 0) ? Pix(t) : 0;
Pix <T>SplayPQ::enq(<T&> item)
<T>SplayNode* newnode = new <T>SplayNode(item);
int comp = <T>CMP(item, t->item);
<T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
dummy->rt = dummy->lt = dummy->par = 0;
<T>SplayNode* tr = t->rt;
comp = <T>CMP(item, tr->item);
<T>SplayNode* trr = tr->rt;
comp = <T>CMP(item, trr->item);
if ((t->rt = tr->lt) != 0) t->rt->par = t;
<T>SplayNode* tl = t->lt;
comp = <T>CMP(item, tl->item);
<T>SplayNode* tll = tl->lt;
comp = <T>CMP(item, tll->item);
if ((t->lt = tl->rt) != 0) t->lt->par = t;
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;
void <T>SplayPQ::del(Pix pix)
<T>SplayNode* t = (<T>SplayNode*)pix;
<T>SplayNode* p = t->par;
if ((root = t->lt) != 0) root->par = 0;
if ((p->lt = t->lt) != 0) p->lt->par = p;
if ((p->rt = t->lt) != 0) p->rt->par = p;
if ((r->lt = t->lt) != 0) r->lt->par = r;
if ((r->lt = l->rt) != 0) r->lt->par = r;
error ("min: empty tree\n");
<T>SplayNode* l = root->lt;
if ((t->lt = l->rt) != 0) t->lt->par = t;
void <T>SplayPQ::del_front()
<T>SplayNode* l = root->lt;
if ((root = t->rt) != 0) root->par = 0;
<T>SplayNode* ll = l->lt;
if ((t->lt = l->rt) != 0) t->lt->par = t;
<T>SplayNode* lll = ll->lt;
if ((l->lt = ll->rt) != 0) l->lt->par = l;
if ((l->lt = ll->rt) != 0) l->lt->par = l;
error("deq: empty tree");
<T>SplayNode* l = root->lt;
if ((root = t->rt) != 0) root->par = 0;
<T>SplayNode* ll = l->lt;
if ((t->lt = l->rt) != 0) t->lt->par = t;
<T>SplayNode* lll = ll->lt;
if ((l->lt = ll->rt) != 0) l->lt->par = l;
if ((l->lt = ll->rt) != 0) l->lt->par = l;
void <T>SplayPQ::_kill(<T>SplayNode* t)
<T>SplayNode* <T>SplayPQ::_copy(<T>SplayNode* t)
<T>SplayNode* l = _copy(t->lt);
<T>SplayNode* r = _copy(t->rt);
<T>SplayNode* x = new <T>SplayNode(t->item, l, r);
<T>SplayNode* trail = leftmost();
<T>SplayNode* t = succ(trail);
v &= <T>CMP(trail->item, t->item) < 0;
if (!v) error("invariant failure");