home *** CD-ROM | disk | FTP | other *** search
/ Symantec Visual Cafe for Java 2.5 / symantec-visual-cafe-2.5-database-dev-edition.iso / Extras / OSpace / jgl.exe / jgl_2_0 / src / COM / objectspace / jgl / OrderedMultiMap.java < prev    next >
Encoding:
Java Source  |  1997-03-14  |  4.7 KB  |  133 lines
  1. // Copyright(c) 1996,1997 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package COM.objectspace.jgl;
  5.  
  6. import java.util.Dictionary;
  7. import java.util.Enumeration;
  8.  
  9. /**
  10.  * An OrderedMultiMap is an associative container that manages a set of ordered key/value pairs.
  11.  * The pairs are ordered by key, using a comparator. By default, a HashComparator is used,
  12.  * which orders keys based on their hash value. Any number of values may be associated with
  13.  * a particular key. A OrderedMultiMap's underlying data structure allows you to very efficiently
  14.  * find all of the values associated with a particular key.
  15.  * <p>
  16.  * A OrderedMultiMap is useful for implementing a collection of one-to-many mappings.
  17.  * <p>
  18.  * Strictly speaking, there is no reason why null is not a valid key. However, most
  19.  * comparators (including the default HashComparator) will fail and throw an exception
  20.  * if you attempt to add a null key because they cast the key to a class and then
  21.  * activate one of its methods. It is perfectly possible to hand-craft a comparator
  22.  * that will accept null as a valid key.
  23.  * <p>
  24.  * There are many different approaches that could be used to implementing an associative
  25.  * container. For example, most of the older libraries used a hashing scheme for
  26.  * positioning and retrieving items. This implementation use a data structure called a
  27.  * red-black tree. A red-black tree is a binary search tree that uses an extra field in
  28.  * every node to store the node's color. Red-black trees constrain the way that nodes may
  29.  * be colored in such a way that the tree remains reasonably balanced. This property is
  30.  * important for ensuring a good overall performance - red-black trees guarantee that the
  31.  * worst case performance for the most common dynamic set operations is O(log N). One
  32.  * conseqence of using a binary tree for storage of data is that the items remain in a
  33.  * sorted order. This allows JGL users to iterate through an associative container and
  34.  * access its elements in a sequenced manner. Each node of the red-black tree holds a
  35.  * Pair( key, value ). The comparator is used to order the Pairs based only on their keys.
  36.  * <p>
  37.  * Insertion does not affect iterators or references.
  38.  * <p>
  39.  * Removal only invalidates the iterators and references to the removed elements.
  40.  * <p>
  41.  * @see COM.objectspace.jgl.OrderedMap
  42.  * @see COM.objectspace.jgl.BinaryPredicate
  43.  * @see COM.objectspace.jgl.examples.OrderedMultiMapExamples
  44.  * @version 2.0.2
  45.  * @author ObjectSpace, Inc.
  46.  * @deprecated
  47.  * @see COM.objectspace.jgl.OrderedMap
  48.  */
  49.  
  50. public class OrderedMultiMap extends OrderedMap
  51.   {
  52.   /**
  53.    * Construct myself to be an empty OrderedMultiMap that orders its keys based on
  54.    * their hash value.
  55.    */
  56.   public OrderedMultiMap()
  57.     {
  58.     myTree = new Tree( true, true, this );
  59.     }
  60.  
  61.   /**
  62.    * Construct myself to be an empty OrderedMultiMap that orders its keys using
  63.    * a specified binary predicate.
  64.    * @param comparator The predicate for ordering keys.
  65.    */
  66.   public OrderedMultiMap( BinaryPredicate comparator )
  67.     {
  68.     myTree = new Tree( true, true, comparator, this );
  69.     }
  70.  
  71.   /**
  72.    * Construct myself to be a shallow copy of an existing OrderedMultiMap.
  73.    * @param map The OrderedMultiMap to copy.
  74.    */
  75.   public OrderedMultiMap( OrderedMultiMap map )
  76.     {
  77.     super( map );
  78.     }
  79.  
  80.   /**
  81.    * Return a shallow copy of myself.
  82.    */
  83.   public synchronized Object clone()
  84.     {
  85.     return new OrderedMultiMap( this );
  86.     }
  87.  
  88.   /**
  89.    * Become a shallow copy of an existing OrderedMultiMap.
  90.    * @param map The OrderedMultiMap that I shall become a shallow copy of.
  91.    */
  92.   public synchronized void copy( OrderedMultiMap map )
  93.     {
  94.     super.copy( map );
  95.     }
  96.  
  97.   /**
  98.    * Return a string that describes me.
  99.    */
  100.   public synchronized String toString()
  101.     {
  102.     return Printing.toString( this, "OrderedMultiMap" );
  103.     }
  104.  
  105.   /**
  106.    * Return true if I'm equal to another object.
  107.    * @param object The object to compare myself against.
  108.    */
  109.   public boolean equals( Object object )
  110.     {
  111.     return object instanceof OrderedMultiMap && equals( (OrderedMultiMap) object );
  112.     }
  113.  
  114.   /**
  115.    * Return true if I contain the same items in the same order as
  116.    * another OrderedMultiMap. Use equals() to compare the individual elements.
  117.    * @param map The OrderedMultiMap to compare myself against.
  118.    */
  119.   public synchronized boolean equals( OrderedMultiMap map )
  120.     {
  121.     return super.equals( map );
  122.     }
  123.  
  124.   /**
  125.    * Swap my contents with another OrderedMultiMap.
  126.    * @param map The OrderedMultiMap that I will swap my contents with.
  127.    */
  128.   public synchronized void swap( OrderedMultiMap map )
  129.     {
  130.     super.swap( map );
  131.     }
  132.   }
  133.