/***************************************************************************
    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.Comparator;
import java.lang.Object;
import com.neoworks.util.MultiMap;

/**
 * A multimap that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its
 * keys (see the <code>Comparable</code> interface), or by a comparator provided at sorted multimap creation time. This order is
 * reflected when iterating over the sorted multimap's collection views (returned by the <code>entrySet</code>, <code>keys</code>
 * and <code>values</code> methods). Several additional operations are provided to take advantage of the ordering.
 *
 * <p>
 * All keys inserted into a sorted multimap must implement the <code>Comparable</code> interface (or be accepted by the specified
 * comparator). Furthermore, all such keys must be mutually comparable: <code>k1.compareTo(k2)</code> (or
 * <code>comparator.compare(k1, k2)</code>) must not throw a <code>ClassCastException</code> for any elements
 * <code>k1</code> and <code>k2</code> in the sorted multimap. Attempts to violate this restriction will cause the
 * offending method or constructor invocation to throw a <code>ClassCastException</code>.
 * </p>
 * <p>
 * Note that the ordering maintained by a sorted multimap (whether or not an explicit comparator is provided) must be onsistent
 * with equals if the sorted multimap is to correctly implement the <code>MultiMap</code> interface. (See the
 * <code>Comparable</code> interface or <code>Comparator</code> interface for a precise definition of consistent with equals.)
 * This is so because the <code>MultiMap</code> interface is defined in terms of the <code>equals</code> operation, but a sorted
 * multimap performs all key comparisons using its <code>compareTo</code> (or <code>compare</code>) method, so two keys that are
 * deemed equal by this method are, from the standpoint of the sorted multimap, equal.
 * </p>
 * <p>
 * All general-purpose sorted multimap implementation classes should provide four "standard" constructors: 1) A void (no
 * arguments) constructor, which creates an empty sorted multimap sorted according to the natural order of its keys. 2) A
 * constructor with a single argument of type <code>Comparator</code>, which creates an empty sorted multimap sorted according to
 * the specified comparator. 3) A constructor with a single argument of type <code>MultiMap</code>, which creates a new multimap
 * with the same key-value mappings as its argument, sorted according to the keys' natural ordering. 4) A constructor with a
 * single argument of type sorted multimap, which creates a new sorted multimap with the same key-value mappings and the same
 * ordering as the input sorted multimap. There is no way to enforce this recommendation (as interfaces cannot contain
 * constructors) but the SDK implementation (TreeMap) complies.
 * </p>
 *
 * @author Stuart Farnan <a href="mailto: stuart@neoworks.com">stuart@neoworks.com</a>
 * @version 0.1
 */
public interface SortedMultiMap extends MultiMap
{
	/**
	 * Returns the comparator associated with this sorted multimap, or <code>null</code> if it uses its keys' natural ordering.
	 *
	 * @return the comparator associated with this sorted multimap, or <code>null</code> if it uses its keys' natural ordering.
	 */
	Comparator comparator ();


	/**
	 * Returns a view of the portion of this sorted multimap whose keys range from <code>fromKey</code>, inclusive, to
	 * <code>toKey</code>, exclusive. (If <code>fromKey</code> and <code>toKey</code> are equal, the returned sorted map
	 * is empty.) The returned sorted multimap is backed by this sorted multimap, so changes in the returned sorted multimap are
	 * reflected in this sorted multimap, and vice-versa. The returned Map supports all optional multimap operations that this
	 * sorted multimap supports.
	 *
	 * <p>
	 * The multimap returned by this method will throw an <code>IllegalArgumentException</code> if the user attempts to insert
	 * a key outside the specified range.
	 * </p>
	 *
	 * Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If
	 * you need a closed range (which includes both endpoints), and the key type allows for calculation of the successor a
	 * given key, merely request the subrange from <code>lowEndpoint</code> to <code>successor(highEndpoint)</code>.
	 * For example, suppose that <code>m</code> is a multimap whose keys are strings. The following idiom obtains a view
	 * containing all of the key-value mappings in <code>m</code> whose keys are between <code>low</code> and
	 * <code>high</code>, inclusive:
	 * </p> 
	 * <p>
	 * <code>MultiMap sub = m.subMap(low, high+"\0");</code>
	 * </p>
	 * <p>
	 * A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom
	 * obtains a view containing all of the key-value mappings in <code>m</code> whose keys are between <code>low</code> and
	 * <code>high</code>, exclusive:
	 * </p>
	 * <p>
	 * <code>MultiMap sub = m.subMap(low+"\0", high);</code>
	 * </p>
	 *
	 * @return A view of the specified range within this sorted multimap.
	 * @param fromKey Low endpoint (inclusive) of the subMap.
	 * @param toKey High endpoint (exclusive) of the subMap. */
	SortedMultiMap subMap (Object fromKey, Object toKey);

	/**
	 * Returns a view of the portion of this sorted multimap whose keys are strictly less than toKey. The returned sorted
	 * multimap is backed by this sorted multimap, so changes in the returned sorted multimap are reflected in this
	 * sorted multimap, and vice-versa. The returned multimap supports all optional map operations that this sorted multimap
	 * supports.
	 *
	 * <p>
	 * The multimap returned by this method will throw an IllegalArgumentException if the user attempts to insert a key
	 * outside the specified range.
	 * </p>
	 * <p>
	 * Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain
	 * this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded
	 * by successor(highEndpoint). For example, suppose that suppose that <code>m</code> is a multimap whose keys are strings.
	 * The following idiom obtains a view containing all of the key-value mappings in <code>m</code> whose keys are less than
	 * or equal to * <code>high</code>:
	 * </p>
	 * <p>
	 * <code>MultiMap head = m.headMap(high+"\0");</code>
	 * </p>
	 *
	 * @return A view of the specified initial range of this sorted map.
	 * @param toKey High endpoint (exclusive) of the subMap. */
	SortedMultiMap headMap (Object toKey);


	/**
	 * Returns a view of the portion of this sorted multimap whose keys are greater than or equal to <code>fromKey</code>. The
	 * returned sorted multimap is backed by this sorted multimap, so changes in the returned sorted multimap are reflected in
	 * this sorted multimap, and vice-versa. The returned multimap supports all optional multimap operations that this sorted
	 * multimap supports.
	 *
	 * <p>
	 * The multimap returned by this method will throw an <code>IllegalArgumentException</code> if the user attempts to insert
	 * a key outside the specified range.
	 * </p>
	 * <p>
	 * Note: this method always returns a view that contains its (low endpoint. If you need a view that does not contain this
	 * endpoint, and the element type allows for calculation of the successor a given value, merely request a tailMap bounded
	 * by <code>successor(lowEndpoint)</code>. For example, suppose that suppose that <code>m</code> is a multimap whose keys
	 * are strings. The following idiom obtains a view containing all of the key-value mappings in <code>m</code> whose keys
	 * are strictly greater than <code>low</code>:
	 * </p>
	 * <p>
	 * <code>MultiMap tail = m.tailMap(low+"\0");</code>
	 * </p>
	 *
	 * @return A view of the specified final range of this sorted multimap.
	 * @param fromKey Low endpoint (inclusive) of the tailMap. */
	SortedMultiMap tailMap (Object fromKey);


	/**
	 * Returns the first (lowest) key currently in this sorted multimap.
	 *
	 * @return the first (lowest) key currently in this sorted multimap. */
	Object firstKey ();


	/**
	 * Returns the last (highest) key currently in this sorted multimap.
	 *
	 * @return the last (highest) key currently in this sorted multimap. */
	Object lastKey ();
}
