KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > util > collections > AbstractHashMap


1 /*
2  Copyright 1999 CERN - European Organization for Nuclear Research.
3  Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
4  is hereby granted without fee, provided that the above copyright notice appear in all copies and
5  that both that copyright notice and this permission notice appear in supporting documentation.
6  CERN makes no representations about the suitability of this software for any purpose.
7  It is provided "as is" without expressed or implied warranty.
8  */

9 package prefuse.util.collections;
10
11 /**
12  * Abstract base class for hash maps holding objects or primitive data types
13  * such as <code>int</code>, <code>float</code>, etc. as keys and/or
14  * values. First see the <a HREF="package-summary.html">package summary</a> and
15  * javadoc <a HREF="package-tree.html">tree view</a> to get the broad picture.
16  * <p>
17  * Note that implementations are not synchronized.
18  *
19  * @author wolfgang.hoschek@cern.ch
20  * @version 1.0, 09/24/99
21  * @see java.util.HashMap
22  */

23 public abstract class AbstractHashMap {
24
25     /**
26      * The number of distinct associations in the map; its "size()".
27      */

28     protected int distinct;
29
30     /**
31      * The table capacity c=table.length always satisfies the invariant
32      * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size()
33      * is the number of associations currently contained. The term "c *
34      * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is
35      * called the "highWaterMark". In other words, the table capacity (and
36      * proportionally the memory used by this class) oscillates within these
37      * constraints. The terms are precomputed and cached to avoid recalculating
38      * them each time put(..) or removeKey(...) is called.
39      */

40     protected int lowWaterMark;
41
42     protected int highWaterMark;
43
44     /**
45      * The minimum load factor for the hashtable.
46      */

47     protected double minLoadFactor;
48
49     /**
50      * The maximum load factor for the hashtable.
51      */

52     protected double maxLoadFactor;
53
54     protected static final int defaultCapacity = 277;
55
56     protected static final double defaultMinLoadFactor = 0.2;
57
58     protected static final double defaultMaxLoadFactor = 0.5;
59
60     /**
61      * Makes this class non instantiable, but still let's others inherit from
62      * it.
63      */

64     protected AbstractHashMap() {
65     }
66
67     /**
68      * Chooses a new prime table capacity optimized for growing that
69      * (approximately) satisfies the invariant
70      * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
71      * least one FREE slot for the given size.
72      */

73     protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
74         return nextPrime(Math.max(size + 1,
75                 (int) ((4 * size / (3 * minLoad + maxLoad)))));
76     }
77
78     /**
79      * Returns new high water mark threshold based on current capacity and
80      * maxLoadFactor.
81      *
82      * @return int the new threshold.
83      */

84     protected int chooseHighWaterMark(int capacity, double maxLoad) {
85         return Math.min(capacity - 2, (int) (capacity * maxLoad)); // makes
86
// sure
87
// there is
88
// always at
89
// least one
90
// FREE slot
91
}
92
93     /**
94      * Returns new low water mark threshold based on current capacity and
95      * minLoadFactor.
96      *
97      * @return int the new threshold.
98      */

99     protected int chooseLowWaterMark(int capacity, double minLoad) {
100         return (int) (capacity * minLoad);
101     }
102
103     /**
104      * Chooses a new prime table capacity neither favoring shrinking nor
105      * growing, that (approximately) satisfies the invariant
106      * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
107      * least one FREE slot for the given size.
108      */

109     protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
110         return nextPrime(Math.max(size + 1,
111                 (int) ((2 * size / (minLoad + maxLoad)))));
112     }
113
114     /**
115      * Chooses a new prime table capacity optimized for shrinking that
116      * (approximately) satisfies the invariant
117      * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
118      * least one FREE slot for the given size.
119      */

120     protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
121         return nextPrime(Math.max(size + 1,
122                 (int) ((4 * size / (minLoad + 3 * maxLoad)))));
123     }
124
125     /**
126      * Removes all (key,value) associations from the receiver.
127      */

128     public abstract void clear();
129
130     /**
131      * Ensures that the receiver can hold at least the specified number of
132      * elements without needing to allocate new internal memory. If necessary,
133      * allocates new internal memory and increases the capacity of the receiver.
134      * <p>
135      * This method never need be called; it is for performance tuning only.
136      * Calling this method before <tt>put()</tt>ing a large number of
137      * associations boosts performance, because the receiver will grow only once
138      * instead of potentially many times.
139      * <p>
140      * <b>This default implementation does nothing.</b> Override this method if
141      * necessary.
142      *
143      * @param minCapacity
144      * the desired minimum capacity.
145      */

146     public void ensureCapacity(int minCapacity) {
147     }
148
149     /**
150      * Returns <tt>true</tt> if the receiver contains no (key,value)
151      * associations.
152      *
153      * @return <tt>true</tt> if the receiver contains no (key,value)
154      * associations.
155      */

156     public boolean isEmpty() {
157         return distinct == 0;
158     }
159
160     /**
161      * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
162      * very close to <code>desiredCapacity</code> (within 11% if
163      * <code>desiredCapacity &gt;= 1000</code>).
164      *
165      * @param desiredCapacity
166      * the capacity desired by the user.
167      * @return the capacity which should be used for a hashtable.
168      */

169     protected int nextPrime(int desiredCapacity) {
170         return PrimeFinder.nextPrime(desiredCapacity);
171     }
172
173     /**
174      * Initializes the receiver. You will almost certainly need to override this
175      * method in subclasses to initialize the hash table.
176      *
177      * @param initialCapacity
178      * the initial capacity of the receiver.
179      * @param minLoadFactor
180      * the minLoadFactor of the receiver.
181      * @param maxLoadFactor
182      * the maxLoadFactor of the receiver.
183      * @throws IllegalArgumentException
184      * if
185      * <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
186      */

187     protected void setUp(int initialCapacity, double minLoadFactor,
188             double maxLoadFactor) {
189         if (initialCapacity < 0)
190             throw new IllegalArgumentException JavaDoc(
191                     "Initial Capacity must not be less than zero: "
192                             + initialCapacity);
193         if (minLoadFactor < 0.0 || minLoadFactor >= 1.0)
194             throw new IllegalArgumentException JavaDoc("Illegal minLoadFactor: "
195                     + minLoadFactor);
196         if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0)
197             throw new IllegalArgumentException JavaDoc("Illegal maxLoadFactor: "
198                     + maxLoadFactor);
199         if (minLoadFactor >= maxLoadFactor)
200             throw new IllegalArgumentException JavaDoc("Illegal minLoadFactor: "
201                     + minLoadFactor + " and maxLoadFactor: " + maxLoadFactor);
202     }
203
204     /**
205      * Returns the number of (key,value) associations currently contained.
206      *
207      * @return the number of (key,value) associations currently contained.
208      */

209     public int size() {
210         return distinct;
211     }
212
213     /**
214      * Trims the capacity of the receiver to be the receiver's current
215      * size. Releases any superfluous internal memory. An application can use this operation to minimize the
216      * storage of the receiver.
217      * <p>
218      * This default implementation does nothing. Override this method if necessary.
219      */

220     public void trimToSize() {
221     }
222     
223 } // end of class AbstractHashMap
224
Popular Tags