AbstractMap


1   
2   /*
3   This is based very heavily on the AbstractMap implementation fom CEN as part of their COLT project. See copyright below.
4   
5   */
6   /*
7   
8   Copyright � 1999 CERN - European Organization for Nuclear Research.
9   
10  Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
11  
12  is hereby granted without fee, provided that the above copyright notice appear in all copies and 
13  
14  that both that copyright notice and this permission notice appear in supporting documentation. 
15  
16  CERN makes no representations about the suitability of this software for any purpose. 
17  
18  It is provided "as is" without expressed or implied warranty.
19  
20  */
21  
22  package com.jofti.util;
23  
24  
25  
26  /**
27  
28  Abstract base class for hash maps holding objects or primitive data types such as <code>int</code>, <code>float</code>, etc. as keys and/or values.
29  
30  First see the <a HREF="package-summary.html">package summary</a> and javadoc <a HREF="package-tree.html">tree view</a> to get the broad picture.
31  
32  <p>
33  
34  Note that implementations are not synchronized.
35  
36  
37  @author steve@jofti.com
38  @author wolfgang.hoschek@cern.ch
39  
40  @version 1.1, 03/01/06
41  @version 1.0, 09/24/99
42  
43  @see        java.util.HashMap
44  
45  */
46  
47  public abstract class AbstractMap  {
48  
49  
50      
51  
52      /**
53  
54       * The number of distinct associations in the map; its "size()".
55  
56       */
57  
58      protected int distinct;
59  
60  
61  
62      /**
63  
64       * The table capacity c=table.length always satisfies the invariant
65  
66       * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size() is the number of associations currently contained.
67  
68       * The term "c * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is called the "highWaterMark".
69  
70       * In other words, the table capacity (and proportionally the memory used by this class) oscillates within these constraints.
71  
72       * The terms are precomputed and cached to avoid recalculating them each time put(..) or removeKey(...) is called.
73  
74       */
75  
76      protected int lowWaterMark;
77  
78      protected int highWaterMark;
79  
80  
81  
82      /**
83  
84       * The minimum load factor for the hashtable.
85  
86       */
87  
88      protected double minLoadFactor;
89  
90  
91  
92      /**
93  
94       * The maximum load factor for the hashtable.
95  
96       */
97  
98      protected double maxLoadFactor;
99  
100 
101 
102     protected static final int defaultCapacity = 277;
103 
104     protected static final double defaultMinLoadFactor = 0.2;
105 
106     protected static final double defaultMaxLoadFactor = 0.5;
107 
108 /**
109 
110  * Makes this class non instantiable, but still let's others inherit from it.
111 
112  */
113 
114 protected AbstractMap() {}
115 
116 /**
117 
118  * Chooses a new prime table capacity optimized for growing that (approximately) satisfies the invariant
119 
120  * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
121 
122  * and has at least one FREE slot for the given size.
123 
124  */
125 
126 protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
127 
128     return nextPrime(Math.max(size+1, (int) ((4*size / (3*minLoad+maxLoad)))));
129 
130 }
131 
132 /**
133 
134  * Returns new high water mark threshold based on current capacity and maxLoadFactor.
135 
136  * @return int the new threshold.
137 
138  */
139 
140 protected int chooseHighWaterMark(int capacity, double maxLoad) {
141 
142     return Math.min(capacity-2, (int) (capacity * maxLoad)); //makes sure there is always at least one FREE slot
143 
144 }
145 
146 /**
147 
148  * Returns new low water mark threshold based on current capacity and minLoadFactor.
149 
150  * @return int the new threshold.
151 
152  */
153 
154 protected int chooseLowWaterMark(int capacity, double minLoad) {
155 
156     return (int) (capacity * minLoad);
157 
158 }
159 
160 /**
161 
162  * Chooses a new prime table capacity neither favoring shrinking nor growing,
163 
164  * that (approximately) satisfies the invariant
165 
166  * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
167 
168  * and has at least one FREE slot for the given size.
169 
170  */
171 
172 protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
173 
174     return nextPrime(Math.max(size+1, (int) ((2*size / (minLoad+maxLoad)))));
175 
176 }
177 
178 /**
179 
180  * Chooses a new prime table capacity optimized for shrinking that (approximately) satisfies the invariant
181 
182  * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
183 
184  * and has at least one FREE slot for the given size.
185 
186  */
187 
188 protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
189 
190     return nextPrime(Math.max(size+1, (int) ((4*size / (minLoad+3*maxLoad)))));
191 
192 }
193 
194 /**
195 
196  * Removes all (key,value) associations from the receiver.
197 
198  */
199 
200 public abstract void clear();
201 
202 /**
203 
204  * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory.
205 
206  * If necessary, allocates new internal memory and increases the capacity of the receiver.
207 
208  * <p>
209 
210  * This method never need be called; it is for performance tuning only.
211 
212  * Calling this method before <tt>put()</tt>ing a large number of associations boosts performance,
213 
214  * because the receiver will grow only once instead of potentially many times.
215 
216  * <p>
217 
218  * <b>This default implementation does nothing.</b> Override this method if necessary.
219 
220  *
221 
222  * @param   minCapacity   the desired minimum capacity.
223 
224  */
225 
226 public abstract void ensureCapacity(int minCapacity) ;
227 
228 /**
229 
230  * Returns <tt>true</tt> if the receiver contains no (key,value) associations.
231 
232  *
233 
234  * @return <tt>true</tt> if the receiver contains no (key,value) associations.
235 
236  */
237 
238 public boolean isEmpty() {
239 
240     return distinct == 0;
241 
242 }
243 
244 /**
245 
246  * Returns a prime number which is <code>&gt;= desiredCapacity</code> and very close to <code>desiredCapacity</code> (within 11% if <code>desiredCapacity &gt;= 1000</code>).
247 
248  * @param desiredCapacity the capacity desired by the user.
249 
250  * @return the capacity which should be used for a hashtable.
251 
252  */
253 
254 protected int nextPrime(int desiredCapacity) {
255 
256     return PrimeFinder.nextPrime(desiredCapacity);
257 
258 }
259 
260 /**
261 
262  * Initializes the receiver.
263 
264  * You will almost certainly need to override this method in subclasses to initialize the hash table.
265 
266  *
267 
268  * @param      initialCapacity   the initial capacity of the receiver.
269 
270  * @param      minLoadFactor     the minLoadFactor of the receiver.
271 
272  * @param      maxLoadFactor     the maxLoadFactor of the receiver.
273 
274  * @throws  IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
275 
276  */
277 
278 protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
279 
280     if (initialCapacity < 0)
281 
282         throw new IllegalArgumentException  ("Initial Capacity must not be less than zero: "+ initialCapacity);
283 
284     if (minLoadFactor < 0.0 || minLoadFactor >= 1.0)
285 
286         throw new IllegalArgumentException  ("Illegal minLoadFactor: "+ minLoadFactor);
287 
288     if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0)
289 
290         throw new IllegalArgumentException  ("Illegal maxLoadFactor: "+ maxLoadFactor);
291 
292     if (minLoadFactor >= maxLoadFactor)
293 
294         throw new IllegalArgumentException  ("Illegal minLoadFactor: "+ minLoadFactor+" and maxLoadFactor: "+ maxLoadFactor);
295 
296 }
297 
298 /**
299 
300  * Returns the number of (key,value) associations currently contained.
301 
302  *
303 
304  * @return the number of (key,value) associations currently contained.
305 
306  */
307 
308 public int size() {
309 
310     return distinct;
311 
312 }
313 
314 /**
315 
316  * Trims the capacity of the receiver to be the receiver's current 
317 
318  * size. Releases any superfluous internal memory. An application can use this operation to minimize the 
319 
320  * storage of the receiver.
321 
322  * <p>
323 
324  * This default implementation does nothing. Override this method if necessary.
325 
326  */
327 
328 public abstract void trimToSize();
329 
330 }
331 
332
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags