/***************************************************************************
    Copyright          : (C) 2002 by Neoworks Limited. All rights reserved
    URL                : http://www.neoworks.com
 ***************************************************************************/
/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

package com.neoworks.util;

import java.lang.Object;
import com.neoworks.util.MultiMap;
import java.util.HashMap;
import java.lang.NullPointerException;
import java.util.Set;
import java.lang.UnsupportedOperationException;
import java.lang.ClassCastException;
import java.lang.IllegalArgumentException;
import java.util.Collection;
import com.neoworks.util.MultiMap.Entry;
import java.lang.Error;
import java.lang.RuntimeException;
import java.lang.Exception;
import java.lang.Throwable;
import java.util.AbstractMap;
import java.util.HashSet;
import java.util.AbstractSet;
import java.util.AbstractCollection;
import java.util.List;
import java.util.LinkedList;
import java.util.AbstractSequentialList;
import java.util.AbstractList;
import java.util.Iterator;


/**
 * HashMapMultiMap is a Multimap backed by a <code>HashMap</code> of 
 * <code>Set</code> objects.  This means it differs from a standard MultiMap in 
 * a few important ways.
 * 
 * <ul>
 *	<li>It cannot contain duplicate entries in the keys
 *	<li>It cannot contain duplicates in the values
 *	<li>It might even be in any way quick
 * </ul>
 *
 * @author <a href="mailto:nick@neoworks.com">nick@neoworks.com</a>
 * @version $Revision: 1.2 $
 */
public class HashMapMultiMap implements MultiMap
{
	HashMap m_map = null;

	/**
	 * Public constructor
	 */
	public HashMapMultiMap()
	{
		m_map = new HashMap();
	}
	
	/**
	 * Check values for nulls
	 *
	 * @param key Key to check
	 * @param value Value to check
	 * @exception NullPointerException If either parameter is null
	 */
	private void checkParams(Object key, Object value) throws NullPointerException
	{
		if (key == null) throw new NullPointerException("HashMapMultiMap cannot accept a null key");
		if (value == null) throw new NullPointerException("HashMapMultiMap cannot accept a null value");
	}
	
	/**
	 * Associates the specified value with the specified key in this multimap (optional operation). If the multimap previously
	 * contained a mapping for this key this mapping is not lost.
	 *
	 * @param key Key with which the specified value is to be associated.
	 * @param value Value to be associated with the specified key.
	 * @return <code>Set</code> of values associated with the specified key (including the new addition).
	 * @exception UnsupportedOperationException If the put operation is not supported by this multimap.
	 * @exception ClassCastException If the class of the specified key or value prevents it from being stored in this
	 * multimap.
	 * @exception IllegalArgumentException If some aspect of this key or value prevents it from being stored in this multimap.
	 * @exception NullPointerException This multimap does not permit <code>null</code> keys or values, and the specified key
	 * or value is <code>null</code>.
	 */
	public Set put(Object key, Object value) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException, NullPointerException
	{
		checkParams(key,value);
		
		Set values = (Set) m_map.get(key);
		if ( values == null ) m_map.put( key , values = new HashSet() );
		
		values.add(value);
		return values;
	}
	
	/**
	 * Returns a collection view of the keys contained in this multimap. The collection is backed by the multimap, so changes
	 * to the multimap are reflected in the collection, and vice-versa. If the multimap is modified while an iteration over
	 * the collection is in progress, the results of the iteration are undefined. The collection supports element removal,
	 * which removes the corresponding mapping from the multimap, via the <code>Iterator.remove</code>,
	 * <code>Collection.remove</code>, <code>removeAll</code> <code>retainAll</code>, and <code>clear</code> operations.
	 * It does not support the <code>add</code> or <code>addAll</code> operations.
	 *
	 * This implementation does <b>not</b> return duplicate keys in the keyset.
	 *
	 * @return A collection view of the keys contained in this multimap.
	 */
	public Collection keys()
	{
		return m_map.keySet();
	}
	
	/**
	 * Removes all the mappings for this key from this multimap if present (optional operation).
	 *
	 * @param key Key whose mappings is to be removed from the multimap.
	 * @return <code>Set</code> of values associated with the specified key, or <code>null</code> if there were no mappings
	 * for key.
	 * @exception UnsupportedOperationException If the remove operation is not supported by this multimap.
	 */
	public Set remove(Object key) throws UnsupportedOperationException
	{
		Set values = (Set) m_map.get(key);
		m_map.put( key , null );
		return values;
	}
	
	/**
	 * Removes all mappings from this multimap (optional operation).
	 *
	 * @exception UnsupportedOperationException If clear is not supported by this multimap.
	 */
	public void clear() throws UnsupportedOperationException
	{
		m_map = new HashMap();
	}
	
	/**
	 * Returns a collection view of the values contained in this multimap. The collection is backed by the multimap,
	 * so changes to the multimap are reflected in the collection, and vice-versa. If the multimap is modified while an
	 * iteration over the collection is in progress, the results of the iteration are undefined. The collection supports
	 * element removal, which removes the corresponding mapping from the multimap, via the <code>Iterator.remove</code>,
	 * <code>Collection.remove</code>, <code>removeAll</code>, <code>retainAll</code> and <code>clear</code> operations.
	 * It does not support the <code>add</code> or <code>addAll</code> operations.
	 *
	 * @return A collection view of the values contained in this multimap.
	 */
	public Collection values()
	{
		List values = new LinkedList();
		for ( Iterator valueSetIterator = m_map.values().iterator() ; valueSetIterator.hasNext() ;  values.addAll( (Set) valueSetIterator.next() ) );
		return values;
	}
	
	/**
	 * Get the EntrySet.  This is pretty pointless for this particular implementation, but is included because
	 * it's in the interface.
	 * @return A set of entries
	 */
	public Set entrySet()
	{
		Set entrySet = new HashSet();
		Iterator keySetIter = m_map.keySet().iterator();
		
		while (keySetIter.hasNext())
		{
			Object currKey = keySetIter.next();
			Set currValueSet = (Set) m_map.get( currKey );
			
			if (currValueSet != null)
			{
				Iterator currValSetIter = currValueSet.iterator() ; 
				while( currValSetIter.hasNext() )
				{
					entrySet.add( new Entry( currKey , currValSetIter.next() ) );
				}
			}
		}
		
		return entrySet;
	}
	
	/**
	 * Returns the hash code value for this multimap. The hash code of a multimap is defined to be the sum of the
	 * <code>hashCodes</code> of each entry in the multimap's <code>entrySet</code> view. This ensures that
	 * <code>t1.equals(t2)</code> implies that <code>t1.hashCode()==t2.hashCode()</code> for any two multimaps t1 and t2,
	 * as required by the general contract of <code>Object.hashCode</code>.
	 *
	 * @return The hash code value for this multimap.
	 */
	public int hashCode()
	{
		Iterator values = values().iterator();
		int hashCode = 0;
		
		while (values.hasNext())
		{
			hashCode += values.next().hashCode();
		}
		
		return hashCode;
	}
	
	/**
	 * Returns <code>true</code> if this multimap contains a mapping for the specified key.
	 *
	 * @param key Key whose presence in this multimap is to be tested.
	 * @return <code>true</code> if this multimap contains a mapping for the specified key.
	 * @exception ClassCastException If the key is of an inappropriate type for this multimap.
	 * @exception NullPointerException If the key is null and this multimap does not not permit null keys
	 */
	public boolean containsKey(Object key) throws ClassCastException, NullPointerException
	{
		return m_map.containsKey(key);
	}
	
	/**
	 * Copies all of the mappings from the specified multimap to this multimap (optional operation). These mappings will
	 * replace any mappings that this multimap had for any of the keys currently in the specified multimap.
	 *
	 * @param multimap Mappings to be stored in this multimap.
	 * @exception UnsupportedOperationException If the put operation is not supported by this multimap.
	 * @exception ClassCastException If the class of the specified key or value prevents it from being stored in this
	 * multimap.
	 * @exception IllegalArgumentException If some aspect of a key or value in the specified multimap prevents it from being
	 * stored in this multimap.
	 * @exception NullPointerException This multimap does not permit <code>null</code> keys or values, and the specified key
	 * or value is <code>null</code>.
	 */
	public void putAll(MultiMap multimap) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException, NullPointerException
	{
		throw new UnsupportedOperationException("Not implemented :)");
	}
	
	/**
	 * Returns the number of key-values mappings in this multimap. If the multimap contains more than
	 * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
	 *
	 * @return The number of key-values mappings in this multimap
	 */
	public int size()
	{
		return values().size();
	}
	
	/**
	 * Returns a collection of the <b>unique</b> keys in this multimap.
	 * @return A Collection of unique keys
	 */
	public Collection uniqueKeys()
	{
		return keys();
	}
	
	/**
	 * Removes the (key, value) mapping from this multimap if present (optional operation).
	 *
	 * @return Value that was unmapped from the specified key, or <code>null</code> if the given mapping did not exist.
	 * @param value The value associated with the key to identify the item to remove
	 * @param key Key whose mapping to the value is to be removed from the multimap.
	 * @exception UnsupportedOperationException If the remove operation is not supported by this multimap.
	 */
	public Object remove(Object key, Object value) throws UnsupportedOperationException
	{
		Set values = (Set) m_map.get(key);
		
		if (values != null)
		{
			values.remove(value);
			if (values.size() == 0) 
			{
				m_map.put(key,null);
				values = null;
			}
		}
		
		return values;
	}
	
	/**
	 * Returns true if this multimap maps one or more keys to the specified value. More formally, returns true if and only if
	 * this multimap contains at least one mapping to a value v such that
	 * <code>(value==null ? v==null : value.equals(v))</code>. This operation will probably require time linear in the
	 * multimap size for most implementations of the <code>MultiMap</code> interface.
	 *
	 * @param value Value whose presence in this multimap is to be tested.
	 * @return <code>true</code> if this multimap maps one or more keys to the specified value.
	 */
	public boolean containsValue(Object value)
	{
		return values().contains(value);
	}
	
	/**
	 * Compares the specified object with this multimap for equality. Returns true if the given object is also a multimap
	 * and the two multimaps represent the same mappings. More formally, two maps t1 and t2 represent the same mappings if
	 * <code>t1.entrySet().equals(t2.entrySet())</code>. This ensures that the equals method works properly across different
	 * implementations of the <code>MultiMap</code> interface.
	 *
	 * @param o Object to be compared for equality with this multimap.
	 * @return <code>true</code> if the specified object is equal to this multimap.
	 */
	public boolean equals(Object o)
	{
		if (o instanceof HashMapMultiMap) 
		{
			HashMapMultiMap compare = (HashMapMultiMap) o;
			return ( ( compare.keys().equals( keys() ) ) && ( compare.values().equals( values() ) ) );
		}
		
		return false;
	}
	
	/**
	 * Returns the set of values to which this multimap maps the specified key. Returns null if the multimap contains no
	 * mappings for this key. A return value of <code>null</code> does indicate that the multimap contains no mappings for the
	 * key; it's possible that the multimap explicitly maps the key to null, in this case the returned set will contain
	 * <code>null</code> possibly along with other objects. The <code>containsKey</code> operation may also be used to
	 * distinguish these two cases.
	 *
	 * @param key Key whose associated value is to be returned.
	 * @return A <code>Set</code> of values to which this multimap maps the specified key, or <code>null</code> if the
	 * multimap contains no mapping for this key.
	 * @exception ClassCastException If the key is of an inappropriate type for this multimap.
	 * @exception NullPointerException If the key is <code>null</code> and this multimap does not not permit<code> null</code>
	 * keys
	 */
	public Set get(Object key) throws ClassCastException, NullPointerException
	{
		return (Set) m_map.get(key);
	}
	
	/**
	 * Returns <code>true</code> if this multimap contains no key-value mappings.
	 *
	 * @return <code>true</code> if this multimap contains no key-value mappings.
	 */
	public boolean isEmpty()
	{
		return ( m_map.keySet().size() == 0 );
	}
	
	/**
	 * An entry.  Don't see why this has to be here, but it's too late to change the interface huh?
	 */
	private static class Entry implements MultiMap.Entry
	{
		/**
		 * The key
		 */
		private Object key;
		
		/**
		 * The value
		 */
		private Object value;

		/**
		 * Construct a new Entry
		 * @param k the key
		 * @param v the value
		 */		
		public Entry(Object k, Object v)
		{
			key = k;
			value = v;
		}

		/**
		 * Get the key
		 * @return Return the key
		 */		
		public Object getKey()
		{
			return key;
		}

		/** 
		 * Get the value
		 * @return the value
		 */		
		public Object getValue()
		{
			return value;
		}

		/**
		 * Set the Value
		 * @param o The value to set
		 * @return The previous value, otherwise null
		 */		
		public Object setValue(Object o)
		{
			Object oldValue = value;
			value = o;
			return oldValue;
		}

		/**
		 * Test if this Entry is equal to another Object
		 * @param o Object to compare to
		 * @return true if this object is equal to the argument
		 */		
		public boolean equals(Object o)
		{
			if (!(o instanceof Entry))
			{
				return false;
			}
			Entry e = (Entry) o;
			return (key.equals(e.getKey()) && value.equals(e.getValue()));
		}

		/**
		 * Get the hashcode of the object
		 * @return the hash code of the object
		 */		
		public int hashCode()
		{
			return key.hashCode() + value.hashCode();
		}
	}
}
