ObjectIntHashMap


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>Object</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 ObjectIntHashMap 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 Object  [] 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 ObjectIntHashMap(int count, double fill, int miss, Object   tech) {
64          super(count, fill, Object  .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 ObjectIntHashMap(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 ObjectIntHashMap(int count, Object   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 ObjectIntHashMap(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 ObjectIntHashMap(Object   tech) {
115         this(0, DEFAULT_FILL, DEFAULT_NOT_FOUND, tech);
116     }
117 
118     /**
119      * Default constructor.
120      */
121 
122     public ObjectIntHashMap() {
123         this(0, DEFAULT_FILL);
124     }
125 
126     /**
127      * Copy (clone) constructor.
128      *
129      * @param base instance being copied
130      */
131 
132     public ObjectIntHashMap(ObjectIntHashMap 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  [] 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   array) {
158         m_keyTable = (Object  [])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   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   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         Object   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   karray, Object   varray) {
214         Object  [] keys = (Object  [])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(Object   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(Object   key, int value) {
253 
254         // first validate the parameters
255         if (key == null) {
256             throw new IllegalArgumentException  ("null key not supported");
257         } else if (value == m_notFoundValue) {
258             throw new IllegalArgumentException  
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(Object   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(Object   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.
316      *
317      * @param key key to be removed from table
318      * @return value associated with removed key, or reserved not found value
319      * if key not found in table
320      */
321 
322     public int remove(Object   key) {
323         int slot = standardFind(key);
324         if (slot >= 0) {
325             int value = m_valueTable[slot];
326             internalRemove(slot);
327             return value;
328         } else {
329             return m_notFoundValue;
330         }
331     }
332 
333     /**
334      * Construct a copy of the table.
335      *
336      * @return shallow copy of table
337      */
338 
339     public Object   clone() {
340         return new ObjectIntHashMap(this);
341     }
342 }
343
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags