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>.SplaySet.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>SplaySet::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>SplaySet::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>SplaySet::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>SplaySet::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>SplaySet::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
195
196Pix <T>SplaySet::add(<T&> item)
197{
198  <T>SplayNode* t = root;
199  if (t == 0)
200  {
201    ++count;
202    root = new <T>SplayNode(item);
203    return Pix(root);
204  }
205  int comp = <T>CMP(item, t->item);
206  if (comp == 0)
207    return Pix(t);
208
209  <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null);
210  <T>SplayNode* l = dummy;
211  <T>SplayNode* r = dummy;
212  dummy->rt = dummy->lt = dummy->par = 0;
213
214  while (comp != 0)
215  {
216    if (comp > 0)
217    {
218      <T>SplayNode* tr = t->rt;
219      if (tr == 0)
220      {
221        ++count;
222        tr = new <T>SplayNode(item);
223        comp = 0;
224      }
225      else
226        comp = <T>CMP(item, tr->item);
227
228      if (comp <= 0)
229      {
230        l->rt = t; t->par = l;
231        l = t;
232        t = tr;
233      }
234      else
235      {
236        <T>SplayNode* trr = tr->rt;
237        if (trr == 0)
238        {
239          ++count;
240          trr =  new <T>SplayNode(item);
241          comp = 0;
242        }
243        else
244          comp = <T>CMP(item, trr->item);
245
246        if ((t->rt = tr->lt) != 0) t->rt->par = t;
247        tr->lt = t; t->par = tr;
248        l->rt = tr; tr->par = l;
249        l = tr;
250        t = trr;
251      }
252    }
253    else
254    {
255      <T>SplayNode* tl = t->lt;
256      if (tl == 0)
257      {
258        ++count;
259        tl = new <T>SplayNode(item);
260        comp = 0;
261      }
262      else
263        comp = <T>CMP(item, tl->item);
264
265      if (comp >= 0)
266      {
267        r->lt = t; t->par = r;
268        r = t;
269        t = tl;
270      }
271      else
272      {
273        <T>SplayNode* tll = tl->lt;
274        if (tll == 0)
275        {
276          ++count;
277          tll = new <T>SplayNode(item);
278          comp = 0;
279        }
280        else
281          comp = <T>CMP(item, tll->item);
282
283        if ((t->lt = tl->rt) != 0) t->lt->par = t;
284        tl->rt = t; t->par = tl;
285        r->lt = tl; tl->par = r;
286        r = tl;
287        t = tll;
288      }
289    }
290  }
291  if ((r->lt = t->rt) != 0) r->lt->par = r;
292  if ((l->rt = t->lt) != 0) l->rt->par = l;
293  if ((t->lt = dummy->rt) != 0) t->lt->par = t;
294  if ((t->rt = dummy->lt) != 0) t->rt->par = t;
295  t->par = 0;
296  root = t;
297  return Pix(root);
298}
299
300void <T>SplaySet::del(<T&> key)
301{
302  <T>SplayNode* t = (<T>SplayNode*)(seek(key));
303  if (t == 0) return;
304
305  <T>SplayNode* p = t->par;
306
307  --count;
308  if (t->rt == 0)
309  {
310    if (t == root)
311    {
312      if ((root = t->lt) != 0) root->par = 0;
313    }
314    else if (t == p->lt)
315    {
316      if ((p->lt = t->lt) != 0) p->lt->par = p;
317    }
318    else
319      if ((p->rt = t->lt) != 0) p->rt->par = p;
320  }
321  else
322  {
323    <T>SplayNode* r = t->rt;
324    <T>SplayNode* l = r->lt;
325    for(;;)
326    {
327      if (l == 0)
328      {
329        if (t == root)
330        {
331          root = r;
332          r->par = 0;
333        }
334        else if (t == p->lt)
335        {
336          p->lt = r;
337          r->par = p;
338        }
339        else
340        {
341          p->rt = r;
342          r->par = p;
343        }
344        if ((r->lt = t->lt) != 0) r->lt->par = r;
345        break;
346      }
347      else
348      {
349        if ((r->lt = l->rt) != 0) r->lt->par = r;
350        l->rt = r; r->par = l;
351        r = l;
352        l = l->lt;
353      }
354    }
355  }
356  delete t;
357}
358
359
360void <T>SplaySet::_kill(<T>SplayNode* t)
361{
362  if (t != 0)
363  {
364    _kill(t->lt);
365    _kill(t->rt);
366    delete t;
367  }
368}
369
370
371<T>SplayNode* <T>SplaySet::_copy(<T>SplayNode* t)
372{
373  if (t != 0)
374  {
375    <T>SplayNode* l = _copy(t->lt);
376    <T>SplayNode* r = _copy(t->rt);
377    <T>SplayNode* x = new <T>SplayNode(t->item, l, r);
378    if (l != 0) l->par = x;
379    if (r != 0) r->par = x;
380    return x;
381  }
382  else
383    return 0;
384}
385
386/* relationals */
387
388int <T>SplaySet::operator == (<T>SplaySet& y)
389{
390  if (count != y.count)
391    return 0;
392  else
393  {
394    <T>SplayNode* t = leftmost();
395    <T>SplayNode* u = y.leftmost();
396    for (;;)
397    {
398      if (t == 0)
399        return 1;
400      else if (!<T>EQ(t->item, u->item))
401        return 0;
402      else
403      {
404        t = succ(t);
405        u = y.succ(u);
406      }
407    }
408  }
409}
410
411int <T>SplaySet::operator <= (<T>SplaySet& y)
412{
413  if (count > y.count)
414    return 0;
415  else
416  {
417    <T>SplayNode* t = leftmost();
418    <T>SplayNode* u = y.leftmost();
419    for (;;)
420    {
421      if (t == 0)
422        return 1;
423      else if (u == 0)
424        return 0;
425      int cmp = <T>CMP(t->item, u->item);
426      if (cmp == 0)
427      {
428        t = succ(t);
429        u = y.succ(u);
430      }
431      else if (cmp < 0)
432        return 0;
433      else
434        u = y.succ(u);
435    }
436  }
437}
438
439
440void <T>SplaySet::operator |=(<T>SplaySet& y)
441{
442  if (&y == this) return;
443  <T>SplayNode* u = y.leftmost();
444  while (u != 0)
445  {
446    add(u->item);
447    u = y.succ(u);
448  }
449}
450
451void <T>SplaySet::operator &= (<T>SplaySet& y)
452{
453  if (y.count == 0)
454    clear();
455  else if (&y != this && count != 0)
456  {
457    <T>SplayNode* t = leftmost();
458    while (t != 0)
459    {
460      <T>SplayNode* s = succ(t);
461      if (y.seek(t->item) == 0) del(t->item);
462      t = s;
463    }
464  }
465}
466
467
468void <T>SplaySet::operator -=(<T>SplaySet& y)
469{
470  if (&y == this)
471    clear();
472  else if (y.count != 0)
473  {
474    <T>SplayNode* t = leftmost();
475    while (t != 0)
476    {
477      <T>SplayNode* s = succ(t);
478      if (y.seek(t->item) != 0) del(t->item);
479      t = s;
480    }
481  }
482}
483
484int <T>SplaySet::OK()
485{
486  int v = 1;
487  if (root == 0)
488    v = count == 0;
489  else
490  {
491    int n = 1;
492    <T>SplayNode* trail = leftmost();
493    <T>SplayNode* t = succ(trail);
494    while (t != 0)
495    {
496      ++n;
497      v &= <T>CMP(trail->item, t->item) < 0;
498      trail = t;
499      t = succ(t);
500    }
501    v &= n == count;
502  }
503  if (!v) error("invariant failure");
504  return v;
505}
506