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 "<T>.OXPBag.h"
28
29
30Pix <T>OXPBag::seek(<T&> item, Pix i)
31{
32  if (i == 0)
33  {
34    int l = p.low();
35    int h = p.high();
36    while (l <= h)
37    {
38      int mid = (l + h) / 2;
39      int cmp = <T>CMP(item, p[mid]);
40      if (cmp == 0)
41      {
42        while (mid > p.low() && <T>EQ(item, p[mid - 1])) --mid;
43        return p.index_to_Pix(mid);
44      }
45      else if (cmp < 0)
46        h = mid - 1;
47      else
48        l = mid + 1;
49    }
50    return 0;
51  }
52  int cmp = <T>CMP(item, p(i));
53  if (cmp == 0)
54  {
55    next(i);
56    return (<T>EQ(item, p(i)))? i : 0;
57  }
58  else if (cmp < 0)
59  {
60    int ind = p.Pix_to_index(i);
61    int l = ind;
62    int h = p.high();
63    while (l <= h)
64    {
65      int mid = (l + h) / 2;
66      cmp = <T>CMP(item, p[mid]);
67      if (cmp == 0)
68      {
69        while (mid > ind && <T>EQ(item, p[mid - 1])) --mid;
70        return p.index_to_Pix(mid);
71      }
72      else if (cmp < 0)
73        h = mid - 1;
74      else
75        l = mid + 1;
76    }
77    return 0;
78  }
79  else
80    return 0;
81}
82
83int <T>OXPBag::nof(<T&> item)
84{
85  int l = p.low();
86  int h = p.high();
87  while (l <= h)
88  {
89    int mid = (l + h) / 2;
90    int cmp = <T>CMP(item, p[mid]);
91    if (cmp == 0)
92    {
93      l = h = mid;
94      while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
95      while (h < p.high() && <T>EQ(item, p[h + 1])) ++h;
96      return h - l + 1;
97    }
98    else if (cmp < 0)
99      h = mid - 1;
100    else
101      l = mid + 1;
102  }
103  return 0;
104}
105
106Pix <T>OXPBag::add(<T&> item)
107{
108  if (count == 0)
109  {
110    ++count;
111    return p.index_to_Pix(p.add_high(item));
112  }
113  int l = p.low();
114  int h = p.high();
115  while (l <= h)
116  {
117    int mid = (l + h) / 2;
118    int cmp = <T>CMP(item, p[mid]);
119    if (cmp == 0)
120    {
121      l = mid;
122      break;
123    }
124    else if (cmp < 0)
125      h = mid - 1;
126    else
127      l = mid + 1;
128  }
129  // add on whichever side is shortest
130  ++count;
131  if (l == p.fence())
132    return p.index_to_Pix(p.add_high(item));
133  else if (l == p.low())
134    return p.index_to_Pix(p.add_low(item));
135  else
136  {
137    if (p.high() - l < l - p.low())
138    {
139      h = p.add_high(p.high_element());
140      for (int i = h - 1; i > l; --i) p[i] = p[i-1];
141    }
142    else
143    {
144      --l;
145      h = p.add_low(p.low_element());
146      for (int i = h + 1; i < l; ++i) p[i] = p[i+1];
147    }
148    p[l] = item;
149    return p.index_to_Pix(l);
150  }
151}
152
153void <T>OXPBag::del(<T&> item)
154{
155  int l = p.low();
156  int h = p.high();
157  while (l <= h)
158  {
159    int mid = (l + h) / 2;
160    int cmp = <T>CMP(item, p[mid]);
161    if (cmp == 0)
162    {
163      --count;
164      if (p.high() - mid < mid - p.low())
165      {
166        for (int i = mid; i < p.high(); ++i) p[i] = p[i+1];
167        p.del_high();
168      }
169      else
170      {
171        for (int i = mid; i > p.low(); --i) p[i] = p[i-1];
172        p.del_low();
173      }
174      return;
175    }
176    else if (cmp < 0)
177      h = mid - 1;
178    else
179      l = mid + 1;
180  }
181}
182
183void <T>OXPBag::remove(<T&> item)
184{
185  int l = p.low();
186  int h = p.high();
187  while (l <= h)
188  {
189    int mid = (l + h) / 2;
190    int cmp = <T>CMP(item, p[mid]);
191    if (cmp == 0)
192    {
193      l = h = mid;
194      while (l > p.low() && <T>EQ(item, p[l - 1])) --l;
195      while (h < p.high() && <T>EQ(item, p[h + 1])) ++h;
196      int n = h - l + 1;
197      count -= n;
198      if (p.high() - h < l - p.low())
199      {
200        h = p.high() - n;
201        for (int i = l; i <= h; ++i) p[i] = p[i+n];
202        while (n-- > 0) p.del_high();
203      }
204      else
205      {
206        l = p.low() + n;
207        for (int i = h; i >= l; --i) p[i] = p[i-n];
208        while (n-- > 0) p.del_low();
209      }
210      return;
211    }
212    else if (cmp < 0)
213      h = mid - 1;
214    else
215      l = mid + 1;
216  }
217}
218
219int <T>OXPBag::OK()
220{
221  int v = p.OK();
222  v &= count == p.length();
223  for (int i = p.low(); i < p.high(); ++i) v &= <T>CMP(p[i], p[i+1]) <= 0;
224  if (!v) error("invariant failure");
225  return v;
226}
227