KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sosnoski > util > hashmap > StringIntHashMap


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 /**
26  * Hash map using <code>String</code> values as keys mapped to primitive
27  * <code>int</code> values. This implementation is unsynchronized
28  * in order to provide the best possible performance for typical usage
29  * scenarios, so explicit synchronization must be implemented by a wrapper
30  * class or directly by the application in cases where instances are modified
31  * in a multithreaded environment. See the base classes for other details of
32  * the implementation.
33  *
34  * @author Dennis M. Sosnoski
35  * @version 1.1
36  */

37
38 public class StringIntHashMap extends ObjectKeyBase
39 {
40     /** Default value returned when key not found in table. */
41     public static final int DEFAULT_NOT_FOUND = Integer.MIN_VALUE;
42
43     /** Array of key table slots. */
44     protected String JavaDoc[] m_keyTable;
45
46     /** Array of value table slots. */
47     protected int[] m_valueTable;
48
49     /** Value returned when key not found in table. */
50     protected int m_notFoundValue;
51
52     /**
53      * Constructor with full specification.
54      *
55      * @param count number of values to assume in initial sizing of table
56      * @param fill fraction full allowed for table before growing
57      * @param miss value returned when key not found in table
58      * @param tech hash technique specifier (one of STANDARD_HASH,
59      * IDENTITY_COMP, or IDENTITY_HASH, inherited from
60      * {@link com.sosnoski.util.ObjectHashBase})
61      */

62
63     public StringIntHashMap(int count, double fill, int miss, Object JavaDoc tech) {
64         super(count, fill, String JavaDoc.class, int.class, tech);
65         m_notFoundValue = miss;
66     }
67
68     /**
69      * Constructor with size and fill fraction specified. Uses default hash
70      * technique and value returned when key not found in table.
71      *
72      * @param count number of values to assume in initial sizing of table
73      * @param fill fraction full allowed for table before growing
74      */

75
76     public StringIntHashMap(int count, double fill) {
77         this(count, fill, DEFAULT_NOT_FOUND, STANDARD_HASH);
78     }
79
80     /**
81      * Constructor with only size and hash technique supplied. Uses default
82      * values for fill fraction and value returned when key not found in table.
83      *
84      * @param count number of values to assume in initial sizing of table
85      * @param tech hash technique specifier (one of STANDARD_HASH,
86      * IDENTITY_COMP, or IDENTITY_HASH, inherited from
87      * {@link com.sosnoski.util.ObjectHashBase})
88      */

89
90     public StringIntHashMap(int count, Object JavaDoc tech) {
91         this(count, DEFAULT_FILL, DEFAULT_NOT_FOUND, tech);
92     }
93
94     /**
95      * Constructor with only size supplied. Uses default hash technique and
96      * values for fill fraction and value returned when key not found in table.
97      *
98      * @param count number of values to assume in initial sizing of table
99      */

100
101     public StringIntHashMap(int count) {
102         this(count, DEFAULT_FILL);
103     }
104
105     /**
106      * Constructor with hash technique specified. Uses standard default values
107      * for size, fill fraction, and value returned when key not found in table.
108      *
109      * @param tech hash technique specifier (one of STANDARD_HASH,
110      * IDENTITY_COMP, or IDENTITY_HASH, inherited from
111      * {@link com.sosnoski.util.ObjectHashBase})
112      */

113
114     public StringIntHashMap(Object JavaDoc tech) {
115         this(0, DEFAULT_FILL, DEFAULT_NOT_FOUND, tech);
116     }
117
118     /**
119      * Default constructor.
120      */

121
122     public StringIntHashMap() {
123         this(0, DEFAULT_FILL);
124     }
125
126     /**
127      * Copy (clone) constructor.
128      *
129      * @param base instance being copied
130      */

131
132     public StringIntHashMap(StringIntHashMap base) {
133         super(base);
134         m_notFoundValue = base.m_notFoundValue;
135     }
136
137     /**
138      * Get the backing array of keys. This implementation of an abstract
139      * method is used by the type-agnostic base class code to access the
140      * array used for type-specific storage by the child class.
141      *
142      * @return backing key array object
143      */

144
145     protected final Object JavaDoc[] getKeyArray() {
146         return m_keyTable;
147     }
148
149     /**
150      * Set the backing array of keys. This implementation of an abstract
151      * method is used by the type-agnostic base class code to set the
152      * array used for type-specific storage by the child class.
153      *
154      * @param array backing key array object
155      */

156
157     protected final void setKeyArray(Object JavaDoc array) {
158         m_keyTable = (String JavaDoc[])array;
159     }
160
161     /**
162      * Get the backing array of values. This implementation of an abstract
163      * method is used by the type-agnostic base class code to access the
164      * array used for type-specific storage by the child class.
165      *
166      * @return backing key array object
167      */

168
169     protected final Object JavaDoc getValueArray() {
170         return m_valueTable;
171     }
172
173     /**
174      * Set the backing array of values. This implementation of an abstract
175      * method is used by the type-agnostic base class code to set the
176      * array used for type-specific storage by the child class.
177      *
178      * @param array backing value array object
179      */

180
181     protected final void setValueArray(Object JavaDoc array) {
182         m_valueTable = (int[])array;
183     }
184
185     /**
186      * Reinsert an entry into the hash map. This implementation of an abstract
187      * method is used when the table is being directly modified by
188      * the base class, and does not adjust the count present or check the table
189      * capacity.
190      *
191      * @param slot position of entry to be reinserted into hash map
192      * @return <code>true</code> if the slot number used by the entry has
193      * has changed, <code>false</code> if not
194      */

195
196     protected final boolean reinsert(int slot) {
197         String JavaDoc key = m_keyTable[slot];
198         m_keyTable[slot] = null;
199         return assignSlot(key, m_valueTable[slot]) != slot;
200     }
201
202     /**
203      * Restructure the table. This implementation of an abstract method is
204      * used when the table is increasing or decreasing in size,
205      * and works directly with the old table representation arrays. It
206      * inserts pairs from the old arrays directly into the table without
207      * adjusting the count present or checking the table size.
208      *
209      * @param karray array of keys
210      * @param varray array of values
211      */

212
213     protected void restructure(Object JavaDoc karray, Object JavaDoc varray) {
214         String JavaDoc[] keys = (String JavaDoc[])karray;
215         int[] values = (int[])varray;
216         for (int i = 0; i < keys.length; i++) {
217             if (keys[i] != null) {
218                 assignSlot(keys[i], values[i]);
219             }
220         }
221     }
222
223     /**
224      * Assign slot for entry. Starts at the slot found by the hashed key
225      * value. If this slot is already occupied, it steps the slot number and
226      * checks the resulting slot, repeating until an unused slot is found. This
227      * method does not check for duplicate keys, so it should only be used for
228      * internal reordering of the tables.
229      *
230      * @param key to be added to table
231      * @param value associated value for key
232      * @return slot at which entry was added
233      */

234
235     protected int assignSlot(String JavaDoc key, int value) {
236         int offset = freeSlot(standardSlot(key));
237         m_keyTable[offset] = key;
238         m_valueTable[offset] = value;
239         return offset;
240     }
241
242     /**
243      * Add an entry to the table. If the key is already present in the table,
244      * this replaces the existing value associated with the key.
245      *
246      * @param key key to be added to table (non-<code>null</code>)
247      * @param value associated value for key
248      * @return value previously associated with key, or reserved not found
249      * value if key not previously present in table
250      */

251
252     public int add(String JavaDoc key, int value) {
253
254         // first validate the parameters
255
if (key == null) {
256             throw new IllegalArgumentException JavaDoc("null key not supported");
257         } else if (value == m_notFoundValue) {
258             throw new IllegalArgumentException JavaDoc
259                 ("value matching not found return not supported");
260         } else {
261
262             // check space and duplicate key
263
ensureCapacity(m_entryCount+1);
264             int offset = standardFind(key);
265             if (offset >= 0) {
266
267                 // replace existing value for key
268
int prior = m_valueTable[offset];
269                 m_valueTable[offset] = value;
270                 return prior;
271
272             } else {
273
274                 // add new pair to table
275
m_entryCount++;
276                 offset = -offset - 1;
277                 m_keyTable[offset] = key;
278                 m_valueTable[offset] = value;
279                 return m_notFoundValue;
280
281             }
282         }
283     }
284
285     /**
286      * Check if an entry is present in the table. This method is supplied to
287      * support the use of values matching the reserved not found value.
288      *
289      * @param key key for entry to be found
290      * @return <code>true</code> if key found in table, <code>false</code>
291      * if not
292      */

293
294     public final boolean containsKey(String JavaDoc key) {
295         return standardFind(key) >= 0;
296     }
297
298     /**
299      * Find an entry in the table.
300      *
301      * @param key key for entry to be returned
302      * @return value for key, or reserved not found value if key not found
303      */

304
305     public final int get(String JavaDoc key) {
306         int slot = standardFind(key);
307         if (slot >= 0) {
308             return m_valueTable[slot];
309         } else {
310             return m_notFoundValue;
311         }
312     }
313
314     /**
315      * Remove an entry from the table. If multiple entries are present with
316      * the same key value, only the first one found will be removed.
317      *
318      * @param key key to be removed from table
319      * @return value associated with removed key, or reserved not found value
320      * if key not found in table
321      */

322
323     public int remove(String JavaDoc key) {
324         int slot = standardFind(key);
325         if (slot >= 0) {
326             int value = m_valueTable[slot];
327             internalRemove(slot);
328             return value;
329         } else {
330             return m_notFoundValue;
331         }
332     }
333
334     /**
335      * Construct a copy of the table.
336      *
337      * @return shallow copy of table
338      */

339
340     public Object JavaDoc clone() {
341         return new StringIntHashMap(this);
342     }
343 }
344
Popular Tags