001: /* *****************************************************************************
002: * HashIntTable.java
003: * ****************************************************************************/
004:
005: /* J_LZ_COPYRIGHT_BEGIN *******************************************************
006: * Copyright 2001-2004 Laszlo Systems, Inc. All Rights Reserved. *
007: * Use is subject to license terms. *
008: * J_LZ_COPYRIGHT_END *********************************************************/
009:
010: /**
011: * Redistribution and use of this software and associated documentation
012: * ("Software"), with or without modification, are permitted provided
013: * that the following conditions are met:
014: *
015: * 1. Redistributions of source code must retain copyright
016: * statements and notices. Redistributions must also contain a
017: * copy of this document.
018: *
019: * 2. Redistributions in binary form must reproduce the
020: * above copyright notice, this list of conditions and the
021: * following disclaimer in the documentation and/or other
022: * materials provided with the distribution.
023: *
024: * 3. The name "Exolab" must not be used to endorse or promote
025: * products derived from this Software without prior written
026: * permission of Intalio. For written permission,
027: * please contact info@exolab.org.
028: *
029: * 4. Products derived from this Software may not be called "Exolab"
030: * nor may "Exolab" appear in their names without prior written
031: * permission of Intalio. Exolab is a registered
032: * trademark of Intalio.
033: *
034: * 5. Due credit should be given to the Exolab Project
035: * (http://www.exolab.org/).
036: *
037: * THIS SOFTWARE IS PROVIDED BY INTALIO AND CONTRIBUTORS
038: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
039: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
040: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
041: * INTALIO OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
042: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
043: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
044: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
045: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
046: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
047: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
048: * OF THE POSSIBILITY OF SUCH DAMAGE.
049: *
050: * Copyright 2000 (C) Intalio Inc. All Rights Reserved.
051: *
052: */package org.openlaszlo.utils;
053:
054: import java.util.ConcurrentModificationException;
055: import java.util.Enumeration;
056: import java.util.NoSuchElementException;
057:
058: ///////////////////////////////////////////////////////////////////////////////
059: // HashIntTable
060: ///////////////////////////////////////////////////////////////////////////////
061:
062: /**
063: * This class provides unsynchronized hash get, put, remove
064: * and increment of int values. If multiple threads are accessing
065: * the table then access to the table must be synchronized.
066: *
067: * @author <a href="mohammed@intalio.com">Riad Mohammed</a>
068: */
069: public final class HashIntTable {
070: /**
071: * The array of entries
072: */
073: Entry[] table = null;
074:
075: /**
076: * The default value of the HashIntTable if the
077: * key does not exist
078: */
079: private/*final*/int defaultValue; //javac error
080:
081: /**
082: * The number of entries in the table
083: */
084: private int numberOfEntries = 0;
085:
086: /**
087: * The modification count
088: */
089: private int modificationCount = 0;
090:
091: /**
092: * Create the HashIntTable using the default
093: * size
094: */
095: public HashIntTable() {
096: this (101, 0);
097: }
098:
099: /**
100: * Create the HashIntTable with the specified
101: * size.
102: *
103: * @param size the size (must be greater than zero)
104: */
105: public HashIntTable(int size, int defaultValue) {
106: if (size <= 0) {
107: throw new IllegalArgumentException(
108: /* (non-Javadoc)
109: * @i18n.test
110: * @org-mes="The argument 'size' is not greater than 0."
111: */
112: org.openlaszlo.i18n.LaszloMessages.getMessage(
113: HashIntTable.class.getName(), "051018-121"));
114: }
115:
116: this .table = new Entry[size];
117: this .defaultValue = defaultValue;
118: }
119:
120: /**
121: * Return the size of the HashIntTable.
122: *
123: * @return the size of the HashIntTable.
124: */
125: public int size() {
126: return numberOfEntries;
127: }
128:
129: /**
130: * Return the enumeration of keys.
131: * <P>
132: * If the size of the HashIntTable changes
133: * (via put, remove, increment) while the
134: * keys are being enuemrated a
135: * ConcurrentModificationException is thrown
136: * by the enumeration.
137: *
138: * @return the enumeration of keys.
139: */
140: public Enumeration keys() {
141: return new KeysEnumeration(modificationCount, table, this );
142: }
143:
144: /**
145: * Get the value of the specified key. If the key does not
146: * exist in the table return the default value.
147: *
148: * @param key the key. Cannot be null.
149: * @return the value of the key in the table
150: */
151: public int get(Object key) {
152: if (null == key) {
153: throw new IllegalArgumentException(
154: /* (non-Javadoc)
155: * @i18n.test
156: * @org-mes="The arguments 'key' is null."
157: */
158: org.openlaszlo.i18n.LaszloMessages.getMessage(
159: HashIntTable.class.getName(), "051018-172"));
160: }
161:
162: // get the hash code of the key
163: int hashCode = key.hashCode();
164: // get the entry at the index
165: Entry entry = table[(hashCode & 0x7FFFFFFF) % table.length];
166:
167: // loop over the entries looking for a match
168: while (null != entry) {
169: if ((entry.hashCode == hashCode) && (entry.key.equals(key))) {
170: return entry.value;
171: }
172: // try the next entry
173: entry = entry.next;
174: }
175: // failed - return defalut value
176: return defaultValue;
177: }
178:
179: /**
180: * Check if key exists
181: *
182: * @param key the key. Cannot be null.
183: * @return the value of the key in the table
184: */
185: public boolean containsKey(Object key) {
186: if (null == key) {
187: throw new IllegalArgumentException(
188: /* (non-Javadoc)
189: * @i18n.test
190: * @org-mes="The arguments 'key' is null."
191: */
192: org.openlaszlo.i18n.LaszloMessages.getMessage(
193: HashIntTable.class.getName(), "051018-172"));
194: }
195:
196: // get the hash code of the key
197: int hashCode = key.hashCode();
198: // get the entry at the index
199: Entry entry = table[(hashCode & 0x7FFFFFFF) % table.length];
200:
201: // loop over the entries looking for a match
202: while (null != entry) {
203: if ((entry.hashCode == hashCode) && (entry.key.equals(key))) {
204: return true;
205: }
206: // try the next entry
207: entry = entry.next;
208: }
209: // failed - return false
210: return false;
211: }
212:
213: /**
214: * Remove the value for specified key
215: *
216: * @param key the key. Cannot be null.
217: * @return the old value. If the key does not exist in the
218: * table return the default value.
219: */
220: public int remove(Object key) {
221: if (null == key) {
222: throw new IllegalArgumentException(
223: /* (non-Javadoc)
224: * @i18n.test
225: * @org-mes="The arguments 'key' is null."
226: */
227: org.openlaszlo.i18n.LaszloMessages.getMessage(
228: HashIntTable.class.getName(), "051018-172"));
229: }
230:
231: // get the hash code of the key
232: int hashCode = key.hashCode();
233: // the index in the table of the key
234: int index = (hashCode & 0x7FFFFFFF) % table.length;
235: // get the entry at the index
236: Entry entry = table[index];
237: // the previous entry to the current entry
238: Entry previousEntry = null;
239:
240: // loop over the entries looking for a match
241: while (null != entry) {
242: if ((entry.hashCode == hashCode) && (entry.key.equals(key))) {
243: // remove the current entry
244: if (null == previousEntry) {
245: table[index] = entry.next;
246: } else {
247: previousEntry.next = entry.next;
248: }
249: // decrement the size
250: --numberOfEntries;
251: // increment the mod count
252: ++modificationCount;
253: return entry.value;
254: }
255: // set the previous entry
256: previousEntry = entry;
257: // try the next entry
258: entry = entry.next;
259: }
260: // failed - return default value
261: return defaultValue;
262: }
263:
264: /**
265: * Associate the specified key with the
266: * specified value.
267: *
268: * @param key the key. Cannot be null
269: * @param value the new value
270: * @return the existing value. If the
271: * key does not exist in the table
272: * return the default value.
273: */
274: public int put(Object key, int value) {
275: if (null == key) {
276: throw new IllegalArgumentException(
277: /* (non-Javadoc)
278: * @i18n.test
279: * @org-mes="The arguments 'key' is null."
280: */
281: org.openlaszlo.i18n.LaszloMessages.getMessage(
282: HashIntTable.class.getName(), "051018-172"));
283: }
284:
285: // get the hash code of the key
286: int hashCode = key.hashCode();
287: // the index in the table of the key
288: int index = (hashCode & 0x7FFFFFFF) % table.length;
289: // the current entry examined - get the entry at the index
290: Entry entry = table[index];
291: // the previous entry to the current entry
292: Entry previousEntry = null;
293:
294: // loop over the entries looking for a match
295: while (null != entry) {
296: if ((entry.hashCode == hashCode) && (entry.key.equals(key))) {
297: // get the old value
298: int oldValue = entry.value;
299: // set the new value
300: entry.value = value;
301: return oldValue;
302: }
303: // set the previous entry
304: previousEntry = entry;
305: // try the next entry
306: entry = entry.next;
307: }
308:
309: // add a new entry
310: if (null == previousEntry) {
311: table[index] = new Entry(key, hashCode, value);
312: } else {
313: previousEntry.next = new Entry(key, hashCode, value);
314: }
315:
316: // increment the size
317: ++numberOfEntries;
318: // increment the mod count
319: ++modificationCount;
320: // return value
321: return value;
322: }
323:
324: /**
325: * Increment the value associated with the specified key
326: * by the specified amount.
327: * If key does not exist in the table then increment the
328: * default value and store the result
329: *
330: * @param key the key. Cannot be null
331: * @param increment the increment
332: * @return the incremented value
333: */
334: public int increment(Object key, int increment) {
335: if (null == key) {
336: throw new IllegalArgumentException(
337: /* (non-Javadoc)
338: * @i18n.test
339: * @org-mes="The arguments 'key' is null."
340: */
341: org.openlaszlo.i18n.LaszloMessages.getMessage(
342: HashIntTable.class.getName(), "051018-172"));
343: }
344:
345: // get the hash code of the key
346: int hashCode = key.hashCode();
347: // the index in the table of the key
348: int index = (hashCode & 0x7FFFFFFF) % table.length;
349: // the current entry examined - get the entry at the index
350: Entry entry = table[index];
351: // the previous entry to the current entry
352: Entry previousEntry = null;
353:
354: // loop over the entries looking for a match
355: while (null != entry) {
356: if ((entry.hashCode == hashCode) && (entry.key.equals(key))) {
357: // set the new value
358: entry.value += increment;
359: return entry.value;
360: }
361: // set the previous entry
362: previousEntry = entry;
363: // try the next entry
364: entry = entry.next;
365: }
366:
367: // set the new value
368: int value = defaultValue + increment;
369:
370: // add a new entry
371: if (null == previousEntry) {
372: table[index] = new Entry(key, hashCode, value);
373: } else {
374: previousEntry.next = new Entry(key, hashCode, value);
375: }
376:
377: // increment the size
378: ++numberOfEntries;
379: // increment the mod count
380: ++modificationCount;
381: // return value
382: return value;
383: }
384:
385: public static void main(String args[]) {
386: HashIntTable table = new HashIntTable();
387: Object[] keys = new Object[4];
388:
389: for (int i = keys.length; --i >= 0;) {
390: final String name = "Key" + i;
391: keys[i] = new Object() {
392: public String toString() {
393: return name;
394: }
395: };
396: }
397:
398: System.out.println("size " + table.size());
399: System.out.println("get " + keys[0]);
400: System.out.println("= " + table.get(keys[0]));
401:
402: for (int i = keys.length; --i >= 0;) {
403: table.put(keys[i], i);
404: }
405:
406: System.out.println("size " + table.size());
407:
408: for (int i = keys.length; --i >= 0;) {
409: System.out.println("get " + keys[i]);
410: System.out.println("= " + table.get(keys[i]));
411: }
412:
413: for (int i = keys.length; --i >= 0;) {
414: table.increment(keys[i], 100);
415: }
416:
417: System.out.println("size " + table.size());
418:
419: for (int i = keys.length; --i >= 0;) {
420: System.out.println("get " + keys[i]);
421: System.out.println("= " + table.get(keys[i]));
422: }
423:
424: for (int i = keys.length; --i >= 0;) {
425: System.out.println("remove " + keys[i]);
426: System.out.println("= " + table.remove(keys[i]));
427: }
428:
429: System.out.println("size " + table.size());
430:
431: for (int i = keys.length; --i >= 0;) {
432: System.out.println("get " + keys[i]);
433: System.out.println("= " + table.get(keys[i]));
434: }
435:
436: for (int i = keys.length; --i >= 0;) {
437: System.out.println("remove " + keys[i]);
438: System.out.println("= " + table.remove(keys[i]));
439: }
440:
441: System.out.println("size " + table.size());
442:
443: for (int i = keys.length; --i >= 0;) {
444: System.out.println("get " + keys[i]);
445: System.out.println("= " + table.get(keys[i]));
446: }
447:
448: for (int i = keys.length; --i >= 0;) {
449: table.increment(keys[i], 100);
450: }
451:
452: System.out.println("size " + table.size());
453:
454: for (int i = keys.length; --i >= 0;) {
455: System.out.println("get " + keys[i]);
456: System.out.println("= " + table.get(keys[i]));
457: }
458:
459: for (int i = keys.length; --i >= 0;) {
460: table.put(keys[i], i);
461: }
462:
463: System.out.println("size " + table.size());
464:
465: for (int i = keys.length; --i >= 0;) {
466: System.out.println("get " + keys[i]);
467: System.out.println("= " + table.get(keys[i]));
468: }
469:
470: for (Enumeration e = table.keys(); e.hasMoreElements();) {
471: System.out.println("key " + e.nextElement());
472: }
473: }
474:
475: }
476:
477: /**
478: * The Enumeration of keys in the HashIntTable
479: */
480: class KeysEnumeration implements Enumeration {
481: /**
482: * The expected modification count of
483: * the underlying HashIntTable
484: */
485: final int expectedModificationCount;
486:
487: /**
488: * The current index in the table whose
489: * entries are being examined
490: */
491: private int index = -1;
492:
493: /**
494: * The current entry being examined
495: */
496: Entry entry = null;
497:
498: Entry[] table;
499: HashIntTable ht;
500:
501: /**
502: * Create the KeysEnumeration
503: *
504: * @param modificationCount the current
505: * modification count of the
506: * underlying HashIntTable
507: */
508: KeysEnumeration(int modificationCount, Entry[] table,
509: HashIntTable ht) {
510: this .expectedModificationCount = modificationCount;
511: this .table = table;
512: this .ht = ht;
513: }
514:
515: /**
516: * Return true if there is a next element to return in the
517: * enumeration
518: *
519: * @return true if there is a next element to return in the
520: * enumeration
521: */
522: public boolean hasMoreElements() {
523: if (null == entry) {
524: for (; ++index < table.length;) {
525: entry = table[index];
526:
527: if (null != entry) {
528: return true;
529: }
530: }
531: }
532:
533: return null != entry;
534: }
535:
536: /**
537: * Return the next element in the enumeration
538: *
539: * @return the next element in the enumeration
540: * @throws NoSuchElementException if there is no
541: * next element in the enumeration
542: */
543: public Object nextElement() {
544: if (!hasMoreElements()) {
545: throw new NoSuchElementException(
546: /* (non-Javadoc)
547: * @i18n.test
548: * @org-mes="No more elements in exception."
549: */
550: org.openlaszlo.i18n.LaszloMessages.getMessage(
551: HashIntTable.class.getName(), "051018-589"));
552: }
553:
554: // get the key from the entry
555: Object key = entry.key;
556: // set the entry to the next entry
557: entry = entry.next;
558:
559: return key;
560: }
561: }
562:
563: /**
564: * The class that stores the association between the
565: * key and the int, with a pointer to the next Entry
566: */
567: class Entry {
568: /**
569: * The key
570: */
571: final Object key;
572:
573: /**
574: * The hash code of the key
575: */
576: final int hashCode;
577:
578: /**
579: * The value
580: */
581: int value;
582:
583: /**
584: * The next entry
585: */
586: Entry next = null;
587:
588: /**
589: * Create the Entry with the specified
590: * arguments
591: *
592: * @param key the key
593: * @param value the value
594: */
595: Entry(Object key, int hashCode, int value) {
596: this.key = key;
597: this.hashCode = hashCode;
598: this.value = value;
599: }
600: }
|