1// This may look like C code, but it is really -*- C++ -*-
2/*
3Copyright (C) 1988 Free Software Foundation
4    written by Doug Lea (dl@rocky.oswego.edu)
5
6This file is part of GNU CC.
7
8GNU CC is distributed in the hope that it will be useful,
9but WITHOUT ANY WARRANTY.  No author or distributor
10accepts responsibility to anyone for the consequences of using it
11or for whether it serves any particular purpose or works at all,
12unless he says so in writing.  Refer to the GNU CC General Public
13License for full details.
14
15Everyone is granted permission to copy, modify and redistribute
16GNU CC, but only under the conditions described in the
17GNU CC General Public License.   A copy of this license is
18supposed to have been given to you along with GNU CC so you
19can know your rights and responsibilities.  It should be in a
20file named COPYING.  Among other things, the copyright notice
21and this notice must be preserved on all copies.
22*/
23
24#ifdef __GNUG__
25#pragma implementation
26#endif
27#include <stream.h>
28#include <assert.h>
29#include "<T>.SplayPQ.h"
30
31
32/*
33
34 struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985
35 splay tree algorithms
36
37 All routines use a version of their `simple top-down' splay alg. (p 669)
38
39*/
40
41struct _dummySplayNode
42{
43  <T>SplayNode*    lt;
44  <T>SplayNode*    rt;
45  <T>SplayNode*    par;
46} _dummy_null;
47
48
49/*
50 traversal primitives
51*/
52
53
54<T>SplayNode* <T>SplayPQ::leftmost()
55{
56  <T>SplayNode* t = root;
57  if (t != 0) while (t->lt != 0) t = t->lt;
58  return t;
59}
60
61<T>SplayNode* <T>SplayPQ::rightmost()
62{
63  <T>SplayNode* t = root;
64  if (t != 0) while (t->rt != 0) t = t->rt;
65  return t;
66}
67
68<T>SplayNode* <T>SplayPQ::succ(<T>SplayNode* t)
69{
70  if (t == 0)
71    return 0;
72  if (t->rt != 0)
73  {
74    t = t->rt;
75    while (t->lt != 0) t = t->lt;
76    return t;
77  }
78  else
79  {
80    for (;;)
81    {
82      if (t->par == 0 || t == t->par->lt)
83        return t->par;
84      else
85        t = t->par;
86    }
87  }
88}
89
90<T>SplayNode* <T>SplayPQ::pred(<T>SplayNode* t)
91{
92  if (t == 0)
93    return 0;
94  else if (t->lt != 0)
95  {
96    t = t->lt;
97    while (t->rt != 0) t = t->rt;
98    return t;
99  }
100  else
101  {
102    for (;;)
103    {
104      if (t->par == 0 || t == t->par->rt)
105        return t->par;
106      else
107        t = t->par;
108    }
109  }
110}
111
112
113Pix <T>SplayPQ::seek(<T&> key)
114{
115  <T>SplayNode* t = root;
116  if (t == 0)
117    return 0;
118
119  int comp = <T>CMP(key, t->item);
120  if (comp == 0)
121    return Pix(t);
122
123  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
124  <T>SplayNode* l = dummy;
125  <T>SplayNode* r = dummy;
126  dummy->rt = dummy->lt = dummy->par = 0;
127
128  while (comp != 0)
129  {
130    if (comp > 0)
131    {
132      <T>SplayNode* tr = t->rt;
133      if (tr == 0)
134        break;
135      else
136      {
137        comp = <T>CMP(key, tr->item);
138        if (comp <= 0 || tr->rt == 0)
139        {
140          l->rt = t; t->par = l;
141          l = t;
142          t = tr;
143          if (comp >= 0)
144            break;
145        }
146        else
147        {
148          if ((t->rt = tr->lt) != 0) t->rt->par = t;
149          tr->lt = t; t->par = tr;
150          l->rt = tr; tr->par = l;
151          l = tr;
152          t = tr->rt;
153          comp = <T>CMP(key, t->item);
154        }
155      }
156    }
157    else
158    {
159      <T>SplayNode* tl = t->lt;
160      if (tl == 0)
161        break;
162      else
163      {
164        comp = <T>CMP(key, tl->item);
165        if (comp >= 0 || tl->lt == 0)
166        {
167          r->lt = t; t->par = r;
168          r = t;
169          t = tl;
170          if (comp <= 0)
171            break;
172        }
173        else
174        {
175          if ((t->lt = tl->rt) != 0) t->lt->par = t;
176          tl->rt = t; t->par = tl;
177          r->lt = tl; tl->par = r;
178          r = tl;
179          t = tl->lt;
180          comp = <T>CMP(key, t->item);
181        }
182      }
183    }
184  }
185  if ((r->lt = t->rt) != 0) r->lt->par = r;
186  if ((l->rt = t->lt) != 0) l->rt->par = l;
187  if ((t->lt = dummy->rt) != 0) t->lt->par = t;
188  if ((t->rt = dummy->lt) != 0) t->rt->par = t;
189  t->par = 0;
190  root = t;
191  return (comp == 0) ? Pix(t) : 0;
192}
193
194
195Pix <T>SplayPQ::enq(<T&> item)
196{
197  ++count;
198  <T>SplayNode* newnode = new <T>SplayNode(item);
199  <T>SplayNode* t = root;
200  if (t == 0)
201  {
202    root = newnode;
203    return Pix(root);
204  }
205
206  int comp = <T>CMP(item, t->item);
207
208  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
209  <T>SplayNode* l = dummy;
210  <T>SplayNode* r = dummy;
211  dummy->rt = dummy->lt = dummy->par = 0;
212
213  int done = 0;
214  while (!done)
215  {
216    if (comp >= 0)
217    {
218      <T>SplayNode* tr = t->rt;
219      if (tr == 0)
220      {
221        tr = newnode;
222        comp = 0; done = 1;
223      }
224      else
225        comp = <T>CMP(item, tr->item);
226
227      if (comp <= 0)
228      {
229        l->rt = t; t->par = l;
230        l = t;
231        t = tr;
232      }
233      else
234      {
235        <T>SplayNode* trr = tr->rt;
236        if (trr == 0)
237        {
238          trr =  newnode;
239          comp = 0; done = 1;
240        }
241        else
242          comp = <T>CMP(item, trr->item);
243
244        if ((t->rt = tr->lt) != 0) t->rt->par = t;
245        tr->lt = t; t->par = tr;
246        l->rt = tr; tr->par = l;
247        l = tr;
248        t = trr;
249      }
250    }
251    else
252    {
253      <T>SplayNode* tl = t->lt;
254      if (tl == 0)
255      {
256        tl = newnode;
257        comp = 0; done = 1;
258      }
259      else
260        comp = <T>CMP(item, tl->item);
261
262      if (comp >= 0)
263      {
264        r->lt = t; t->par = r;
265        r = t;
266        t = tl;
267      }
268      else
269      {
270        <T>SplayNode* tll = tl->lt;
271        if (tll == 0)
272        {
273          tll = newnode;
274          comp = 0; done = 1;
275        }
276        else
277          comp = <T>CMP(item, tll->item);
278
279        if ((t->lt = tl->rt) != 0) t->lt->par = t;
280        tl->rt = t; t->par = tl;
281        r->lt = tl; tl->par = r;
282        r = tl;
283        t = tll;
284      }
285    }
286  }
287  if ((r->lt = t->rt) != 0) r->lt->par = r;
288  if ((l->rt = t->lt) != 0) l->rt->par = l;
289  if ((t->lt = dummy->rt) != 0) t->lt->par = t;
290  if ((t->rt = dummy->lt) != 0) t->rt->par = t;
291  t->par = 0;
292  root = t;
293  return Pix(root);
294}
295
296
297void <T>SplayPQ::del(Pix pix)
298{
299  <T>SplayNode* t = (<T>SplayNode*)pix;
300  if (t == 0) return;
301
302  <T>SplayNode* p = t->par;
303
304  --count;
305  if (t->rt == 0)
306  {
307    if (t == root)
308    {
309      if ((root = t->lt) != 0) root->par = 0;
310    }
311    else if (t == p->lt)
312    {
313      if ((p->lt = t->lt) != 0) p->lt->par = p;
314    }
315    else
316      if ((p->rt = t->lt) != 0) p->rt->par = p;
317  }
318  else
319  {
320    <T>SplayNode* r = t->rt;
321    <T>SplayNode* l = r->lt;
322    for(;;)
323    {
324      if (l == 0)
325      {
326        if (t == root)
327        {
328          root = r;
329          r->par = 0;
330        }
331        else if (t == p->lt)
332        {
333          p->lt = r;
334          r->par = p;
335        }
336        else
337        {
338          p->rt = r;
339          r->par = p;
340        }
341        if ((r->lt = t->lt) != 0) r->lt->par = r;
342        break;
343      }
344      else
345      {
346        if ((r->lt = l->rt) != 0) r->lt->par = r;
347        l->rt = r; r->par = l;
348        r = l;
349        l = l->lt;
350      }
351    }
352  }
353  delete t;
354}
355
356<T>& <T>SplayPQ::front()
357{
358  if (root == 0)
359    error ("min: empty tree\n");
360//  else
361  {
362    <T>SplayNode* t = root;
363    <T>SplayNode* l = root->lt;
364    for(;;)
365    {
366      if (l == 0)
367      {
368        root = t;
369        root->par = 0;
370        return root->item;
371      }
372      else
373      {
374        if ((t->lt = l->rt) != 0) t->lt->par = t;
375        l->rt = t; t->par = l;
376        t = l;
377        l = l->lt;
378      }
379    }
380  }
381}
382
383void <T>SplayPQ::del_front()
384{
385  if (root != 0)
386  {
387    --count;
388    <T>SplayNode* t = root;
389    <T>SplayNode* l = root->lt;
390    if (l == 0)
391    {
392      if ((root = t->rt) != 0) root->par = 0;
393      delete t;
394    }
395    else
396    {
397      for(;;)
398      {
399        <T>SplayNode* ll = l->lt;
400        if (ll == 0)
401        {
402          if ((t->lt = l->rt) != 0) t->lt->par = t;
403          delete l;
404          break;
405        }
406        else
407        {
408          <T>SplayNode* lll = ll->lt;
409          if (lll == 0)
410          {
411            if ((l->lt = ll->rt) != 0) l->lt->par = l;
412            delete ll;
413            break;
414          }
415          else
416          {
417            t->lt = ll; ll->par = t;
418            if ((l->lt = ll->rt) != 0) l->lt->par = l;
419            ll->rt = l; l->par = ll;
420            t = ll;
421            l = lll;
422          }
423        }
424      }
425    }
426  }
427}
428
429<T> <T>SplayPQ::deq()
430{
431  if (root == 0)
432    error("deq: empty tree");
433//  else
434  {
435    --count;
436    <T>SplayNode* t = root;
437    <T>SplayNode* l = root->lt;
438    if (l == 0)
439    {
440      if ((root = t->rt) != 0) root->par = 0;
441      <T> res = t->item;
442      delete t;
443      return res;
444    }
445    else
446    {
447      for(;;)
448      {
449        <T>SplayNode* ll = l->lt;
450        if (ll == 0)
451        {
452          if ((t->lt = l->rt) != 0) t->lt->par = t;
453          <T> res = l->item;
454          delete l;
455          return res;
456        }
457        else
458        {
459          <T>SplayNode* lll = ll->lt;
460          if (lll == 0)
461          {
462            if ((l->lt = ll->rt) != 0) l->lt->par = l;
463            <T> res = ll->item;
464            delete ll;
465            return res;
466          }
467          else
468          {
469            t->lt = ll; ll->par = t;
470            if ((l->lt = ll->rt) != 0) l->lt->par = l;
471            ll->rt = l; l->par = ll;
472            t = ll;
473            l = lll;
474          }
475        }
476      }
477    }
478  }
479}
480
481
482void <T>SplayPQ::_kill(<T>SplayNode* t)
483{
484  if (t != 0)
485  {
486    _kill(t->lt);
487    _kill(t->rt);
488    delete t;
489  }
490}
491
492
493<T>SplayNode* <T>SplayPQ::_copy(<T>SplayNode* t)
494{
495  if (t != 0)
496  {
497    <T>SplayNode* l = _copy(t->lt);
498    <T>SplayNode* r = _copy(t->rt);
499    <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
500    if (l != 0) l->par = x;
501    if (r != 0) r->par = x;
502    return x;
503  }
504  else
505    return 0;
506}
507
508int <T>SplayPQ::OK()
509{
510  int v = 1;
511  if (root == 0)
512    v = count == 0;
513  else
514  {
515    int n = 1;
516    <T>SplayNode* trail = leftmost();
517    <T>SplayNode* t = succ(trail);
518    while (t != 0)
519    {
520      ++n;
521      v &= <T>CMP(trail->item, t->item) < 0;
522      trail = t;
523      t = succ(t);
524    }
525    v &= n == count;
526  }
527  if (!v) error("invariant failure");
528  return v;
529}
530