dependencies/plugins/org.apache.commons.collections/source-bundle/org/apache/commons/collections/map/ListOrderedMap.java - gerrit/amp/org.eclipse.amp - Git at Google

 /*
  *  Copyright 2003-2006 The Apache Software Foundation
  *
  *  Licensed under the Apache License, Version 2.0 (the "License");
  *  you may not use this file except in compliance with the License.
  *  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  *  Unless required by applicable law or agreed to in writing, software
  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
 package org.apache.commons.collections.map;

 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
 import java.io.Serializable;
 import java.util.AbstractList;
 import java.util.AbstractSet;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.ListIterator;
 import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;

 import org.apache.commons.collections.MapIterator;
 import org.apache.commons.collections.OrderedMap;
 import org.apache.commons.collections.OrderedMapIterator;
 import org.apache.commons.collections.ResettableIterator;
 import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
 import org.apache.commons.collections.keyvalue.AbstractMapEntry;
 import org.apache.commons.collections.list.UnmodifiableList;

 /**
  * Decorates a <code>Map</code> to ensure that the order of addition is retained
  * using a <code>List</code> to maintain order.
  * <p>
  * The order will be used via the iterators and toArray methods on the views.
  * The order is also returned by the <code>MapIterator</code>.
  * The <code>orderedMapIterator()</code> method accesses an iterator that can
  * iterate both forwards and backwards through the map.
  * In addition, non-interface methods are provided to access the map by index.
  * <p>
  * If an object is added to the Map for a second time, it will remain in the
  * original position in the iteration.
  * <p>
  * <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong>
  * If you wish to use this map from multiple threads concurrently, you must use
  * appropriate synchronization. The simplest approach is to wrap this map
  * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
  * exceptions when accessed by concurrent threads without synchronization.
  * <p>
  * This class is Serializable from Commons Collections 3.1.
  *
  * @since Commons Collections 3.0
  * @version $Revision: 1.1 $ $Date: 2009/05/27 22:16:30 $
  *
  * @author Henri Yandell
  * @author Stephen Colebourne
  * @author Matt Benson
  */
 public class ListOrderedMap
         extends AbstractMapDecorator
         implements OrderedMap, Serializable {

     /** Serialization version */
     private static final long serialVersionUID = 2728177751851003750L;

     /** Internal list to hold the sequence of objects */
     protected final List insertOrder = new ArrayList();

     /**
      * Factory method to create an ordered map.
      * <p>
      * An <code>ArrayList</code> is used to retain order.
      *
      * @param map  the map to decorate, must not be null
      * @throws IllegalArgumentException if map is null
      */
     public static OrderedMap decorate(Map map) {
         return new ListOrderedMap(map);
     }

     //-----------------------------------------------------------------------
     /**
      * Constructs a new empty <code>ListOrderedMap</code> that decorates
      * a <code>HashMap</code>.
      *
      * @since Commons Collections 3.1
      */
     public ListOrderedMap() {
         this(new HashMap());
     }

     /**
      * Constructor that wraps (not copies).
      *
      * @param map  the map to decorate, must not be null
      * @throws IllegalArgumentException if map is null
      */
     protected ListOrderedMap(Map map) {
         super(map);
         insertOrder.addAll(getMap().keySet());
     }

     //-----------------------------------------------------------------------
     /**
      * Write the map out using a custom routine.
      *
      * @param out  the output stream
      * @throws IOException
      * @since Commons Collections 3.1
      */
     private void writeObject(ObjectOutputStream out) throws IOException {
         out.defaultWriteObject();
         out.writeObject(map);
     }

     /**
      * Read the map in using a custom routine.
      *
      * @param in  the input stream
      * @throws IOException
      * @throws ClassNotFoundException
      * @since Commons Collections 3.1
      */
     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
         in.defaultReadObject();
         map = (Map) in.readObject();
     }

     // Implement OrderedMap
     //-----------------------------------------------------------------------
     public MapIterator mapIterator() {
         return orderedMapIterator();
     }

     public OrderedMapIterator orderedMapIterator() {
         return new ListOrderedMapIterator(this);
     }

     /**
      * Gets the first key in this map by insert order.
      *
      * @return the first key currently in this map
      * @throws NoSuchElementException if this map is empty
      */
     public Object firstKey() {
         if (size() == 0) {
             throw new NoSuchElementException("Map is empty");
         }
         return insertOrder.get(0);
     }

     /**
      * Gets the last key in this map by insert order.
      *
      * @return the last key currently in this map
      * @throws NoSuchElementException if this map is empty
      */
     public Object lastKey() {
         if (size() == 0) {
             throw new NoSuchElementException("Map is empty");
         }
         return insertOrder.get(size() - 1);
     }

     /**
      * Gets the next key to the one specified using insert order.
      * This method performs a list search to find the key and is O(n).
      *
      * @param key  the key to find previous for
      * @return the next key, null if no match or at start
      */
     public Object nextKey(Object key) {
         int index = insertOrder.indexOf(key);
         if (index >= 0 && index < size() - 1) {
             return insertOrder.get(index + 1);
         }
         return null;
     }

     /**
      * Gets the previous key to the one specified using insert order.
      * This method performs a list search to find the key and is O(n).
      *
      * @param key  the key to find previous for
      * @return the previous key, null if no match or at start
      */
     public Object previousKey(Object key) {
         int index = insertOrder.indexOf(key);
         if (index > 0) {
             return insertOrder.get(index - 1);
         }
         return null;
     }

     //-----------------------------------------------------------------------
     public Object put(Object key, Object value) {
         if (getMap().containsKey(key)) {
             // re-adding doesn't change order
             return getMap().put(key, value);
         } else {
             // first add, so add to both map and list
             Object result = getMap().put(key, value);
             insertOrder.add(key);
             return result;
         }
     }

     public void putAll(Map map) {
         for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
             Map.Entry entry = (Map.Entry) it.next();
             put(entry.getKey(), entry.getValue());
         }
     }

     public Object remove(Object key) {
         Object result = getMap().remove(key);
         insertOrder.remove(key);
         return result;
     }

     public void clear() {
         getMap().clear();
         insertOrder.clear();
     }

     //-----------------------------------------------------------------------
     /**
      * Gets a view over the keys in the map.
      * <p>
      * The Collection will be ordered by object insertion into the map.
      *
      * @see #keyList()
      * @return the fully modifiable collection view over the keys
      */
     public Set keySet() {
         return new KeySetView(this);
     }

     /**
      * Gets a view over the keys in the map as a List.
      * <p>
      * The List will be ordered by object insertion into the map.
      * The List is unmodifiable.
      *
      * @see #keySet()
      * @return the unmodifiable list view over the keys
      * @since Commons Collections 3.2
      */
     public List keyList() {
         return UnmodifiableList.decorate(insertOrder);
     }

     /**
      * Gets a view over the values in the map.
      * <p>
      * The Collection will be ordered by object insertion into the map.
      * <p>
      * From Commons Collections 3.2, this Collection can be cast
      * to a list, see {@link #valueList()}
      *
      * @see #valueList()
      * @return the fully modifiable collection view over the values
      */
     public Collection values() {
         return new ValuesView(this);
     }

     /**
      * Gets a view over the values in the map as a List.
      * <p>
      * The List will be ordered by object insertion into the map.
      * The List supports remove and set, but does not support add.
      *
      * @see #values()
      * @return the partially modifiable list view over the values
      * @since Commons Collections 3.2
      */
     public List valueList() {
         return new ValuesView(this);
     }

     /**
      * Gets a view over the entries in the map.
      * <p>
      * The Set will be ordered by object insertion into the map.
      *
      * @return the fully modifiable set view over the entries
      */
     public Set entrySet() {
         return new EntrySetView(this, this.insertOrder);
     }

     //-----------------------------------------------------------------------
     /**
      * Returns the Map as a string.
      *
      * @return the Map as a String
      */
     public String toString() {
         if (isEmpty()) {
             return "{}";
         }
         StringBuffer buf = new StringBuffer();
         buf.append('{');
         boolean first = true;
         Iterator it = entrySet().iterator();
         while (it.hasNext()) {
             Map.Entry entry = (Map.Entry) it.next();
             Object key = entry.getKey();
             Object value = entry.getValue();
             if (first) {
                 first = false;
             } else {
                 buf.append(", ");
             }
             buf.append(key == this ? "(this Map)" : key);
             buf.append('=');
             buf.append(value == this ? "(this Map)" : value);
         }
         buf.append('}');
         return buf.toString();
     }

     //-----------------------------------------------------------------------
     /**
      * Gets the key at the specified index.
      *
      * @param index  the index to retrieve
      * @return the key at the specified index
      * @throws IndexOutOfBoundsException if the index is invalid
      */
     public Object get(int index) {
         return insertOrder.get(index);
     }

     /**
      * Gets the value at the specified index.
      *
      * @param index  the index to retrieve
      * @return the key at the specified index
      * @throws IndexOutOfBoundsException if the index is invalid
      */
     public Object getValue(int index) {
         return get(insertOrder.get(index));
     }

     /**
      * Gets the index of the specified key.
      *
      * @param key  the key to find the index of
      * @return the index, or -1 if not found
      */
     public int indexOf(Object key) {
         return insertOrder.indexOf(key);
     }

     /**
      * Sets the value at the specified index.
      *
      * @param index  the index of the value to set
      * @return the previous value at that index
      * @throws IndexOutOfBoundsException if the index is invalid
      * @since Commons Collections 3.2
      */
     public Object setValue(int index, Object value) {
         Object key = insertOrder.get(index);
         return put(key, value);
     }

     /**
      * Puts a key-value mapping into the map at the specified index.
      * <p>
      * If the map already contains the key, then the original mapping
      * is removed and the new mapping added at the specified index.
      * The remove may change the effect of the index. The index is
      * always calculated relative to the original state of the map.
      * <p>
      * Thus the steps are: (1) remove the existing key-value mapping,
      * then (2) insert the new key-value mapping at the position it
      * would have been inserted had the remove not ocurred.
      *
      * @param index  the index at which the mapping should be inserted
      * @param key  the key
      * @param value  the value
      * @return the value previously mapped to the key
      * @throws IndexOutOfBoundsException if the index is out of range
      * @since Commons Collections 3.2
      */
     public Object put(int index, Object key, Object value) {
         Map m = getMap();
         if (m.containsKey(key)) {
             Object result = m.remove(key);
             int pos = insertOrder.indexOf(key);
             insertOrder.remove(pos);
             if (pos < index) {
                 index--;
             }
             insertOrder.add(index, key);
             m.put(key, value);
             return result;
         } else {
             insertOrder.add(index, key);
             m.put(key, value);
             return null;
         }
     }

     /**
      * Removes the element at the specified index.
      *
      * @param index  the index of the object to remove
      * @return the removed value, or <code>null</code> if none existed
      * @throws IndexOutOfBoundsException if the index is invalid
      */
     public Object remove(int index) {
         return remove(get(index));
     }

     /**
      * Gets an unmodifiable List view of the keys which changes as the map changes.
      * <p>
      * The returned list is unmodifiable because changes to the values of
      * the list (using {@link java.util.ListIterator#set(Object)}) will
      * effectively remove the value from the list and reinsert that value at
      * the end of the list, which is an unexpected side effect of changing the
      * value of a list.  This occurs because changing the key, changes when the
      * mapping is added to the map and thus where it appears in the list.
      * <p>
      * An alternative to this method is to use the better named
      * {@link #keyList()} or {@link #keySet()}.
      *
      * @see #keyList()
      * @see #keySet()
      * @return The ordered list of keys.
      */
     public List asList() {
         return keyList();
     }

     //-----------------------------------------------------------------------
     static class ValuesView extends AbstractList {
         private final ListOrderedMap parent;

         ValuesView(ListOrderedMap parent) {
             super();
             this.parent = parent;
         }

         public int size() {
             return this.parent.size();
         }

         public boolean contains(Object value) {
             return this.parent.containsValue(value);
         }

         public void clear() {
             this.parent.clear();
         }

         public Iterator iterator() {
             return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
                 public Object next() {
                     return ((Map.Entry) iterator.next()).getValue();
                 }
             };
         }

         public Object get(int index) {
             return this.parent.getValue(index);
         }

         public Object set(int index, Object value) {
             return this.parent.setValue(index, value);
         }

         public Object remove(int index) {
             return this.parent.remove(index);
         }
     }

     //-----------------------------------------------------------------------
     static class KeySetView extends AbstractSet {
         private final ListOrderedMap parent;

         KeySetView(ListOrderedMap parent) {
             super();
             this.parent = parent;
         }

         public int size() {
             return this.parent.size();
         }

         public boolean contains(Object value) {
             return this.parent.containsKey(value);
         }

         public void clear() {
             this.parent.clear();
         }

         public Iterator iterator() {
             return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
                 public Object next() {
                     return ((Map.Entry) super.next()).getKey();
                 }
             };
         }
     }

     //-----------------------------------------------------------------------
     static class EntrySetView extends AbstractSet {
         private final ListOrderedMap parent;
         private final List insertOrder;
         private Set entrySet;

         public EntrySetView(ListOrderedMap parent, List insertOrder) {
             super();
             this.parent = parent;
             this.insertOrder = insertOrder;
         }

         private Set getEntrySet() {
             if (entrySet == null) {
                 entrySet = parent.getMap().entrySet();
             }
             return entrySet;
         }

         public int size() {
             return this.parent.size();
         }
         public boolean isEmpty() {
             return this.parent.isEmpty();
         }

         public boolean contains(Object obj) {
             return getEntrySet().contains(obj);
         }

         public boolean containsAll(Collection coll) {
             return getEntrySet().containsAll(coll);
         }

         public boolean remove(Object obj) {
             if (obj instanceof Map.Entry == false) {
                 return false;
             }
             if (getEntrySet().contains(obj)) {
                 Object key = ((Map.Entry) obj).getKey();
                 parent.remove(key);
                 return true;
             }
             return false;
         }

         public void clear() {
             this.parent.clear();
         }

         public boolean equals(Object obj) {
             if (obj == this) {
                 return true;
             }
             return getEntrySet().equals(obj);
         }

         public int hashCode() {
             return getEntrySet().hashCode();
         }

         public String toString() {
             return getEntrySet().toString();
         }

         public Iterator iterator() {
             return new ListOrderedIterator(parent, insertOrder);
         }
     }

     //-----------------------------------------------------------------------
     static class ListOrderedIterator extends AbstractIteratorDecorator {
         private final ListOrderedMap parent;
         private Object last = null;

         ListOrderedIterator(ListOrderedMap parent, List insertOrder) {
             super(insertOrder.iterator());
             this.parent = parent;
         }

         public Object next() {
             last = super.next();
             return new ListOrderedMapEntry(parent, last);
         }

         public void remove() {
             super.remove();
             parent.getMap().remove(last);
         }
     }

     //-----------------------------------------------------------------------
     static class ListOrderedMapEntry extends AbstractMapEntry {
         private final ListOrderedMap parent;

         ListOrderedMapEntry(ListOrderedMap parent, Object key) {
             super(key, null);
             this.parent = parent;
         }

         public Object getValue() {
             return parent.get(key);
         }

         public Object setValue(Object value) {
             return parent.getMap().put(key, value);
         }
     }

     //-----------------------------------------------------------------------
     static class ListOrderedMapIterator implements OrderedMapIterator, ResettableIterator {
         private final ListOrderedMap parent;
         private ListIterator iterator;
         private Object last = null;
         private boolean readable = false;

         ListOrderedMapIterator(ListOrderedMap parent) {
             super();
             this.parent = parent;
             this.iterator = parent.insertOrder.listIterator();
         }

         public boolean hasNext() {
             return iterator.hasNext();
         }

         public Object next() {
             last = iterator.next();
             readable = true;
             return last;
         }

         public boolean hasPrevious() {
             return iterator.hasPrevious();
         }

         public Object previous() {
             last = iterator.previous();
             readable = true;
             return last;
         }

         public void remove() {
             if (readable == false) {
                 throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
             }
             iterator.remove();
             parent.map.remove(last);
             readable = false;
         }

         public Object getKey() {
             if (readable == false) {
                 throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
             }
             return last;
         }

         public Object getValue() {
             if (readable == false) {
                 throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
             }
             return parent.get(last);
         }

         public Object setValue(Object value) {
             if (readable == false) {
                 throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
             }
             return parent.map.put(last, value);
         }

         public void reset() {
             iterator = parent.insertOrder.listIterator();
             last = null;
             readable = false;
         }

         public String toString() {
             if (readable == true) {
                 return "Iterator[" + getKey() + "=" + getValue() + "]";
             } else {
                 return "Iterator[]";
             }
         }
     }

 }
	/*
	* Copyright 2003-2006 The Apache Software Foundation
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package org.apache.commons.collections.map;

	import java.io.IOException;
	import java.io.ObjectInputStream;
	import java.io.ObjectOutputStream;
	import java.io.Serializable;
	import java.util.AbstractList;
	import java.util.AbstractSet;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.HashMap;
	import java.util.Iterator;
	import java.util.List;
	import java.util.ListIterator;
	import java.util.Map;
	import java.util.NoSuchElementException;
	import java.util.Set;

	import org.apache.commons.collections.MapIterator;
	import org.apache.commons.collections.OrderedMap;
	import org.apache.commons.collections.OrderedMapIterator;
	import org.apache.commons.collections.ResettableIterator;
	import org.apache.commons.collections.iterators.AbstractIteratorDecorator;
	import org.apache.commons.collections.keyvalue.AbstractMapEntry;
	import org.apache.commons.collections.list.UnmodifiableList;

	/**
	* Decorates a <code>Map</code> to ensure that the order of addition is retained
	* using a <code>List</code> to maintain order.
	* <p>
	* The order will be used via the iterators and toArray methods on the views.
	* The order is also returned by the <code>MapIterator</code>.
	* The <code>orderedMapIterator()</code> method accesses an iterator that can
	* iterate both forwards and backwards through the map.
	* In addition, non-interface methods are provided to access the map by index.
	* <p>
	* If an object is added to the Map for a second time, it will remain in the
	* original position in the iteration.
	* <p>
	* <strong>Note that ListOrderedMap is not synchronized and is not thread-safe.</strong>
	* If you wish to use this map from multiple threads concurrently, you must use
	* appropriate synchronization. The simplest approach is to wrap this map
	* using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw
	* exceptions when accessed by concurrent threads without synchronization.
	* <p>
	* This class is Serializable from Commons Collections 3.1.
	*
	* @since Commons Collections 3.0
	* @version $Revision: 1.1 $ $Date: 2009/05/27 22:16:30 $
	*
	* @author Henri Yandell
	* @author Stephen Colebourne
	* @author Matt Benson
	*/
	public class ListOrderedMap
	extends AbstractMapDecorator
	implements OrderedMap, Serializable {

	/** Serialization version */
	private static final long serialVersionUID = 2728177751851003750L;

	/** Internal list to hold the sequence of objects */
	protected final List insertOrder = new ArrayList();

	/**
	* Factory method to create an ordered map.
	* <p>
	* An <code>ArrayList</code> is used to retain order.
	*
	* @param map the map to decorate, must not be null
	* @throws IllegalArgumentException if map is null
	*/
	public static OrderedMap decorate(Map map) {
	return new ListOrderedMap(map);
	}

	//-----------------------------------------------------------------------
	/**
	* Constructs a new empty <code>ListOrderedMap</code> that decorates
	* a <code>HashMap</code>.
	*
	* @since Commons Collections 3.1
	*/
	public ListOrderedMap() {
	this(new HashMap());
	}

	/**
	* Constructor that wraps (not copies).
	*
	* @param map the map to decorate, must not be null
	* @throws IllegalArgumentException if map is null
	*/
	protected ListOrderedMap(Map map) {
	super(map);
	insertOrder.addAll(getMap().keySet());
	}

	//-----------------------------------------------------------------------
	/**
	* Write the map out using a custom routine.
	*
	* @param out the output stream
	* @throws IOException
	* @since Commons Collections 3.1
	*/
	private void writeObject(ObjectOutputStream out) throws IOException {
	out.defaultWriteObject();
	out.writeObject(map);
	}

	/**
	* Read the map in using a custom routine.
	*
	* @param in the input stream
	* @throws IOException
	* @throws ClassNotFoundException
	* @since Commons Collections 3.1
	*/
	private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
	in.defaultReadObject();
	map = (Map) in.readObject();
	}

	// Implement OrderedMap
	//-----------------------------------------------------------------------
	public MapIterator mapIterator() {
	return orderedMapIterator();
	}

	public OrderedMapIterator orderedMapIterator() {
	return new ListOrderedMapIterator(this);
	}

	/**
	* Gets the first key in this map by insert order.
	*
	* @return the first key currently in this map
	* @throws NoSuchElementException if this map is empty
	*/
	public Object firstKey() {
	if (size() == 0) {
	throw new NoSuchElementException("Map is empty");
	}
	return insertOrder.get(0);
	}

	/**
	* Gets the last key in this map by insert order.
	*
	* @return the last key currently in this map
	* @throws NoSuchElementException if this map is empty
	*/
	public Object lastKey() {
	if (size() == 0) {
	throw new NoSuchElementException("Map is empty");
	}
	return insertOrder.get(size() - 1);
	}

	/**
	* Gets the next key to the one specified using insert order.
	* This method performs a list search to find the key and is O(n).
	*
	* @param key the key to find previous for
	* @return the next key, null if no match or at start
	*/
	public Object nextKey(Object key) {
	int index = insertOrder.indexOf(key);
	if (index >= 0 && index < size() - 1) {
	return insertOrder.get(index + 1);
	}
	return null;
	}

	/**
	* Gets the previous key to the one specified using insert order.
	* This method performs a list search to find the key and is O(n).
	*
	* @param key the key to find previous for
	* @return the previous key, null if no match or at start
	*/
	public Object previousKey(Object key) {
	int index = insertOrder.indexOf(key);
	if (index > 0) {
	return insertOrder.get(index - 1);
	}
	return null;
	}

	//-----------------------------------------------------------------------
	public Object put(Object key, Object value) {
	if (getMap().containsKey(key)) {
	// re-adding doesn't change order
	return getMap().put(key, value);
	} else {
	// first add, so add to both map and list
	Object result = getMap().put(key, value);
	insertOrder.add(key);
	return result;
	}
	}

	public void putAll(Map map) {
	for (Iterator it = map.entrySet().iterator(); it.hasNext();) {
	Map.Entry entry = (Map.Entry) it.next();
	put(entry.getKey(), entry.getValue());
	}
	}

	public Object remove(Object key) {
	Object result = getMap().remove(key);
	insertOrder.remove(key);
	return result;
	}

	public void clear() {
	getMap().clear();
	insertOrder.clear();
	}

	//-----------------------------------------------------------------------
	/**
	* Gets a view over the keys in the map.
	* <p>
	* The Collection will be ordered by object insertion into the map.
	*
	* @see #keyList()
	* @return the fully modifiable collection view over the keys
	*/
	public Set keySet() {
	return new KeySetView(this);
	}

	/**
	* Gets a view over the keys in the map as a List.
	* <p>
	* The List will be ordered by object insertion into the map.
	* The List is unmodifiable.
	*
	* @see #keySet()
	* @return the unmodifiable list view over the keys
	* @since Commons Collections 3.2
	*/
	public List keyList() {
	return UnmodifiableList.decorate(insertOrder);
	}

	/**
	* Gets a view over the values in the map.
	* <p>
	* The Collection will be ordered by object insertion into the map.
	* <p>
	* From Commons Collections 3.2, this Collection can be cast
	* to a list, see {@link #valueList()}
	*
	* @see #valueList()
	* @return the fully modifiable collection view over the values
	*/
	public Collection values() {
	return new ValuesView(this);
	}

	/**
	* Gets a view over the values in the map as a List.
	* <p>
	* The List will be ordered by object insertion into the map.
	* The List supports remove and set, but does not support add.
	*
	* @see #values()
	* @return the partially modifiable list view over the values
	* @since Commons Collections 3.2
	*/
	public List valueList() {
	return new ValuesView(this);
	}

	/**
	* Gets a view over the entries in the map.
	* <p>
	* The Set will be ordered by object insertion into the map.
	*
	* @return the fully modifiable set view over the entries
	*/
	public Set entrySet() {
	return new EntrySetView(this, this.insertOrder);
	}

	//-----------------------------------------------------------------------
	/**
	* Returns the Map as a string.
	*
	* @return the Map as a String
	*/
	public String toString() {
	if (isEmpty()) {
	return "{}";
	}
	StringBuffer buf = new StringBuffer();
	buf.append('{');
	boolean first = true;
	Iterator it = entrySet().iterator();
	while (it.hasNext()) {
	Map.Entry entry = (Map.Entry) it.next();
	Object key = entry.getKey();
	Object value = entry.getValue();
	if (first) {
	first = false;
	} else {
	buf.append(", ");
	}
	buf.append(key == this ? "(this Map)" : key);
	buf.append('=');
	buf.append(value == this ? "(this Map)" : value);
	}
	buf.append('}');
	return buf.toString();
	}

	//-----------------------------------------------------------------------
	/**
	* Gets the key at the specified index.
	*
	* @param index the index to retrieve
	* @return the key at the specified index
	* @throws IndexOutOfBoundsException if the index is invalid
	*/
	public Object get(int index) {
	return insertOrder.get(index);
	}

	/**
	* Gets the value at the specified index.
	*
	* @param index the index to retrieve
	* @return the key at the specified index
	* @throws IndexOutOfBoundsException if the index is invalid
	*/
	public Object getValue(int index) {
	return get(insertOrder.get(index));
	}

	/**
	* Gets the index of the specified key.
	*
	* @param key the key to find the index of
	* @return the index, or -1 if not found
	*/
	public int indexOf(Object key) {
	return insertOrder.indexOf(key);
	}

	/**
	* Sets the value at the specified index.
	*
	* @param index the index of the value to set
	* @return the previous value at that index
	* @throws IndexOutOfBoundsException if the index is invalid
	* @since Commons Collections 3.2
	*/
	public Object setValue(int index, Object value) {
	Object key = insertOrder.get(index);
	return put(key, value);
	}

	/**
	* Puts a key-value mapping into the map at the specified index.
	* <p>
	* If the map already contains the key, then the original mapping
	* is removed and the new mapping added at the specified index.
	* The remove may change the effect of the index. The index is
	* always calculated relative to the original state of the map.
	* <p>
	* Thus the steps are: (1) remove the existing key-value mapping,
	* then (2) insert the new key-value mapping at the position it
	* would have been inserted had the remove not ocurred.
	*
	* @param index the index at which the mapping should be inserted
	* @param key the key
	* @param value the value
	* @return the value previously mapped to the key
	* @throws IndexOutOfBoundsException if the index is out of range
	* @since Commons Collections 3.2
	*/
	public Object put(int index, Object key, Object value) {
	Map m = getMap();
	if (m.containsKey(key)) {
	Object result = m.remove(key);
	int pos = insertOrder.indexOf(key);
	insertOrder.remove(pos);
	if (pos < index) {
	index--;
	}
	insertOrder.add(index, key);
	m.put(key, value);
	return result;
	} else {
	insertOrder.add(index, key);
	m.put(key, value);
	return null;
	}
	}

	/**
	* Removes the element at the specified index.
	*
	* @param index the index of the object to remove
	* @return the removed value, or <code>null</code> if none existed
	* @throws IndexOutOfBoundsException if the index is invalid
	*/
	public Object remove(int index) {
	return remove(get(index));
	}

	/**
	* Gets an unmodifiable List view of the keys which changes as the map changes.
	* <p>
	* The returned list is unmodifiable because changes to the values of
	* the list (using {@link java.util.ListIterator#set(Object)}) will
	* effectively remove the value from the list and reinsert that value at
	* the end of the list, which is an unexpected side effect of changing the
	* value of a list. This occurs because changing the key, changes when the
	* mapping is added to the map and thus where it appears in the list.
	* <p>
	* An alternative to this method is to use the better named
	* {@link #keyList()} or {@link #keySet()}.
	*
	* @see #keyList()
	* @see #keySet()
	* @return The ordered list of keys.
	*/
	public List asList() {
	return keyList();
	}

	//-----------------------------------------------------------------------
	static class ValuesView extends AbstractList {
	private final ListOrderedMap parent;

	ValuesView(ListOrderedMap parent) {
	super();
	this.parent = parent;
	}

	public int size() {
	return this.parent.size();
	}

	public boolean contains(Object value) {
	return this.parent.containsValue(value);
	}

	public void clear() {
	this.parent.clear();
	}

	public Iterator iterator() {
	return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
	public Object next() {
	return ((Map.Entry) iterator.next()).getValue();
	}
	};
	}

	public Object get(int index) {
	return this.parent.getValue(index);
	}

	public Object set(int index, Object value) {
	return this.parent.setValue(index, value);
	}

	public Object remove(int index) {
	return this.parent.remove(index);
	}
	}

	//-----------------------------------------------------------------------
	static class KeySetView extends AbstractSet {
	private final ListOrderedMap parent;

	KeySetView(ListOrderedMap parent) {
	super();
	this.parent = parent;
	}

	public int size() {
	return this.parent.size();
	}

	public boolean contains(Object value) {
	return this.parent.containsKey(value);
	}

	public void clear() {
	this.parent.clear();
	}

	public Iterator iterator() {
	return new AbstractIteratorDecorator(parent.entrySet().iterator()) {
	public Object next() {
	return ((Map.Entry) super.next()).getKey();
	}
	};
	}
	}

	//-----------------------------------------------------------------------
	static class EntrySetView extends AbstractSet {
	private final ListOrderedMap parent;
	private final List insertOrder;
	private Set entrySet;

	public EntrySetView(ListOrderedMap parent, List insertOrder) {
	super();
	this.parent = parent;
	this.insertOrder = insertOrder;
	}

	private Set getEntrySet() {
	if (entrySet == null) {
	entrySet = parent.getMap().entrySet();
	}
	return entrySet;
	}

	public int size() {
	return this.parent.size();
	}
	public boolean isEmpty() {
	return this.parent.isEmpty();
	}

	public boolean contains(Object obj) {
	return getEntrySet().contains(obj);
	}

	public boolean containsAll(Collection coll) {
	return getEntrySet().containsAll(coll);
	}

	public boolean remove(Object obj) {
	if (obj instanceof Map.Entry == false) {
	return false;
	}
	if (getEntrySet().contains(obj)) {
	Object key = ((Map.Entry) obj).getKey();
	parent.remove(key);
	return true;
	}
	return false;
	}

	public void clear() {
	this.parent.clear();
	}

	public boolean equals(Object obj) {
	if (obj == this) {
	return true;
	}
	return getEntrySet().equals(obj);
	}

	public int hashCode() {
	return getEntrySet().hashCode();
	}

	public String toString() {
	return getEntrySet().toString();
	}

	public Iterator iterator() {
	return new ListOrderedIterator(parent, insertOrder);
	}
	}

	//-----------------------------------------------------------------------
	static class ListOrderedIterator extends AbstractIteratorDecorator {
	private final ListOrderedMap parent;
	private Object last = null;

	ListOrderedIterator(ListOrderedMap parent, List insertOrder) {
	super(insertOrder.iterator());
	this.parent = parent;
	}

	public Object next() {
	last = super.next();
	return new ListOrderedMapEntry(parent, last);
	}

	public void remove() {
	super.remove();
	parent.getMap().remove(last);
	}
	}

	//-----------------------------------------------------------------------
	static class ListOrderedMapEntry extends AbstractMapEntry {
	private final ListOrderedMap parent;

	ListOrderedMapEntry(ListOrderedMap parent, Object key) {
	super(key, null);
	this.parent = parent;
	}

	public Object getValue() {
	return parent.get(key);
	}

	public Object setValue(Object value) {
	return parent.getMap().put(key, value);
	}
	}

	//-----------------------------------------------------------------------
	static class ListOrderedMapIterator implements OrderedMapIterator, ResettableIterator {
	private final ListOrderedMap parent;
	private ListIterator iterator;
	private Object last = null;
	private boolean readable = false;

	ListOrderedMapIterator(ListOrderedMap parent) {
	super();
	this.parent = parent;
	this.iterator = parent.insertOrder.listIterator();
	}

	public boolean hasNext() {
	return iterator.hasNext();
	}

	public Object next() {
	last = iterator.next();
	readable = true;
	return last;
	}

	public boolean hasPrevious() {
	return iterator.hasPrevious();
	}

	public Object previous() {
	last = iterator.previous();
	readable = true;
	return last;
	}

	public void remove() {
	if (readable == false) {
	throw new IllegalStateException(AbstractHashedMap.REMOVE_INVALID);
	}
	iterator.remove();
	parent.map.remove(last);
	readable = false;
	}

	public Object getKey() {
	if (readable == false) {
	throw new IllegalStateException(AbstractHashedMap.GETKEY_INVALID);
	}
	return last;
	}

	public Object getValue() {
	if (readable == false) {
	throw new IllegalStateException(AbstractHashedMap.GETVALUE_INVALID);
	}
	return parent.get(last);
	}

	public Object setValue(Object value) {
	if (readable == false) {
	throw new IllegalStateException(AbstractHashedMap.SETVALUE_INVALID);
	}
	return parent.map.put(last, value);
	}

	public void reset() {
	iterator = parent.insertOrder.listIterator();
	last = null;
	readable = false;
	}

	public String toString() {
	if (readable == true) {
	return "Iterator[" + getKey() + "=" + getValue() + "]";
	} else {
	return "Iterator[]";
	}
	}
	}

	}