KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > compiler > util > SimpleSet


1 /*******************************************************************************
2  * Copyright (c) 2000, 2007 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jdt.internal.compiler.util;
12
13 /**
14  * A simple lookup table is a non-synchronized Hashtable, whose keys
15  * and values are Objects. It also uses linear probing to resolve collisions
16  * rather than a linked list of hash table entries.
17  */
18 public final class SimpleSet implements Cloneable JavaDoc {
19
20 // to avoid using Enumerations, walk the individual values skipping nulls
21 public Object JavaDoc[] values;
22 public int elementSize; // number of elements in the table
23 public int threshold;
24
25 public SimpleSet() {
26     this(13);
27 }
28
29 public SimpleSet(int size) {
30     if (size < 3) size = 3;
31     this.elementSize = 0;
32     this.threshold = size + 1; // size is the expected number of elements
33 this.values = new Object JavaDoc[2 * size + 1];
34 }
35
36 public Object JavaDoc add(Object JavaDoc object) {
37     int length = this.values.length;
38     int index = (object.hashCode() & 0x7FFFFFFF) % length;
39     Object JavaDoc current;
40     while ((current = this.values[index]) != null) {
41         if (current.equals(object)) return this.values[index] = object;
42         if (++index == length) index = 0;
43     }
44     this.values[index] = object;
45
46     // assumes the threshold is never equal to the size of the table
47 if (++this.elementSize > this.threshold) rehash();
48     return object;
49 }
50
51 public Object JavaDoc addIfNotIncluded(Object JavaDoc object) {
52     int length = this.values.length;
53     int index = (object.hashCode() & 0x7FFFFFFF) % length;
54     Object JavaDoc current;
55     while ((current = this.values[index]) != null) {
56         if (current.equals(object)) return null; // already existed
57 if (++index == length) index = 0;
58     }
59     this.values[index] = object;
60
61     // assumes the threshold is never equal to the size of the table
62 if (++this.elementSize > this.threshold) rehash();
63     return object;
64 }
65
66 public void asArray(Object JavaDoc[] copy) {
67     if (this.elementSize != copy.length)
68         throw new IllegalArgumentException JavaDoc();
69     int index = this.elementSize;
70     for (int i = 0, l = this.values.length; i < l && index > 0; i++)
71         if (this.values[i] != null)
72             copy[--index] = this.values[i];
73 }
74
75 public void clear() {
76     for (int i = this.values.length; --i >= 0;)
77         this.values[i] = null;
78     this.elementSize = 0;
79 }
80
81 public Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
82     SimpleSet result = (SimpleSet) super.clone();
83     result.elementSize = this.elementSize;
84     result.threshold = this.threshold;
85
86     int length = this.values.length;
87     result.values = new Object JavaDoc[length];
88     System.arraycopy(this.values, 0, result.values, 0, length);
89     return result;
90 }
91
92 public boolean includes(Object JavaDoc object) {
93     int length = values.length;
94     int index = (object.hashCode() & 0x7FFFFFFF) % length;
95     Object JavaDoc current;
96     while ((current = values[index]) != null) {
97         if (current.equals(object)) return true;
98         if (++index == length) index = 0;
99     }
100     return false;
101 }
102
103 public Object JavaDoc remove(Object JavaDoc object) {
104     int length = values.length;
105     int index = (object.hashCode() & 0x7FFFFFFF) % length;
106     Object JavaDoc current;
107     while ((current = values[index]) != null) {
108         if (current.equals(object)) {
109             elementSize--;
110             Object JavaDoc oldValue = values[index];
111             values[index] = null;
112             if (values[index + 1 == length ? 0 : index + 1] != null)
113                 rehash(); // only needed if a possible collision existed
114 return oldValue;
115         }
116         if (++index == length) index = 0;
117     }
118     return null;
119 }
120
121 private void rehash() {
122     SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number of expected elements
123 Object JavaDoc current;
124     for (int i = values.length; --i >= 0;)
125         if ((current = values[i]) != null)
126             newSet.add(current);
127
128     this.values = newSet.values;
129     this.elementSize = newSet.elementSize;
130     this.threshold = newSet.threshold;
131 }
132
133 public String JavaDoc toString() {
134     String JavaDoc s = ""; //$NON-NLS-1$
135 Object JavaDoc object;
136     for (int i = 0, l = values.length; i < l; i++)
137         if ((object = values[i]) != null)
138             s += object.toString() + "\n"; //$NON-NLS-1$
139 return s;
140 }
141 }
142
Popular Tags