KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > openlaszlo > utils > HashIntTable


1 /* *****************************************************************************
2  * HashIntTable.java
3  * ****************************************************************************/

4
5 /* J_LZ_COPYRIGHT_BEGIN *******************************************************
6 * Copyright 2001-2004 Laszlo Systems, Inc. All Rights Reserved. *
7 * Use is subject to license terms. *
8 * J_LZ_COPYRIGHT_END *********************************************************/

9
10
11 /**
12  * Redistribution and use of this software and associated documentation
13  * ("Software"), with or without modification, are permitted provided
14  * that the following conditions are met:
15  *
16  * 1. Redistributions of source code must retain copyright
17  * statements and notices. Redistributions must also contain a
18  * copy of this document.
19  *
20  * 2. Redistributions in binary form must reproduce the
21  * above copyright notice, this list of conditions and the
22  * following disclaimer in the documentation and/or other
23  * materials provided with the distribution.
24  *
25  * 3. The name "Exolab" must not be used to endorse or promote
26  * products derived from this Software without prior written
27  * permission of Intalio. For written permission,
28  * please contact info@exolab.org.
29  *
30  * 4. Products derived from this Software may not be called "Exolab"
31  * nor may "Exolab" appear in their names without prior written
32  * permission of Intalio. Exolab is a registered
33  * trademark of Intalio.
34  *
35  * 5. Due credit should be given to the Exolab Project
36  * (http://www.exolab.org/).
37  *
38  * THIS SOFTWARE IS PROVIDED BY INTALIO AND CONTRIBUTORS
39  * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
40  * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
41  * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
42  * INTALIO OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
43  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
44  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
45  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
47  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
49  * OF THE POSSIBILITY OF SUCH DAMAGE.
50  *
51  * Copyright 2000 (C) Intalio Inc. All Rights Reserved.
52  *
53  */

54
55
56 package org.openlaszlo.utils;
57
58 import java.util.ConcurrentModificationException JavaDoc;
59 import java.util.Enumeration JavaDoc;
60 import java.util.NoSuchElementException JavaDoc;
61
62 ///////////////////////////////////////////////////////////////////////////////
63
// HashIntTable
64
///////////////////////////////////////////////////////////////////////////////
65

66 /**
67  * This class provides unsynchronized hash get, put, remove
68  * and increment of int values. If multiple threads are accessing
69  * the table then access to the table must be synchronized.
70  *
71  * @author <a HREF="mohammed@intalio.com">Riad Mohammed</a>
72  */

73 public final class HashIntTable
74 {
75     /**
76      * The array of entries
77      */

78     Entry[] table = null;
79
80     /**
81      * The default value of the HashIntTable if the
82      * key does not exist
83      */

84     private /*final*/ int defaultValue; //javac error
85

86     /**
87      * The number of entries in the table
88      */

89     private int numberOfEntries = 0;
90
91     /**
92      * The modification count
93      */

94     private int modificationCount = 0;
95     
96
97     /**
98      * Create the HashIntTable using the default
99      * size
100      */

101     public HashIntTable()
102     {
103         this(101, 0);
104     }
105
106
107     /**
108      * Create the HashIntTable with the specified
109      * size.
110      *
111      * @param size the size (must be greater than zero)
112      */

113     public HashIntTable(int size, int defaultValue)
114     {
115         if (size <= 0) {
116             throw new IllegalArgumentException JavaDoc("The argument 'size' is not greater than 0.");
117         }
118
119         this.table = new Entry[size];
120         this.defaultValue = defaultValue;
121     }
122
123     /**
124      * Return the size of the HashIntTable.
125      *
126      * @return the size of the HashIntTable.
127      */

128     public int size()
129     {
130         return numberOfEntries;
131     }
132
133
134     /**
135      * Return the enumeration of keys.
136      * <P>
137      * If the size of the HashIntTable changes
138      * (via put, remove, increment) while the
139      * keys are being enuemrated a
140      * ConcurrentModificationException is thrown
141      * by the enumeration.
142      *
143      * @return the enumeration of keys.
144      */

145     public Enumeration JavaDoc keys()
146     {
147         return new KeysEnumeration(modificationCount, table, this);
148     }
149
150     /**
151      * Get the value of the specified key. If the key does not
152      * exist in the table return the default value.
153      *
154      * @param key the key. Cannot be null.
155      * @return the value of the key in the table
156      */

157     public int get(Object JavaDoc key)
158     {
159         if (null == key) {
160             throw new IllegalArgumentException JavaDoc("The arguments 'key' is null.");
161         }
162
163         // get the hash code of the key
164
int hashCode = key.hashCode();
165         // get the entry at the index
166
Entry entry = table[(hashCode & 0x7FFFFFFF) % table.length];
167
168         // loop over the entries looking for a match
169
while (null != entry) {
170             if ((entry.hashCode == hashCode) &&
171                 (entry.key.equals(key))) {
172                 return entry.value;
173             }
174             // try the next entry
175
entry = entry.next;
176         }
177         // failed - return defalut value
178
return defaultValue;
179     }
180
181     /**
182      * Check if key exists
183      *
184      * @param key the key. Cannot be null.
185      * @return the value of the key in the table
186      */

187     public boolean containsKey(Object JavaDoc key)
188     {
189         if (null == key) {
190             throw new IllegalArgumentException JavaDoc("The arguments 'key' is null.");
191         }
192
193         // get the hash code of the key
194
int hashCode = key.hashCode();
195         // get the entry at the index
196
Entry entry = table[(hashCode & 0x7FFFFFFF) % table.length];
197
198         // loop over the entries looking for a match
199
while (null != entry) {
200             if ((entry.hashCode == hashCode) &&
201                 (entry.key.equals(key))) {
202                 return true;
203             }
204             // try the next entry
205
entry = entry.next;
206         }
207         // failed - return false
208
return false;
209     }
210
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 JavaDoc key)
221     {
222         if (null == key) {
223             throw new IllegalArgumentException JavaDoc("The arguments 'key' is null.");
224         }
225
226         // get the hash code of the key
227
int hashCode = key.hashCode();
228         // the index in the table of the key
229
int index = (hashCode & 0x7FFFFFFF) % table.length;
230         // get the entry at the index
231
Entry entry = table[index];
232         // the previous entry to the current entry
233
Entry previousEntry = null;
234
235         // loop over the entries looking for a match
236
while (null != entry) {
237             if ((entry.hashCode == hashCode) &&
238                 (entry.key.equals(key))) {
239                 // remove the current entry
240
if (null == previousEntry) {
241                     table[index] = entry.next;
242                 }
243                 else {
244                     previousEntry.next = entry.next;
245                 }
246                 // decrement the size
247
--numberOfEntries;
248                 // increment the mod count
249
++modificationCount;
250                 return entry.value;
251             }
252             // set the previous entry
253
previousEntry = entry;
254             // try the next entry
255
entry = entry.next;
256         }
257         // failed - return default value
258
return defaultValue;
259     }
260
261
262     /**
263      * Associate the specified key with the
264      * specified value.
265      *
266      * @param key the key. Cannot be null
267      * @param value the new value
268      * @return the existing value. If the
269      * key does not exist in the table
270      * return the default value.
271      */

272     public int put(Object JavaDoc key, int value)
273     {
274         if (null == key) {
275             throw new IllegalArgumentException JavaDoc("The arguments 'key' is null.");
276         }
277
278         // get the hash code of the key
279
int hashCode = key.hashCode();
280         // the index in the table of the key
281
int index = (hashCode & 0x7FFFFFFF) % table.length;
282         // the current entry examined - get the entry at the index
283
Entry entry = table[index];
284         // the previous entry to the current entry
285
Entry previousEntry = null;
286
287         // loop over the entries looking for a match
288
while (null != entry) {
289             if ((entry.hashCode == hashCode) &&
290                 (entry.key.equals(key))) {
291                 // get the old value
292
int oldValue = entry.value;
293                 // set the new value
294
entry.value = value;
295                 return oldValue;
296             }
297             // set the previous entry
298
previousEntry = entry;
299             // try the next entry
300
entry = entry.next;
301         }
302
303         // add a new entry
304
if (null == previousEntry) {
305             table[index] = new Entry(key, hashCode, value);
306         }
307         else {
308             previousEntry.next= new Entry(key, hashCode, value);
309         }
310
311         // increment the size
312
++numberOfEntries;
313         // increment the mod count
314
++modificationCount;
315         // return value
316
return value;
317     }
318
319
320     /**
321      * Increment the value associated with the specified key
322      * by the specified amount.
323      * If key does not exist in the table then increment the
324      * default value and store the result
325      *
326      * @param key the key. Cannot be null
327      * @param increment the increment
328      * @return the incremented value
329      */

330     public int increment(Object JavaDoc key, int increment)
331     {
332         if (null == key) {
333             throw new IllegalArgumentException JavaDoc("The arguments 'key' is null.");
334         }
335
336         // get the hash code of the key
337
int hashCode = key.hashCode();
338         // the index in the table of the key
339
int index = (hashCode & 0x7FFFFFFF) % table.length;
340         // the current entry examined - get the entry at the index
341
Entry entry = table[index];
342         // the previous entry to the current entry
343
Entry previousEntry = null;
344
345         // loop over the entries looking for a match
346
while (null != entry) {
347             if ((entry.hashCode == hashCode) &&
348                 (entry.key.equals(key))) {
349                 // set the new value
350
entry.value += increment;
351                 return entry.value;
352             }
353             // set the previous entry
354
previousEntry = entry;
355             // try the next entry
356
entry = entry.next;
357         }
358
359         // set the new value
360
int value = defaultValue + increment;
361
362         // add a new entry
363
if (null == previousEntry) {
364             table[index] = new Entry(key, hashCode, value);
365         }
366         else {
367             previousEntry.next= new Entry(key, hashCode, value);
368         }
369
370         // increment the size
371
++numberOfEntries;
372         // increment the mod count
373
++modificationCount;
374         // return value
375
return value;
376     }
377
378
379     public static void main (String JavaDoc args[]) {
380         HashIntTable table = new HashIntTable();
381         Object JavaDoc[] keys = new Object JavaDoc[4];
382
383         for (int i = keys.length; --i >= 0;) {
384             final String JavaDoc name = "Key" + i;
385             keys[i] = new Object JavaDoc(){public String JavaDoc toString(){return name;}};
386         }
387         
388         System.out.println("size " + table.size());
389         System.out.println("get " + keys[0]);
390         System.out.println("= " + table.get(keys[0]));
391
392         for (int i = keys.length; --i >= 0;) {
393             table.put(keys[i], i);
394         }
395
396         System.out.println("size " + table.size());
397
398         for (int i = keys.length; --i >= 0;) {
399             System.out.println("get " + keys[i]);
400             System.out.println("= " + table.get(keys[i]));
401         }
402
403         for (int i = keys.length; --i >= 0;) {
404             table.increment(keys[i], 100);
405         }
406
407         System.out.println("size " + table.size());
408
409         for (int i = keys.length; --i >= 0;) {
410             System.out.println("get " + keys[i]);
411             System.out.println("= " + table.get(keys[i]));
412         }
413
414         for (int i = keys.length; --i >= 0;) {
415             System.out.println("remove " + keys[i]);
416             System.out.println("= " + table.remove(keys[i]));
417         }
418
419         System.out.println("size " + table.size());
420
421         for (int i = keys.length; --i >= 0;) {
422             System.out.println("get " + keys[i]);
423             System.out.println("= " + table.get(keys[i]));
424         }
425
426         for (int i = keys.length; --i >= 0;) {
427             System.out.println("remove " + keys[i]);
428             System.out.println("= " + table.remove(keys[i]));
429         }
430
431         System.out.println("size " + table.size());
432
433         for (int i = keys.length; --i >= 0;) {
434             System.out.println("get " + keys[i]);
435             System.out.println("= " + table.get(keys[i]));
436         }
437
438         for (int i = keys.length; --i >= 0;) {
439             table.increment(keys[i], 100);
440         }
441
442         System.out.println("size " + table.size());
443
444         for (int i = keys.length; --i >= 0;) {
445             System.out.println("get " + keys[i]);
446             System.out.println("= " + table.get(keys[i]));
447         }
448
449         for (int i = keys.length; --i >= 0;) {
450             table.put(keys[i], i);
451         }
452
453         System.out.println("size " + table.size());
454
455         for (int i = keys.length; --i >= 0;) {
456             System.out.println("get " + keys[i]);
457             System.out.println("= " + table.get(keys[i]));
458         }
459
460         for (Enumeration JavaDoc e = table.keys(); e.hasMoreElements();) {
461             System.out.println("key " + e.nextElement());
462         }
463     }
464     
465 }
466
467 /**
468  * The Enumeration of keys in the HashIntTable
469  */

470 class KeysEnumeration
471     implements Enumeration JavaDoc {
472     /**
473      * The expected modification count of
474      * the underlying HashIntTable
475      */

476     final int expectedModificationCount;
477     
478     
479     /**
480      * The current index in the table whose
481      * entries are being examined
482      */

483     private int index = -1;
484     
485     
486     /**
487      * The current entry being examined
488      */

489     Entry entry = null;
490     
491
492     Entry[] table;
493     HashIntTable ht;
494     
495     /**
496      * Create the KeysEnumeration
497      *
498      * @param modificationCount the current
499      * modification count of the
500      * underlying HashIntTable
501      */

502     KeysEnumeration(int modificationCount, Entry[] table, HashIntTable ht)
503     {
504         this.expectedModificationCount = modificationCount;
505         this.table = table;
506         this.ht = ht;
507     }
508     
509     
510     /**
511      * Return true if there is a next element to return in the
512      * enumeration
513      *
514      * @return true if there is a next element to return in the
515      * enumeration
516      */

517     public boolean hasMoreElements()
518     {
519         if (null == entry) {
520             for (; ++index < table.length;) {
521                 entry = table[index];
522                 
523                 if (null != entry) {
524                     return true;
525                 }
526             }
527         }
528         
529         return null != entry;
530     }
531     
532     /**
533      * Return the next element in the enumeration
534      *
535      * @return the next element in the enumeration
536      * @throws NoSuchElementException if there is no
537      * next element in the enumeration
538      */

539     public Object JavaDoc nextElement()
540     {
541         if (!hasMoreElements()) {
542             throw new NoSuchElementException JavaDoc("No more elements in exception.");
543         }
544         
545         // get the key from the entry
546
Object JavaDoc key = entry.key;
547         // set the entry to the next entry
548
entry = entry.next;
549         
550         return key;
551     }
552 }
553
554 /**
555  * The class that stores the association between the
556  * key and the int, with a pointer to the next Entry
557  */

558 class Entry {
559     /**
560      * The key
561      */

562     final Object JavaDoc key;
563     
564     /**
565      * The hash code of the key
566      */

567     final int hashCode;
568     
569     /**
570      * The value
571      */

572     int value;
573     
574     /**
575      * The next entry
576      */

577     Entry next = null;
578     
579     /**
580      * Create the Entry with the specified
581      * arguments
582      *
583      * @param key the key
584      * @param value the value
585      */

586     Entry(Object JavaDoc key, int hashCode, int value)
587     {
588         this.key = key;
589         this.hashCode = hashCode;
590         this.value = value;
591     }
592 }
593
594
595
596
Popular Tags