001: //--------------------------------------------------------------------------
002: // Copyright (c) 1998-2004, Drew Davidson and Luke Blanshard
003: // All rights reserved.
004: //
005: // Redistribution and use in source and binary forms, with or without
006: // modification, are permitted provided that the following conditions are
007: // met:
008: //
009: // Redistributions of source code must retain the above copyright notice,
010: // this list of conditions and the following disclaimer.
011: // Redistributions in binary form must reproduce the above copyright
012: // notice, this list of conditions and the following disclaimer in the
013: // documentation and/or other materials provided with the distribution.
014: // Neither the name of the Drew Davidson nor the names of its contributors
015: // may be used to endorse or promote products derived from this software
016: // without specific prior written permission.
017: //
018: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
019: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
020: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
021: // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
022: // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
023: // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
024: // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
025: // OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
026: // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
027: // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
028: // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
029: // DAMAGE.
030: //--------------------------------------------------------------------------
031: package ognl;
032:
033: import java.util.*;
034:
035: /**
036: * A Map that uses ints as the keys.
037: * <p>Use just like any java.util.Map, except that the keys must be ints.
038: * This is much faster than creating a new Integer for each access.</p>
039: * <p>For non-Map access (faster) use the put(int, Object) method.</p>
040: * <p>This class implements Map for convenience, but this is not the most
041: * efficient usage.</p>
042: * @see java.util.HashMap
043: * @see java.util.Map
044: */
045: public class IntHashMap extends Object implements Map {
046: private Entry table[];
047: private int count;
048: private int threshold;
049: private float loadFactor;
050:
051: /*===================================================================
052: Private static classes
053: ===================================================================*/
054: private static class IntHashMapIterator implements Iterator {
055: boolean keys;
056: int index;
057: Entry table[];
058: Entry entry;
059:
060: IntHashMapIterator(Entry table[], boolean keys) {
061: super ();
062: this .table = table;
063: this .keys = keys;
064: this .index = table.length;
065: }
066:
067: /*===================================================================
068: Iterator interface
069: ===================================================================*/
070: public boolean hasNext() {
071: if (entry != null) {
072: return true;
073: }
074: while (index-- > 0) {
075: if ((entry = table[index]) != null) {
076: return true;
077: }
078: }
079: return false;
080: }
081:
082: public Object next() {
083: if (entry == null) {
084: while ((index-- > 0)
085: && ((entry = table[index]) == null)) {
086: /* do nothing */
087: }
088: }
089: if (entry != null) {
090: Entry e = entry;
091:
092: entry = e.next;
093: return keys ? new Integer(e.key) : e.value;
094: }
095: throw new NoSuchElementException("IntHashMapIterator");
096: }
097:
098: public void remove() {
099: throw new UnsupportedOperationException("remove");
100: }
101: }
102:
103: /*===================================================================
104: Public static classes
105: ===================================================================*/
106: public static class Entry extends Object {
107: int hash;
108: int key;
109: Object value;
110: Entry next;
111:
112: public Entry() {
113: super ();
114: }
115: }
116:
117: /*===================================================================
118: Constructors
119: ===================================================================*/
120: public IntHashMap(int initialCapacity, float loadFactor) {
121: super ();
122: if (initialCapacity <= 0 || loadFactor <= 0.0) {
123: throw new IllegalArgumentException();
124: }
125: this .loadFactor = loadFactor;
126: table = new Entry[initialCapacity];
127: threshold = (int) (initialCapacity * loadFactor);
128: }
129:
130: public IntHashMap(int initialCapacity) {
131: this (initialCapacity, 0.75f);
132: }
133:
134: public IntHashMap() {
135: this (101, 0.75f);
136: }
137:
138: /*===================================================================
139: Protected methods
140: ===================================================================*/
141: protected void rehash() {
142: int oldCapacity = table.length;
143: Entry oldTable[] = table;
144: int newCapacity = oldCapacity * 2 + 1;
145: Entry newTable[] = new Entry[newCapacity];
146:
147: threshold = (int) (newCapacity * loadFactor);
148: table = newTable;
149: for (int i = oldCapacity; i-- > 0;) {
150: for (Entry old = oldTable[i]; old != null;) {
151: Entry e = old;
152: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
153:
154: old = old.next;
155: e.next = newTable[index];
156: newTable[index] = e;
157: }
158: }
159: }
160:
161: /*===================================================================
162: Public methods
163: ===================================================================*/
164: public final boolean containsKey(int key) {
165: int index = (key & 0x7FFFFFFF) % table.length;
166:
167: for (Entry e = table[index]; e != null; e = e.next) {
168: if ((e.hash == key) && (e.key == key)) {
169: return true;
170: }
171: }
172: return false;
173: }
174:
175: public final Object get(int key) {
176: int index = (key & 0x7FFFFFFF) % table.length;
177:
178: for (Entry e = table[index]; e != null; e = e.next) {
179: if ((e.hash == key) && (e.key == key)) {
180: return e.value;
181: }
182: }
183: return null;
184: }
185:
186: public final Object put(int key, Object value) {
187: int index = (key & 0x7FFFFFFF) % table.length;
188:
189: if (value == null) {
190: throw new IllegalArgumentException();
191: }
192: for (Entry e = table[index]; e != null; e = e.next) {
193: if ((e.hash == key) && (e.key == key)) {
194: Object old = e.value;
195:
196: e.value = value;
197: return old;
198: }
199: }
200:
201: if (count >= threshold) {
202: // Rehash the table if the threshold is exceeded.
203: rehash();
204: return put(key, value);
205: }
206:
207: Entry e = new Entry();
208:
209: e.hash = key;
210: e.key = key;
211: e.value = value;
212: e.next = table[index];
213: table[index] = e;
214: ++count;
215: return null;
216: }
217:
218: public final Object remove(int key) {
219: int index = (key & 0x7FFFFFFF) % table.length;
220:
221: for (Entry e = table[index], prev = null; e != null; prev = e, e = e.next) {
222: if ((e.hash == key) && (e.key == key)) {
223: if (prev != null) {
224: prev.next = e.next;
225: } else {
226: table[index] = e.next;
227: }
228: --count;
229: return e.value;
230: }
231: }
232: return null;
233: }
234:
235: /*===================================================================
236: Map interface
237: ===================================================================*/
238: public int size() {
239: return count;
240: }
241:
242: public boolean isEmpty() {
243: return count == 0;
244: }
245:
246: public Object get(Object key) {
247: if (!(key instanceof Number)) {
248: throw new IllegalArgumentException(
249: "key is not an Number subclass");
250: }
251: return get(((Number) key).intValue());
252: }
253:
254: public Object put(Object key, Object value) {
255: if (!(key instanceof Number)) {
256: throw new IllegalArgumentException("key cannot be null");
257: }
258: return put(((Number) key).intValue(), value);
259: }
260:
261: public void putAll(Map otherMap) {
262: for (Iterator it = otherMap.keySet().iterator(); it.hasNext();) {
263: Object k = it.next();
264:
265: put(k, otherMap.get(k));
266: }
267: }
268:
269: public Object remove(Object key) {
270: if (!(key instanceof Number)) {
271: throw new IllegalArgumentException("key cannot be null");
272: }
273: return remove(((Number) key).intValue());
274: }
275:
276: public void clear() {
277: Entry tab[] = table;
278:
279: for (int index = tab.length; --index >= 0;) {
280: tab[index] = null;
281: }
282: count = 0;
283: }
284:
285: public boolean containsKey(Object key) {
286: if (!(key instanceof Number)) {
287: throw new InternalError("key is not an Number subclass");
288: }
289: return containsKey(((Number) key).intValue());
290: }
291:
292: public boolean containsValue(Object value) {
293: Entry tab[] = table;
294:
295: if (value == null) {
296: throw new IllegalArgumentException();
297: }
298: for (int i = tab.length; i-- > 0;) {
299: for (Entry e = tab[i]; e != null; e = e.next) {
300: if (e.value.equals(value)) {
301: return true;
302: }
303: }
304: }
305: return false;
306: }
307:
308: public Set keySet() {
309: Set result = new HashSet();
310:
311: for (Iterator it = new IntHashMapIterator(table, true); it
312: .hasNext();) {
313: result.add(it.next());
314: }
315: return result;
316: }
317:
318: public Collection values() {
319: List result = new ArrayList();
320:
321: for (Iterator it = new IntHashMapIterator(table, false); it
322: .hasNext();) {
323: result.add(it.next());
324: }
325: return result;
326: }
327:
328: public Set entrySet() {
329: throw new UnsupportedOperationException("entrySet");
330: }
331: }
|