/***************************************************************************
    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 com.neoworks.util.MultiMap;
import com.neoworks.util.MultiMap.Entry;
import java.util.AbstractCollection;
import java.util.Collection;
import java.util.Set;
import java.util.HashSet;
import java.util.AbstractSet;
import java.util.Iterator;
import java.lang.Object;
import java.lang.String;
import java.lang.UnsupportedOperationException;
import java.lang.RuntimeException;
import java.lang.Exception;
import java.lang.Throwable;
import java.lang.StringBuffer;
import java.lang.Error;
import java.lang.ClassCastException;
import java.lang.NullPointerException;

/**
 * This class provides a skeletal implementation of the <code>MultiMap</code> interface, to minimize the effort required to
 * implement this interface.
 *
 * <p>
 * To implement an unmodifiable multimap, the programmer needs only to extend this class and provide an implementation for the
 * <code>entrySet</code> method, which returns a set-view of the multimap's mappings. Typically, the returned set will, in turn,
 * be implemented atop <code>AbstractSet</code>. This set should not support the <code>add</code> or <code>remove</code> methods,
 * and its iterator should not support the <code>remove</code> method.
 * </p>
 * <p>
 * To implement a modifiable multimap, the programmer must additionally override this class's <code>put</code> method (which
 * otherwise throws an <code>UnsupportedOperationException</code>), and the iterator returned by
 * <code>entrySet().iterator()</code> must additionally implement its <code>remove</code> method.
 * </p>
 * <p>
 * The programmer should generally provide a void (no argument) and multimap constructor, as per the recommendation in the
 * <code>MultiMap</code> interface specification.
 * </p>
 * <p>
 * The documentation for each non-abstract methods in this class describes its implementation in detail. Each of these methods
 * may be overridden if the multimap being implemented admits a more efficient implementation.
 * </p>
 *
 * @author Stuart Farnan <a href="mailto:stuart@neoworks.com">stuart@neoworks.com</a>
 * @version 0.1
 */
public abstract class AbstractMultiMap implements MultiMap
{
	/**
	 * Sole constructor. (For invocation by subclass constructors, typically implicit.)
	 */
	protected AbstractMultiMap ()
	{
	}


	/**
	 * Returns the number of key-value mappings in this multimap. If the multimap contains more than
	 * <code>Integer.MAX_VALUE</code> elements, returns <code>Integer.MAX_VALUE</code>.
	 *
	 * <p>
	 * This implementation returns <code>entrySet().size()</code>.
	 * </p>
	 *
	 * @return the number of key-value mappings in this multimap.
	 */
	public int size ()
	{
		return entrySet().size();
	}


	/**
	 * Returns <code>true</code> if this multimap contains no key-value mappings.
	 *
	 * <p>
	 * This implementation returns <code>size() == 0</code>.
	 * </p>
	 *
	 * @return <code>true</code> if this multimap contains no key-value mappings.
	 */
	public boolean isEmpty ()
	{
		return size() == 0;
	}


	/**
	 * Returns <code>true</code> if this multimap maps one or more keys to this value. More formally, returns
	 * <code>true</code> if and only if this multimap contains at least one mapping to a value <code>v</code> such that:
	 *
	 * <p>
	 * <code>(value == null ? v == null : value.equals(v))</code>.
	 * </p>
	 * <p>
	 * This operation will probably require time linear in the multimap size for most implementations of multimap.
	 * </p>
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified value. If such
	 * an entry is found, <code>true</code> is returned. If the iteration terminates without finding such an entry,
	 * <code>false</code> is returned. Note that this implementation requires linear time in the size of the multimap.
	 * </p>
	 *
	 * @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 this value.
	 */
	public boolean containsValue (Object value)
	{
		Iterator i = entrySet().iterator();
		if (value == null)
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (e.getValue() == null)
				{
					return true;
				}
			}
		}
		else
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (value.equals(e.getValue()))
				{
					return true;
				}
			}
		}
		return false;
	}


	/**
	 * Returns <code>true</code> if this multimap contains a mapping for the specified key.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified key. If such an
	 * entry is found, <code>true</code> is returned. If the iteration terminates without finding such an entry,
	 * <code>false</code> is returned. Note that this implementation requires linear time in the size of the multimap;
	 * many implementations will override this method.
	 * </p>
	 *
	 * @return <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. */
	public boolean containsKey (Object key)
	{
		Iterator i = entrySet().iterator();
		if (key == null)
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (e.getKey() == null)
				{
					return true;
				}
			}
		}
		else
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (key.equals(e.getKey()))
				{
					return true;
				}
			}
		}
		return false;
	}


	/**
	 * Returns the set of values to which this multimap maps the specified key. Returns <code>null</code> if the multimap
	 * contains no mapping for this key. A return value of <code>null</code> does indicate that the multimap contains no
	 * mapping for the key; it's possible that the map explicitly maps the key to <code>null</code>, in this case the
	 * returned set will contain null possibly along with other objects. The <code>containsKey</code> operation may also be
	 * used to distinguish these two cases.
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for an entry with the specified key. If such an
	 * entry is found, the entry's values are placed in a <code>Set</code> and returned. If the iteration terminates without
	 * finding such an entry, <code>null</code> is returned. This implementation allows null keys. Note that this
	 * implementation requires linear time in the size of the multimap; many implementations will override this method.
	 * </p>
	 *
	 * @return A <code>Set</code> of values to which this multimap maps the specified key.
	 * @see #containsKey(Object) 
	 * @param key Key whose associated value is to be returned. */
	public Set get (Object key)
	{
		Set valueSet = new HashSet();
		Iterator i = entrySet().iterator();
		if (key == null)
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (e.getKey() == null)
				{
					valueSet.add(e.getValue());
				}
			}
		}
		else
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (key.equals(e.getKey()))
				{
					valueSet.add(e.getValue());
				}
			}
		}

		return (valueSet.size() == 0 ? null : valueSet);
	}


	/**
	 * Associates the specified value with the specified key in this map (optional operation). If the multimap previously
	 * contained a mapping for this key, the old value is not lost.
	 *
	 * <p>
	 * This implementation always throws an <code>UnsupportedOperationException</code>.
	 * </p>
	 *
	 * @return <code>Set</code> of values associated with the specified key.
	 * @param key Key with which the specified value is to be associated.
	 * @param value Value to be associated with the specified key. */
	public Set put (Object key, Object value)
	{
		throw new UnsupportedOperationException();
	}


	/**
	 * Removes all the mappings for this key from this multimap if present (optional operation).
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for entries with the specified key. If such an
	 * entry is found, its value is obtained with its <code>getValue</code> operation, the entry is removed from the
	 * collection (and the backing map) with the iterator's <code>remove</code> operation, and the saved value is added to a 
	 * <code>Set<code> object which is returned at the end of this method. If the iteration terminates without finding such an
	 * entry, <code>null</code> is returned. Note that this implementation requires linear time in the size of the map; many
	 * implementations will override this method.
	 * </p>
	 *
	 * @return <code>Set</code> of values associated with the specified key, or <code>null</code> if there were no mappings
	 * for key.
	 * @param key Key whose mappings is to be removed from the multimap. */
	public Set remove (Object key)
	{
		Set oldValues = new HashSet();
		Iterator i = entrySet().iterator();
		if (key == null)
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (e.getKey() == null)
				{
					i.remove();
					oldValues.add(e.getValue());
				}
			}
		}
		else
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (key.equals(e.getKey()))
				{
					i.remove();
					oldValues.add(e.getValue());
				}
			}
		}

		return (oldValues.size() == 0 ? null : oldValues);
	}


	/**
	 * Removes the specified mapping from this multimap if present (optional operation).
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code> searching for entries with the specified key and value. If
	 * such an entry is found, its value is obtained with its <code>getValue</code> operation, the entry is removed from the
	 * collection (and the backing map) with the iterator's <code>remove</code> operation, it is returned at the end of this
	 * method. If the iteration terminates without finding such an entry, <code>null</code> is returned. Note that this
	 * implementation requires linear time in the size of the map; many implementations will override this method.
	 * </p>
	 *
	 * @return Value associated with the specified key, or <code>null</code> if there were no mappings for key.
	 * @param key Key whose mapping is to be removed from the multimap.
	 * @param value Value that is being mapped to by the given key. */
	public Object remove (Object key, Object value)
	{
		Object oldValue = null;
		Iterator i = entrySet().iterator();
		if (key == null)
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (e.getKey() == null)
				{
					if (value == null)
					{
						if (e.getValue() == null)
						{
							i.remove();
							oldValue = null;
						}
					}
					else
					{
						if (value.equals(e.getValue()))
						{
							i.remove();
							oldValue = e.getValue();
						}
					}
				}
			}
		}
		else
		{
			while (i.hasNext())
			{
				Entry e = (Entry) i.next();
				if (key.equals(e.getKey()))
				{
					if (value == null)
					{
						if (e.getValue() == null)
						{
							i.remove();
							oldValue = null;
						}
					}
					else
					{
						if (value.equals(e.getValue()))
						{
							i.remove();
							oldValue = e.getValue();
						}
					}
				}
			}
		}

		return null;
	}


	/**
	 * Copies all of the mappings from the specified multimap to this multimap (optional operation). These mappings will
	 * add to any mappings that this multimap had for any of the keys currently in the specified multimap.
	 *
	 * <p>
	 * This implementation iterates over the specified multi's <code>entrySet()</code> collection, and calls this
	 * multimap's <code>put</code> operation once for each entry returned by the iteration.
	 * </p>
	 *
	 * @param map Mappings to be stored in this multimap. */
	public void putAll (MultiMap map)
	{
		Iterator i = map.entrySet().iterator();
		while (i.hasNext())
		{
			MultiMap.Entry e = (MultiMap.Entry) i.next();
			put(e.getKey(), e.getValue());
		}
	}


	/**
	 * Removes all mappings from this multimap (optional operation).
	 *
	 * <p>
	 * This implementation calls <code>entrySet().clear()</code>.
	 * </p>
	 */
	public void clear ()
	{
		entrySet().clear();
	}


	/**
	 * Temporary cached collection of the keys
	 */	
	private transient Collection keys = null;


	/**
	 * 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 set is in progress, the results of the iteration are undefined.) The collection supports element removal, which
	 * removes the corresponding entry 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.
	 *
	 * <p>
	 * This implementation returns a <code>Collection</code> that subclasses <code>AbstractCollection</code>. The subclass's
	 * iterator method returns a "wrapper object" over this multimap's <code>entrySet()</code> iterator. The size method
	 * delegates to this multimap's size method and the contains method delegates to this multimap's <code>containsKey</code>
	 * method.
	 * </p>
	 * <p>
	 * The collection is created the first time this method is called, and returned in response to all subsequent calls. No
	 * synchronization is performed, so there is a slight chance that multiple calls to this method will not all return
	 * the same collection.
	 * </p>
	 *
	 * @return A collection view of the keys contained in this multimap.
	 */
	public Collection keys ()
	{
		if (keys == null)
		{
			keys = new AbstractCollection() {
				public Iterator iterator()
				{
					return new Iterator()
					{
						private Iterator i = entrySet().iterator();

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

						public Object next()
						{
							return ((Entry) i.next()).getKey();
						}

						public void remove()
						{
							i.remove();
						}
					};
				}

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

				public boolean contains(Object k)
				{
					return AbstractMultiMap.this.containsKey(k);
				}
			};
		}
		return keys;
	}

	/**
	 * Return a Collection of unique keys from the Multimap
	 *
	 * @return A Collection of unique keys
	 */
	public Collection uniqueKeys()
	{
		Iterator keyIter = keys().iterator();
		Set uniqueKeys = new HashSet();
		
		while (keyIter.hasNext())
		{
			uniqueKeys.add( keyIter.next() );
		}
		
		return uniqueKeys;
	}
	
	/**
	 * Temporary cached collection of the values
	 */
	private transient Collection values = null;


	/**
	 * 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 entry 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.
	 *
	 * <p>
	 * This implementation returns a <code>Collection</code> that subclasses <code>AbstractCollection</code>. The subclass's
	 * iterator method returns a "wrapper object" over this multimap's <code>entrySet()</code> iterator. The size method
	 * delegates to this multimap's size method and the contains method delegates to this multimap's containsValue method.
	 * </p>
	 * <p>
	 * The collection is created the first time this method is called, and returned in response to all subsequent calls.
	 * No synchronization is performed, so there is a slight chance that multiple calls to this method will not all return
	 * the same collection.
	 * </p>
	 *
	 * @return A collection view of the values contained in this multimap.
	 */
	public Collection values()
	{
		if (values == null)
		{
			values = new AbstractCollection()
			{
				public Iterator iterator()
				{
					return new Iterator()
					{
						private Iterator i = entrySet().iterator();

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

						public Object next()
						{
							return ((Entry)i.next()).getValue();
						}

						public void remove()
						{
							i.remove();
						}
					};
				}

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

				public boolean contains(Object v)
				{
					return AbstractMultiMap.this.containsValue(v);
				}
			};
		}
		return values;
	}


	/**
	 * Returns a set view of the mappings contained in this multimap. Each element in this set is a Map.Entry. The set is
	 * backed by the map, so changes to the multimap are reflected in the set, and vice-versa. (If the map is modified while
	 * an iteration over the set is in progress, the results of the iteration are undefined.) The set supports element
	 * removal, which removes the corresponding entry from the map, via the <code>Iterator.remove</code>,
	 * <code>Set.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 set view of the mappings contained in this multimap.
	 */
	public abstract Set entrySet ();


	/**
	 * Compares the specified object with this multimap for equality. Returns <code>true</code> if the given object is also
	 * a multimap and the two multimaps represent the same mappings. More formally, two maps <code>t1</code> and
	 * <code>t2</code> represent the same mappings iff:
	 *
	 * <p>
	 * <code>t1.keySet().equals(t2.keySet())</code>
	 * </p>
	 * <p>
	 * and for every key <code>k</code> in <code>t1.keySet()</code>,
	 * </p>
	 * <p>
	 * <code>(t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k)))</code>. This ensures that the
	 * <code>equals</code> method works properly across different implementations of the multimap interface.
	 * </p>
	 * <p>
	 * This implementation first checks if the specified object is this map; if so it returns <code>true</code>. Then, it
	 * checks if the specified object is a multimap whose size is identical to the size of this set; if not, it it returns
	 * <code>false</code>. If so, it iterates over this multimap's <code>entrySet</code> collection, and checks that the
	 * specified map contains each mapping that this multimap contains. If the specified map fails to contain such a mapping,
	 * <code>false</code> is returned. If the iteration completes, <code>true</code> is returned.
	 * </p>
	 *
	 * @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 == this)
		{
			return true;
		}

		if (!(o instanceof MultiMap))
		{
			return false;
		}

		MultiMap m = (MultiMap) o;
		if (m.size() != size())
		{
			return false;
		}

		Iterator i = entrySet().iterator();
		while (i.hasNext())
		{
			Entry e = (Entry) i.next();
			Object key = e.getKey();
			Object value = e.getValue();
			if (value == null)
			{
				if (!(m.get(key) == null && m.containsKey(key)))
				{
					return false;
				}
			}
			else
			{
				if (!value.equals(m.get(key)))
				{
					return false;
				}
			}
		}
		return true;
	}


	/**
	 * Returns the hash code value for this multimap. The hash code of a multimap is defined to be the sum of the hash codes
	 * 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 maps <code>t1</code> and <code>t2</code>, as required by the
	 * general contract of <code>Object.hashCode.</code>
	 *
	 * <p>
	 * This implementation iterates over <code>entrySet()</code>, calling <code>hashCode</code> on each element (entry) in
	 * the Collection, and adding up the results.
	 * </p>
	 *
	 * @return The hash code value for this multimap.
	 * @see MultiMap.Entry#hashCode()
	 */
	public int hashCode()
	{
		int h = 0;
		Iterator i = entrySet().iterator();
		while (i.hasNext())
		{
			h += i.next().hashCode();
		}
		return h;
	}


	/**
	 * Returns a string representation of this multimap. The string representation consists of a list of key-value mappings
	 * in the order returned by the multimap's <code>entrySet</code> view's iterator, enclosed in braces (<code>"{}"</code>).
	 * Adjacent mappings are separated by the characters <code>", "</code> (comma and space). Each key-value mapping is
	 * rendered as the key followed by an equals sign (<code>"="</code>) followed by the associated value. Keys and values are
	 * converted to strings as by <code>String.valueOf(Object)</code>.
	 *
	 * <p>
	 * This implementation creates an empty string buffer, appends a left brace, and iterates over the multimap's
	 * <code>entrySet</code> view, appending the string representation of each <code>MultiMap.Entry</code> in turn. After
	 * appending each entry except the last, the string <code>", "</code> is appended. Finally a right brace is appended. A
	 * <code>String</code> is obtained from the <code>StringBuffer</code>, and returned.
	 * </p>
	 *
	 * @return A <code>String</code> representation of this multimap.
	 */
	public String toString()
	{
		int max = size() - 1;
		StringBuffer buf = new StringBuffer();
		Iterator i = entrySet().iterator();

		buf.append("{");
		for (int j = 0; j <= max; j++)
		{
			Entry e = (Entry) (i.next());
			buf.append(e.getKey() + "=" + e.getValue());
			if (j < max)
			{
				buf.append(", ");
			}
		}
		buf.append("}");
		return buf.toString();
	}
}
