001: /*******************************************************************************
002: * Copyright (c) 2000, 2007 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jdt.internal.compiler.util;
011:
012: /**
013: * A simple lookup table is a non-synchronized Hashtable, whose keys
014: * and values are Objects. It also uses linear probing to resolve collisions
015: * rather than a linked list of hash table entries.
016: */
017: public final class SimpleSet implements Cloneable {
018:
019: // to avoid using Enumerations, walk the individual values skipping nulls
020: public Object[] values;
021: public int elementSize; // number of elements in the table
022: public int threshold;
023:
024: public SimpleSet() {
025: this (13);
026: }
027:
028: public SimpleSet(int size) {
029: if (size < 3)
030: size = 3;
031: this .elementSize = 0;
032: this .threshold = size + 1; // size is the expected number of elements
033: this .values = new Object[2 * size + 1];
034: }
035:
036: public Object add(Object object) {
037: int length = this .values.length;
038: int index = (object.hashCode() & 0x7FFFFFFF) % length;
039: Object current;
040: while ((current = this .values[index]) != null) {
041: if (current.equals(object))
042: return this .values[index] = object;
043: if (++index == length)
044: index = 0;
045: }
046: this .values[index] = object;
047:
048: // assumes the threshold is never equal to the size of the table
049: if (++this .elementSize > this .threshold)
050: rehash();
051: return object;
052: }
053:
054: public Object addIfNotIncluded(Object object) {
055: int length = this .values.length;
056: int index = (object.hashCode() & 0x7FFFFFFF) % length;
057: Object current;
058: while ((current = this .values[index]) != null) {
059: if (current.equals(object))
060: return null; // already existed
061: if (++index == length)
062: index = 0;
063: }
064: this .values[index] = object;
065:
066: // assumes the threshold is never equal to the size of the table
067: if (++this .elementSize > this .threshold)
068: rehash();
069: return object;
070: }
071:
072: public void asArray(Object[] copy) {
073: if (this .elementSize != copy.length)
074: throw new IllegalArgumentException();
075: int index = this .elementSize;
076: for (int i = 0, l = this .values.length; i < l && index > 0; i++)
077: if (this .values[i] != null)
078: copy[--index] = this .values[i];
079: }
080:
081: public void clear() {
082: for (int i = this .values.length; --i >= 0;)
083: this .values[i] = null;
084: this .elementSize = 0;
085: }
086:
087: public Object clone() throws CloneNotSupportedException {
088: SimpleSet result = (SimpleSet) super .clone();
089: result.elementSize = this .elementSize;
090: result.threshold = this .threshold;
091:
092: int length = this .values.length;
093: result.values = new Object[length];
094: System.arraycopy(this .values, 0, result.values, 0, length);
095: return result;
096: }
097:
098: public boolean includes(Object object) {
099: int length = values.length;
100: int index = (object.hashCode() & 0x7FFFFFFF) % length;
101: Object current;
102: while ((current = values[index]) != null) {
103: if (current.equals(object))
104: return true;
105: if (++index == length)
106: index = 0;
107: }
108: return false;
109: }
110:
111: public Object remove(Object object) {
112: int length = values.length;
113: int index = (object.hashCode() & 0x7FFFFFFF) % length;
114: Object current;
115: while ((current = values[index]) != null) {
116: if (current.equals(object)) {
117: elementSize--;
118: Object oldValue = values[index];
119: values[index] = null;
120: if (values[index + 1 == length ? 0 : index + 1] != null)
121: rehash(); // only needed if a possible collision existed
122: return oldValue;
123: }
124: if (++index == length)
125: index = 0;
126: }
127: return null;
128: }
129:
130: private void rehash() {
131: SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number of expected elements
132: Object current;
133: for (int i = values.length; --i >= 0;)
134: if ((current = values[i]) != null)
135: newSet.add(current);
136:
137: this .values = newSet.values;
138: this .elementSize = newSet.elementSize;
139: this .threshold = newSet.threshold;
140: }
141:
142: public String toString() {
143: String s = ""; //$NON-NLS-1$
144: Object object;
145: for (int i = 0, l = values.length; i < l; i++)
146: if ((object = values[i]) != null)
147: s += object.toString() + "\n"; //$NON-NLS-1$
148: return s;
149: }
150: }
|