ObjectKeyBase


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.lang.reflect.Array  ;
26  import java.util.Iterator  ;
27  
28  import com.sosnoski.util.ObjectHashBase;
29  import com.sosnoski.util.SparseArrayIterator;
30  
31  /**
32   * Base class for type-specific hash map classes with object keys. This
33   * class builds on the basic structure provided by <code>ObjectHashBase</code>,
34   * specializing it for the case of a hash map where data values are associated
35   * with the keys. See the base class description for details of the
36   * implementation.<p>
37   *
38   * Hash maps based on this class are unsynchronized in order to provide the
39   * best possible performance for typical usage scenarios, so explicit
40   * synchronization must be implemented by the subclass or the application in
41   * cases where they are to be modified in a multithreaded environment.<p>
42   *
43   * Subclasses need to implement the abstract methods defined by the base class
44   * for working with the key array, and by this class for working with the value
45   * array and for restructuring, as well as the actual data access methods (at
46   * least the basic <code>add()</code>, <code>containsKey()</code>,
47   * <code>get()</code>, and <code>remove()</code> methods).
48   *
49   * @author Dennis M. Sosnoski
50   * @version 1.1
51   * @see PrimitiveKeyBase
52   */
53  
54  public abstract class ObjectKeyBase extends ObjectHashBase
55  {
56      /**
57       * Constructor with full specification.
58       *
59       * @param count number of values to assume in initial sizing of table
60       * @param fill fraction full allowed for table before growing
61       * @param ktype type of primitives used for keys
62       * @param vtype type of primitives or objects used for values
63       * @param tech hash technique specifier (one of STANDARD_HASH,
64       * IDENTITY_COMP, or IDENTITY_HASH, inherited from
65       * {@link com.sosnoski.util.ObjectHashBase})
66       */
67  
68      public ObjectKeyBase(int count, double fill, Class   ktype, Class   vtype,
69          Object   tech) {
70          super(count, fill, ktype, tech);
71          setValueArray(Array.newInstance(vtype, m_arraySize));
72      }
73  
74      /**
75       * Copy (clone) constructor.
76       *
77       * @param from instance being copied
78       */
79  
80      public ObjectKeyBase(ObjectKeyBase from) {
81          super(from);
82          Class   type = from.getValueArray().getClass().getComponentType();
83          Object   copy = Array.newInstance(type, m_arraySize);
84          System.arraycopy(from.getValueArray(), 0, copy, 0, m_arraySize);
85          setValueArray(copy);
86      }
87  
88      /**
89       * Get the backing array of values. This method is used by the type-agnostic
90       * base class code to access the array used for type-specific storage by
91       * the child class.
92       *
93       * @return backing key array object
94       */
95  
96      protected abstract Object   getValueArray();
97  
98      /**
99       * Set the backing array of values. This method is used by the type-agnostic
100      * base class code to set the array used for type-specific storage by the
101      * child class.
102      *
103      * @param array backing value array object
104      */
105 
106     protected abstract void setValueArray(Object   array);
107 
108     /**
109      * Restructure the table. This abstract method is used when the table
110      * is increasing or decreasing in size, and works directly with the old
111      * table representation arrays. It should insert pairs from the old arrays
112      * directly into the table without adjusting the count present or checking
113      * the table size.
114      *
115      * @param karray array of keys
116      * @param varray array of values
117      */
118 
119     protected abstract void restructure(Object   karray, Object   varray);
120 
121     /**
122      * Resize the base arrays after a size change. This implementation of the
123      * abstract base class method allocates the new arrays and then calls
124      * another method for handling the actual transfer of the keys and values
125      * from the old arrays to the new ones.
126      *
127      * @param size new size for base arrays
128      */
129 
130     protected void reallocate(int size) {
131 
132         // allocate the larger arrays
133         Object   keys = getKeyArray();;
134         Class   type = keys.getClass().getComponentType();
135         setKeyArray(Array.newInstance(type, size));
136         Object   values = getValueArray();
137         type = values.getClass().getComponentType();
138         setValueArray(Array.newInstance(type, size));
139 
140         // reinsert all entries into new arrays
141         restructure(keys, values);
142     }
143 
144     /**
145      * Reinsert an entry into the hash map. This abstract method is used
146      * when the table is being directly modified by the base class, and should
147      * not adjust the count present or check the table capacity.
148      *
149      * @param slot position of entry to be reinserted into hash map
150      * @return <code>true</code> if the slot number used by the entry has
151      * has changed, <code>false</code> if not
152      */
153 
154     protected abstract boolean reinsert(int slot);
155 
156     /**
157      * Internal remove pair from the table. Removes the pair from the table
158      * by setting the key entry to <code>null</code> and adjusting the count
159      * present, then chains through the table to reinsert any other pairs
160      * which may have collided with the removed pair. If the associated value
161      * is an object reference, it should be set to <code>null</code> before
162      * this method is called.
163      *
164      * @param slot index number of pair to be removed
165      */
166 
167     protected void internalRemove(int slot) {
168 
169         // delete pair from table
170         Object  [] keys = getKeyArray();
171         keys[slot] = null;
172         m_entryCount--;
173         while (keys[(slot = stepSlot(slot))] != null) {
174 
175             // reinsert current entry in table to fill holes
176             reinsert(slot);
177 
178         }
179     }
180 
181     /**
182      * Set the table to the empty state. This override of the base class method
183      * first calls the base class method to clear the entry information, then
184      * checks if the hash map values are objects, and if so clears all
185      * references to these objects.
186      */
187 
188     public void clear() {
189         super.clear();
190         Object   values = getValueArray();
191         if (!values.getClass().getComponentType().isPrimitive()) {
192             Object  [] objects = (Object  [])values;
193             for (int i = 0; i < objects.length; i++) {
194                 objects[i] = null;
195             }
196         }
197     }
198 
199     /**
200      * Return an iterator for the key <code>Object</code>s in this map. The
201      * iterator returns all keys in arbitrary order, but is not "live". Any
202      * changes to the map while the iteration is in progress will give
203      * indeterminant results.
204      *
205      * @return iterator for keys in map
206      */
207 
208     public final Iterator   iterator() {
209         return SparseArrayIterator.buildIterator((Object  [])getKeyArray());
210     }
211 }
212
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags