import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 *  An object that maps keys to values. A dictionary cannot contain duplicate
 *  keys; each key can map to at most one value. A sorted dictioanry that
 *  further guarantees that it will be in ascending key order, sorted according
 *  to the natural ordering of its keys (see the Comparable interface), or by a
 *  comparator provided at creation time. This order is reflected when
 *  iterating over the sorted dictionary's collection views (returned by the
 *  <tt>keys</tt> and <tt>elements</tt> methods).
 *  <p>
 *  All implementations of a sorted dictionary should provide two "standard"
 *  constructors: 1) A void (no arguments) constructor, which creates an empty
 *  sorted map sorted according to the natural order of its keys. 2) A
 *  constructor with a single argument of type Comparator, which creates an
 *  empty sorted map sorted according to the specified comparator.  There is no
 *  way to enforce this recommendation (as interfaces cannot contain
 *  constructors) but should an implementation be handed in that does not
 *  comply, it will be failed immediately.
 */
public interface SortedDictionary
{
    /**
     *  Returns the number of key-value mappings in the dictionary.
     */
    public int size ();

    /**
     *  Returns <tt>true</tt> if and only if the dictionary contains no key-value mappings.
     */
    public boolean isEmpty ();

    /**
     *  Returns an iterator over the values stored in the dictionary. The
     *  iterator will traverse the values in the order their corresponding keys
     *  occur in the dictionary. The iterator does not support the remove
     *  opertion.  If the dictionary is change while an iteration is in
     *  progress the results of the iteration are undefined.
     */
    public Iterator elements ();

    /**
     *  Returns an iterator over the keys stored in the dictionary. The
     *  iterator will traverse the keys in ascending order. The iterator does
     *  not support the remove opertion.  If the dictionary is change while an
     *  iteration is in progress the results of the iteration are undefined.
     */
    public Iterator keys ();


    /**
     * Returns <tt>true</tt> if this dictionary contains a mapping for the specified key.
     */
    public boolean containsKey(Object key);

    /**
     *  Returns the value to which the dictionary maps the specified key.  If
     *  the dictionary contains a mapping from the key <tt>key</tt> to the
     *  value <tt>val</tt>, then this method returns <tt>val</tt>, otherwise it
     *  throws a <tt>java.util.NoSuchElementException</tt>.
     *  @throws NoSuchElementException when <tt>key</tt> is not in the dictionary.
     *  @param key the key to be located.
     *  @return the element associated with <tt>key</tt> in the dictionary.
     */
    public Object findElement (Object key)
        throws NoSuchElementException;

    
    /**
     *  Associates the value <tt>value</tt> with the key <tt>key</tt> in the
     *  dictionary.  If the dictionary already contains a mapping for the key
     *  the old value is replaced.
     *  @param key the key that should be mapped.
     *  @param value the value to which the key should be mapped.
     */
    public void insertItem (Object key, Object value);

    /**
     *  Removes the mapping for this key from the dictionary. Returns the value to
     *  which the key was mapped. If the dictionary does not contain a mapping for
     *  the specified key a <tt>java.util.NoSuchElementException</tt> is thrown.
     *  @throws NoSuchElementException when <tt>key</tt> is not in the dictionary.
     *  @param key the key whose mapping should be removed.
     *  @return the element associated with <tt>key</tt> in the dictionary.
     */
    public Object removeElement (Object key)
        throws NoSuchElementException;

    /**
     *  Removes all mappings from this dictionary.
     */
    public void clear();
}