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