KickJava   Java API By Example, From Geeks To Geeks.

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


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 Common Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/cpl-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 SimpleLookupTable implements Cloneable JavaDoc {
19
20 // to avoid using Enumerations, walk the individual tables skipping nulls
21 public Object JavaDoc[] keyTable;
22 public Object JavaDoc[] valueTable;
23 public int elementSize; // number of elements in the table
24 public int threshold;
25
26 public SimpleLookupTable() {
27     this(13);
28 }
29
30 public SimpleLookupTable(int size) {
31     this.elementSize = 0;
32     this.threshold = size; // size represents the expected number of elements
33 int extraRoom = (int) (size * 1.5f);
34     if (this.threshold == extraRoom)
35         extraRoom++;
36     this.keyTable = new Object JavaDoc[extraRoom];
37     this.valueTable = new Object JavaDoc[extraRoom];
38 }
39
40 public Object JavaDoc clone() throws CloneNotSupportedException JavaDoc {
41     SimpleLookupTable result = (SimpleLookupTable) super.clone();
42     result.elementSize = this.elementSize;
43     result.threshold = this.threshold;
44
45     int length = this.keyTable.length;
46     result.keyTable = new Object JavaDoc[length];
47     System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
48
49     length = this.valueTable.length;
50     result.valueTable = new Object JavaDoc[length];
51     System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
52     return result;
53 }
54
55 public boolean containsKey(Object JavaDoc key) {
56     int length = keyTable.length;
57     int index = (key.hashCode() & 0x7FFFFFFF) % length;
58     Object JavaDoc currentKey;
59     while ((currentKey = keyTable[index]) != null) {
60         if (currentKey.equals(key)) return true;
61         if (++index == length) index = 0;
62     }
63     return false;
64 }
65
66 public Object JavaDoc get(Object JavaDoc key) {
67     int length = keyTable.length;
68     int index = (key.hashCode() & 0x7FFFFFFF) % length;
69     Object JavaDoc currentKey;
70     while ((currentKey = keyTable[index]) != null) {
71         if (currentKey.equals(key)) return valueTable[index];
72         if (++index == length) index = 0;
73     }
74     return null;
75 }
76
77 public Object JavaDoc keyForValue(Object JavaDoc valueToMatch) {
78     if (valueToMatch != null)
79         for (int i = 0, l = valueTable.length; i < l; i++)
80             if (valueToMatch.equals(valueTable[i]))
81                 return keyTable[i];
82     return null;
83 }
84
85 public Object JavaDoc put(Object JavaDoc key, Object JavaDoc value) {
86     int length = keyTable.length;
87     int index = (key.hashCode() & 0x7FFFFFFF) % length;
88     Object JavaDoc currentKey;
89     while ((currentKey = keyTable[index]) != null) {
90         if (currentKey.equals(key)) return valueTable[index] = value;
91         if (++index == length) index = 0;
92     }
93     keyTable[index] = key;
94     valueTable[index] = value;
95
96     // assumes the threshold is never equal to the size of the table
97 if (++elementSize > threshold) rehash();
98     return value;
99 }
100
101 public Object JavaDoc removeKey(Object JavaDoc key) {
102     int length = keyTable.length;
103     int index = (key.hashCode() & 0x7FFFFFFF) % length;
104     Object JavaDoc currentKey;
105     while ((currentKey = keyTable[index]) != null) {
106         if (currentKey.equals(key)) {
107             elementSize--;
108             Object JavaDoc oldValue = valueTable[index];
109             keyTable[index] = null;
110             valueTable[index] = null;
111             if (keyTable[index + 1 == length ? 0 : index + 1] != null)
112                 rehash(); // only needed if a possible collision existed
113 return oldValue;
114         }
115         if (++index == length) index = 0;
116     }
117     return null;
118 }
119
120 public void removeValue(Object JavaDoc valueToRemove) {
121     boolean rehash = false;
122     for (int i = 0, l = valueTable.length; i < l; i++) {
123         Object JavaDoc value = valueTable[i];
124         if (value != null && value.equals(valueToRemove)) {
125             elementSize--;
126             keyTable[i] = null;
127             valueTable[i] = null;
128             if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
129                 rehash = true; // only needed if a possible collision existed
130 }
131     }
132     if (rehash) rehash();
133 }
134
135 private void rehash() {
136     SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
137 Object JavaDoc currentKey;
138     for (int i = keyTable.length; --i >= 0;)
139         if ((currentKey = keyTable[i]) != null)
140             newLookupTable.put(currentKey, valueTable[i]);
141
142     this.keyTable = newLookupTable.keyTable;
143     this.valueTable = newLookupTable.valueTable;
144     this.elementSize = newLookupTable.elementSize;
145     this.threshold = newLookupTable.threshold;
146 }
147
148 public String JavaDoc toString() {
149     String JavaDoc s = ""; //$NON-NLS-1$
150 Object JavaDoc object;
151     for (int i = 0, l = valueTable.length; i < l; i++)
152         if ((object = valueTable[i]) != null)
153             s += keyTable[i].toString() + " -> " + object.toString() + "\n"; //$NON-NLS-2$ //$NON-NLS-1$
154 return s;
155 }
156 }
157
Popular Tags