/***************************************************************************
    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.util.Collection;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;
import java.lang.Object;
import java.lang.ClassCastException;
import java.lang.NullPointerException;
import java.lang.UnsupportedOperationException;
import java.lang.IllegalArgumentException;
import java.lang.Throwable;
import java.lang.RuntimeException;
import java.lang.Exception;


/**
 * An object that maps keys to multiple values. A multimap can contain duplicate keys, this is something that <code>Map</code>
 * objects cannot do.
 *
 * <p>
 * The <code>MultiMap</code> interface provides three collection views, which allow a multimap's contents to be viewed as a set
 * of keys, collection of values, or set of key-values mappings. The order of a multimap is defined as the order in which the
 * iterators on the multimap's collection views return their elements.
 * </p>
 * <p>
 * Note: great care must be exercised if mutable objects are used as multimap keys. The behavior of a multimap is not specified
 * if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the multimap. A
 * special case of this prohibition is that it is not permissible for a multimap to contain itself as a key. While it is
 * permissible for a multimap to contain itself as a value, extreme caution is advised: the <code>equals</code> and
 * <code>hashCode</code> methods are no longer well defined on a such a multimap.
 * </p>
 * <p>
 * All general-purpose multimap implementation classes should provide two "standard" constructors: a void (no arguments)
 * constructor which creates an empty multimap, and a constructor with a single argument of type <code>MultiMap</code>, which
 * creates a new multimap with the same key-values mappings as its argument. In effect, the latter constructor allows the user to
 * copy any multimap, producing an equivalent multimap of the desired class. There is no way to enforce this recommendation
 * (as interfaces cannot contain constructors) but all of the general-purpose multimap implementations in the
 * <code>com.neoworks.util</code> package comply.
 * </p>
 *
 * @author Stuart Farnan <a href="mailto:stuart@neoworks.com">stuart@neoworks.com</a>
 * @version 0.1
 */
public interface MultiMap
{
	/**
	 * 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 ();


	/**
	 * 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 ();


	/**
	 * 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;


	/**
	 * 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);


	/**
	 * 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;


	/**
	 * 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.
	 * @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;


	/**
	 * 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;


	/**
	 * 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;


	/**
	 * 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;


	/**
	 * Removes all mappings from this multimap (optional operation).
	 *
	 * @exception UnsupportedOperationException If clear is not supported by this multimap.
	 */
	public void clear () throws UnsupportedOperationException;


	/**
	 * 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.
	 *
	 * Note: As a MultiMap may contain duplicate keys this method may also return duplicate values.
	 *
	 * @return A collection view of the keys contained in this multimap.
	 */
	public Collection keys ();
	
	/**
	 * Returns a collection of the <b>unique<b> keys in this multimap.
	 *
	 * @return A collection view of the unique keys contained in this multimap.
	 */
	public Collection uniqueKeys();

	/**
	 * 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 ();

	/**
	 * Returns a set view of the mappings contained in this multimap. Each element in the returned set is a
	 * <code>MultiMap.Entry</code>. The set is backed by the multimap, so changes to the multimap are reflected in the set,
	 * 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 set supports element removal, which removes the corresponding mapping from the multimap,
	 * 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 Set entrySet ();

	/**
	 * 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);

	/**
	 * 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 ();


	/**
	 * A multimap entry (key-value pair). The <code>MultiMap.entrySet</code> method returns a collection-view of the multimap,
	 * whose elements are of this class. The only way to obtain a reference to a multimap entry is from the iterator of this
	 * collection-view. These <code>MultiMap.Entry</code> objects are valid only for the duration of the iteration; more
	 * formally, the behavior of a multimap entry is undefined if the backing multimap has been modified after the entry was
	 * returned by the iterator, except through the iterator's own remove operation, or through the <code>setValue</code>
	 * operation on a multimap entry returned by the iterator. 
	 *
	 * @author Stuart Farnan <a href="mailto:stuart@neoworks.com">stuart@neoworks.com</a>
	 * @version 0.1
	 */
	public static interface Entry
	{
		/**
		 * Returns the key corresponding to this entry.
		 *
		 * @return The key corresponding to this entry.
		 */
		public Object getKey ();


		/**
		 * Returns the value corresponding to this entry. If the mapping has been removed from the backing
		 * multimap (by the iterator's remove operation), the results of this call are undefined.
		 *
		 * @return The value corresponding to this entry.
		 */
		public Object getValue ();


		/**
		 * Replaces the value corresponding to this entry with the specified value (optional operation). (Writes through
		 * to the multimap.) The behavior of this call is undefined if the mapping has already been removed from the
		 * multimap (by the iterator's remove operation).
		 *
		 * @return The old value corresponding to the entry.
		 * @param value The value to set
		 * @exception UnsupportedOperationException If the put operation is not supported by the backing multimap.
		 * @exception ClassCastException If the class of the specified value prevents it from being stored in the
		 * backing multimap.
		 * @exception IllegalArgumentException If some aspect of this value prevents it from being stored in the backing
		 * multimap.
		 * @exception NullPointerException The backing multimap does not permit null values, and the specified value is
		 * null.
		 */
		public Object setValue (Object value) throws UnsupportedOperationException, ClassCastException, IllegalArgumentException, NullPointerException;


		/**
		 * Compares the specified object with this entry for equality. Returns true if the given object is also a multimap
		 * entry and the two entries represent the same mapping. More formally, two entries e1 and e2 represent the
		 * same mapping if:
		 *
		 * <p>
		 * <code>(e1.getKey() == null ? e2.getKey() == null : e1.getKey().equals(e2.getKey())) &&</code><br>
		 * <code>(e1.getValues() == null ? e2.getValues() == null : e1.getValues().equals(e2.getValues()))</code>
		 * </p>
		 * <p>
		 * This ensures that the equals method works properly across different implementations of the
		 * <code>MultiMap.Entry</code> interface.
		 * </p>
		 *
		 * @return <code>true</code> if the specified object is equal to this multimap entry.
		 * @param o The object to compare with
		 */
		public boolean equals (Object o);


		/**
		 * Returns the hash code value for this multimap entry. The hash code of a multimap entry e is defined to be: 
		 *
		 * <p>
		 * <code>(e.getKey() == null ? 0 : e.getKey().hashCode()) ^</code><br>
		 * <code>(e.getValues() == null ? 0 : e.getValues().hashCode())</code>
		 * </p>
		 * <p>
		 * This ensures that <code>e1.equals(e2)</code> implies that <code>e1.hashCode() == e2.hashCode()</code> for any two
		 * entries e1 and e2, as required by the general contract of <code>Object.hashCode</code>.
		 * </p>
		 *
		 * @return The hash code value for this multimap entry.
		 */
		public int hashCode ();
	}
}
