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 }