KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sosnoski > util > hashmap > 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 JavaDoc;
26 import java.util.Iterator JavaDoc;
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 JavaDoc ktype, Class JavaDoc vtype,
69         Object JavaDoc 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 JavaDoc type = from.getValueArray().getClass().getComponentType();
83         Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc karray, Object JavaDoc 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 JavaDoc keys = getKeyArray();;
134         Class JavaDoc type = keys.getClass().getComponentType();
135         setKeyArray(Array.newInstance(type, size));
136         Object JavaDoc 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 JavaDoc[] 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 JavaDoc values = getValueArray();
191         if (!values.getClass().getComponentType().isPrimitive()) {
192             Object JavaDoc[] objects = (Object JavaDoc[])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 JavaDoc iterator() {
209         return SparseArrayIterator.buildIterator((Object JavaDoc[])getKeyArray());
210     }
211 }
212
Popular Tags