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>.AVLSet.h"
30
31
32/*
33 constants & inlines for maintaining balance & thread status in tree nodes
34*/
35
36#define AVLBALANCEMASK    3
37#define AVLBALANCED       0
38#define AVLLEFTHEAVY      1
39#define AVLRIGHTHEAVY     2
40
41#define LTHREADBIT        4
42#define RTHREADBIT        8
43
44
45static inline int bf(<T>AVLNode* t)
46{
47  return t->stat & AVLBALANCEMASK;
48}
49
50static inline void set_bf(<T>AVLNode* t, int b)
51{
52  t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK);
53}
54
55
56static inline int rthread(<T>AVLNode* t)
57{
58  return t->stat & RTHREADBIT;
59}
60
61static inline void set_rthread(<T>AVLNode* t, int b)
62{
63  if (b)
64    t->stat |= RTHREADBIT;
65  else
66    t->stat &= ~RTHREADBIT;
67}
68
69static inline int lthread(<T>AVLNode* t)
70{
71  return t->stat & LTHREADBIT;
72}
73
74static inline void set_lthread(<T>AVLNode* t, int b)
75{
76  if (b)
77    t->stat |= LTHREADBIT;
78  else
79    t->stat &= ~LTHREADBIT;
80}
81
82/*
83 traversal primitives
84*/
85
86
87<T>AVLNode* <T>AVLSet::leftmost()
88{
89  <T>AVLNode* t = root;
90  if (t != 0) while (t->lt != 0) t = t->lt;
91  return t;
92}
93
94<T>AVLNode* <T>AVLSet::rightmost()
95{
96  <T>AVLNode* t = root;
97  if (t != 0) while (t->rt != 0) t = t->rt;
98  return t;
99}
100
101<T>AVLNode* <T>AVLSet::succ(<T>AVLNode* t)
102{
103  <T>AVLNode* r = t->rt;
104  if (!rthread(t)) while (!lthread(r)) r = r->lt;
105  return r;
106}
107
108<T>AVLNode* <T>AVLSet::pred(<T>AVLNode* t)
109{
110  <T>AVLNode* l = t->lt;
111  if (!lthread(t)) while (!rthread(l)) l = l->rt;
112  return l;
113}
114
115
116Pix <T>AVLSet::seek(<T&> key)
117{
118  <T>AVLNode* t = root;
119  if (t == 0)
120    return 0;
121  for (;;)
122  {
123    int cmp = <T>CMP(key, t->item);
124    if (cmp == 0)
125      return Pix(t);
126    else if (cmp < 0)
127    {
128      if (lthread(t))
129        return 0;
130      else
131        t = t->lt;
132    }
133    else if (rthread(t))
134      return 0;
135    else
136      t = t->rt;
137  }
138}
139
140
141/*
142 The combination of threads and AVL bits make adding & deleting
143 interesting, but very awkward.
144
145 We use the following statics to avoid passing them around recursively
146*/
147
148static int _need_rebalancing;   // to send back balance info from rec. calls
149static <T>*   _target_item;     // add/del_item target
150static <T>AVLNode* _found_node; // returned added/deleted node
151static int    _already_found;   // for deletion subcases
152
153static <T>AVLNode** _hold_nodes;       // used for rebuilding trees
154static int  _max_hold_index;              // # elements-1 in _hold_nodes
155
156
157void <T>AVLSet:: _add(<T>AVLNode*& t)
158{
159  int cmp = <T>CMP(*_target_item, t->item);
160  if (cmp == 0)
161  {
162    _found_node = t;
163    return;
164  }
165  else if (cmp < 0)
166  {
167    if (lthread(t))
168    {
169      ++count;
170      _found_node = new <T>AVLNode(*_target_item);
171      set_lthread(_found_node, 1);
172      set_rthread(_found_node, 1);
173      _found_node->lt = t->lt;
174      _found_node->rt = t;
175      t->lt = _found_node;
176      set_lthread(t, 0);
177      _need_rebalancing = 1;
178    }
179    else
180      _add(t->lt);
181    if (_need_rebalancing)
182    {
183      switch(bf(t))
184      {
185      case AVLRIGHTHEAVY:
186        set_bf(t, AVLBALANCED);
187        _need_rebalancing = 0;
188        return;
189      case AVLBALANCED:
190        set_bf(t, AVLLEFTHEAVY);
191        return;
192      case AVLLEFTHEAVY:
193        <T>AVLNode* l = t->lt;
194        if (bf(l) == AVLLEFTHEAVY)
195        {
196          if (rthread(l))
197            t->lt = l;
198          else
199            t->lt = l->rt;
200          set_lthread(t, rthread(l));
201          l->rt = t;
202          set_rthread(l, 0);
203          set_bf(t, AVLBALANCED);
204          set_bf(l, AVLBALANCED);
205          t = l;
206          _need_rebalancing = 0;
207        }
208        else
209        {
210          <T>AVLNode* r = l->rt;
211          set_rthread(l, lthread(r));
212          if (lthread(r))
213            l->rt = r;
214          else
215            l->rt = r->lt;
216          r->lt = l;
217          set_lthread(r, 0);
218          set_lthread(t, rthread(r));
219          if (rthread(r))
220            t->lt = r;
221          else
222            t->lt = r->rt;
223          r->rt = t;
224          set_rthread(r, 0);
225          if (bf(r) == AVLLEFTHEAVY)
226            set_bf(t, AVLRIGHTHEAVY);
227          else
228            set_bf(t, AVLBALANCED);
229          if (bf(r) == AVLRIGHTHEAVY)
230            set_bf(l, AVLLEFTHEAVY);
231          else
232            set_bf(l, AVLBALANCED);
233          set_bf(r, AVLBALANCED);
234          t = r;
235          _need_rebalancing = 0;
236          return;
237        }
238      }
239    }
240  }
241  else
242  {
243    if (rthread(t))
244    {
245      ++count;
246      _found_node = new <T>AVLNode(*_target_item);
247      set_rthread(t, 0);
248      set_lthread(_found_node, 1);
249      set_rthread(_found_node, 1);
250      _found_node->lt = t;
251      _found_node->rt = t->rt;
252      t->rt = _found_node;
253      _need_rebalancing = 1;
254    }
255    else
256      _add(t->rt);
257    if (_need_rebalancing)
258    {
259      switch(bf(t))
260      {
261      case AVLLEFTHEAVY:
262        set_bf(t, AVLBALANCED);
263        _need_rebalancing = 0;
264        return;
265      case AVLBALANCED:
266        set_bf(t, AVLRIGHTHEAVY);
267        return;
268      case AVLRIGHTHEAVY:
269        <T>AVLNode* r = t->rt;
270        if (bf(r) == AVLRIGHTHEAVY)
271        {
272          if (lthread(r))
273            t->rt = r;
274          else
275            t->rt = r->lt;
276          set_rthread(t, lthread(r));
277          r->lt = t;
278          set_lthread(r, 0);
279          set_bf(t, AVLBALANCED);
280          set_bf(r, AVLBALANCED);
281          t = r;
282          _need_rebalancing = 0;
283        }
284        else
285        {
286          <T>AVLNode* l = r->lt;
287          set_lthread(r, rthread(l));
288          if (rthread(l))
289            r->lt = l;
290          else
291            r->lt = l->rt;
292          l->rt = r;
293          set_rthread(l, 0);
294          set_rthread(t, lthread(l));
295          if (lthread(l))
296            t->rt = l;
297          else
298            t->rt = l->lt;
299          l->lt = t;
300          set_lthread(l, 0);
301          if (bf(l) == AVLRIGHTHEAVY)
302            set_bf(t, AVLLEFTHEAVY);
303          else
304            set_bf(t, AVLBALANCED);
305          if (bf(l) == AVLLEFTHEAVY)
306            set_bf(r, AVLRIGHTHEAVY);
307          else
308            set_bf(r, AVLBALANCED);
309          set_bf(l, AVLBALANCED);
310          t = l;
311          _need_rebalancing = 0;
312          return;
313        }
314      }
315    }
316  }
317}
318
319
320Pix <T>AVLSet::add(<T&> item)
321{
322  if (root == 0)
323  {
324    ++count;
325    root = new <T>AVLNode(item);
326    set_rthread(root, 1);
327    set_lthread(root, 1);
328    return Pix(root);
329  }
330  else
331  {
332    _target_item = &item;
333    _need_rebalancing = 0;
334    _add(root);
335    return Pix(_found_node);
336  }
337}
338
339
340void <T>AVLSet::_del(<T>AVLNode* par, <T>AVLNode*& t)
341{
342  int comp;
343  if (_already_found)
344  {
345    if (rthread(t))
346      comp = 0;
347    else
348      comp = 1;
349  }
350  else
351    comp = <T>CMP(*_target_item, t->item);
352  if (comp == 0)
353  {
354    if (lthread(t) && rthread(t))
355    {
356      _found_node = t;
357      if (t == par->lt)
358      {
359        set_lthread(par, 1);
360        par->lt = t->lt;
361      }
362      else
363      {
364        set_rthread(par, 1);
365        par->rt = t->rt;
366      }
367      _need_rebalancing = 1;
368      return;
369    }
370    else if (lthread(t))
371    {
372      _found_node = t;
373      <T>AVLNode* s = succ(t);
374      if (s != 0 && lthread(s))
375        s->lt = t->lt;
376      t = t->rt;
377      _need_rebalancing = 1;
378      return;
379    }
380    else if (rthread(t))
381    {
382      _found_node = t;
383      <T>AVLNode* p = pred(t);
384      if (p != 0 && rthread(p))
385        p->rt = t->rt;
386      t = t->lt;
387      _need_rebalancing = 1;
388      return;
389    }
390    else                        // replace item & find someone deletable
391    {
392      <T>AVLNode* p = pred(t);
393      t->item = p->item;
394      _already_found = 1;
395      comp = -1;                // fall through below to left
396    }
397  }
398
399  if (comp < 0)
400  {
401    if (lthread(t))
402      return;
403    _del(t, t->lt);
404    if (!_need_rebalancing)
405      return;
406    switch (bf(t))
407    {
408    case AVLLEFTHEAVY:
409      set_bf(t, AVLBALANCED);
410      return;
411    case AVLBALANCED:
412      set_bf(t, AVLRIGHTHEAVY);
413      _need_rebalancing = 0;
414      return;
415    case AVLRIGHTHEAVY:
416      <T>AVLNode* r = t->rt;
417      switch (bf(r))
418      {
419      case AVLBALANCED:
420        if (lthread(r))
421          t->rt = r;
422        else
423          t->rt = r->lt;
424        set_rthread(t, lthread(r));
425        r->lt = t;
426        set_lthread(r, 0);
427        set_bf(t, AVLRIGHTHEAVY);
428        set_bf(r, AVLLEFTHEAVY);
429        _need_rebalancing = 0;
430        t = r;
431        return;
432      case AVLRIGHTHEAVY:
433        if (lthread(r))
434          t->rt = r;
435        else
436          t->rt = r->lt;
437        set_rthread(t, lthread(r));
438        r->lt = t;
439        set_lthread(r, 0);
440        set_bf(t, AVLBALANCED);
441        set_bf(r, AVLBALANCED);
442        t = r;
443        return;
444      case AVLLEFTHEAVY:
445        <T>AVLNode* l = r->lt;
446        set_lthread(r, rthread(l));
447        if (rthread(l))
448          r->lt = l;
449        else
450          r->lt = l->rt;
451        l->rt = r;
452        set_rthread(l, 0);
453        set_rthread(t, lthread(l));
454        if (lthread(l))
455          t->rt = l;
456        else
457          t->rt = l->lt;
458        l->lt = t;
459        set_lthread(l, 0);
460        if (bf(l) == AVLRIGHTHEAVY)
461          set_bf(t, AVLLEFTHEAVY);
462        else
463          set_bf(t, AVLBALANCED);
464        if (bf(l) == AVLLEFTHEAVY)
465          set_bf(r, AVLRIGHTHEAVY);
466        else
467          set_bf(r, AVLBALANCED);
468        set_bf(l, AVLBALANCED);
469        t = l;
470        return;
471      }
472    }
473  }
474  else
475  {
476    if (rthread(t))
477      return;
478    _del(t, t->rt);
479    if (!_need_rebalancing)
480      return;
481    switch (bf(t))
482    {
483    case AVLRIGHTHEAVY:
484      set_bf(t, AVLBALANCED);
485      return;
486    case AVLBALANCED:
487      set_bf(t, AVLLEFTHEAVY);
488      _need_rebalancing = 0;
489      return;
490    case AVLLEFTHEAVY:
491      <T>AVLNode* l = t->lt;
492      switch (bf(l))
493      {
494      case AVLBALANCED:
495        if (rthread(l))
496          t->lt = l;
497        else
498          t->lt = l->rt;
499        set_lthread(t, rthread(l));
500        l->rt = t;
501        set_rthread(l, 0);
502        set_bf(t, AVLLEFTHEAVY);
503        set_bf(l, AVLRIGHTHEAVY);
504        _need_rebalancing = 0;
505        t = l;
506        return;
507      case AVLLEFTHEAVY:
508        if (rthread(l))
509          t->lt = l;
510        else
511          t->lt = l->rt;
512        set_lthread(t, rthread(l));
513        l->rt = t;
514        set_rthread(l, 0);
515        set_bf(t, AVLBALANCED);
516        set_bf(l, AVLBALANCED);
517        t = l;
518        return;
519      case AVLRIGHTHEAVY:
520        <T>AVLNode* r = l->rt;
521        set_rthread(l, lthread(r));
522        if (lthread(r))
523          l->rt = r;
524        else
525          l->rt = r->lt;
526        r->lt = l;
527        set_lthread(r, 0);
528        set_lthread(t, rthread(r));
529        if (rthread(r))
530          t->lt = r;
531        else
532          t->lt = r->rt;
533        r->rt = t;
534        set_rthread(r, 0);
535        if (bf(r) == AVLLEFTHEAVY)
536          set_bf(t, AVLRIGHTHEAVY);
537        else
538          set_bf(t, AVLBALANCED);
539        if (bf(r) == AVLRIGHTHEAVY)
540          set_bf(l, AVLLEFTHEAVY);
541        else
542          set_bf(l, AVLBALANCED);
543        set_bf(r, AVLBALANCED);
544        t = r;
545        return;
546      }
547    }
548  }
549}
550
551
552
553void <T>AVLSet::del(<T&> item)
554{
555  if (root == 0) return;
556  _need_rebalancing = 0;
557  _already_found = 0;
558  _found_node = 0;
559  _target_item = &item;
560  _del(root, root);
561  if (_found_node)
562  {
563    delete(_found_node);
564    if (--count == 0)
565      root = 0;
566  }
567}
568
569// build an ordered array of pointers to tree nodes back into a tree
570// we know that at least one element exists
571
572static <T>AVLNode* _do_treeify(int lo, int hi, int& h)
573{
574  int lh, rh;
575  int mid = (lo + hi) / 2;
576  <T>AVLNode* t = _hold_nodes[mid];
577  if (lo > mid - 1)
578  {
579    set_lthread(t, 1);
580    if (mid == 0)
581      t->lt = 0;
582    else
583      t->lt = _hold_nodes[mid-1];
584    lh = 0;
585  }
586  else
587  {
588    set_lthread(t, 0);
589    t->lt = _do_treeify(lo, mid-1, lh);
590  }
591  if (hi < mid + 1)
592  {
593    set_rthread(t, 1);
594    if (mid == _max_hold_index)
595      t->rt = 0;
596    else
597      t->rt = _hold_nodes[mid+1];
598    rh = 0;
599  }
600  else
601  {
602    set_rthread(t, 0);
603    t->rt = _do_treeify(mid+1, hi, rh);
604  }
605  if (lh == rh)
606  {
607    set_bf(t, AVLBALANCED);
608    h = lh + 1;
609  }
610  else if (lh == rh - 1)
611  {
612    set_bf(t, AVLRIGHTHEAVY);
613    h = rh + 1;
614  }
615  else if (rh == lh - 1)
616  {
617    set_bf(t, AVLLEFTHEAVY);
618    h = lh + 1;
619  }
620  else                          // can't happen
621    abort();
622
623  return t;
624}
625
626static <T>AVLNode* _treeify(int n)
627{
628  <T>AVLNode* t;
629  if (n == 0)
630    t = 0;
631  else
632  {
633    int b;
634    _max_hold_index = n-1;
635    t = _do_treeify(0, _max_hold_index, b);
636  }
637  delete _hold_nodes;
638  return t;
639}
640
641
642void <T>AVLSet::_kill(<T>AVLNode* t)
643{
644  if (t != 0)
645  {
646    if (!lthread(t)) _kill(t->lt);
647    if (!rthread(t)) _kill(t->rt);
648    delete t;
649  }
650}
651
652
653<T>AVLSet::<T>AVLSet(<T>AVLSet& b)
654{
655  if ((count = b.count) == 0)
656  {
657    root = 0;
658  }
659  else
660  {
661    _hold_nodes = new <T>AVLNodePtr [count];
662    <T>AVLNode* t = b.leftmost();
663    int i = 0;
664    while (t != 0)
665    {
666      _hold_nodes[i++] = new <T>AVLNode(t->item);
667      t = b.succ(t);
668    }
669    root = _treeify(count);
670  }
671}
672
673
674int <T>AVLSet::operator == (<T>AVLSet& y)
675{
676  if (count != y.count)
677    return 0;
678  else
679  {
680    <T>AVLNode* t = leftmost();
681    <T>AVLNode* u = y.leftmost();
682    for (;;)
683    {
684      if (t == 0)
685        return 1;
686      else if (!(<T>EQ(t->item, u->item)))
687        return 0;
688      else
689      {
690        t = succ(t);
691        u = y.succ(u);
692      }
693    }
694  }
695}
696
697int <T>AVLSet::operator <= (<T>AVLSet& y)
698{
699  if (count > y.count)
700    return 0;
701  else
702  {
703    <T>AVLNode* t = leftmost();
704    <T>AVLNode* u = y.leftmost();
705    for (;;)
706    {
707      if (t == 0)
708        return 1;
709      else if (u == 0)
710        return 0;
711      int cmp = <T>CMP(t->item, u->item);
712      if (cmp == 0)
713      {
714        t = succ(t);
715        u = y.succ(u);
716      }
717      else if (cmp < 0)
718        return 0;
719      else
720        u = y.succ(u);
721    }
722  }
723}
724
725void <T>AVLSet::operator |=(<T>AVLSet& y)
726{
727  <T>AVLNode* t = leftmost();
728  <T>AVLNode* u = y.leftmost();
729  int rsize = count + y.count;
730  _hold_nodes = new <T>AVLNodePtr [rsize];
731  int k = 0;
732  for (;;)
733  {
734    if (t == 0)
735    {
736      while (u != 0)
737      {
738        _hold_nodes[k++] = new <T>AVLNode(u->item);
739        u = y.succ(u);
740      }
741      break;
742    }
743    else if (u == 0)
744    {
745      while (t != 0)
746      {
747        _hold_nodes[k++] = t;
748        t = succ(t);
749      }
750      break;
751    }
752    int cmp = <T>CMP(t->item, u->item);
753    if (cmp == 0)
754    {
755      _hold_nodes[k++] = t;
756      t = succ(t);
757      u = y.succ(u);
758    }
759    else if (cmp < 0)
760    {
761      _hold_nodes[k++] = t;
762      t = succ(t);
763    }
764    else
765    {
766      _hold_nodes[k++] = new <T>AVLNode(u->item);
767      u = y.succ(u);
768    }
769  }
770  root = _treeify(k);
771  count = k;
772}
773
774void <T>AVLSet::operator &= (<T>AVLSet& y)
775{
776  <T>AVLNode* t = leftmost();
777  <T>AVLNode* u = y.leftmost();
778  int rsize = (count < y.count)? count : y.count;
779  _hold_nodes = new <T>AVLNodePtr [rsize];
780  int k = 0;
781  for (;;)
782  {
783    if (t == 0)
784      break;
785    if (u == 0)
786    {
787      while (t != 0)
788      {
789        <T>AVLNode* tmp = succ(t);
790        delete t;
791        t = tmp;
792      }
793      break;
794    }
795    int cmp = <T>CMP(t->item, u->item);
796    if (cmp == 0)
797    {
798      _hold_nodes[k++] = t;
799      t = succ(t);
800      u = y.succ(u);
801    }
802    else if (cmp < 0)
803    {
804      <T>AVLNode* tmp = succ(t);
805      delete t;
806      t = tmp;
807    }
808    else
809      u = y.succ(u);
810  }
811  root = _treeify(k);
812  count = k;
813}
814
815
816void <T>AVLSet::operator -=(<T>AVLSet& y)
817{
818  <T>AVLNode* t = leftmost();
819  <T>AVLNode* u = y.leftmost();
820  int rsize = count;
821  _hold_nodes = new <T>AVLNodePtr [rsize];
822  int k = 0;
823  for (;;)
824  {
825    if (t == 0)
826      break;
827    else if (u == 0)
828    {
829      while (t != 0)
830      {
831        _hold_nodes[k++] = t;
832        t = succ(t);
833      }
834      break;
835    }
836    int cmp = <T>CMP(t->item, u->item);
837    if (cmp == 0)
838    {
839      <T>AVLNode* tmp = succ(t);
840      delete t;
841      t = tmp;
842      u = y.succ(u);
843    }
844    else if (cmp < 0)
845    {
846      _hold_nodes[k++] = t;
847      t = succ(t);
848    }
849    else
850      u = y.succ(u);
851  }
852  root = _treeify(k);
853  count = k;
854}
855
856int <T>AVLSet::owns(Pix i)
857{
858  if (i == 0) return 0;
859  for (<T>AVLNode* t = leftmost(); t != 0; t = succ(t))
860    if (Pix(t) == i) return 1;
861  return 0;
862}
863
864int <T>AVLSet::OK()
865{
866  int v = 1;
867  if (root == 0)
868    v = count == 0;
869  else
870  {
871    int n = 1;
872    <T>AVLNode* trail = leftmost();
873    <T>AVLNode* t = succ(trail);
874    while (t != 0)
875    {
876      ++n;
877      v &= <T>CMP(trail->item, t->item) < 0;
878      trail = t;
879      t = succ(t);
880    }
881    v &= n == count;
882  }
883  if (!v) error("invariant failure");
884  return v;
885}
886