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