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