// Copyright(c) 1996,1997 ObjectSpace, Inc.
// Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.

package COM.objectspace.jgl;

import java.util.Dictionary;
import java.util.Enumeration;

/**
 * An OrderedMultiMap is an associative container that manages a set of ordered key/value pairs.
 * The pairs are ordered by key, using a comparator. By default, a HashComparator is used,
 * which orders keys based on their hash value. Any number of values may be associated with
 * a particular key. A OrderedMultiMap's underlying data structure allows you to very efficiently
 * find all of the values associated with a particular key.
 * <p>
 * A OrderedMultiMap is useful for implementing a collection of one-to-many mappings.
 * <p>
 * Strictly speaking, there is no reason why null is not a valid key. However, most
 * comparators (including the default HashComparator) will fail and throw an exception
 * if you attempt to add a null key because they cast the key to a class and then
 * activate one of its methods. It is perfectly possible to hand-craft a comparator
 * that will accept null as a valid key.
 * <p>
 * There are many different approaches that could be used to implementing an associative
 * container. For example, most of the older libraries used a hashing scheme for
 * positioning and retrieving items. This implementation use a data structure called a
 * red-black tree. A red-black tree is a binary search tree that uses an extra field in
 * every node to store the node's color. Red-black trees constrain the way that nodes may
 * be colored in such a way that the tree remains reasonably balanced. This property is
 * important for ensuring a good overall performance - red-black trees guarantee that the
 * worst case performance for the most common dynamic set operations is O(log N). One
 * conseqence of using a binary tree for storage of data is that the items remain in a
 * sorted order. This allows JGL users to iterate through an associative container and
 * access its elements in a sequenced manner. Each node of the red-black tree holds a
 * Pair( key, value ). The comparator is used to order the Pairs based only on their keys.
 * <p>
 * Insertion does not affect iterators or references.
 * <p>
 * Removal only invalidates the iterators and references to the removed elements.
 * <p>
 * @see COM.objectspace.jgl.OrderedMap
 * @see COM.objectspace.jgl.BinaryPredicate
 * @see COM.objectspace.jgl.examples.OrderedMultiMapExamples
 * @version 2.0.2
 * @author ObjectSpace, Inc.
 * @deprecated
 * @see COM.objectspace.jgl.OrderedMap
 */

public class OrderedMultiMap extends OrderedMap
  {
  /**
   * Construct myself to be an empty OrderedMultiMap that orders its keys based on
   * their hash value.
   */
  public OrderedMultiMap()
    {
    myTree = new Tree( true, true, this );
    }

  /**
   * Construct myself to be an empty OrderedMultiMap that orders its keys using
   * a specified binary predicate.
   * @param comparator The predicate for ordering keys.
   */
  public OrderedMultiMap( BinaryPredicate comparator )
    {
    myTree = new Tree( true, true, comparator, this );
    }

  /**
   * Construct myself to be a shallow copy of an existing OrderedMultiMap.
   * @param map The OrderedMultiMap to copy.
   */
  public OrderedMultiMap( OrderedMultiMap map )
    {
    super( map );
    }

  /**
   * Return a shallow copy of myself.
   */
  public synchronized Object clone()
    {
    return new OrderedMultiMap( this );
    }

  /**
   * Become a shallow copy of an existing OrderedMultiMap.
   * @param map The OrderedMultiMap that I shall become a shallow copy of.
   */
  public synchronized void copy( OrderedMultiMap map )
    {
    super.copy( map );
    }

  /**
   * Return a string that describes me.
   */
  public synchronized String toString()
    {
    return Printing.toString( this, "OrderedMultiMap" );
    }

  /**
   * Return true if I'm equal to another object.
   * @param object The object to compare myself against.
   */
  public boolean equals( Object object )
    {
    return object instanceof OrderedMultiMap && equals( (OrderedMultiMap) object );
    }

  /**
   * Return true if I contain the same items in the same order as
   * another OrderedMultiMap. Use equals() to compare the individual elements.
   * @param map The OrderedMultiMap to compare myself against.
   */
  public synchronized boolean equals( OrderedMultiMap map )
    {
    return super.equals( map );
    }

  /**
   * Swap my contents with another OrderedMultiMap.
   * @param map The OrderedMultiMap that I will swap my contents with.
   */
  public synchronized void swap( OrderedMultiMap map )
    {
    super.swap( map );
    }
  }