001: /*
002: This is based very heavily on the AbstractMap implementation fom CEN as part of their COLT project. See copyright below.
003:
004: */
005: /*
006:
007: Copyright © 1999 CERN - European Organization for Nuclear Research.
008:
009: Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
010:
011: is hereby granted without fee, provided that the above copyright notice appear in all copies and
012:
013: that both that copyright notice and this permission notice appear in supporting documentation.
014:
015: CERN makes no representations about the suitability of this software for any purpose.
016:
017: It is provided "as is" without expressed or implied warranty.
018:
019: */
020:
021: package com.jofti.util;
022:
023: /**
024:
025: 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.
026:
027: 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.
028:
029: <p>
030:
031: Note that implementations are not synchronized.
032:
033:
034: @author steve@jofti.com
035: @author wolfgang.hoschek@cern.ch
036:
037: @version 1.1, 03/01/06
038: @version 1.0, 09/24/99
039:
040: @see java.util.HashMap
041:
042: */
043:
044: public abstract class AbstractMap {
045:
046: /**
047:
048: * The number of distinct associations in the map; its "size()".
049:
050: */
051:
052: protected int distinct;
053:
054: /**
055:
056: * The table capacity c=table.length always satisfies the invariant
057:
058: * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size() is the number of associations currently contained.
059:
060: * The term "c * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is called the "highWaterMark".
061:
062: * In other words, the table capacity (and proportionally the memory used by this class) oscillates within these constraints.
063:
064: * The terms are precomputed and cached to avoid recalculating them each time put(..) or removeKey(...) is called.
065:
066: */
067:
068: protected int lowWaterMark;
069:
070: protected int highWaterMark;
071:
072: /**
073:
074: * The minimum load factor for the hashtable.
075:
076: */
077:
078: protected double minLoadFactor;
079:
080: /**
081:
082: * The maximum load factor for the hashtable.
083:
084: */
085:
086: protected double maxLoadFactor;
087:
088: protected static final int defaultCapacity = 277;
089:
090: protected static final double defaultMinLoadFactor = 0.2;
091:
092: protected static final double defaultMaxLoadFactor = 0.5;
093:
094: /**
095:
096: * Makes this class non instantiable, but still let's others inherit from it.
097:
098: */
099:
100: protected AbstractMap() {
101: }
102:
103: /**
104:
105: * Chooses a new prime table capacity optimized for growing that (approximately) satisfies the invariant
106:
107: * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
108:
109: * and has at least one FREE slot for the given size.
110:
111: */
112:
113: protected int chooseGrowCapacity(int size, double minLoad,
114: double maxLoad) {
115:
116: return nextPrime(Math.max(size + 1,
117: (int) ((4 * size / (3 * minLoad + maxLoad)))));
118:
119: }
120:
121: /**
122:
123: * Returns new high water mark threshold based on current capacity and maxLoadFactor.
124:
125: * @return int the new threshold.
126:
127: */
128:
129: protected int chooseHighWaterMark(int capacity, double maxLoad) {
130:
131: return Math.min(capacity - 2, (int) (capacity * maxLoad)); //makes sure there is always at least one FREE slot
132:
133: }
134:
135: /**
136:
137: * Returns new low water mark threshold based on current capacity and minLoadFactor.
138:
139: * @return int the new threshold.
140:
141: */
142:
143: protected int chooseLowWaterMark(int capacity, double minLoad) {
144:
145: return (int) (capacity * minLoad);
146:
147: }
148:
149: /**
150:
151: * Chooses a new prime table capacity neither favoring shrinking nor growing,
152:
153: * that (approximately) satisfies the invariant
154:
155: * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
156:
157: * and has at least one FREE slot for the given size.
158:
159: */
160:
161: protected int chooseMeanCapacity(int size, double minLoad,
162: double maxLoad) {
163:
164: return nextPrime(Math.max(size + 1,
165: (int) ((2 * size / (minLoad + maxLoad)))));
166:
167: }
168:
169: /**
170:
171: * Chooses a new prime table capacity optimized for shrinking that (approximately) satisfies the invariant
172:
173: * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt>
174:
175: * and has at least one FREE slot for the given size.
176:
177: */
178:
179: protected int chooseShrinkCapacity(int size, double minLoad,
180: double maxLoad) {
181:
182: return nextPrime(Math.max(size + 1,
183: (int) ((4 * size / (minLoad + 3 * maxLoad)))));
184:
185: }
186:
187: /**
188:
189: * Removes all (key,value) associations from the receiver.
190:
191: */
192:
193: public abstract void clear();
194:
195: /**
196:
197: * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory.
198:
199: * If necessary, allocates new internal memory and increases the capacity of the receiver.
200:
201: * <p>
202:
203: * This method never need be called; it is for performance tuning only.
204:
205: * Calling this method before <tt>put()</tt>ing a large number of associations boosts performance,
206:
207: * because the receiver will grow only once instead of potentially many times.
208:
209: * <p>
210:
211: * <b>This default implementation does nothing.</b> Override this method if necessary.
212:
213: *
214:
215: * @param minCapacity the desired minimum capacity.
216:
217: */
218:
219: public abstract void ensureCapacity(int minCapacity);
220:
221: /**
222:
223: * Returns <tt>true</tt> if the receiver contains no (key,value) associations.
224:
225: *
226:
227: * @return <tt>true</tt> if the receiver contains no (key,value) associations.
228:
229: */
230:
231: public boolean isEmpty() {
232:
233: return distinct == 0;
234:
235: }
236:
237: /**
238:
239: * Returns a prime number which is <code>>= desiredCapacity</code> and very close to <code>desiredCapacity</code> (within 11% if <code>desiredCapacity >= 1000</code>).
240:
241: * @param desiredCapacity the capacity desired by the user.
242:
243: * @return the capacity which should be used for a hashtable.
244:
245: */
246:
247: protected int nextPrime(int desiredCapacity) {
248:
249: return PrimeFinder.nextPrime(desiredCapacity);
250:
251: }
252:
253: /**
254:
255: * Initializes the receiver.
256:
257: * You will almost certainly need to override this method in subclasses to initialize the hash table.
258:
259: *
260:
261: * @param initialCapacity the initial capacity of the receiver.
262:
263: * @param minLoadFactor the minLoadFactor of the receiver.
264:
265: * @param maxLoadFactor the maxLoadFactor of the receiver.
266:
267: * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
268:
269: */
270:
271: protected void setUp(int initialCapacity, double minLoadFactor,
272: double maxLoadFactor) {
273:
274: if (initialCapacity < 0)
275:
276: throw new IllegalArgumentException(
277: "Initial Capacity must not be less than zero: "
278: + initialCapacity);
279:
280: if (minLoadFactor < 0.0 || minLoadFactor >= 1.0)
281:
282: throw new IllegalArgumentException(
283: "Illegal minLoadFactor: " + minLoadFactor);
284:
285: if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0)
286:
287: throw new IllegalArgumentException(
288: "Illegal maxLoadFactor: " + maxLoadFactor);
289:
290: if (minLoadFactor >= maxLoadFactor)
291:
292: throw new IllegalArgumentException(
293: "Illegal minLoadFactor: " + minLoadFactor
294: + " 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: }
|