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 / OrderedSet.java < prev    next >
Encoding:
Java Source  |  1997-03-14  |  18.0 KB  |  572 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. import java.io.ObjectInputStream;
  8. import java.io.ObjectOutputStream;
  9. import java.io.IOException;
  10.  
  11. /**
  12.  * A OrderedSet is a container that is optimized for fast associative lookup.
  13.  * Items are matched using equals(). When an item is inserted into a
  14.  * OrderedSet, it is stored in a data structure that allows the item to be
  15.  * found very quickly. Within the data structure, the items are ordered
  16.  * according to a comparator object. By default, the comparator is a
  17.  * HashComparator that orders objects based on their hash value.
  18.  * The OrderedSet class supports the full range of generic set algorithms such
  19.  * as union() and intersection() in a user-friendly manner.  Duplicates are not
  20.  * allowed by default.
  21.  * <p>
  22.  * OrderedSets are useful when fast associate lookup is important and when index-based
  23.  * lookup is unnecessary.
  24.  * <p>
  25.  * Strictly speaking, there is no reason why null is not a valid entry.
  26.  * However, most comparators (including the default HashComparator) will fail
  27.  * and throw an exception if you attempt to add a null entry because they cast
  28.  * the entry to a class and then activate one of its methods. It is perfectly
  29.  * possible to hand-craft a comparator that will accept null as a valid key.
  30.  * <p>
  31.  * There are many different approaches that could be used to implementing an
  32.  * associative container. For example, most of the older libraries used a
  33.  * hashing scheme for positioning and retrieving items. This implementation
  34.  * uses a data structure called a red-black tree. A red-black tree is a binary
  35.  * search tree that uses an extra field in every node to store the node's
  36.  * color. Red-black trees constrain the way that nodes may be colored in such a
  37.  * way that the tree remains reasonably balanced. This property is important
  38.  * for ensuring a good overall performance - red-black trees guarantee that the
  39.  * worst case performance for the most common dynamic set operations is
  40.  * O( log N ). One conseqence of using a binary tree for storage of data is
  41.  * that the items remain in a sorted order. This allows JGL users to iterate
  42.  * through an associative container and access its elements in a sequenced
  43.  * manner.
  44.  * <p>
  45.  * Insertion does not affect iterators or references.
  46.  * <p>
  47.  * Removal only invalidates the iterators and references to the removed
  48.  * elements.
  49.  * <p>
  50.  * @see COM.objectspace.jgl.Set
  51.  * @see COM.objectspace.jgl.BinaryPredicate
  52.  * @see COM.objectspace.jgl.SetOperations
  53.  * @see COM.objectspace.jgl.examples.OrderedSetExamples
  54.  * @version 2.0.2
  55.  * @author ObjectSpace, Inc.
  56.  */
  57.  
  58. public class OrderedSet implements Set
  59.   {
  60.   transient Tree myTree;
  61.  
  62.   /**
  63.    * Construct myself to be an empty OrderedSet that orders elements based on
  64.    * their hash value and does not allow duplicates.
  65.    */
  66.   public OrderedSet()
  67.     {
  68.     myTree = new Tree( false, false, this );
  69.     }
  70.  
  71.   /**
  72.    * Construct myself to be an empty OrderedSet that orders elements based on
  73.    * their hash value and conditionally allows duplicates.
  74.    * @param allowDuplicates true if duplicates are allowed.
  75.    */
  76.   public OrderedSet( boolean allowDuplicates )
  77.     {
  78.     myTree = new Tree( false, allowDuplicates, this );
  79.     }
  80.  
  81.   /**
  82.    * Construct myself to be an empty OrderedSet that orders elements using
  83.    * a specified binary predicate and does not allow duplicates.
  84.    * @param comparator The predicate for ordering objects.
  85.    */
  86.   public OrderedSet( BinaryPredicate comparator )
  87.     {
  88.     myTree = new Tree( false, false, comparator, this );
  89.     }
  90.  
  91.   /**
  92.    * Construct myself to be an empty OrderedSet that orders elements using
  93.    * a specified binary predicate and conditionally allows duplicates.
  94.    * @param comparator The predicate for ordering objects.
  95.    * @param allowDuplicates true if duplicates are allowed.
  96.    */
  97.   public OrderedSet( BinaryPredicate comparator, boolean allowDuplicates )
  98.     {
  99.     myTree = new Tree( false, allowDuplicates, comparator, this );
  100.     }
  101.  
  102.   /**
  103.    * Construct myself to be a shallow copy of an existing OrderedSet.
  104.    * @param set The OrderedSet to copy.
  105.    */
  106.   public OrderedSet( OrderedSet set )
  107.     {
  108.     synchronized( set )
  109.       {
  110.       myTree = new Tree( set.myTree );
  111.       }
  112.     }
  113.  
  114.   /**
  115.    * Return true if duplicates are allowed.
  116.    */
  117.   public boolean allowsDuplicates()
  118.     {
  119.     return myTree.myInsertAlways;
  120.     }
  121.  
  122.   /**
  123.    * Return a shallow copy of myself.
  124.    */
  125.   public synchronized Object clone()
  126.     {
  127.     return new OrderedSet( this );
  128.     }
  129.  
  130.   /**
  131.    * Become a shallow copy of an existing OrderedSet.
  132.    * @param set The OrderedSet that I shall become a shallow copy of.
  133.    */
  134.   public synchronized void copy( OrderedSet set )
  135.     {
  136.     synchronized( set )
  137.       {
  138.       myTree.copy( set.myTree );
  139.       }
  140.     }
  141.  
  142.   /**
  143.    * Return a string that describes me.
  144.    */
  145.   public synchronized String toString()
  146.     {
  147.     return Printing.toString( this, "OrderedSet" );
  148.     }
  149.  
  150.   /**
  151.    * Return an Enumeration of my components.
  152.    */
  153.   public synchronized Enumeration elements()
  154.     {
  155.     return myTree.beginSet();
  156.     }
  157.  
  158.   /**
  159.    * Return an iterator positioned at my first item.
  160.    */
  161.   public ForwardIterator start()
  162.     {
  163.     return begin();
  164.     }
  165.  
  166.   /**
  167.    * Return an iterator positioned immediately afer my last item.
  168.    */
  169.   public ForwardIterator finish()
  170.     {
  171.     return end();
  172.     }
  173.  
  174.   /**
  175.    * Return an iterator positioned at my first item.
  176.    */
  177.   public synchronized OrderedSetIterator begin()
  178.     {
  179.     return myTree.beginSet();
  180.     }
  181.  
  182.   /**
  183.    * Return an iterator positioned immediately after my last item.
  184.    */
  185.   public synchronized OrderedSetIterator end()
  186.     {
  187.     return myTree.endSet();
  188.     }
  189.  
  190.   /**
  191.    * Return true if I contain no entries.
  192.    */
  193.   public boolean isEmpty()
  194.     {
  195.     return myTree.size == 0;
  196.     }
  197.  
  198.   /**
  199.    * Return the number of entries that I contain.
  200.    */
  201.   public int size()
  202.     {
  203.     return myTree.size;
  204.     }
  205.  
  206.   /**
  207.    * Return the maximum number of entries that I can contain.
  208.    */
  209.   public int maxSize()
  210.     {
  211.     return myTree.maxSize();
  212.     }
  213.  
  214.   /**
  215.    * Return true if I'm equal to another object.
  216.    * @param object The object to compare myself against.
  217.    */
  218.   public boolean equals( Object object )
  219.     {
  220.     return object instanceof OrderedSet && equals( (OrderedSet)object );
  221.     }
  222.  
  223.   /**
  224.    * Return true if I contain the same items in the same order as
  225.    * another OrderedSet. Use equals() to compare the individual elements.
  226.    * @param set The OrderedSet to compare myself against.
  227.    */
  228.   public synchronized boolean equals( OrderedSet set )
  229.     {
  230.     synchronized( set )
  231.       {
  232.       return Comparing.equal( this, set );
  233.       }
  234.     }
  235.  
  236.   /**
  237.    * Return my hash code for support of hashing containers
  238.    */
  239.   public synchronized int hashCode()
  240.     {
  241.     return Hashing.orderedHash( this );
  242.     }
  243.  
  244.   /**
  245.    * Swap my contents with another OrderedSet.
  246.    * @param set The OrderedSet that I will swap my contents with.
  247.    */
  248.   public synchronized void swap( OrderedSet set )
  249.     {
  250.     synchronized( set )
  251.       {
  252.       Tree tmp = myTree;
  253.       myTree = set.myTree;
  254.       set.myTree = tmp;
  255.       }
  256.     }
  257.  
  258.   /**
  259.    * Remove all of my elements.
  260.    */
  261.   public synchronized void clear()
  262.     {
  263.     myTree.clear();
  264.     }
  265.  
  266.   /**
  267.    * Remove all objects that match the given object.
  268.    * @param object The object to match for removals
  269.    * @return Return The number of objects removed.
  270.    */
  271.   public synchronized int remove( Object object )
  272.     {
  273.     Pair result = myTree.remove( object );
  274.     return ( (Number)result.second ).intValue();
  275.     }
  276.  
  277.  
  278.   /**
  279.    * Remove at most a given number of objects that match the given object.
  280.    * @param object The object to match for removals
  281.    * @param count The maximum number of objects to remove.
  282.    * @return Return The number of objects removed.
  283.    */
  284.   public synchronized int remove( Object object, int count )
  285.     {
  286.     Pair result = myTree.remove( object, count );
  287.     return ( (Number)result.second ).intValue();
  288.     }
  289.  
  290.   /**
  291.    * Remove the element at a particular position.
  292.    * @param e An Enumeration positioned at the element to remove.
  293.    * @exception IllegalArgumentException if the Enumeration isn't a
  294.    * OrderedSetIterator for this OrderedSet object.
  295.    * @return The object that was removed or null if none
  296.    */
  297.   public synchronized Object remove( Enumeration e )
  298.     {
  299.     if ( ! (e instanceof OrderedSetIterator) )
  300.       throw new IllegalArgumentException( "Enumeration not a OrderedSetIterator" );
  301.  
  302.     if ( ((OrderedSetIterator)e).myOrderedSet != this )
  303.       throw new IllegalArgumentException( "Enumeration not for this OrderedSet" );
  304.  
  305.     Tree.TreeNode node = myTree.remove( ((OrderedSetIterator)e).myNode );
  306.     return ( node == null ? null : node.object );
  307.     }
  308.  
  309.   /**
  310.    * Remove the elements within a specified range.
  311.    * @param first An Enumeration positioned at the first element to remove.
  312.    * @param last An Enumeration positioned immediately after the last element to remove.
  313.    * @exception IllegalArgumentException is the Enumeration isn't a
  314.    * OrderedSetIterator for this OrderedSet object.
  315.    * @return Return the nubmer of values removed.
  316.    */
  317.   public synchronized int remove( Enumeration first, Enumeration last )
  318.     {
  319.     if ( ( ! (first instanceof OrderedSetIterator) ) ||
  320.         ( ! (last instanceof OrderedSetIterator) ) )
  321.       throw new IllegalArgumentException( "Enumeration not a OrderedSetIterator" );
  322.  
  323.     if ( ( ((OrderedSetIterator)first).myOrderedSet != this ) ||
  324.         ( ((OrderedSetIterator)last).myOrderedSet != this ) )
  325.       throw new IllegalArgumentException( "Enumeration not for this OrderedSet" );
  326.  
  327.     Pair result = myTree.remove( ((OrderedSetIterator)first).myNode, ((OrderedSetIterator)last).myNode );
  328.     return ( (Number)result.second ).intValue();
  329.     }
  330.  
  331.   /**
  332.    * Find an object and return its position. If the object
  333.    * is not found, return end().
  334.    * @param object The object to locate.
  335.    */
  336.   public synchronized OrderedSetIterator find( Object object )
  337.     {
  338.     return new OrderedSetIterator( myTree, myTree.find( object ), this );
  339.     }
  340.  
  341.   /**
  342.    * Return the number of items that match a particular object.
  343.    * @param object The object to match against.
  344.    */
  345.   public synchronized int count( Object object )
  346.     {
  347.     return myTree.count( object );
  348.     }
  349.  
  350.   /**
  351.    * Return an iterator positioned at the first location that a
  352.    * particular object could be inserted without violating the ordering
  353.    * criteria. If no such location is found, return an iterator
  354.    * positioned at end().
  355.    * @param object The object in question.
  356.    */
  357.   public synchronized OrderedSetIterator lowerBound( Object object )
  358.     {
  359.     return new OrderedSetIterator( myTree, myTree.lowerBound( object ), this );
  360.     }
  361.  
  362.   /**
  363.    * Return an iterator positioned at the last location that
  364.    * a particular object could be inserted without violating the ordering
  365.    * criteria. If no such location is found, return an iterator
  366.    * positioned at end().
  367.    * @param object The object in question.
  368.    */
  369.   public synchronized OrderedSetIterator upperBound( Object object )
  370.     {
  371.     return new OrderedSetIterator( myTree, myTree.upperBound( object ), this );
  372.     }
  373.  
  374.   /**
  375.    * Return a pair of iterators whose first element is equal to
  376.    * lowerBound() and whose second element is equal to upperBound().
  377.    * @param object The object whose bounds are to be found.
  378.    */
  379.   public synchronized Range equalRange( Object object )
  380.     {
  381.     Pair range = myTree.equalRange( object );
  382.     return new Range
  383.       (
  384.       new OrderedSetIterator( myTree, (Tree.TreeNode)range.first, this ),
  385.       new OrderedSetIterator( myTree, (Tree.TreeNode)range.second, this )
  386.       );
  387.     }
  388.  
  389.   /**
  390.    * Return my comparator.
  391.    */
  392.   public BinaryPredicate getComparator()
  393.     {
  394.     return myTree.myComparator;
  395.     }
  396.  
  397.   /**
  398.    * If the object doesn't exist or duplicates are allowed, add the object and return null,
  399.    * otherwise don't modify the set and return the matching object.
  400.    * @param object The object to be added.
  401.    * @exception NullPointerException If the value of the object is equal to null.
  402.    */
  403.   public synchronized Object add( Object object )
  404.     {
  405.     if ( object == null )
  406.       throw new NullPointerException();
  407.  
  408.     Tree.InsertResult result = myTree.insert( object );
  409.     return result.ok ? null : result.node.object;
  410.     }
  411.  
  412.   /**
  413.    * Return the first object that matches the given object, or null if no match exists.
  414.    * @param object The object to match against.
  415.    */
  416.   public synchronized Object get( Object object )
  417.     {
  418.     Tree.TreeNode node = myTree.find( object );
  419.  
  420.     if ( node.object == null )
  421.       return null;
  422.  
  423.     return node.object.equals( object ) ? node.object : null;
  424.     }
  425.  
  426.   /**
  427.    * If the object doesn't exist, add the object and return null, otherwise replace the
  428.    * first object that matches and return the old object.
  429.    * @param object The object to add.
  430.    * @exception NullPointerException If the value of the object is equal to null.
  431.    */
  432.   public synchronized Object put( Object object )
  433.     {
  434.     if ( object == null )
  435.       throw new NullPointerException();
  436.  
  437.     Tree.InsertResult result = myTree.put( object );
  438.     if ( result.ok )
  439.       return null;
  440.  
  441.     Object previous = result.node.object;
  442.     result.node.object = object;
  443.     return previous;
  444.     }
  445.  
  446.   /**
  447.    * Return a new OrderedSet that contains all of my elements and all of the elements in
  448.    * a specified OrderedSet.
  449.    * @param set The OrderedSet to union myself with.
  450.    * @exception COM.objectspace.jgl.InvalidOperationException if set is in multi-mode.
  451.    */
  452.   public synchronized OrderedSet union( OrderedSet set )
  453.     {
  454.     if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  455.       throw new InvalidOperationException( "union operation invalid on multisets" );
  456.  
  457.     OrderedSet result = new OrderedSet( getComparator(), allowsDuplicates() );
  458.     SetOperations.setUnion( this, set, new InsertIterator( result ), getComparator() );
  459.     return result;
  460.     }
  461.  
  462.   /**
  463.    * Return a new OrderedSet that contains the elements that are both in me and in
  464.    * a specified set.
  465.    * @param set The OrderedSet to intersect myself with.
  466.    */
  467.   public synchronized OrderedSet intersection( OrderedSet set )
  468.     {
  469.     synchronized( set )
  470.       {
  471.       if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  472.         throw new InvalidOperationException( "intersection operation invalid on multisets" );
  473.  
  474.       OrderedSet result = new OrderedSet( getComparator(), allowsDuplicates() );
  475.       SetOperations.setIntersection( this, set, new InsertIterator( result ), getComparator() );
  476.       return result;
  477.       }
  478.     }
  479.  
  480.   /**
  481.    * Return a new OrderedSet that contains the elements that are in me but not in a
  482.    * specified set.
  483.    * @param set The OrderedSet to difference myself with.
  484.    */
  485.   public synchronized OrderedSet difference( OrderedSet set )
  486.     {
  487.     synchronized( set )
  488.       {
  489.       if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  490.         throw new InvalidOperationException( "difference operation invalid on multisets" );
  491.  
  492.       OrderedSet result = new OrderedSet( getComparator(), allowsDuplicates() );
  493.       SetOperations.setDifference( this, set, new InsertIterator( result ), getComparator() );
  494.       return result;
  495.       }
  496.     }
  497.  
  498.   /**
  499.    * Return a new OrderedSet that contains the elements that are either in me or in
  500.    * a specified OrderedSet, but not both.
  501.    * @param set The OrderedSet to symmetric difference myself with.
  502.    */
  503.   public synchronized OrderedSet symmetricDifference( OrderedSet set )
  504.     {
  505.     synchronized( set )
  506.       {
  507.       if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  508.         throw new InvalidOperationException( "symmetricDifference operation invalid on multisets" );
  509.  
  510.       OrderedSet result = new OrderedSet( getComparator(), allowsDuplicates() );
  511.       SetOperations.setSymmetricDifference( this, set, new InsertIterator( result ), getComparator() );
  512.       return result;
  513.       }
  514.     }
  515.  
  516.   /**
  517.    * Return true if every element in me is also in a specified OrderedSet.
  518.    * @param set The OrderedSet to test against.
  519.    */
  520.   public synchronized boolean subsetOf( OrderedSet set )
  521.     {
  522.     synchronized( set )
  523.       {
  524.       if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  525.         throw new InvalidOperationException( "subsetOf operation invalid on multisets" );
  526.  
  527.       return SetOperations.includes( set, this, getComparator() );
  528.       }
  529.     }
  530.  
  531.   /**
  532.    * Return true if every element in me is also in a specified OrderedSet and I'm smaller
  533.    * than the specified OrderedSet.
  534.    * @param set The OrderedSet to test against.
  535.    */
  536.   public synchronized boolean properSubsetOf( OrderedSet set )
  537.     {
  538.     synchronized( set )
  539.       {
  540.       if ( myTree.myInsertAlways || set.myTree.myInsertAlways )
  541.         throw new InvalidOperationException( "properSubsetOf operation invalid on multisets" );
  542.  
  543.       return (size() < set.size()) && subsetOf( set );
  544.       }
  545.     }
  546.  
  547.   private synchronized void writeObject( ObjectOutputStream stream ) throws IOException
  548.     {
  549.     stream.defaultWriteObject();
  550.  
  551.     stream.writeBoolean( allowsDuplicates() );
  552.     stream.writeObject( getComparator() );
  553.  
  554.     stream.writeInt( size() );
  555.     Copying.copy( begin(), end(), new ObjectOutputStreamIterator( stream ) );
  556.     }
  557.  
  558.   private void readObject( ObjectInputStream stream ) throws IOException, ClassNotFoundException
  559.     {
  560.     stream.defaultReadObject();
  561.  
  562.     boolean allowDuplicates = stream.readBoolean();
  563.     BinaryPredicate comparator = (BinaryPredicate)stream.readObject();
  564.  
  565.     myTree = new Tree( false, allowDuplicates, comparator, this );
  566.  
  567.     int count = stream.readInt();
  568.     while ( count-- > 0 )
  569.       add( stream.readObject() );
  570.     }
  571.   }
  572.