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.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.util.AbstractList; 024import java.util.AbstractSet; 025import java.util.ArrayList; 026import java.util.Collection; 027import java.util.HashMap; 028import java.util.Iterator; 029import java.util.List; 030import java.util.ListIterator; 031import java.util.Map; 032import java.util.NoSuchElementException; 033import java.util.Set; 034 035import org.apache.commons.collections4.OrderedMap; 036import org.apache.commons.collections4.OrderedMapIterator; 037import org.apache.commons.collections4.ResettableIterator; 038import org.apache.commons.collections4.iterators.AbstractUntypedIteratorDecorator; 039import org.apache.commons.collections4.keyvalue.AbstractMapEntry; 040import org.apache.commons.collections4.list.UnmodifiableList; 041 042/** 043 * Decorates a <code>Map</code> to ensure that the order of addition is retained 044 * using a <code>List</code> to maintain order. 045 * <p> 046 * The order will be used via the iterators and toArray methods on the views. 047 * The order is also returned by the <code>MapIterator</code>. 048 * The <code>orderedMapIterator()</code> method accesses an iterator that can 049 * iterate both forwards and backwards through the map. 050 * In addition, non-interface methods are provided to access the map by index. 051 * </p> 052 * <p> 053 * If an object is added to the Map for a second time, it will remain in the 054 * original position in the iteration. 055 * </p> 056 * <p> 057 * <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong> 058 * If you wish to use this map from multiple threads concurrently, you must use 059 * appropriate synchronization. The simplest approach is to wrap this map 060 * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 061 * exceptions when accessed by concurrent threads without synchronization. 062 * </p> 063 * <p> 064 * <strong>Note that ListOrderedMap doesn't work with 065 * {@link java.util.IdentityHashMap IdentityHashMap}, {@link CaseInsensitiveMap}, 066 * or similar maps that violate the general contract of {@link java.util.Map}.</strong> 067 * The <code>ListOrderedMap</code> (or, more precisely, the underlying <code>List</code>) 068 * is relying on {@link Object#equals(Object) equals()}. This is fine, as long as the 069 * decorated <code>Map</code> is also based on {@link Object#equals(Object) equals()}, 070 * and {@link Object#hashCode() hashCode()}, which 071 * {@link java.util.IdentityHashMap IdentityHashMap}, and 072 * {@link CaseInsensitiveMap} don't: The former uses <code>==</code>, and 073 * the latter uses {@link Object#equals(Object) equals()} on a lower-cased 074 * key. 075 * </p> 076 * <p> 077 * This class is {@link Serializable} starting with Commons Collections 3.1. 078 * </p> 079 * 080 * @param <K> the type of the keys in this map 081 * @param <V> the type of the values in this map 082 * @since 3.0 083 */ 084public class ListOrderedMap<K, V> 085 extends AbstractMapDecorator<K, V> 086 implements OrderedMap<K, V>, Serializable { 087 088 /** Serialization version */ 089 private static final long serialVersionUID = 2728177751851003750L; 090 091 /** Internal list to hold the sequence of objects */ 092 private final List<K> insertOrder = new ArrayList<>(); 093 094 /** 095 * Factory method to create an ordered map. 096 * <p> 097 * An <code>ArrayList</code> is used to retain order. 098 * 099 * @param <K> the key type 100 * @param <V> the value type 101 * @param map the map to decorate, must not be null 102 * @return a new list ordered map 103 * @throws NullPointerException if map is null 104 * @since 4.0 105 */ 106 public static <K, V> ListOrderedMap<K, V> listOrderedMap(final Map<K, V> map) { 107 return new ListOrderedMap<>(map); 108 } 109 110 //----------------------------------------------------------------------- 111 /** 112 * Constructs a new empty <code>ListOrderedMap</code> that decorates 113 * a <code>HashMap</code>. 114 * 115 * @since 3.1 116 */ 117 public ListOrderedMap() { 118 this(new HashMap<K, V>()); 119 } 120 121 /** 122 * Constructor that wraps (not copies). 123 * 124 * @param map the map to decorate, must not be null 125 * @throws NullPointerException if map is null 126 */ 127 protected ListOrderedMap(final Map<K, V> map) { 128 super(map); 129 insertOrder.addAll(decorated().keySet()); 130 } 131 132 //----------------------------------------------------------------------- 133 /** 134 * Write the map out using a custom routine. 135 * 136 * @param out the output stream 137 * @throws IOException if an error occurs while writing to the stream 138 * @since 3.1 139 */ 140 private void writeObject(final ObjectOutputStream out) throws IOException { 141 out.defaultWriteObject(); 142 out.writeObject(map); 143 } 144 145 /** 146 * Read the map in using a custom routine. 147 * 148 * @param in the input stream 149 * @throws IOException if an error occurs while reading from the stream 150 * @throws ClassNotFoundException if an object read from the stream can not be loaded 151 * @since 3.1 152 */ 153 @SuppressWarnings("unchecked") // (1) should only fail if input stream is incorrect 154 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 155 in.defaultReadObject(); 156 map = (Map<K, V>) in.readObject(); // (1) 157 } 158 159 // Implement OrderedMap 160 //----------------------------------------------------------------------- 161 @Override 162 public OrderedMapIterator<K, V> mapIterator() { 163 return new ListOrderedMapIterator<>(this); 164 } 165 166 /** 167 * Gets the first key in this map by insert order. 168 * 169 * @return the first key currently in this map 170 * @throws NoSuchElementException if this map is empty 171 */ 172 @Override 173 public K firstKey() { 174 if (size() == 0) { 175 throw new NoSuchElementException("Map is empty"); 176 } 177 return insertOrder.get(0); 178 } 179 180 /** 181 * Gets the last key in this map by insert order. 182 * 183 * @return the last key currently in this map 184 * @throws NoSuchElementException if this map is empty 185 */ 186 @Override 187 public K lastKey() { 188 if (size() == 0) { 189 throw new NoSuchElementException("Map is empty"); 190 } 191 return insertOrder.get(size() - 1); 192 } 193 194 /** 195 * Gets the next key to the one specified using insert order. 196 * This method performs a list search to find the key and is O(n). 197 * 198 * @param key the key to find previous for 199 * @return the next key, null if no match or at start 200 */ 201 @Override 202 public K nextKey(final Object key) { 203 final int index = insertOrder.indexOf(key); 204 if (index >= 0 && index < size() - 1) { 205 return insertOrder.get(index + 1); 206 } 207 return null; 208 } 209 210 /** 211 * Gets the previous key to the one specified using insert order. 212 * This method performs a list search to find the key and is O(n). 213 * 214 * @param key the key to find previous for 215 * @return the previous key, null if no match or at start 216 */ 217 @Override 218 public K previousKey(final Object key) { 219 final int index = insertOrder.indexOf(key); 220 if (index > 0) { 221 return insertOrder.get(index - 1); 222 } 223 return null; 224 } 225 226 //----------------------------------------------------------------------- 227 @Override 228 public V put(final K key, final V value) { 229 if (decorated().containsKey(key)) { 230 // re-adding doesn't change order 231 return decorated().put(key, value); 232 } 233 // first add, so add to both map and list 234 final V result = decorated().put(key, value); 235 insertOrder.add(key); 236 return result; 237 } 238 239 @Override 240 public void putAll(final Map<? extends K, ? extends V> map) { 241 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 242 put(entry.getKey(), entry.getValue()); 243 } 244 } 245 246 /** 247 * Puts the values contained in a supplied Map into the Map starting at 248 * the specified index. 249 * 250 * @param index the index in the Map to start at. 251 * @param map the Map containing the entries to be added. 252 * @throws IndexOutOfBoundsException if the index is out of range [0, size] 253 */ 254 public void putAll(int index, final Map<? extends K, ? extends V> map) { 255 if (index < 0 || index > insertOrder.size()) { 256 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size()); 257 } 258 for (final Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 259 final K key = entry.getKey(); 260 final boolean contains = containsKey(key); 261 // The return value of put is null if the key did not exist OR the value was null 262 // so it cannot be used to determine whether the key was added 263 put(index, entry.getKey(), entry.getValue()); 264 if (!contains) { 265 // if no key was replaced, increment the index 266 index++; 267 } else { 268 // otherwise put the next item after the currently inserted key 269 index = indexOf(entry.getKey()) + 1; 270 } 271 } 272 } 273 274 @Override 275 public V remove(final Object key) { 276 V result = null; 277 if (decorated().containsKey(key)) { 278 result = decorated().remove(key); 279 insertOrder.remove(key); 280 } 281 return result; 282 } 283 284 @Override 285 public void clear() { 286 decorated().clear(); 287 insertOrder.clear(); 288 } 289 290 //----------------------------------------------------------------------- 291 /** 292 * Gets a view over the keys in the map. 293 * <p> 294 * The Collection will be ordered by object insertion into the map. 295 * 296 * @see #keyList() 297 * @return the fully modifiable collection view over the keys 298 */ 299 @Override 300 public Set<K> keySet() { 301 return new KeySetView<>(this); 302 } 303 304 /** 305 * Gets a view over the keys in the map as a List. 306 * <p> 307 * The List will be ordered by object insertion into the map. 308 * The List is unmodifiable. 309 * 310 * @see #keySet() 311 * @return the unmodifiable list view over the keys 312 * @since 3.2 313 */ 314 public List<K> keyList() { 315 return UnmodifiableList.unmodifiableList(insertOrder); 316 } 317 318 /** 319 * Gets a view over the values in the map. 320 * <p> 321 * The Collection will be ordered by object insertion into the map. 322 * <p> 323 * From Commons Collections 3.2, this Collection can be cast 324 * to a list, see {@link #valueList()} 325 * 326 * @see #valueList() 327 * @return the fully modifiable collection view over the values 328 */ 329 @Override 330 public Collection<V> values() { 331 return new ValuesView<>(this); 332 } 333 334 /** 335 * Gets a view over the values in the map as a List. 336 * <p> 337 * The List will be ordered by object insertion into the map. 338 * The List supports remove and set, but does not support add. 339 * 340 * @see #values() 341 * @return the partially modifiable list view over the values 342 * @since 3.2 343 */ 344 public List<V> valueList() { 345 return new ValuesView<>(this); 346 } 347 348 /** 349 * Gets a view over the entries in the map. 350 * <p> 351 * The Set will be ordered by object insertion into the map. 352 * 353 * @return the fully modifiable set view over the entries 354 */ 355 @Override 356 public Set<Map.Entry<K, V>> entrySet() { 357 return new EntrySetView<>(this, this.insertOrder); 358 } 359 360 //----------------------------------------------------------------------- 361 /** 362 * Returns the Map as a string. 363 * 364 * @return the Map as a String 365 */ 366 @Override 367 public String toString() { 368 if (isEmpty()) { 369 return "{}"; 370 } 371 final StringBuilder buf = new StringBuilder(); 372 buf.append('{'); 373 boolean first = true; 374 for (final Map.Entry<K, V> entry : entrySet()) { 375 final K key = entry.getKey(); 376 final V value = entry.getValue(); 377 if (first) { 378 first = false; 379 } else { 380 buf.append(", "); 381 } 382 buf.append(key == this ? "(this Map)" : key); 383 buf.append('='); 384 buf.append(value == this ? "(this Map)" : value); 385 } 386 buf.append('}'); 387 return buf.toString(); 388 } 389 390 //----------------------------------------------------------------------- 391 /** 392 * Gets the key at the specified index. 393 * 394 * @param index the index to retrieve 395 * @return the key at the specified index 396 * @throws IndexOutOfBoundsException if the index is invalid 397 */ 398 public K get(final int index) { 399 return insertOrder.get(index); 400 } 401 402 /** 403 * Gets the value at the specified index. 404 * 405 * @param index the index to retrieve 406 * @return the key at the specified index 407 * @throws IndexOutOfBoundsException if the index is invalid 408 */ 409 public V getValue(final int index) { 410 return get(insertOrder.get(index)); 411 } 412 413 /** 414 * Gets the index of the specified key. 415 * 416 * @param key the key to find the index of 417 * @return the index, or -1 if not found 418 */ 419 public int indexOf(final Object key) { 420 return insertOrder.indexOf(key); 421 } 422 423 /** 424 * Sets the value at the specified index. 425 * 426 * @param index the index of the value to set 427 * @param value the new value to set 428 * @return the previous value at that index 429 * @throws IndexOutOfBoundsException if the index is invalid 430 * @since 3.2 431 */ 432 public V setValue(final int index, final V value) { 433 final K key = insertOrder.get(index); 434 return put(key, value); 435 } 436 437 /** 438 * Puts a key-value mapping into the map at the specified index. 439 * <p> 440 * If the map already contains the key, then the original mapping 441 * is removed and the new mapping added at the specified index. 442 * The remove may change the effect of the index. The index is 443 * always calculated relative to the original state of the map. 444 * <p> 445 * Thus the steps are: (1) remove the existing key-value mapping, 446 * then (2) insert the new key-value mapping at the position it 447 * would have been inserted had the remove not occurred. 448 * 449 * @param index the index at which the mapping should be inserted 450 * @param key the key 451 * @param value the value 452 * @return the value previously mapped to the key 453 * @throws IndexOutOfBoundsException if the index is out of range [0, size] 454 * @since 3.2 455 */ 456 public V put(int index, final K key, final V value) { 457 if (index < 0 || index > insertOrder.size()) { 458 throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + insertOrder.size()); 459 } 460 461 final Map<K, V> m = decorated(); 462 if (m.containsKey(key)) { 463 final V result = m.remove(key); 464 final int pos = insertOrder.indexOf(key); 465 insertOrder.remove(pos); 466 if (pos < index) { 467 index--; 468 } 469 insertOrder.add(index, key); 470 m.put(key, value); 471 return result; 472 } 473 insertOrder.add(index, key); 474 m.put(key, value); 475 return null; 476 } 477 478 /** 479 * Removes the element at the specified index. 480 * 481 * @param index the index of the object to remove 482 * @return the removed value, or <code>null</code> if none existed 483 * @throws IndexOutOfBoundsException if the index is invalid 484 */ 485 public V remove(final int index) { 486 return remove(get(index)); 487 } 488 489 /** 490 * Gets an unmodifiable List view of the keys which changes as the map changes. 491 * <p> 492 * The returned list is unmodifiable because changes to the values of 493 * the list (using {@link java.util.ListIterator#set(Object)}) will 494 * effectively remove the value from the list and reinsert that value at 495 * the end of the list, which is an unexpected side effect of changing the 496 * value of a list. This occurs because changing the key, changes when the 497 * mapping is added to the map and thus where it appears in the list. 498 * <p> 499 * An alternative to this method is to use the better named 500 * {@link #keyList()} or {@link #keySet()}. 501 * 502 * @see #keyList() 503 * @see #keySet() 504 * @return The ordered list of keys. 505 */ 506 public List<K> asList() { 507 return keyList(); 508 } 509 510 //----------------------------------------------------------------------- 511 static class ValuesView<V> extends AbstractList<V> { 512 private final ListOrderedMap<Object, V> parent; 513 514 @SuppressWarnings("unchecked") 515 ValuesView(final ListOrderedMap<?, V> parent) { 516 super(); 517 this.parent = (ListOrderedMap<Object, V>) parent; 518 } 519 520 @Override 521 public int size() { 522 return this.parent.size(); 523 } 524 525 @Override 526 public boolean contains(final Object value) { 527 return this.parent.containsValue(value); 528 } 529 530 @Override 531 public void clear() { 532 this.parent.clear(); 533 } 534 535 @Override 536 public Iterator<V> iterator() { 537 return new AbstractUntypedIteratorDecorator<Map.Entry<Object, V>, V>(parent.entrySet().iterator()) { 538 @Override 539 public V next() { 540 return getIterator().next().getValue(); 541 } 542 }; 543 } 544 545 @Override 546 public V get(final int index) { 547 return this.parent.getValue(index); 548 } 549 550 @Override 551 public V set(final int index, final V value) { 552 return this.parent.setValue(index, value); 553 } 554 555 @Override 556 public V remove(final int index) { 557 return this.parent.remove(index); 558 } 559 } 560 561 //----------------------------------------------------------------------- 562 static class KeySetView<K> extends AbstractSet<K> { 563 private final ListOrderedMap<K, Object> parent; 564 565 @SuppressWarnings("unchecked") 566 KeySetView(final ListOrderedMap<K, ?> parent) { 567 super(); 568 this.parent = (ListOrderedMap<K, Object>) parent; 569 } 570 571 @Override 572 public int size() { 573 return this.parent.size(); 574 } 575 576 @Override 577 public boolean contains(final Object value) { 578 return this.parent.containsKey(value); 579 } 580 581 @Override 582 public void clear() { 583 this.parent.clear(); 584 } 585 586 @Override 587 public Iterator<K> iterator() { 588 return new AbstractUntypedIteratorDecorator<Map.Entry<K, Object>, K>(parent.entrySet().iterator()) { 589 @Override 590 public K next() { 591 return getIterator().next().getKey(); 592 } 593 }; 594 } 595 } 596 597 //----------------------------------------------------------------------- 598 static class EntrySetView<K, V> extends AbstractSet<Map.Entry<K, V>> { 599 private final ListOrderedMap<K, V> parent; 600 private final List<K> insertOrder; 601 private Set<Map.Entry<K, V>> entrySet; 602 603 public EntrySetView(final ListOrderedMap<K, V> parent, final List<K> insertOrder) { 604 super(); 605 this.parent = parent; 606 this.insertOrder = insertOrder; 607 } 608 609 private Set<Map.Entry<K, V>> getEntrySet() { 610 if (entrySet == null) { 611 entrySet = parent.decorated().entrySet(); 612 } 613 return entrySet; 614 } 615 616 @Override 617 public int size() { 618 return this.parent.size(); 619 } 620 @Override 621 public boolean isEmpty() { 622 return this.parent.isEmpty(); 623 } 624 625 @Override 626 public boolean contains(final Object obj) { 627 return getEntrySet().contains(obj); 628 } 629 630 @Override 631 public boolean containsAll(final Collection<?> coll) { 632 return getEntrySet().containsAll(coll); 633 } 634 635 @Override 636 @SuppressWarnings("unchecked") 637 public boolean remove(final Object obj) { 638 if (obj instanceof Map.Entry == false) { 639 return false; 640 } 641 if (getEntrySet().contains(obj)) { 642 final Object key = ((Map.Entry<K, V>) obj).getKey(); 643 parent.remove(key); 644 return true; 645 } 646 return false; 647 } 648 649 @Override 650 public void clear() { 651 this.parent.clear(); 652 } 653 654 @Override 655 public boolean equals(final Object obj) { 656 if (obj == this) { 657 return true; 658 } 659 return getEntrySet().equals(obj); 660 } 661 662 @Override 663 public int hashCode() { 664 return getEntrySet().hashCode(); 665 } 666 667 @Override 668 public String toString() { 669 return getEntrySet().toString(); 670 } 671 672 @Override 673 public Iterator<Map.Entry<K, V>> iterator() { 674 return new ListOrderedIterator<>(parent, insertOrder); 675 } 676 } 677 678 //----------------------------------------------------------------------- 679 static class ListOrderedIterator<K, V> extends AbstractUntypedIteratorDecorator<K, Map.Entry<K, V>> { 680 private final ListOrderedMap<K, V> parent; 681 private K last = null; 682 683 ListOrderedIterator(final ListOrderedMap<K, V> parent, final List<K> insertOrder) { 684 super(insertOrder.iterator()); 685 this.parent = parent; 686 } 687 688 @Override 689 public Map.Entry<K, V> next() { 690 last = getIterator().next(); 691 return new ListOrderedMapEntry<>(parent, last); 692 } 693 694 @Override 695 public void remove() { 696 super.remove(); 697 parent.decorated().remove(last); 698 } 699 } 700 701 //----------------------------------------------------------------------- 702 static class ListOrderedMapEntry<K, V> extends AbstractMapEntry<K, V> { 703 private final ListOrderedMap<K, V> parent; 704 705 ListOrderedMapEntry(final ListOrderedMap<K, V> parent, final K key) { 706 super(key, null); 707 this.parent = parent; 708 } 709 710 @Override 711 public V getValue() { 712 return parent.get(getKey()); 713 } 714 715 @Override 716 public V setValue(final V value) { 717 return parent.decorated().put(getKey(), value); 718 } 719 } 720 721 //----------------------------------------------------------------------- 722 static class ListOrderedMapIterator<K, V> implements OrderedMapIterator<K, V>, ResettableIterator<K> { 723 private final ListOrderedMap<K, V> parent; 724 private ListIterator<K> iterator; 725 private K last = null; 726 private boolean readable = false; 727 728 ListOrderedMapIterator(final ListOrderedMap<K, V> parent) { 729 super(); 730 this.parent = parent; 731 this.iterator = parent.insertOrder.listIterator(); 732 } 733 734 @Override 735 public boolean hasNext() { 736 return iterator.hasNext(); 737 } 738 739 @Override 740 public K next() { 741 last = iterator.next(); 742 readable = true; 743 return last; 744 } 745 746 @Override 747 public boolean hasPrevious() { 748 return iterator.hasPrevious(); 749 } 750 751 @Override 752 public K previous() { 753 last = iterator.previous(); 754 readable = true; 755 return last; 756 } 757 758 @Override 759 public void remove() { 760 if (readable == false) { 761 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID); 762 } 763 iterator.remove(); 764 parent.map.remove(last); 765 readable = false; 766 } 767 768 @Override 769 public K getKey() { 770 if (readable == false) { 771 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID); 772 } 773 return last; 774 } 775 776 @Override 777 public V getValue() { 778 if (readable == false) { 779 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID); 780 } 781 return parent.get(last); 782 } 783 784 @Override 785 public V setValue(final V value) { 786 if (readable == false) { 787 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID); 788 } 789 return parent.map.put(last, value); 790 } 791 792 @Override 793 public void reset() { 794 iterator = parent.insertOrder.listIterator(); 795 last = null; 796 readable = false; 797 } 798 799 @Override 800 public String toString() { 801 if (readable == true) { 802 return "Iterator[" + getKey() + "=" + getValue() + "]"; 803 } 804 return "Iterator[]"; 805 } 806 } 807 808}