1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20/** 21 * This class is an abstract implementation of the {@code Map} interface. This 22 * implementation does not support adding. A subclass must implement the 23 * abstract method entrySet(). 24 * 25 * @since 1.2 26 */ 27public abstract class AbstractMap<K, V> implements Map<K, V> { 28 29 // Lazily initialized key set. 30 Set<K> keySet; 31 32 Collection<V> valuesCollection; 33 34 /** 35 * Constructs a new instance of this {@code AbstractMap}. 36 */ 37 protected AbstractMap() { 38 super(); 39 } 40 41 /** 42 * Removes all elements from this map, leaving it empty. 43 * 44 * @throws UnsupportedOperationException 45 * if removing from this map is not supported. 46 * @see #isEmpty() 47 * @see #size() 48 */ 49 public void clear() { 50 entrySet().clear(); 51 } 52 53 /** 54 * Returns whether this map contains the specified key. 55 * 56 * @param key 57 * the key to search for. 58 * @return {@code true} if this map contains the specified key, 59 * {@code false} otherwise. 60 */ 61 public boolean containsKey(Object key) { 62 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 63 if (key != null) { 64 while (it.hasNext()) { 65 if (key.equals(it.next().getKey())) { 66 return true; 67 } 68 } 69 } else { 70 while (it.hasNext()) { 71 if (it.next().getKey() == null) { 72 return true; 73 } 74 } 75 } 76 return false; 77 } 78 79 /** 80 * Returns whether this map contains the specified value. 81 * 82 * @param value 83 * the value to search for. 84 * @return {@code true} if this map contains the specified value, 85 * {@code false} otherwise. 86 */ 87 public boolean containsValue(Object value) { 88 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 89 if (value != null) { 90 while (it.hasNext()) { 91 if (value.equals(it.next().getValue())) { 92 return true; 93 } 94 } 95 } else { 96 while (it.hasNext()) { 97 if (it.next().getValue() == null) { 98 return true; 99 } 100 } 101 } 102 return false; 103 } 104 105 /** 106 * Returns a set containing all of the mappings in this map. Each mapping is 107 * an instance of {@link Map.Entry}. As the set is backed by this map, 108 * changes in one will be reflected in the other. 109 * 110 * @return a set of the mappings. 111 */ 112 public abstract Set<Map.Entry<K, V>> entrySet(); 113 114 /** 115 * Compares the specified object to this instance, and returns {@code true} 116 * if the specified object is a map and both maps contain the same mappings. 117 * 118 * @param object 119 * the object to compare with this object. 120 * @return boolean {@code true} if the object is the same as this object, 121 * and {@code false} if it is different from this object. 122 * @see #hashCode() 123 * @see #entrySet() 124 */ 125 @Override 126 public boolean equals(Object object) { 127 if (this == object) { 128 return true; 129 } 130 if (object instanceof Map) { 131 Map<?, ?> map = (Map<?, ?>) object; 132 if (size() != map.size()) { 133 return false; 134 } 135 136 try { 137 for (Entry<K, V> entry : entrySet()) { 138 K key = entry.getKey(); 139 V mine = entry.getValue(); 140 Object theirs = map.get(key); 141 if (mine == null) { 142 if (theirs != null || !map.containsKey(key)) { 143 return false; 144 } 145 } else if (!mine.equals(theirs)) { 146 return false; 147 } 148 } 149 } catch (NullPointerException ignored) { 150 return false; 151 } catch (ClassCastException ignored) { 152 return false; 153 } 154 return true; 155 } 156 return false; 157 } 158 159 /** 160 * Returns the value of the mapping with the specified key. 161 * 162 * @param key 163 * the key. 164 * @return the value of the mapping with the specified key, or {@code null} 165 * if no mapping for the specified key is found. 166 */ 167 public V get(Object key) { 168 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 169 if (key != null) { 170 while (it.hasNext()) { 171 Map.Entry<K, V> entry = it.next(); 172 if (key.equals(entry.getKey())) { 173 return entry.getValue(); 174 } 175 } 176 } else { 177 while (it.hasNext()) { 178 Map.Entry<K, V> entry = it.next(); 179 if (entry.getKey() == null) { 180 return entry.getValue(); 181 } 182 } 183 } 184 return null; 185 } 186 187 /** 188 * Returns the hash code for this object. Objects which are equal must 189 * return the same value for this method. 190 * 191 * @return the hash code of this object. 192 * @see #equals(Object) 193 */ 194 @Override 195 public int hashCode() { 196 int result = 0; 197 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 198 while (it.hasNext()) { 199 result += it.next().hashCode(); 200 } 201 return result; 202 } 203 204 /** 205 * Returns whether this map is empty. 206 * 207 * @return {@code true} if this map has no elements, {@code false} 208 * otherwise. 209 * @see #size() 210 */ 211 public boolean isEmpty() { 212 return size() == 0; 213 } 214 215 /** 216 * Returns a set of the keys contained in this map. The set is backed by 217 * this map so changes to one are reflected by the other. The returned set 218 * does not support adding. 219 * 220 * @return a set of the keys. 221 */ 222 public Set<K> keySet() { 223 if (keySet == null) { 224 keySet = new AbstractSet<K>() { 225 @Override 226 public boolean contains(Object object) { 227 return containsKey(object); 228 } 229 230 @Override 231 public int size() { 232 return AbstractMap.this.size(); 233 } 234 235 @Override 236 public Iterator<K> iterator() { 237 return new Iterator<K>() { 238 Iterator<Map.Entry<K, V>> setIterator = entrySet() 239 .iterator(); 240 241 public boolean hasNext() { 242 return setIterator.hasNext(); 243 } 244 245 public K next() { 246 return setIterator.next().getKey(); 247 } 248 249 public void remove() { 250 setIterator.remove(); 251 } 252 }; 253 } 254 }; 255 } 256 return keySet; 257 } 258 259 /** 260 * Maps the specified key to the specified value. 261 * 262 * @param key 263 * the key. 264 * @param value 265 * the value. 266 * @return the value of any previous mapping with the specified key or 267 * {@code null} if there was no mapping. 268 * @throws UnsupportedOperationException 269 * if adding to this map is not supported. 270 * @throws ClassCastException 271 * if the class of the key or value is inappropriate for this 272 * map. 273 * @throws IllegalArgumentException 274 * if the key or value cannot be added to this map. 275 * @throws NullPointerException 276 * if the key or value is {@code null} and this Map does not 277 * support {@code null} keys or values. 278 */ 279 public V put(K key, V value) { 280 throw new UnsupportedOperationException(); 281 } 282 283 /** 284 * Copies every mapping in the specified map to this map. 285 * 286 * @param map 287 * the map to copy mappings from. 288 * @throws UnsupportedOperationException 289 * if adding to this map is not supported. 290 * @throws ClassCastException 291 * if the class of a key or value is inappropriate for this 292 * map. 293 * @throws IllegalArgumentException 294 * if a key or value cannot be added to this map. 295 * @throws NullPointerException 296 * if a key or value is {@code null} and this map does not 297 * support {@code null} keys or values. 298 */ 299 public void putAll(Map<? extends K, ? extends V> map) { 300 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 301 put(entry.getKey(), entry.getValue()); 302 } 303 } 304 305 /** 306 * Removes a mapping with the specified key from this Map. 307 * 308 * @param key 309 * the key of the mapping to remove. 310 * @return the value of the removed mapping or {@code null} if no mapping 311 * for the specified key was found. 312 * @throws UnsupportedOperationException 313 * if removing from this map is not supported. 314 */ 315 public V remove(Object key) { 316 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 317 if (key != null) { 318 while (it.hasNext()) { 319 Map.Entry<K, V> entry = it.next(); 320 if (key.equals(entry.getKey())) { 321 it.remove(); 322 return entry.getValue(); 323 } 324 } 325 } else { 326 while (it.hasNext()) { 327 Map.Entry<K, V> entry = it.next(); 328 if (entry.getKey() == null) { 329 it.remove(); 330 return entry.getValue(); 331 } 332 } 333 } 334 return null; 335 } 336 337 /** 338 * Returns the number of elements in this map. 339 * 340 * @return the number of elements in this map. 341 */ 342 public int size() { 343 return entrySet().size(); 344 } 345 346 /** 347 * Returns the string representation of this map. 348 * 349 * @return the string representation of this map. 350 */ 351 @Override 352 public String toString() { 353 if (isEmpty()) { 354 return "{}"; //$NON-NLS-1$ 355 } 356 357 StringBuilder buffer = new StringBuilder(size() * 28); 358 buffer.append('{'); 359 Iterator<Map.Entry<K, V>> it = entrySet().iterator(); 360 while (it.hasNext()) { 361 Map.Entry<K, V> entry = it.next(); 362 Object key = entry.getKey(); 363 if (key != this) { 364 buffer.append(key); 365 } else { 366 buffer.append("(this Map)"); //$NON-NLS-1$ 367 } 368 buffer.append('='); 369 Object value = entry.getValue(); 370 if (value != this) { 371 buffer.append(value); 372 } else { 373 buffer.append("(this Map)"); //$NON-NLS-1$ 374 } 375 if (it.hasNext()) { 376 buffer.append(", "); //$NON-NLS-1$ 377 } 378 } 379 buffer.append('}'); 380 return buffer.toString(); 381 } 382 383 /** 384 * Returns a collection of the values contained in this map. The collection 385 * is backed by this map so changes to one are reflected by the other. The 386 * collection supports remove, removeAll, retainAll and clear operations, 387 * and it does not support add or addAll operations. 388 * <p> 389 * This method returns a collection which is the subclass of 390 * AbstractCollection. The iterator method of this subclass returns a 391 * "wrapper object" over the iterator of map's entrySet(). The {@code size} 392 * method wraps the map's size method and the {@code contains} method wraps 393 * the map's containsValue method. 394 * <p> 395 * The collection is created when this method is called for the first time 396 * and returned in response to all subsequent calls. This method may return 397 * different collections when multiple concurrent calls occur to this 398 * method, since no synchronization is performed. 399 * 400 * @return a collection of the values contained in this map. 401 */ 402 public Collection<V> values() { 403 if (valuesCollection == null) { 404 valuesCollection = new AbstractCollection<V>() { 405 @Override 406 public int size() { 407 return AbstractMap.this.size(); 408 } 409 410 @Override 411 public boolean contains(Object object) { 412 return containsValue(object); 413 } 414 415 @Override 416 public Iterator<V> iterator() { 417 return new Iterator<V>() { 418 Iterator<Map.Entry<K, V>> setIterator = entrySet() 419 .iterator(); 420 421 public boolean hasNext() { 422 return setIterator.hasNext(); 423 } 424 425 public V next() { 426 return setIterator.next().getValue(); 427 } 428 429 public void remove() { 430 setIterator.remove(); 431 } 432 }; 433 } 434 }; 435 } 436 return valuesCollection; 437 } 438 439 /** 440 * Returns a new instance of the same class as this instance, whose slots 441 * have been filled in with the values of the slots of this instance. 442 * 443 * @return a shallow copy of this object. 444 * @throws CloneNotSupportedException 445 * if the receiver's class does not implement the interface 446 * {@code Cloneable}. 447 */ 448 @Override 449 @SuppressWarnings("unchecked") 450 protected Object clone() throws CloneNotSupportedException { 451 AbstractMap<K, V> result = (AbstractMap<K, V>) super.clone(); 452 result.keySet = null; 453 result.valuesCollection = null; 454 return result; 455 } 456} 457