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 / OrderedMultiSet.java < prev    next >
Encoding:
Java Source  |  1997-03-14  |  4.7 KB  |  134 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.Enumeration;
  7.  
  8. /**
  9.  * An OrderedMultiSet is a container that is optimized for fast associative lookup. Items are
  10.  * matched using equals(). When an item is inserted into a OrderedMultiSet, it is stored in a
  11.  * data structure that allows the item to be found very quickly. Within the data
  12.  * structure, the items are ordered according to a comparator object. By default, the
  13.  * comparator is a HashComparator that orders objects based on their hash value.
  14.  * An OrderedMultiSet may contain matching items.
  15.  * <p>
  16.  * OrderedMultiSets are useful when fast associate lookup is important and when index-based
  17.  * lookup is unnecessary.
  18.  * <p>
  19.  * Strictly speaking, there is no reason why null is not a valid entry. However, most
  20.  * comparators (including the default HashComparator) will fail and throw an exception
  21.  * if you attempt to add a null entry because they cast the entry to a class and then
  22.  * activate one of its methods. It is perfectly possible to hand-craft a comparator
  23.  * that will accept null as a valid key.
  24.  * <p>
  25.  * There are many different approaches that could be used to implementing an associative
  26.  * container. For example, most of the older libraries used a hashing scheme for
  27.  * positioning and retrieving items. This implementation use a data structure called a
  28.  * red-black tree. A red-black tree is a binary search tree that uses an extra field in
  29.  * every node to store the node's color. Red-black trees constrain the way that nodes may
  30.  * be colored in such a way that the tree remains reasonably balanced. This property is
  31.  * important for ensuring a good overall performance - red-black trees guarantee that the
  32.  * worst case performance for the most common dynamic set operations is O(log N). One
  33.  * conseqence of using a binary tree for storage of data is that the items remain in a
  34.  * sorted order. This allows JGL users to iterate through an associative container and
  35.  * access its elements in a sequenced manner.
  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.OrderedSet
  42.  * @see COM.objectspace.jgl.BinaryPredicate
  43.  * @see COM.objectspace.jgl.SetOperations
  44.  * @see COM.objectspace.jgl.examples.OrderedSetExamples
  45.  * @version 2.0.2
  46.  * @author ObjectSpace, Inc.
  47.  * @deprecated
  48.  * @see COM.objectspace.jgl.OrderedSet
  49.  */
  50.  
  51. public class OrderedMultiSet extends OrderedSet
  52.   {
  53.   /**
  54.    * Construct myself to be an empty OrderedMultiSet that orders elements based on
  55.    * their hash value.
  56.    */
  57.   public OrderedMultiSet()
  58.     {
  59.     myTree = new Tree( false, true, this );
  60.     }
  61.  
  62.   /**
  63.    * Construct myself to be an empty OrderedMultiSet that orders elements using
  64.    * a specified binary predicate.
  65.    * @param comparator The predicate for ordering objects.
  66.    */
  67.   public OrderedMultiSet( BinaryPredicate comparator )
  68.     {
  69.     myTree = new Tree( false, true, comparator, this );
  70.     }
  71.  
  72.   /**
  73.    * Construct myself to be a shallow copy of an existing OrderedMultiSet.
  74.    * @param set The OrderedMultiSet to copy.
  75.    */
  76.   public OrderedMultiSet( OrderedMultiSet set )
  77.     {
  78.     super( set );
  79.     }
  80.  
  81.   /**
  82.    * Return a shallow copy of myself.
  83.    */
  84.   public synchronized Object clone()
  85.     {
  86.     return new OrderedMultiSet( this );
  87.     }
  88.  
  89.   /**
  90.    * Become a shallow copy of an existing OrderedMultiSet.
  91.    * @param set The OrderedMultiSet that I shall become a shallow copy of.
  92.    */
  93.   public synchronized void copy( OrderedMultiSet set )
  94.     {
  95.     super.copy( set );
  96.     }
  97.  
  98.   /**
  99.    * Return a string that describes me.
  100.    */
  101.   public synchronized String toString()
  102.     {
  103.     return Printing.toString( this, "OrderedMultiSet" );
  104.     }
  105.  
  106.   /**
  107.    * Return true if I'm equal to another object.
  108.    * @param object The object to compare myself against.
  109.    */
  110.   public boolean equals( Object object )
  111.     {
  112.     return object instanceof OrderedMultiSet && equals( (OrderedMultiSet) object );
  113.     }
  114.  
  115.   /**
  116.    * Return true if I contain the same items in the same order as
  117.    * another OrderedMultiSet. Use equals() to compare the individual elements.
  118.    * @param set The OrderedMultiSet to compare myself against.
  119.    */
  120.   public synchronized boolean equals( OrderedMultiSet set )
  121.     {
  122.     return super.equals( set );
  123.     }
  124.  
  125.   /**
  126.    * Swap my contents with another OrderedMultiSet.
  127.    * @param set The OrderedMultiSet that I will swap my contents with.
  128.    */
  129.   public synchronized void swap( OrderedMultiSet set )
  130.     {
  131.     super.swap( set );
  132.     }
  133.   }
  134.