KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*******************************************************************************
2  * Copyright (c) 2000, 2004 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.core.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 = values.length;
38     int index = (object.hashCode() & 0x7FFFFFFF) % length;
39     Object JavaDoc current;
40     while ((current = values[index]) != null) {
41         if (current.equals(object)) return values[index] = object;
42         if (++index == length) index = 0;
43     }
44     values[index] = object;
45
46     // assumes the threshold is never equal to the size of the table
47 if (++elementSize > threshold) rehash();
48     return object;
49 }
50
51 public void clear() {
52     for (int i = this.values.length; --i >= 0;)
53         this.values[i] = null;
54     this.elementSize = 0;
55 }
56
57 public Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
58     SimpleSet result = (SimpleSet) super.clone();
59     result.elementSize = this.elementSize;
60     result.threshold = this.threshold;
61
62     int length = this.values.length;
63     result.values = new Object JavaDoc[length];
64     System.arraycopy(this.values, 0, result.values, 0, length);
65     return result;
66 }
67
68 public boolean includes(Object JavaDoc object) {
69     int length = values.length;
70     int index = (object.hashCode() & 0x7FFFFFFF) % length;
71     Object JavaDoc current;
72     while ((current = values[index]) != null) {
73         if (current.equals(object)) return true;
74         if (++index == length) index = 0;
75     }
76     return false;
77 }
78
79 public Object JavaDoc remove(Object JavaDoc object) {
80     int length = values.length;
81     int index = (object.hashCode() & 0x7FFFFFFF) % length;
82     Object JavaDoc current;
83     while ((current = values[index]) != null) {
84         if (current.equals(object)) {
85             elementSize--;
86             Object JavaDoc oldValue = values[index];
87             values[index] = null;
88             if (values[index + 1 == length ? 0 : index + 1] != null)
89                 rehash(); // only needed if a possible collision existed
90 return oldValue;
91         }
92         if (++index == length) index = 0;
93     }
94     return null;
95 }
96
97 private void rehash() {
98     SimpleSet newSet = new SimpleSet(elementSize * 2); // double the number of expected elements
99 Object JavaDoc current;
100     for (int i = values.length; --i >= 0;)
101         if ((current = values[i]) != null)
102             newSet.add(current);
103
104     this.values = newSet.values;
105     this.elementSize = newSet.elementSize;
106     this.threshold = newSet.threshold;
107 }
108
109 public String JavaDoc toString() {
110     String JavaDoc s = ""; //$NON-NLS-1$
111 Object JavaDoc object;
112     for (int i = 0, l = values.length; i < l; i++)
113         if ((object = values[i]) != null)
114             s += object.toString() + "\n"; //$NON-NLS-1$
115 return s;
116 }
117 }
118
Popular Tags