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  ;
59  import java.util.Enumeration  ;
60  import java.util.NoSuchElementException  ;
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  ("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   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   key)
158     {
159         if (null == key) {
160             throw new IllegalArgumentException  ("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   key)
188     {
189         if (null == key) {
190             throw new IllegalArgumentException  ("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   key)
221     {
222         if (null == key) {
223             throw new IllegalArgumentException  ("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   key, int value)
273     {
274         if (null == key) {
275             throw new IllegalArgumentException  ("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   key, int increment)
331     {
332         if (null == key) {
333             throw new IllegalArgumentException  ("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   args[]) {
380         HashIntTable table = new HashIntTable();
381         Object  [] keys = new Object  [4];
382 
383         for (int i = keys.length; --i >= 0;) {
384             final String   name = "Key" + i;
385             keys[i] = new Object  (){public String   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   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   {
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   nextElement()
540     {
541         if (!hasMoreElements()) {
542             throw new NoSuchElementException  ("No more elements in exception.");    
543         }
544         
545         // get the key from the entry
546         Object   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   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   key, int hashCode, int value)
587     {
588         this.key = key;
589         this.hashCode = hashCode;
590         this.value = value;
591     }
592 }
593 
594 
595 
596
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags