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