IntStringHashMap


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8    * copies of the Software, and to permit persons to whom the Software is
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20   * IN THE SOFTWARE.
21   */
22  
23  package com.sosnoski.util.hashmap;
24  
25  import java.util.Iterator  ;
26  
27  import com.sosnoski.util.SparseArrayIterator;
28  
29  /**
30   * Hash map using primitive <code>int</code> values as keys mapped to
31   * <code>String</code> values. This implementation is unsynchronized in order
32   * to provide the best possible performance for typical usage scenarios, so
33   * explicit synchronization must be implemented by a wrapper class or directly
34   * by the application in cases where instances are modified in a multithreaded
35   * environment. See the base classes for other details of the
36   * hash map implementation.
37   *
38   * @author Dennis M. Sosnoski
39   * @version 1.1
40   */
41  
42  public class IntStringHashMap extends PrimitiveKeyBase
43  {
44      /** Array of key table slots. */
45      protected int[] m_keyTable;
46  
47      /** Array of value table slots. */
48      protected String  [] m_valueTable;
49  
50      /**
51       * Constructor with full specification.
52       *
53       * @param count number of values to assume in initial sizing of table
54       * @param fill fraction full allowed for table before growing
55       */
56  
57      public IntStringHashMap(int count, double fill) {
58          super(count, fill, int.class, String  .class);
59      }
60  
61      /**
62       * Constructor with only size supplied. Uses default value for fill
63       * fraction.
64       *
65       * @param count number of values to assume in initial sizing of table
66       */
67  
68      public IntStringHashMap(int count) {
69          this(count, DEFAULT_FILL);
70      }
71  
72      /**
73       * Default constructor.
74       */
75  
76      public IntStringHashMap() {
77          this(0, DEFAULT_FILL);
78      }
79  
80      /**
81       * Copy (clone) constructor.
82       *
83       * @param base instance being copied
84       */
85  
86      public IntStringHashMap(IntStringHashMap base) {
87          super(base);
88      }
89  
90      /**
91       * Get the backing array of keys. This implementation of an abstract
92       * method is used by the type-agnostic base class code to access the
93       * array used for type-specific storage by the child class.
94       *
95       * @return backing key array object
96       */
97  
98      protected final Object   getKeyArray() {
99          return m_keyTable;
100     }
101 
102     /**
103      * Set the backing array of keys. This implementation of an abstract
104      * method is used by the type-agnostic base class code to set the
105      * array used for type-specific storage by the child class.
106      *
107      * @param array backing key array object
108      */
109 
110     protected final void setKeyArray(Object   array) {
111         m_keyTable = (int[])array;
112     }
113 
114     /**
115      * Get the backing array of values. This implementation of an abstract
116      * method is used by the type-agnostic base class code to access the
117      * array used for type-specific storage by the child class.
118      *
119      * @return backing key array object
120      */
121 
122     protected final Object   getValueArray() {
123         return m_valueTable;
124     }
125 
126     /**
127      * Set the backing array of values. This implementation of an abstract
128      * method is used by the type-agnostic base class code to set the
129      * array used for type-specific storage by the child class.
130      *
131      * @param array backing value array object
132      */
133 
134     protected final void setValueArray(Object   array) {
135         m_valueTable = (String  [])array;
136     }
137 
138     /**
139      * Reinsert an entry into the hash map. This method is designed for
140      * internal use when the table is being modified, and does not adjust
141      * the count present or check the table capacity.
142      *
143      * @param slot position of entry to be reinserted into hash map
144      * @return <code>true</code> if the slot number used by the entry has
145      * has changed, <code>false</code> if not
146      */
147 
148     protected final boolean reinsert(int slot) {
149         m_flagTable[slot] = false;
150         return assignSlot(m_keyTable[slot], m_valueTable[slot]) != slot;
151     }
152 
153     /**
154      * Restructure the table. This implementation of an abstract method is
155      * used when the table is increasing or decreasing in size,
156      * and works directly with the old table representation arrays. It
157      * inserts pairs from the old arrays directly into the table without
158      * adjusting the count present or checking the table size.
159      *
160      * @param flags array of flags for array slots used
161      * @param karray array of keys
162      * @param varray array of values
163      */
164 
165     protected void restructure(boolean[] flags, Object   karray, Object   varray) {
166         int[] keys = (int[])karray;
167         String  [] values = (String  [])varray;
168         for (int i = 0; i < flags.length; i++) {
169             if (flags[i]) {
170                 assignSlot(keys[i], values[i]);
171             }
172         }
173     }
174 
175     /**
176      * Compute the base slot for a key.
177      *
178      * @param key key value to be computed
179      * @return base slot for key
180      */
181 
182     protected final int computeSlot(int key) {
183         return (key * KEY_MULTIPLIER & Integer.MAX_VALUE) % m_flagTable.length;
184     }
185 
186     /**
187      * Assign slot for entry. Starts at the slot found by the hashed key
188      * value. If this slot is already occupied, it steps the slot number and
189      * checks the resulting slot, repeating until an unused slot is found. This
190      * method does not check for duplicate keys, so it should only be used for
191      * internal reordering of the tables.
192      *
193      * @param key key to be added to table
194      * @param value associated value for key
195      * @return slot at which entry was added
196      */
197 
198     protected int assignSlot(int key, String   value) {
199         int offset = freeSlot(computeSlot(key));
200         m_flagTable[offset] = true;
201         m_keyTable[offset] = key;
202         m_valueTable[offset] = value;
203         return offset;
204     }
205 
206     /**
207      * Add an entry to the table. If the key is already present in the table,
208      * this replaces the existing value associated with the key.
209      *
210      * @param key key to be added to table
211      * @param value associated value for key
212      * @return value previously associated with key, <code>null</code> if
213      * key not previously present in table
214      */
215 
216     public String   add(int key, String   value) {
217         ensureCapacity(m_entryCount+1);
218         int offset = internalFind(key);
219         if (offset >= 0) {
220             String   prior = m_valueTable[offset];
221             m_valueTable[offset] = value;
222             return prior;
223         } else {
224             m_entryCount++;
225             offset = -offset - 1;
226             m_flagTable[offset] = true;
227             m_keyTable[offset] = key;
228             m_valueTable[offset] = value;
229             return null;
230         }
231     }
232 
233     /**
234      * Internal find key in table.
235      *
236      * @param key to be found in table
237      * @return index of matching key, or <code>-index-1</code> of slot to be
238      * used for inserting key in table if not already present (always negative)
239      */
240 
241     protected final int internalFind(int key) {
242         int slot = computeSlot(key);
243         while (m_flagTable[slot]) {
244             if (key == m_keyTable[slot]) {
245                 return slot;
246             }
247             slot = stepSlot(slot);
248         }
249         return -slot - 1;
250     }
251 
252     /**
253      * Check if an entry is present in the table. This method is supplied to
254      * support the use of <code>null</code> values in the table.
255      *
256      * @param key key for entry to be found
257      * @return <code>true</code> if key found in table, <code>false</code>
258      * if not
259      */
260 
261     public final boolean containsKey(int key) {
262         return internalFind(key) >= 0;
263     }
264 
265     /**
266      * Find an entry in the table.
267      *
268      * @param key key for entry to be returned
269      * @return value for key, or <code>null</code> if key not found
270      */
271 
272     public final String   get(int key) {
273         int slot = internalFind(key);
274         if (slot >= 0) {
275             return m_valueTable[slot];
276         } else {
277             return null;
278         }
279     }
280 
281     /**
282      * Remove an entry from the table.
283      *
284      * @param key key to be removed from table
285      * @return value associated with removed key, <code>null</code> if key
286      * not found in table
287      */
288 
289     public String   remove(int key) {
290         int slot = internalFind(key);
291         if (slot >= 0) {
292             String   value = m_valueTable[slot];
293             m_flagTable[slot] = false;
294             m_entryCount--;
295             while (m_flagTable[(slot = stepSlot(slot))]) {
296                 reinsert(slot);
297             }
298             return value;
299         } else {
300             return null;
301         }
302     }
303 
304     /**
305      * Return an iterator for the value <code>Object</code>s in this map. The
306      * iterator returns all values in arbitrary order, but is not "live". Any
307      * changes to the map while the iteration is in progress will give
308      * indeterminant results.
309      *
310      * @return iterator for values in array
311      */
312 
313     public final Iterator   valueIterator() {
314         return SparseArrayIterator.buildIterator(m_valueTable);
315     }
316 
317     /**
318      * Construct a copy of the table.
319      *
320      * @return shallow copy of table
321      */
322 
323     public Object   clone() {
324         return new IntStringHashMap(this);
325     }
326 }
327
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags