001/* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017package org.apache.commons.collections4.map; 018 019import java.util.ConcurrentModificationException; 020import java.util.Iterator; 021import java.util.Map; 022import java.util.NoSuchElementException; 023 024import org.apache.commons.collections4.OrderedIterator; 025import org.apache.commons.collections4.OrderedMap; 026import org.apache.commons.collections4.OrderedMapIterator; 027import org.apache.commons.collections4.ResettableIterator; 028import org.apache.commons.collections4.iterators.EmptyOrderedIterator; 029import org.apache.commons.collections4.iterators.EmptyOrderedMapIterator; 030 031/** 032 * An abstract implementation of a hash-based map that links entries to create an 033 * ordered map and which provides numerous points for subclasses to override. 034 * <p> 035 * This class implements all the features necessary for a subclass linked 036 * hash-based map. Key-value entries are stored in instances of the 037 * {@code LinkEntry} class which can be overridden and replaced. 038 * The iterators can similarly be replaced, without the need to replace the KeySet, 039 * EntrySet and Values view classes. 040 * </p> 041 * <p> 042 * Overridable methods are provided to change the default hashing behavior, and 043 * to change how entries are added to and removed from the map. Hopefully, all you 044 * need for unusual subclasses is here. 045 * </p> 046 * <p> 047 * This implementation maintains order by original insertion, but subclasses 048 * may work differently. The {@code OrderedMap} interface is implemented 049 * to provide access to bidirectional iteration and extra convenience methods. 050 * </p> 051 * <p> 052 * The {@code orderedMapIterator()} method provides direct access to a 053 * bidirectional iterator. The iterators from the other views can also be cast 054 * to {@code OrderedIterator} if required. 055 * </p> 056 * <p> 057 * All the available iterators can be reset back to the start by casting to 058 * {@code ResettableIterator} and calling {@code reset()}. 059 * </p> 060 * <p> 061 * The implementation is also designed to be subclassed, with lots of useful 062 * methods exposed. 063 * </p> 064 * 065 * @param <K> the type of the keys in this map 066 * @param <V> the type of the values in this map 067 * @since 3.0 068 */ 069public abstract class AbstractLinkedMap<K, V> extends AbstractHashedMap<K, V> implements OrderedMap<K, V> { 070 071 /** 072 * EntrySet iterator. 073 */ 074 protected static class EntrySetIterator<K, V> extends LinkIterator<K, V> implements 075 OrderedIterator<Map.Entry<K, V>>, ResettableIterator<Map.Entry<K, V>> { 076 077 protected EntrySetIterator(final AbstractLinkedMap<K, V> parent) { 078 super(parent); 079 } 080 081 @Override 082 public Map.Entry<K, V> next() { 083 return super.nextEntry(); 084 } 085 086 @Override 087 public Map.Entry<K, V> previous() { 088 return super.previousEntry(); 089 } 090 } 091 092 /** 093 * KeySet iterator. 094 */ 095 protected static class KeySetIterator<K> extends LinkIterator<K, Object> implements 096 OrderedIterator<K>, ResettableIterator<K> { 097 098 @SuppressWarnings("unchecked") 099 protected KeySetIterator(final AbstractLinkedMap<K, ?> parent) { 100 super((AbstractLinkedMap<K, Object>) parent); 101 } 102 103 @Override 104 public K next() { 105 return super.nextEntry().getKey(); 106 } 107 108 @Override 109 public K previous() { 110 return super.previousEntry().getKey(); 111 } 112 } 113 114 /** 115 * LinkEntry that stores the data. 116 * <p> 117 * If you subclass {@code AbstractLinkedMap} but not {@code LinkEntry} 118 * then you will not be able to access the protected fields. 119 * The {@code entryXxx()} methods on {@code AbstractLinkedMap} exist 120 * to provide the necessary access. 121 */ 122 protected static class LinkEntry<K, V> extends HashEntry<K, V> { 123 /** The entry before this one in the order */ 124 protected LinkEntry<K, V> before; 125 /** The entry after this one in the order */ 126 protected LinkEntry<K, V> after; 127 128 /** 129 * Constructs a new entry. 130 * 131 * @param next the next entry in the hash bucket sequence 132 * @param hashCode the hash code 133 * @param key the key 134 * @param value the value 135 */ 136 protected LinkEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) { 137 super(next, hashCode, key, value); 138 } 139 } 140 141 /** 142 * Base Iterator that iterates in link order. 143 */ 144 protected abstract static class LinkIterator<K, V> { 145 146 /** The parent map */ 147 protected final AbstractLinkedMap<K, V> parent; 148 /** The current (last returned) entry */ 149 protected LinkEntry<K, V> last; 150 /** The next entry */ 151 protected LinkEntry<K, V> next; 152 /** The modification count expected */ 153 protected int expectedModCount; 154 155 protected LinkIterator(final AbstractLinkedMap<K, V> parent) { 156 this.parent = parent; 157 this.next = parent.header.after; 158 this.expectedModCount = parent.modCount; 159 } 160 161 protected LinkEntry<K, V> currentEntry() { 162 return last; 163 } 164 165 public boolean hasNext() { 166 return next != parent.header; 167 } 168 169 public boolean hasPrevious() { 170 return next.before != parent.header; 171 } 172 173 protected LinkEntry<K, V> nextEntry() { 174 if (parent.modCount != expectedModCount) { 175 throw new ConcurrentModificationException(); 176 } 177 if (next == parent.header) { 178 throw new NoSuchElementException(NO_NEXT_ENTRY); 179 } 180 last = next; 181 next = next.after; 182 return last; 183 } 184 185 protected LinkEntry<K, V> previousEntry() { 186 if (parent.modCount != expectedModCount) { 187 throw new ConcurrentModificationException(); 188 } 189 final LinkEntry<K, V> previous = next.before; 190 if (previous == parent.header) { 191 throw new NoSuchElementException(NO_PREVIOUS_ENTRY); 192 } 193 next = previous; 194 last = previous; 195 return last; 196 } 197 198 public void remove() { 199 if (last == null) { 200 throw new IllegalStateException(REMOVE_INVALID); 201 } 202 if (parent.modCount != expectedModCount) { 203 throw new ConcurrentModificationException(); 204 } 205 parent.remove(last.getKey()); 206 last = null; 207 expectedModCount = parent.modCount; 208 } 209 210 public void reset() { 211 last = null; 212 next = parent.header.after; 213 } 214 215 @Override 216 public String toString() { 217 if (last != null) { 218 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]"; 219 } 220 return "Iterator[]"; 221 } 222 } 223 224 /** 225 * MapIterator implementation. 226 */ 227 protected static class LinkMapIterator<K, V> extends LinkIterator<K, V> implements 228 OrderedMapIterator<K, V>, ResettableIterator<K> { 229 230 protected LinkMapIterator(final AbstractLinkedMap<K, V> parent) { 231 super(parent); 232 } 233 234 @Override 235 public K getKey() { 236 final LinkEntry<K, V> current = currentEntry(); 237 if (current == null) { 238 throw new IllegalStateException(GETKEY_INVALID); 239 } 240 return current.getKey(); 241 } 242 243 @Override 244 public V getValue() { 245 final LinkEntry<K, V> current = currentEntry(); 246 if (current == null) { 247 throw new IllegalStateException(GETVALUE_INVALID); 248 } 249 return current.getValue(); 250 } 251 252 @Override 253 public K next() { 254 return super.nextEntry().getKey(); 255 } 256 257 @Override 258 public K previous() { 259 return super.previousEntry().getKey(); 260 } 261 262 @Override 263 public V setValue(final V value) { 264 final LinkEntry<K, V> current = currentEntry(); 265 if (current == null) { 266 throw new IllegalStateException(SETVALUE_INVALID); 267 } 268 return current.setValue(value); 269 } 270 } 271 272 /** 273 * Values iterator. 274 */ 275 protected static class ValuesIterator<V> extends LinkIterator<Object, V> implements 276 OrderedIterator<V>, ResettableIterator<V> { 277 278 @SuppressWarnings("unchecked") 279 protected ValuesIterator(final AbstractLinkedMap<?, V> parent) { 280 super((AbstractLinkedMap<Object, V>) parent); 281 } 282 283 @Override 284 public V next() { 285 return super.nextEntry().getValue(); 286 } 287 288 @Override 289 public V previous() { 290 return super.previousEntry().getValue(); 291 } 292 } 293 294 /** Header in the linked list */ 295 transient LinkEntry<K, V> header; 296 297 /** 298 * Constructor only used in deserialization, do not use otherwise. 299 */ 300 protected AbstractLinkedMap() { 301 } 302 303 /** 304 * Constructs a new, empty map with the specified initial capacity. 305 * 306 * @param initialCapacity the initial capacity 307 * @throws IllegalArgumentException if the initial capacity is negative 308 */ 309 protected AbstractLinkedMap(final int initialCapacity) { 310 super(initialCapacity); 311 } 312 313 /** 314 * Constructs a new, empty map with the specified initial capacity and 315 * load factor. 316 * 317 * @param initialCapacity the initial capacity 318 * @param loadFactor the load factor 319 * @throws IllegalArgumentException if the initial capacity is negative 320 * @throws IllegalArgumentException if the load factor is less than zero 321 */ 322 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor) { 323 super(initialCapacity, loadFactor); 324 } 325 326 /** 327 * Constructor which performs no validation on the passed in parameters. 328 * 329 * @param initialCapacity the initial capacity, must be a power of two 330 * @param loadFactor the load factor, must be > 0.0f and generally < 1.0f 331 * @param threshold the threshold, must be sensible 332 */ 333 protected AbstractLinkedMap(final int initialCapacity, final float loadFactor, final int threshold) { 334 super(initialCapacity, loadFactor, threshold); 335 } 336 337 /** 338 * Constructor copying elements from another map. 339 * 340 * @param map the map to copy 341 * @throws NullPointerException if the map is null 342 */ 343 protected AbstractLinkedMap(final Map<? extends K, ? extends V> map) { 344 super(map); 345 } 346 347 /** 348 * Adds an entry into this map, maintaining insertion order. 349 * <p> 350 * This implementation adds the entry to the data storage table and 351 * to the end of the linked list. 352 * 353 * @param entry the entry to add 354 * @param hashIndex the index into the data array to store at 355 */ 356 @Override 357 protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) { 358 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry; 359 link.after = header; 360 link.before = header.before; 361 header.before.after = link; 362 header.before = link; 363 data[hashIndex] = link; 364 } 365 366 /** 367 * Clears the map, resetting the size to zero and nullifying references 368 * to avoid garbage collection issues. 369 */ 370 @Override 371 public void clear() { 372 // override to reset the linked list 373 super.clear(); 374 header.before = header.after = header; 375 } 376 377 /** 378 * Checks whether the map contains the specified value. 379 * 380 * @param value the value to search for 381 * @return true if the map contains the value 382 */ 383 @Override 384 public boolean containsValue(final Object value) { 385 // override uses faster iterator 386 if (value == null) { 387 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) { 388 if (entry.getValue() == null) { 389 return true; 390 } 391 } 392 } else { 393 for (LinkEntry<K, V> entry = header.after; entry != header; entry = entry.after) { 394 if (isEqualValue(value, entry.getValue())) { 395 return true; 396 } 397 } 398 } 399 return false; 400 } 401 402 /** 403 * Creates an entry to store the data. 404 * <p> 405 * This implementation creates a new LinkEntry instance. 406 * 407 * @param next the next entry in sequence 408 * @param hashCode the hash code to use 409 * @param key the key to store 410 * @param value the value to store 411 * @return the newly created entry 412 */ 413 @Override 414 protected LinkEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) { 415 return new LinkEntry<>(next, hashCode, convertKey(key), value); 416 } 417 418 /** 419 * Creates an entry set iterator. 420 * Subclasses can override this to return iterators with different properties. 421 * 422 * @return the entrySet iterator 423 */ 424 @Override 425 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() { 426 if (isEmpty()) { 427 return EmptyOrderedIterator.<Map.Entry<K, V>>emptyOrderedIterator(); 428 } 429 return new EntrySetIterator<>(this); 430 } 431 432 /** 433 * Creates a key set iterator. 434 * Subclasses can override this to return iterators with different properties. 435 * 436 * @return the keySet iterator 437 */ 438 @Override 439 protected Iterator<K> createKeySetIterator() { 440 if (isEmpty()) { 441 return EmptyOrderedIterator.<K>emptyOrderedIterator(); 442 } 443 return new KeySetIterator<>(this); 444 } 445 446 /** 447 * Creates a values iterator. 448 * Subclasses can override this to return iterators with different properties. 449 * 450 * @return the values iterator 451 */ 452 @Override 453 protected Iterator<V> createValuesIterator() { 454 if (isEmpty()) { 455 return EmptyOrderedIterator.<V>emptyOrderedIterator(); 456 } 457 return new ValuesIterator<>(this); 458 } 459 460 /** 461 * Gets the {@code after} field from a {@code LinkEntry}. 462 * Used in subclasses that have no visibility of the field. 463 * 464 * @param entry the entry to query, must not be null 465 * @return the {@code after} field of the entry 466 * @throws NullPointerException if the entry is null 467 * @since 3.1 468 */ 469 protected LinkEntry<K, V> entryAfter(final LinkEntry<K, V> entry) { 470 return entry.after; 471 } 472 473 /** 474 * Gets the {@code before} field from a {@code LinkEntry}. 475 * Used in subclasses that have no visibility of the field. 476 * 477 * @param entry the entry to query, must not be null 478 * @return the {@code before} field of the entry 479 * @throws NullPointerException if the entry is null 480 * @since 3.1 481 */ 482 protected LinkEntry<K, V> entryBefore(final LinkEntry<K, V> entry) { 483 return entry.before; 484 } 485 486 /** 487 * Gets the first key in the map, which is the first inserted. 488 * 489 * @return the eldest key 490 */ 491 @Override 492 public K firstKey() { 493 if (size == 0) { 494 throw new NoSuchElementException("Map is empty"); 495 } 496 return header.after.getKey(); 497 } 498 499 /** 500 * Gets the key at the specified index. 501 * 502 * @param index the index to retrieve 503 * @return the key at the specified index 504 * @throws IndexOutOfBoundsException if the index is invalid 505 */ 506 protected LinkEntry<K, V> getEntry(final int index) { 507 if (index < 0) { 508 throw new IndexOutOfBoundsException("Index " + index + " is less than zero"); 509 } 510 if (index >= size) { 511 throw new IndexOutOfBoundsException("Index " + index + " is invalid for size " + size); 512 } 513 LinkEntry<K, V> entry; 514 if (index < size / 2) { 515 // Search forwards 516 entry = header.after; 517 for (int currentIndex = 0; currentIndex < index; currentIndex++) { 518 entry = entry.after; 519 } 520 } else { 521 // Search backwards 522 entry = header; 523 for (int currentIndex = size; currentIndex > index; currentIndex--) { 524 entry = entry.before; 525 } 526 } 527 return entry; 528 } 529 530 @Override 531 protected LinkEntry<K, V> getEntry(final Object key) { 532 return (LinkEntry<K, V>) super.getEntry(key); 533 } 534 535 /** 536 * Initialize this subclass during construction. 537 * <p> 538 * NOTE: As from v3.2 this method calls 539 * {@link #createEntry(HashEntry, int, Object, Object)} to create 540 * the map entry object. 541 */ 542 @Override 543 protected void init() { 544 header = createEntry(null, -1, null, null); 545 header.before = header.after = header; 546 } 547 548 /** 549 * Gets the last key in the map, which is the most recently inserted. 550 * 551 * @return the most recently inserted key 552 */ 553 @Override 554 public K lastKey() { 555 if (size == 0) { 556 throw new NoSuchElementException("Map is empty"); 557 } 558 return header.before.getKey(); 559 } 560 561 /** 562 * {@inheritDoc} 563 */ 564 @Override 565 public OrderedMapIterator<K, V> mapIterator() { 566 if (size == 0) { 567 return EmptyOrderedMapIterator.<K, V>emptyOrderedMapIterator(); 568 } 569 return new LinkMapIterator<>(this); 570 } 571 572 /** 573 * Gets the next key in sequence. 574 * 575 * @param key the key to get after 576 * @return the next key 577 */ 578 @Override 579 public K nextKey(final Object key) { 580 final LinkEntry<K, V> entry = getEntry(key); 581 return entry == null || entry.after == header ? null : entry.after.getKey(); 582 } 583 584 /** 585 * Gets the previous key in sequence. 586 * 587 * @param key the key to get before 588 * @return the previous key 589 */ 590 @Override 591 public K previousKey(final Object key) { 592 final LinkEntry<K, V> entry = getEntry(key); 593 return entry == null || entry.before == header ? null : entry.before.getKey(); 594 } 595 596 /** 597 * Removes an entry from the map and the linked list. 598 * <p> 599 * This implementation removes the entry from the linked list chain, then 600 * calls the superclass implementation. 601 * 602 * @param entry the entry to remove 603 * @param hashIndex the index into the data structure 604 * @param previous the previous entry in the chain 605 */ 606 @Override 607 protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) { 608 final LinkEntry<K, V> link = (LinkEntry<K, V>) entry; 609 link.before.after = link.after; 610 link.after.before = link.before; 611 link.after = null; 612 link.before = null; 613 super.removeEntry(entry, hashIndex, previous); 614 } 615 616}