/*
Wotonomy: OpenStep design patterns for pure Java applications.
Copyright (C) 2000 Blacksmith, Inc.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, see http://www.gnu.org
*/

package net.wotonomy.foundation.internal;

import java.util.*; //collections

/**
* A queue based implementation of the Map interface.  This class provides for
* all the opertions of a map, but keeps the entries in the same sequence as
* originally added.  The first entry placed in the map will be the first
* entry retreived during iteration: first-in, first-out (FIFO). <BR><BR>
*
* Keys cannot be duplicated.  If an entry is made using a key that already
* exists, the value for that key will be replaced with that new value.  There
* are no such restrictions on the values.  The values may be null.  <BR><BR>
*
* Some convenience methods are provided for the queue type operations.  The
* first key can be retreived as well as the last key.  A key can be used
* to retreive its corresponding value from the map.  A value can also be used
* to retreive its key from the map, however, since there may be multiple values
* of the same equality, the first key found will be returned. <BR><BR>
*
* @author rglista@blacksmith.com
* @author mpowers@blacksmith.com
* @date $Date: 2006-02-18 17:41:36 -0500 (Sat, 18 Feb 2006) $
* @revision $Revision: 899 $
*/
public class QueueMap implements Map
{
    List values;
    List keys;
    Map keyToValue;

/**
* Creates an empty QueueMap.
*/
    public QueueMap()
    {
        values = new LinkedList();
        keys = new LinkedList();
        keyToValue = new HashMap();
    }

/**
* Creates a QueueMap and places the entries from the passed in map into this map.
* The order of the entries is based on however the iterator iteratated through
* the map entries.
* @param t A map object.
*/
    public QueueMap( Map t )
    {
        values = new ArrayList();
        keys = new ArrayList();
        keyToValue = new HashMap();

        putAll( t );
    }

/**
* Removes all the entries from this map.
*/
    public void clear()
    {
        values.clear();
        keys.clear();
        keyToValue.clear();
    }

/**
* Tests to see if the key is contained in the map.  If the key is present in
* the map, then TRUE is returned, otherwise FALSE is returned.  The equals()
* operation is used to determine equality.
* @return True if the map contains the given key, false otherwise.
*/
    public boolean containsKey( Object key )
    {
        return keyToValue.containsKey( key );
    }

/**
* Tests to see if the value is contained in the map.  If the value is present in
* the map, then TRUE is returned, otherwise FALSE is returned.  The equals()
* operation is used to determine equality.  The value can be null and will
* return TRUE if null is a value in the map.  If TRUE is returned, then there
* may be more than one values in the map.
* @return True if the map contains the given value, false otherwise.
*/
    public boolean containsValue( Object value )
    {
        return keyToValue.containsValue( value );
    }

/**
* Returns a set view of the mappings contained in this map.  Each element
* in the returned set is a <tt>Map.Entry</tt>.  The returned set is NOT backed
* by the map, so changes to the map are NOT reflected in the set, and vice-versa.
* The returned set is independent of this Map and its underlying structure.
*
* @return a set view of the mappings contained in this map.
*/
    public Set entrySet()
    {
        Set result = new HashSet(keys.size(), 1F);

        for ( int i = 0; i < keys.size(); i++ )
        {
            result.add( new KeyValuePair( keys.get(i), values.get(i) ) );
        }

        return result;
    }

/**
* Compares the specified object with this map for equality.  Returns
* <tt>true</tt> if the given object is also a map and the two Maps
* represent the same mappings.  More formally, two maps <tt>t1</tt> and
* <tt>t2</tt> represent the same mappings if
* <tt>t1.entrySet().equals(t2.entrySet())</tt>.  This ensures that the
* <tt>equals</tt> method works properly across different implementations
* of the <tt>Map</tt> interface.
*
* @param o object to be compared for equality with this map.
* @return <tt>true</tt> if the specified object is equal to this map.
*/
    public boolean equals( Object o )
    {
        return keyToValue.equals( o );
    }

/**
* Returns the corresponding value for the given key.  The returned value may be
* null as that is a legal value in this map.  However, if the key is not
* contained in this map then null is also returned.  Use the containsKey()
* method to distinguish between the two cases.
* @param key A key into the map.
* @return The value corresponding to the key (can be null), or null if the key
*         is not contained in the map.
*/
    public Object get( Object key )
    {
        return keyToValue.get( key );
    }

/**
* Returns the hash code value for this map.  The hash code of a map
* is defined to be the sum of the hashCodes of each entry in the map's
* entrySet view.  This ensures that <tt>t1.equals(t2)</tt> implies
* that <tt>t1.hashCode()==t2.hashCode()</tt> for any two maps
* <tt>t1</tt> and <tt>t2</tt>, as required by the general
* contract of Object.hashCode.
*
* @return the hash code value for this map.
*/
    public int hashCode()
    {
        return keyToValue.hashCode();
    }

/**
* Returns true is this map contains no key-value mappings.
* @return True is this map contains no entries, false otherwise.
*/
    public boolean isEmpty()
    {
        return keyToValue.isEmpty();
    }

/**
* Returns the keys used in the map. There is no order implied in the returned
* set and may be different than the the order in which they were inserted.
* @return A Set containing all the keys used in the map.
*/
    public Set keySet()
    {
        Set result = new HashSet(keys.size(), 1F);

        for ( int i = 0; i < keys.size(); i++ )
        {
            result.add( keys.get(i) );
        }

        return result;
    }

/**
* Places the key/value entry into the map at the end position.  If the key
* already exists in the map, then its value is replaced by the new given
* value.  The mapping does not change order in this case.  The specified
* key cannot be null.
* @param key The key to place into the map, cannot be null.
* @param value The value to associate with the key, may be null.
* @return Null if the key is new, the replaced value if the key already
*         existed. (Note: If the key was null, then null is returned.)
*/
    public Object put( Object key, Object value )
    {
        if ( key == null ) return null;

        if ( keys.contains( key ) )
        {
            values.remove( keys.indexOf( key ) );
            values.add( keys.indexOf( key ), value );
        }
        else
        {
            values.add( value );
            keys.add( key );
        }

        return keyToValue.put( key, value );
    }

/**
* Places all the entries from this given map into this map.  If the keys
* already exist, then there values are replaced.
* @param t A map of key/value entries.
*/
    public void putAll( Map t )
    {
        if ( t == null )
        {
            // Nothing to do!
            return;
        }

        // Place the entries from the passed in map into this map.
        for ( Iterator it = t.keySet().iterator(); it.hasNext(); )
        {
            Object aKey = it.next();
            put( aKey, t.get( aKey ) );
        }
    }

/**
* Remove the mapping of the key and associated value from this map.
* Note: null is a valid value in the map.
* @param key A key to remove from the map, cannot be null.
* @return The value of the removed mapping, null if the mapping did not exist.
*         Null could also be returned if the associated value of the key was null.
*/
    public Object remove( Object key )
    {
        if ( key == null ) return null;

        Object value = null;

        if ( containsKey( key ) )
        {
            value = keyToValue.remove( key );
            int i = values.indexOf( value );
            if ( i != -1 )
            {
                keys.remove( i );
                values.remove( i );
            }
        }

        return value;
    }

/**
* Returns the number of key/value pairs in this map.
* @return The number of pairs.
*/
    public int size()
    {
        return values.size();
    }

/**
* Returns an ordered list of keys from the map.  The order is the same
* as the added order of the mapped items.<br>
* NOTE: The returned list is the underlying keys list used by this class.
* If modification are to be made to this list, it should be cloned first.
* @return An ordered list of keys.
*/
    public List keys()
    {
        return keys;
    }

/**
* Returns an ordered list of values from the map.  The order is the same
* as the added order of the mapped items.
* NOTE: The returned list is the underlying keys list used by this class.
* If modification are to be made to this list, it should be cloned first.
* @return An ordered list of values.
*/
    public Collection values()
    {
        return values;
    }

/**
* Returns the corresponding value for the given key.  The returned value may be
* null as that is a legal value in this map.  However, if the key is not
* contained in this map then null is also returned.  Use the containsKey()
* method to distinguish between the two cases.
* @param key A key into the map.
* @return The value corresponding to the key (can be null), or null if the key
*         is not contained in the map.
*/
    public Object getValueForKey( Object key )
    {
        return keyToValue.get( key );
    }

/**
* Returns the associated key for this value.  Since there may be more than one
* of the same value in the map, this returns the first key associated with this
* value. Null is returned if the value is not in the map.
* @param value A value that is contained in this map.
* @return A first key that corresponds to this value.
*/
    public Object getKeyForValue( Object value )
    {
        int i = values.indexOf( value );
        if ( i != -1 )
        {
            return keys.get( i );
        }
        return null;
    }

/**
* Returns the first key in the map.  If the map is empty, then null is
* returned.
* @return The first key in the map, null if there are no mappings.
*/
    public Object getFirstKey()
    {
        if ( keys.size() < 1 )
        {
            return null;
        }
        return keys.get(0);
    }

/**
* Returns the last key in the map.  If the map is empty, then null is
* returned.
* @return The last key in the map, null if there are no mappings.
*/
    public Object getLastKey()
    {
        if ( keys.size() < 1 )
        {
            return null;
        }
        return keys.get( keys.size() -1 );
    }

/**
* This class contains a key/value pair.  The key must be a valid object,
* it cannot be null.  The value can be a valid object or null.
*/
    static public class KeyValuePair implements Map.Entry
    {
        Object key;
        Object value;

    /**
    * Default constructor.  The constructor takes the key and value as parameters.
    * Since the key cannot be null, it must be specified during initialization.
    * The value can be null.
    * @param key The key object of this pair.  The key cannot be null.
    * @param value The value object of this pair.  The value can be null.
    */
        public KeyValuePair( Object aKey, Object aValue )
        {
            key = aKey;
            value = aValue;
        }

    /**
    * Returns the key object of this pair.
    * @return The key object.
    */
        public Object getKey()
        {
            return key;
        }

    /**
    * Returns the the value object of this pair.  May be null.
    * @return The value object.
    */
        public Object getValue()
        {
            return value;
        }

    /**
    * Sets the value object of this pair.  May be an object or null.
    * @param aValue The value object to place into this pair.
    */
        public Object setValue( Object aValue )
        {
            Object result = value;
            value = aValue;
            return result;
        }

        public boolean equals( Object o )
        {
            if ( o instanceof KeyValuePair )
            {
                KeyValuePair p = (KeyValuePair) o;
                if ( ( key.equals( p.getKey() ) ) && ( value.equals( p.getValue() ) ) )
                {
                    return true;
                }
            }
            return false;
        }
    }

    /**
     * Returns a string reprsentation of this class.  The contents of the
     * map are placed in the string in its proper order.
     */
    public String toString()
    {
        int max = size() - 1;
        StringBuffer buf = new StringBuffer();

        buf.append("{");
        for (int j = 0; j <= max; j++)
        {
            buf.append(keys.get(j) + "=" + values.get(j));
            if (j < max)
            {
                buf.append(", ");
            }
        }
        buf.append("}");

        return buf.toString();
    }

    // unit test
    public static void main( String[] argv )
    {
        QueueMap qMap;

        qMap = new QueueMap();
        for (int i = 0; i < 5; i++)
        {
            qMap.put(Integer.toString(i), Integer.toString(i));
        }
        System.out.println("\nMap = " + qMap);
        System.out.println("Keys = " + qMap.keys());
        System.out.println("Values = " + qMap.values());

        qMap = new QueueMap();
        for (int i = 0; i < 5; i++)
        {
            qMap.put(Integer.toString(i), "A");
        }
        System.out.println("\nMap = " + qMap);
        System.out.println("Keys = " + qMap.keys());
        System.out.println("Values = " + qMap.values());

        qMap = new QueueMap();
        for (int i = 0; i < 5; i++)
        {
            qMap.put(Integer.toString(i), null);
        }
        System.out.println("\nMap = " + qMap);
        System.out.println("Keys = " + qMap.keys());
        System.out.println("Values = " + qMap.values());

        Map aMap = new HashMap();
        for (int i = 0; i < 5; i++)
        {
            aMap.put(Integer.toString(i), Integer.toString(i));
        }
        qMap = new QueueMap( aMap );
        System.out.println("\nHashMap = " + aMap);
        System.out.println("Map = " + qMap);
        System.out.println("Keys = " + qMap.keys());
        System.out.println("Values = " + qMap.values());

        qMap = new QueueMap();
        qMap.put( "Test1", "String1" );
        qMap.put( "Test2", "String2" );
        qMap.put( "Test3", "String3" );
        qMap.put( "Test4", "String4" );
        qMap.put( "Test5", "String5" );
        System.out.println("\nStandard Test, Map = " + qMap);
        qMap.put( "Test6", "String6" );
        qMap.put( "Test7", "String7" );
        System.out.println("Put New Test, Map = " + qMap);
        qMap.put( "Test2", "New String2" );
        qMap.put( "Test6", "New String6" );
        System.out.println("Put Existing Test, Map = " + qMap);
        qMap.put( "Test5", null );
        qMap.put( "Test8", null );
        System.out.println("Put Null Test, Map = " + qMap);
        qMap.remove( "Test1" );
        qMap.remove( "Test3" );
        qMap.remove( "Test5" );
        qMap.remove( "Test9" );
        System.out.println("Remove Test, Map = " + qMap);
        System.out.println("             Keys = " + qMap.keys());
        System.out.println("             Values = " + qMap.values());
        qMap.clear();
        qMap.put( "Test10", "String10" );
        qMap.put( "Test11", "String11" );
        qMap.put( "Test12", "String12" );
        System.out.println("Clear Test, Map = " + qMap);

        aMap = new HashMap();
        aMap.put( "Test10", "String10" );
        aMap.put( "Test11", "String11" );
        aMap.put( "Test12", "String12" );
        System.out.println("Equality Test, Equal = " + qMap.equals( aMap ));
    }

}