ObjectObjectHashMap


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 <code>Object</code> values as keys mapped to
31   * <code>Object</code> values. This implementation is unsynchronized
32   * in order to provide the best possible performance for typical usage
33   * scenarios, so explicit synchronization must be implemented by a wrapper
34   * class or directly by the application in cases where instances are modified
35   * in a multithreaded environment. See the base classes for other details of
36   * the implementation.
37   *
38   * @author Dennis M. Sosnoski
39   * @version 1.1
40   */
41  
42  public class ObjectObjectHashMap extends ObjectKeyBase
43  {
44      /** Array of key table slots. */
45      protected Object  [] m_keyTable;
46  
47      /** Array of value table slots. */
48      protected Object  [] 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       * @param tech hash technique specifier (one of STANDARD_HASH,
56       * IDENTITY_COMP, or IDENTITY_HASH, inherited from
57       * {@link com.sosnoski.util.ObjectHashBase})
58       */
59  
60      public ObjectObjectHashMap(int count, double fill, Object   tech) {
61          super(count, fill, Object  .class, Object  .class, tech);
62      }
63  
64      /**
65       * Constructor with size and fill fraction specified. Uses default hash
66       * technique.
67       *
68       * @param count number of values to assume in initial sizing of table
69       * @param fill fraction full allowed for table before growing
70       */
71  
72      public ObjectObjectHashMap(int count, double fill) {
73          this(count, fill, STANDARD_HASH);
74      }
75  
76      /**
77       * Constructor with only size and hash technique supplied. Uses default
78       * value for fill fraction.
79       *
80       * @param count number of values to assume in initial sizing of table
81       * @param tech hash technique specifier (one of STANDARD_HASH,
82       * IDENTITY_COMP, or IDENTITY_HASH, inherited from
83       * {@link com.sosnoski.util.ObjectHashBase})
84       */
85  
86      public ObjectObjectHashMap(int count, Object   tech) {
87          this(count, DEFAULT_FILL, tech);
88      }
89  
90      /**
91       * Constructor with only size supplied. Uses default hash technique and
92       * value for fill fraction.
93       *
94       * @param count number of values to assume in initial sizing of table
95       */
96  
97      public ObjectObjectHashMap(int count) {
98          this(count, DEFAULT_FILL);
99      }
100 
101     /**
102      * Constructor with technique specified. Uses standard default values
103      * for size and fill fraction.
104      *
105      * @param tech hash technique specifier (one of STANDARD_HASH,
106      * IDENTITY_COMP, or IDENTITY_HASH, inherited from
107      * {@link com.sosnoski.util.ObjectHashBase})
108      */
109 
110     public ObjectObjectHashMap(Object   tech) {
111         this(0, DEFAULT_FILL, tech);
112     }
113 
114     /**
115      * Default constructor.
116      */
117 
118     public ObjectObjectHashMap() {
119         this(0, DEFAULT_FILL);
120     }
121 
122     /**
123      * Copy (clone) constructor.
124      *
125      * @param base instance being copied
126      */
127 
128     public ObjectObjectHashMap(ObjectObjectHashMap base) {
129         super(base);
130     }
131 
132     /**
133      * Get the backing array of keys. This implementation of an abstract
134      * method is used by the type-agnostic base class code to access the
135      * array used for type-specific storage by the child class.
136      *
137      * @return backing key array object
138      */
139 
140     protected final Object  [] getKeyArray() {
141         return m_keyTable;
142     }
143 
144     /**
145      * Set the backing array of keys. This implementation of an abstract
146      * method is used by the type-agnostic base class code to set the
147      * array used for type-specific storage by the child class.
148      *
149      * @param array backing key array object
150      */
151 
152     protected final void setKeyArray(Object   array) {
153         m_keyTable = (Object  [])array;
154     }
155 
156     /**
157      * Get the backing array of values. This implementation of an abstract
158      * method is used by the type-agnostic base class code to access the
159      * array used for type-specific storage by the child class.
160      *
161      * @return backing key array object
162      */
163 
164     protected final Object   getValueArray() {
165         return m_valueTable;
166     }
167 
168     /**
169      * Set the backing array of values. This implementation of an abstract
170      * method is used by the type-agnostic base class code to set the
171      * array used for type-specific storage by the child class.
172      *
173      * @param array backing value array object
174      */
175 
176     protected final void setValueArray(Object   array) {
177         m_valueTable = (Object  [])array;
178     }
179 
180     /**
181      * Reinsert an entry into the hash map. This implementation of an abstract
182      * method is used when the table is being directly modified by
183      * the base class, and does not adjust the count present or check the table
184      * capacity.
185      *
186      * @param slot position of entry to be reinserted into hash map
187      * @return <code>true</code> if the slot number used by the entry has
188      * has changed, <code>false</code> if not
189      */
190 
191     protected final boolean reinsert(int slot) {
192         Object   key = m_keyTable[slot];
193         m_keyTable[slot] = null;
194         return assignSlot(key, m_valueTable[slot]) != slot;
195     }
196 
197     /**
198      * Restructure the table. This implementation of an abstract method is
199      * used when the table is increasing or decreasing in size,
200      * and works directly with the old table representation arrays. It
201      * inserts pairs from the old arrays directly into the table without
202      * adjusting the count present or checking the table size.
203      *
204      * @param karray array of keys
205      * @param varray array of values
206      */
207 
208     protected void restructure(Object   karray, Object   varray) {
209         Object  [] keys = (Object  [])karray;
210         Object  [] values = (Object  [])varray;
211         for (int i = 0; i < keys.length; i++) {
212             if (keys[i] != null) {
213                 assignSlot(keys[i], values[i]);
214             }
215         }
216     }
217 
218     /**
219      * Assign slot for entry. Starts at the slot found by the hashed key
220      * value. If this slot is already occupied, it steps the slot number and
221      * checks the resulting slot, repeating until an unused slot is found. This
222      * method does not check for duplicate keys, so it should only be used for
223      * internal reordering of the tables.
224      *
225      * @param key to be added to table
226      * @param value associated value for key
227      * @return slot at which entry was added
228      */
229 
230     protected int assignSlot(Object   key, Object   value) {
231         int offset = freeSlot(standardSlot(key));
232         m_keyTable[offset] = key;
233         m_valueTable[offset] = value;
234         return offset;
235     }
236 
237     /**
238      * Add an entry to the table. If the key is already present in the table,
239      * this replaces the existing value associated with the key.
240      *
241      * @param key key to be added to table (non-<code>null</code>)
242      * @param value associated value for key (non-<code>null</code>)
243      * @return value previously associated with key, or <code>null</code>
244      * if key not previously present in table
245      */
246 
247     public Object   add(Object   key, Object   value) {
248 
249         // first validate the parameters
250         if (key == null) {
251             throw new IllegalArgumentException  ("null key not supported");
252         } else if (value == null) {
253             throw new IllegalArgumentException  ("null value not supported");
254         } else {
255 
256             // check space and duplicate key
257             ensureCapacity(m_entryCount+1);
258             int offset = standardFind(key);
259             if (offset >= 0) {
260 
261                 // replace existing value for key
262                 Object   prior = m_valueTable[offset];
263                 m_valueTable[offset] = value;
264                 return prior;
265 
266             } else {
267 
268                 // add new pair to table
269                 m_entryCount++;
270                 offset = -offset - 1;
271                 m_keyTable[offset] = key;
272                 m_valueTable[offset] = value;
273                 return null;
274 
275             }
276         }
277     }
278 
279     /**
280      * Check if an entry is present in the table. This method is supplied to
281      * support the use of values matching the reserved not found value.
282      *
283      * @param key key for entry to be found
284      * @return <code>true</code> if key found in table, <code>false</code>
285      * if not
286      */
287 
288     public final boolean containsKey(Object   key) {
289         return standardFind(key) >= 0;
290     }
291 
292     /**
293      * Find an entry in the table.
294      *
295      * @param key key for entry to be returned
296      * @return value for key, or <code>null</code> if key not found
297      */
298 
299     public final Object   get(Object   key) {
300         int slot = standardFind(key);
301         if (slot >= 0) {
302             return m_valueTable[slot];
303         } else {
304             return null;
305         }
306     }
307 
308     /**
309      * Remove an entry from the table. If multiple entries are present with
310      * the same key value, only the first one found will be removed.
311      *
312      * @param key key to be removed from table
313      * @return value associated with removed key, or <code>null</code>
314      * if key not found in table
315      */
316 
317     public Object   remove(Object   key) {
318         int slot = standardFind(key);
319         if (slot >= 0) {
320             Object   value = m_valueTable[slot];
321             internalRemove(slot);
322             return value;
323         } else {
324             return null;
325         }
326     }
327 
328     /**
329      * Return an iterator for the value <code>Object</code>s in this map. The
330      * iterator returns all values in arbitrary order, but is not "live". Any
331      * changes to the map while the iteration is in progress will give
332      * indeterminant results.
333      *
334      * @return iterator for values in array
335      */
336 
337     public final Iterator   valueIterator() {
338         return SparseArrayIterator.buildIterator(m_valueTable);
339     }
340 
341     /**
342      * Construct a copy of the table.
343      *
344      * @return shallow copy of table
345      */
346 
347     public Object   clone() {
348         return new ObjectObjectHashMap(this);
349     }
350 }
351
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags