001 package edu.rice.cs.cunit.util;
002
003 import java.util.*;
004 import java.lang.ref.SoftReference;
005
006 /**
007 * A hash map with soft references.
008 * @author Mathias Ricken
009 */
010 public class SoftHashMap<K, V> implements Map<K,V> {
011 /**
012 * The wrapped map.
013 */
014 private HashMap<K, SoftReference<V>> _map;
015
016 /**
017 * The default initial capacity - MUST be a power of two.
018 */
019 static final int DEFAULT_INITIAL_CAPACITY = 16;
020
021 /**
022 * The maximum capacity, used if a higher value is implicitly specified
023 * by either of the constructors with arguments.
024 * MUST be a power of two <= 1<<30.
025 */
026 static final int MAXIMUM_CAPACITY = 1 << 30;
027
028 /**
029 * The load factor used when none specified in constructor.
030 **/
031 static final float DEFAULT_LOAD_FACTOR = 0.75f;
032
033 /**
034 * Constructs an empty <tt>SoftHashMap</tt> with the specified initial
035 * capacity and load factor.
036 *
037 * @param initialCapacity The initial capacity.
038 * @param loadFactor The load factor.
039 * @throws IllegalArgumentException if the initial capacity is negative
040 * or the load factor is nonpositive.
041 */
042 public SoftHashMap(int initialCapacity, float loadFactor) {
043 if (initialCapacity < 0)
044 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
045 if (initialCapacity > MAXIMUM_CAPACITY)
046 initialCapacity = MAXIMUM_CAPACITY;
047 if (loadFactor <= 0 || Float.isNaN(loadFactor))
048 throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
049
050 _map = new HashMap<K, SoftReference<V>>(initialCapacity, loadFactor);
051 }
052
053 /**
054 * Constructs an empty <tt>SoftHashMap</tt> with the specified initial
055 * capacity and the default load factor (0.75).
056 *
057 * @param initialCapacity the initial capacity.
058 * @throws IllegalArgumentException if the initial capacity is negative.
059 */
060 public SoftHashMap(int initialCapacity) {
061 this(initialCapacity, DEFAULT_LOAD_FACTOR);
062 }
063
064 /**
065 * Constructs an empty <tt>SoftHashMap</tt> with the default initial capacity
066 * (16) and the default load factor (0.75).
067 */
068 public SoftHashMap() {
069 _map = new HashMap<K, SoftReference<V>>();
070 }
071
072 /**
073 * Constructs a new <tt>SoftHashMap</tt> with the same mappings as the
074 * specified <tt>Map</tt>. The <tt>SoftHashMap</tt> is created with
075 * default load factor (0.75) and an initial capacity sufficient to
076 * hold the mappings in the specified <tt>Map</tt>.
077 *
078 * @param m the map whose mappings are to be placed in this map.
079 * @throws NullPointerException if the specified map is null.
080 */
081 public SoftHashMap(Map<? extends K, ? extends V> m) {
082 _map = new HashMap<K, SoftReference<V>>(m.size(), DEFAULT_LOAD_FACTOR);
083 for(K key: m.keySet()) {
084 V value = m.get(key);
085 if (value!=null) {
086 _map.put(key, new SoftReference<V>(value));
087 }
088 }
089 }
090
091 /**
092 * Returns the value to which this map maps the specified key. Returns <tt>null</tt> if the map contains no mapping
093 * for this key. A return value of <tt>null</tt> does not <i>necessarily</i> indicate that the map contains no mapping
094 * for the key; it's also possible that the map explicitly maps the key to <tt>null</tt>. The containsKey operation
095 * may be used to distinguish these two cases. <p>
096 *
097 * @param key key whose associated value is to be returned.
098 * @return the value to which this map maps the specified key.
099 *
100 * @throws NullPointerException if the key is <tt>null</tt> and this map does not permit <tt>null</tt> keys.
101 * @see #containsKey(Object)
102 */
103 public V get(Object key) {
104 SoftReference<V> sr = _map.get(key);
105 if (sr==null) {
106 return null;
107 }
108 V value = sr.get();
109 if (value==null) {
110 _map.remove(key);
111 return null;
112 }
113 return value;
114 }
115
116 /**
117 * Remove keys whose values have been removed.
118 */
119 public void compact() {
120 for(K key: _map.keySet()) {
121 SoftReference<V> sr = _map.get(key);
122 if (sr!=null) {
123 V value = sr.get();
124 if (value==null) {
125 _map.remove(key);
126 }
127 }
128 }
129 }
130
131 /**
132 * Returns the number of key-value mappings in this map. If the map contains more than <tt>Integer.MAX_VALUE</tt>
133 * elements, returns <tt>Integer.MAX_VALUE</tt>.<p>
134 * <p/>
135 * This implementation returns <tt>entrySet().size()</tt>.
136 *
137 * @return the number of key-value mappings in this map.
138 */
139 public int size() {
140 compact();
141 return _map.size();
142 }
143
144
145 /**
146 * Returns <tt>true</tt> if this map contains no key-value mappings.
147 *
148 * @return <tt>true</tt> if this map contains no key-value mappings.
149 */
150 public boolean isEmpty() {
151 compact();
152 return _map.isEmpty();
153 }
154
155
156 /**
157 * Returns <tt>true</tt> if this map contains a mapping for the specified key. More formally, returns <tt>true</tt>
158 * if and only if this map contains a mapping for a key <tt>k</tt> such that <tt>(key==null ? k==null :
159 * key.equals(k))</tt>. (There can be at most one such mapping.)
160 *
161 * @param key key whose presence in this map is to be tested.
162 *
163 * @return <tt>true</tt> if this map contains a mapping for the specified key.
164 *
165 * @throws ClassCastException if the key is of an inappropriate type for this map (optional).
166 * @throws NullPointerException if the key is <tt>null</tt> and this map does not permit <tt>null</tt> keys
167 * (optional).
168 */
169 public boolean containsKey(Object key) {
170 compact();
171 return _map.containsKey(key);
172 }
173
174
175 /**
176 * Returns <tt>true</tt> if this map maps one or more keys to the specified value. More formally, returns
177 * <tt>true</tt> if and only if this map contains at least one mapping to a value <tt>v</tt> such that
178 * <tt>(value==null ? v==null : value.equals(v))</tt>. This operation will probably require time linear in the map
179 * size for most implementations of the <tt>Map</tt> interface.
180 *
181 * @param value value whose presence in this map is to be tested.
182 *
183 * @return <tt>true</tt> if this map maps one or more keys to the specified value.
184 *
185 * @throws ClassCastException if the value is of an inappropriate type for this map (optional).
186 * @throws NullPointerException if the value is <tt>null</tt> and this map does not permit <tt>null</tt> values
187 * (optional).
188 */
189 public boolean containsValue(Object value) {
190 for(K key: _map.keySet()) {
191 SoftReference<V> sr = _map.get(key);
192 if (sr!=null) {
193 V v = sr.get();
194 if (value.equals(v)) {
195 return true;
196 }
197 else if (v==null) {
198 _map.remove(key);
199 }
200 }
201 }
202 return false;
203 }
204
205
206 /**
207 * Associates the specified value with the specified key in this map (optional operation). If the map previously
208 * contained a mapping for this key, the old value is replaced by the specified value. (A map <tt>m</tt> is said to
209 * contain a mapping for a key <tt>k</tt> if and only if {@link #containsKey(Object) m.containsKey(k)} would return
210 * <tt>true</tt>.))
211 *
212 * @param k key with which the specified value is to be associated.
213 * @param v value to be associated with the specified key.
214 *
215 * @return previous value associated with specified key, or <tt>null</tt> if there was no mapping for key. A
216 * <tt>null</tt> return can also indicate that the map previously associated <tt>null</tt> with the specified
217 * key, if the implementation supports <tt>null</tt> values.
218 *
219 * @throws UnsupportedOperationException if the <tt>put</tt> operation is not supported by this map.
220 * @throws ClassCastException if the class of the specified key or value prevents it from being stored in
221 * this map.
222 * @throws IllegalArgumentException if some aspect of this key or value prevents it from being stored in this
223 * map.
224 * @throws NullPointerException if this map does not permit <tt>null</tt> keys or values, and the specified
225 * key or value is <tt>null</tt>.
226 */
227 public V put(K k, V v) {
228 SoftReference<V> sr = _map.get(k);
229 _map.put(k, new SoftReference<V>(v));
230 if (sr==null) { return null; }
231 return sr.get();
232 }
233
234
235 /**
236 * Removes the mapping for this key from this map if it is present (optional operation). More formally, if this map
237 * contains a mapping from key <tt>k</tt> to value <tt>v</tt> such that <code>(key==null ? k==null :
238 * key.equals(k))</code>, that mapping is removed. (The map can contain at most one such mapping.)
239 * <p/>
240 * <p>Returns the value to which the map previously associated the key, or <tt>null</tt> if the map contained no
241 * mapping for this key. (A <tt>null</tt> return can also indicate that the map previously associated <tt>null</tt>
242 * with the specified key if the implementation supports <tt>null</tt> values.) The map will not contain a mapping for
243 * the specified key once the call returns.
244 *
245 * @param key key whose mapping is to be removed from the map.
246 *
247 * @return previous value associated with specified key, or <tt>null</tt> if there was no mapping for key.
248 *
249 * @throws ClassCastException if the key is of an inappropriate type for this map (optional).
250 * @throws NullPointerException if the key is <tt>null</tt> and this map does not permit <tt>null</tt> keys
251 * (optional).
252 * @throws UnsupportedOperationException if the <tt>remove</tt> method is not supported by this map.
253 */
254 public V remove(Object key) {
255 SoftReference<V> sr = _map.get(key);
256 _map.remove(key);
257 if (sr==null) { return null; }
258 return sr.get();
259 }
260
261
262 /**
263 * Copies all of the mappings from the specified map to this map (optional operation). The effect of this call is
264 * equivalent to that of calling {@link #put(Object,Object) put(k, v)} on this map once for each mapping from key
265 * <tt>k</tt> to value <tt>v</tt> in the specified map. The behavior of this operation is unspecified if the specified
266 * map is modified while the operation is in progress.
267 *
268 * @param map Mappings to be stored in this map.
269 *
270 * @throws UnsupportedOperationException if the <tt>putAll</tt> method is not supported by this map.
271 * @throws ClassCastException if the class of a key or value in the specified map prevents it from being
272 * stored in this map.
273 * @throws IllegalArgumentException some aspect of a key or value in the specified map prevents it from being
274 * stored in this map.
275 * @throws NullPointerException if the specified map is <tt>null</tt>, or if this map does not permit
276 * <tt>null</tt> keys or values, and the specified map contains <tt>null</tt>
277 * keys or values.
278 */
279 public void putAll(Map<? extends K, ? extends V> map) {
280 compact();
281 for(K key: map.keySet()) {
282 V value = map.get(key);
283 if (value!=null) {
284 _map.put(key, new SoftReference<V>(value));
285 }
286 }
287 }
288
289 /**
290 * Removes all mappings from this map (optional operation).
291 *
292 * @throws UnsupportedOperationException clear is not supported by this map.
293 */
294 public void clear() {
295 _map.clear();
296 }
297
298 /**
299 * Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are
300 * reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except
301 * through the iterator's own <tt>remove</tt> operation), the results of the iteration are undefined. The set supports
302 * element removal, which removes the corresponding mapping from the map, via the <tt>Iterator.remove</tt>,
303 * <tt>Set.remove</tt>, <tt>removeAll</tt> <tt>retainAll</tt>, and <tt>clear</tt> operations. It does not support the
304 * add or <tt>addAll</tt> operations.
305 *
306 * @return a set view of the keys contained in this map.
307 */
308 public Set<K> keySet() {
309 compact();
310 return _map.keySet();
311 }
312
313
314 /**
315 * Not supported.
316 * @throws UnsupportedOperationException
317 */
318 public Collection<V> values() {
319 throw new UnsupportedOperationException("entrySet not supported by SoftHashMap");
320 }
321
322 /**
323 * Not supported.
324 * @throws UnsupportedOperationException
325 */
326 public Set<Entry<K, V>> entrySet() {
327 throw new UnsupportedOperationException("entrySet not supported by SoftHashMap");
328 }
329 }