01c61a6f2b22b1a07ad866dea7166293cf693084
[phpeclipse.git] / net.sourceforge.phpeclipse / src / net / sourceforge / phpdt / internal / core / util / SimpleLookupTable.java
1 /*******************************************************************************
2  * Copyright (c) 2000, 2003 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 net.sourceforge.phpdt.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 {
19
20 // to avoid using Enumerations, walk the individual tables skipping nulls
21 public Object[] keyTable;
22 public Object[] 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         if (size < 3) size = 3;
32         this.elementSize = 0;
33         this.threshold = size + 1; // size is the expected number of elements
34         int tableLength = 2 * size + 1;
35         this.keyTable = new Object[tableLength];
36         this.valueTable = new Object[tableLength];
37 }
38
39 public Object clone() throws CloneNotSupportedException {
40         SimpleLookupTable result = (SimpleLookupTable) super.clone();
41         result.elementSize = this.elementSize;
42         result.threshold = this.threshold;
43
44         int length = this.keyTable.length;
45         result.keyTable = new Object[length];
46         System.arraycopy(this.keyTable, 0, result.keyTable, 0, length);
47
48         length = this.valueTable.length;
49         result.valueTable = new Object[length];
50         System.arraycopy(this.valueTable, 0, result.valueTable, 0, length);
51         return result;
52 }
53
54 public boolean containsKey(Object key) {
55         int length = keyTable.length;
56         int index = (key.hashCode() & 0x7FFFFFFF) % length;
57         Object currentKey;
58         while ((currentKey = keyTable[index]) != null) {
59                 if (currentKey.equals(key)) return true;
60                 if (++index == length) index = 0;
61         }
62         return false;
63 }
64
65 public Object get(Object key) {
66         int length = keyTable.length;
67         int index = (key.hashCode() & 0x7FFFFFFF) % length;
68         Object currentKey;
69         while ((currentKey = keyTable[index]) != null) {
70                 if (currentKey.equals(key)) return valueTable[index];
71                 if (++index == length) index = 0;
72         }
73         return null;
74 }
75
76 public Object keyForValue(Object valueToMatch) {
77         if (valueToMatch != null)
78                 for (int i = 0, l = valueTable.length; i < l; i++)
79                         if (valueToMatch.equals(valueTable[i]))
80                                 return keyTable[i];
81         return null;
82 }
83
84 public Object put(Object key, Object value) {
85         int length = keyTable.length;
86         int index = (key.hashCode() & 0x7FFFFFFF) % length;
87         Object currentKey;
88         while ((currentKey = keyTable[index]) != null) {
89                 if (currentKey.equals(key)) return valueTable[index] = value;
90                 if (++index == length) index = 0;
91         }
92         keyTable[index] = key;
93         valueTable[index] = value;
94
95         // assumes the threshold is never equal to the size of the table
96         if (++elementSize > threshold) rehash();
97         return value;
98 }
99
100 public void removeKey(Object key) {
101         int length = keyTable.length;
102         int index = (key.hashCode() & 0x7FFFFFFF) % length;
103         Object currentKey;
104         while ((currentKey = keyTable[index]) != null) {
105                 if (currentKey.equals(key)) {
106                         elementSize--;
107                         keyTable[index] = null;
108                         valueTable[index] = null;
109                         if (keyTable[index + 1 == length ? 0 : index + 1] != null)
110                                 rehash(); // only needed if a possible collision existed
111                         return;
112                 }
113                 if (++index == length) index = 0;
114         }
115 }
116
117 public void removeValue(Object valueToRemove) {
118         boolean rehash = false;
119         for (int i = 0, l = valueTable.length; i < l; i++) {
120                 Object value = valueTable[i];
121                 if (value != null && value.equals(valueToRemove)) {
122                         elementSize--;
123                         keyTable[i] = null;
124                         valueTable[i] = null;
125                         if (!rehash && keyTable[i + 1 == l ? 0 : i + 1] != null)
126                                 rehash = true; // only needed if a possible collision existed
127                 }
128         }
129         if (rehash) rehash();
130 }
131
132 private void rehash() {
133         SimpleLookupTable newLookupTable = new SimpleLookupTable(elementSize * 2); // double the number of expected elements
134         Object currentKey;
135         for (int i = keyTable.length; --i >= 0;)
136                 if ((currentKey = keyTable[i]) != null)
137                         newLookupTable.put(currentKey, valueTable[i]);
138
139         this.keyTable = newLookupTable.keyTable;
140         this.valueTable = newLookupTable.valueTable;
141         this.elementSize = newLookupTable.elementSize;
142         this.threshold = newLookupTable.threshold;
143 }
144
145 public String toString() {
146         String s = ""; //$NON-NLS-1$
147         Object object;
148         for (int i = 0, l = valueTable.length; i < l; i++)
149                 if ((object = valueTable[i]) != null)
150                         s += keyTable[i].toString() + " -> " + object.toString() + "\n";        //$NON-NLS-2$ //$NON-NLS-1$
151         return s;
152 }
153 }