|
1
11 package org.eclipse.core.internal.registry;
12
13
18 public class KeyedHashSet {
19 protected static final int MINIMUM_SIZE = 7;
20 private int capacity;
21 protected int elementCount = 0;
22 protected KeyedElement[] elements;
23 protected boolean replace;
24
25 public KeyedHashSet() {
26 this(MINIMUM_SIZE, true);
27 }
28
29 public KeyedHashSet(int capacity) {
30 this(capacity, true);
31 }
32
33 public KeyedHashSet(int capacity, boolean replace) {
34 elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
35 this.replace = replace;
36 this.capacity = capacity;
37 }
38
39
44 public boolean add(KeyedElement element) {
45 int hash = hash(element);
46
47 for (int i = hash; i < elements.length; i++) {
49 if (elements[i] == null) {
50 elements[i] = element;
51 elementCount++;
52 if (shouldGrow())
54 expand();
55 return true;
56 }
57 if (elements[i].compare(element)) {
58 if (replace)
59 elements[i] = element;
60 return replace;
61 }
62 }
63
64 for (int i = 0; i < hash - 1; i++) {
66 if (elements[i] == null) {
67 elements[i] = element;
68 elementCount++;
69 if (shouldGrow())
71 expand();
72 return true;
73 }
74 if (elements[i].compare(element)) {
75 if (replace)
76 elements[i] = element;
77 return replace;
78 }
79 }
80
81 expand();
83 return add(element);
84 }
85
86 public void clear() {
87 elements = new KeyedElement[Math.max(MINIMUM_SIZE, capacity * 2)];
88 elementCount = 0;
89 }
90
91 public KeyedElement[] elements() {
92 return (KeyedElement[]) elements(new KeyedElement[elementCount]);
93 }
94
95 public Object  [] elements(Object [] result) {
96 int j = 0;
97 for (int i = 0; i < elements.length; i++) {
98 KeyedElement element = elements[i];
99 if (element != null)
100 result[j++] = element;
101 }
102 return result;
103 }
104
105
109 protected void expand() {
110 KeyedElement[] oldElements = elements;
111 elements = new KeyedElement[elements.length * 2];
112
113 int maxArrayIndex = elements.length - 1;
114 for (int i = 0; i < oldElements.length; i++) {
115 KeyedElement element = oldElements[i];
116 if (element != null) {
117 int hash = hash(element);
118 while (elements[hash] != null) {
119 hash++;
120 if (hash > maxArrayIndex)
121 hash = 0;
122 }
123 elements[hash] = element;
124 }
125 }
126 }
127
128
132 public KeyedElement get(KeyedElement key) {
133 if (elementCount == 0)
134 return null;
135 int hash = hash(key);
136
137 for (int i = hash; i < elements.length; i++) {
139 KeyedElement element = elements[i];
140 if (element == null)
141 return null;
142 if (element.compare(key))
143 return element;
144 }
145
146 for (int i = 0; i < hash - 1; i++) {
148 KeyedElement element = elements[i];
149 if (element == null)
150 return null;
151 if (element.compare(key))
152 return element;
153 }
154
155 return null;
157 }
158
159
163 public KeyedElement getByKey(Object key) {
164 if (elementCount == 0)
165 return null;
166 int hash = keyHash(key);
167
168 for (int i = hash; i < elements.length; i++) {
170 KeyedElement element = elements[i];
171 if (element == null)
172 return null;
173 if (element.getKey().equals(key))
174 return element;
175 }
176
177 for (int i = 0; i < hash - 1; i++) {
179 KeyedElement element = elements[i];
180 if (element == null)
181 return null;
182 if (element.getKey().equals(key))
183 return element;
184 }
185
186 return null;
188 }
189
190 private int hash(KeyedElement element) {
191 return Math.abs(element.getKeyHashCode()) % elements.length;
192 }
193
194 public boolean isEmpty() {
195 return elementCount == 0;
196 }
197
198 private int keyHash(Object key) {
199 return Math.abs(key.hashCode()) % elements.length;
200 }
201
202
206 protected void rehashTo(int anIndex) {
207
208 int target = anIndex;
209 int index = anIndex + 1;
210 if (index >= elements.length)
211 index = 0;
212 KeyedElement element = elements[index];
213 while (element != null) {
214 int hashIndex = hash(element);
215 boolean match;
216 if (index < target)
217 match = !(hashIndex > target || hashIndex <= index);
218 else
219 match = !(hashIndex > target && hashIndex <= index);
220 if (match) {
221 elements[target] = element;
222 target = index;
223 }
224 index++;
225 if (index >= elements.length)
226 index = 0;
227 element = elements[index];
228 }
229 elements[target] = null;
230 }
231
232 public boolean remove(KeyedElement toRemove) {
233 if (elementCount == 0)
234 return false;
235
236 int hash = hash(toRemove);
237
238 for (int i = hash; i < elements.length; i++) {
239 KeyedElement element = elements[i];
240 if (element == null)
241 return false;
242 if (element.compare(toRemove)) {
243 rehashTo(i);
244 elementCount--;
245 return true;
246 }
247 }
248
249 for (int i = 0; i < hash - 1; i++) {
250 KeyedElement element = elements[i];
251 if (element == null)
252 return false;
253 if (element.compare(toRemove)) {
254 rehashTo(i);
255 elementCount--;
256 return true;
257 }
258 }
259 return false;
260 }
261
262 public boolean removeByKey(Object key) {
263 if (elementCount == 0)
264 return false;
265 int hash = keyHash(key);
266
267 for (int i = hash; i < elements.length; i++) {
268 KeyedElement element = elements[i];
269 if (element == null)
270 return false;
271 if (element.getKey().equals(key)) {
272 rehashTo(i);
273 elementCount--;
274 return true;
275 }
276 }
277
278 for (int i = 0; i < hash - 1; i++) {
279 KeyedElement element = elements[i];
280 if (element == null)
281 return false;
282 if (element.getKey().equals(key)) {
283 rehashTo(i);
284 elementCount--;
285 return true;
286 }
287 }
288
289 return true;
290 }
291
292 private boolean shouldGrow() {
293 return elementCount > elements.length * 0.75;
294 }
295
296 public int size() {
297 return elementCount;
298 }
299
300 public String toString() {
301 StringBuffer result = new StringBuffer (100);
302 result.append("{"); boolean first = true;
304 for (int i = 0; i < elements.length; i++) {
305 if (elements[i] != null) {
306 if (first)
307 first = false;
308 else
309 result.append(", "); result.append(elements[i]);
311 }
312 }
313 result.append("}"); return result.toString();
315 }
316 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.