ActiveX Programming Unleashed CD/AXU.iso/jgl_1_1/jgl_1_1.exe/src/HashSet.java

Java Source | 1996-09-10 | 22.5 KB | 825 lines

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

package jgl;

import java.util.Enumeration;

/**
 * A HashSet is a container that is optimized for fast associative lookup. Items are
 * matched using a BinaryPredicate which is EqualTo() by default. When an item is
 * inserted into a HashSet, it is stored in a data structure that allows the item
 * to be found very quickly. Items are stored in buckets based on their hash value,
 * computed using the standard function hashCode().
 * By default, a HashSet cannot contain items that match.
 * The HashSet class supports the full range of generic set algorithms such as union()
 * and intersection() in a user-friendly manner.
 * <p>
 * HashSets are useful when fast associate lookup is important, when index-based lookup is
 * unnecessary, and when duplicates are not allowed.
 * <p>
 * Insertion can invalidate iterators.
 * <p>
 * Removal can invalidate iterators.
 * <p>
 * @see jgl.SetOperations
 * @see jgl.examples.HashSetExamples
 * @version 1.1
 * @author ObjectSpace, Inc.
 */

public class HashSet implements Set
  {
  static final int DEFAULT_SIZE = 203;
  static final float DEFAULT_RATIO = 0.75F;

  BinaryPredicate comparator;
  boolean allowDups = false; // does the map allow duplicate keys?
  int size = 0; // # nodes.
  HashSetNode[] buckets; // Array of buckets.
  int length; // buckets.length, cached for speed.
  int limit;
  float ratio;

  /**
   * Construct myself to be an empty HashSet that compares objects using equals() and
   * does not allow duplicates.
   */
  public HashSet()
    {
    this( new EqualTo(), false, DEFAULT_SIZE, DEFAULT_RATIO );
    }

  /**
   * Construct myself to be an empty HashSet that compares objects using equals() and
   * that conditionally allows duplicates.
   * @param allowDuplicates true if duplicates are allowed.
   */
  public HashSet( boolean allowDuplicates )
    {
    this( new EqualTo(), allowDuplicates, DEFAULT_SIZE, DEFAULT_RATIO );
    }

  /**
   * Construct myself to be an empty HashSet that compares objects using the specified
   * binary predicate and does not allow duplicates.
   * @param comparator The predicate for comparing objects.
   */
  public HashSet( BinaryPredicate comparator )
    {
    this( comparator, false, DEFAULT_SIZE, DEFAULT_RATIO );
    }

  /**
   * Construct myself to be an empty HashSet that compares objects using the specified
   * binary predicate and conditionally allows duplicates.
   * @param comparator The predicate for comparing objects.
   * @param allowDuplicates true if duplicates are allowed.
   */
  public HashSet( BinaryPredicate comparator, boolean allowDuplicates )
    {
    this( comparator, allowDuplicates, DEFAULT_SIZE, DEFAULT_RATIO );
    }

  /**
   * Construct myself to be an empty HashSet that compares objects using the specified
   * binary predicate and conditionally allows duplicates. The initial capacity and
   * load ratio must also be specified.
   * @param comparator The predicate for comparing objects.
   * @param allowDuplicates true if duplicates are allowed.
   * @param capacity The initial number of hash buckets to reserve.
   * @param loadRatio The maximum load ratio.
   */
  public HashSet( BinaryPredicate comparator, boolean allowDuplicates, int capacity, float loadRatio  )
    {
    this.comparator = comparator;
    allowDups = allowDuplicates;
    ratio = loadRatio;
    length = capacity;
    limit = (int)( length * ratio );
    buckets = new HashSetNode[ length ];
    }

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

  /**
   * Return true if I allow duplicate objects.
   */
  public boolean allowsDuplicates()
    {
    return allowDups;
    }

 /**
  * Return my comparator.
  */
  public BinaryPredicate getComparator()
    {
    return comparator;
    }

  /**
   * Return my load ratio.
   */
  public float getLoadRatio()
    {
    return ratio;
    }

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

  /**
   * Become a shallow copy of an existing HashSet.
   * @param map The HashSet that I shall become a shallow copy of.
   */
  public synchronized void copy( HashSet set )
    {
    comparator = set.comparator;
    length = set.length;
    ratio = set.ratio;
    limit = set.limit;
    size = set.size;
    buckets = new HashSetNode[ length ];
    allowDups = set.allowDups;

    for( int i = 0; i < length; i++ )
      {
      HashSetNode oldNode = null;
      HashSetNode node = set.buckets[ i ];

      while( node != null )
        {
        HashSetNode newNode = new HashSetNode();
        newNode.object = node.object;
        newNode.hash = node.hash;

        if( buckets[ i ] == null )
          buckets[ i ] = newNode;
        else
          oldNode.next = newNode;

        oldNode = newNode;
        node = node.next;
        }
      }
    }

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

  /**
   * Return an Enumeration of my objects.
   */
  public synchronized Enumeration elements()
    {
    return new HashSetIterator( first(), this );
    }

  /**
   * Return an iterator positioned at my first item.
   */
  public synchronized ForwardIterator start()
    {
    return new HashSetIterator( first(), this );
    }

  /**
   * Return an iterator positioned immediately afer my last item.
   */
  public synchronized ForwardIterator finish()
    {
    return new HashSetIterator( null, this );
    }

  /**
   * Return an iterator positioned at my first item.
   */
  public synchronized HashSetIterator begin()
    {
    return new HashSetIterator( first(), this );
    }

  /**
   * Return an iterator positioned immediately after my last item.
   */
  public synchronized HashSetIterator end()
    {
    return new HashSetIterator( null, this );
    }

  /**
   * Return true if I contain no entries.
   */
  public boolean isEmpty()
    {
    return size == 0;
    }

  /**
   * Return the number of entries that I contain.
   */
  public int size()
    {
    return size;
    }

  /**
   * Return the maximum number of entries that I can contain.
   */
  public int maxSize()
    {
    return Allocator.maxSize();
    }

  /**
   * 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 HashSet && equals( (HashSet) object );
    }

  /**
   * Return true if I contain exactly the same items as another HashSet.
   * Use equals() to compare the individual elements.
   * @param set The HashSet to compare myself against.
   */
  public synchronized boolean equals( HashSet set )
    {
    if( size != set.size )
      return false;

    if( allowDups )
      {
      Object previous = null;

      for( HashSetIterator iterator = begin(); iterator.hasMoreElements(); iterator.advance() )
        {
        Object object = iterator.get();

        // Execute the following code for each unique object in the source.
        if( previous == null || !object.equals( previous ) )
          {
          if( count( object ) != set.count( object ) )
            return false;

          previous = object;
          }
        }

      return true;
      }
    else
      {
      for( HashSetIterator iterator = begin(); iterator.hasMoreElements(); iterator.advance() )
        if( set.count( iterator.get() ) == 0 )
          return false;

      return true;
      }
    }

  /**
   * Return my hash code for support of hashing containers
   */
  public int hashCode()
    {
    return Hashing.unorderedHash( this );
    }

  /**
   * Swap my contents with another HashSet.
   * @param set The HashSet that I will swap my contents with.
   */
  public synchronized void swap( HashSet set )
    {
    int tmpSize = size;
    size = set.size;
    set.size = tmpSize;

    HashSetNode[] tmpBuckets = buckets;
    buckets = set.buckets;
    set.buckets = tmpBuckets;

    int tmpLength = length;
    length = set.length;
    set.length = tmpLength;

    int tmpLimit = limit;
    limit = set.limit;
    set.limit = tmpLimit;

    float tmpRatio = ratio;
    ratio = set.ratio;
    set.ratio = tmpRatio;
    }

  /**
   * Remove all of my elements.
   */
  public synchronized void clear()
    {
    buckets = new HashSetNode[ length ];
    size = 0;
    }

  /**
   * Remove all objects that match the given object.
   * @param object The object to match for removals
   * @return Return the value associated with the first object removed or null if not found.
   */
  public synchronized Object remove( Object object )
    {
    int hash = object.hashCode() & 0x7FFFFFFF;
    int probe = hash % length;

    Object value = null;

    for( HashSetNode node = buckets[ probe ], previous = null; node != null; previous = node, node = node.next )
      if( node.hash == hash && comparator.execute( object, node.object ) )
        {
        HashSetNode end = node.next;
        value = node.object;         // we only want the first one.
        int count = 1;

        if( allowDups )
          {
          while( end != null && end.hash == hash && comparator.execute( object, end.object ) )
            {
            ++count;
            end = end.next;
            }
          }

        if( previous == null )
          buckets[ probe ] = end;
        else
          previous.next = end;

        size -= count;
        return value;
        }

    return value;
    }

  /**
   * Remove the element at a particular position.
   * @param e An Enumeration positioned at the element to remove.
   * @exception IllegalArgumentException is the Enumeration isn't a
   * HashSetIterator for this HashSet object.
   */
  public synchronized void remove( Enumeration e )
    {
    if( ! (e instanceof HashSetIterator) )
      throw new IllegalArgumentException( "Enumeration not a HashSetIterator" );

    if( ((HashSetIterator)e).myHashSet != this )
      throw new IllegalArgumentException( "Enumeration not for this HashSet" );

    HashSetIterator pos = (HashSetIterator)e;
    HashSetNode target = pos.myNode;
    int probe = target.hash % length;
    HashSetNode node = buckets[ probe ];

    if( target == node )
      {
      buckets[ probe ] = target.next;
      }
    else
      {
      while( node.next != target )
        node = node.next;

      node.next = target.next;
      }

    --size;
    }

  /**
   * Remove the elements within a specified range.
   * @param first An Enumeration positioned at the first element to remove.
   * @param last An Enumeration positioned immediately after the last element to remove.
   * @exception IllegalArgumentException is the Enumeration isn't a
   * HashSetIterator for this HashSet object.
   */
  public synchronized void remove( Enumeration first, Enumeration last )
    {
    if( ( ! (first instanceof HashSetIterator) ) ||
        ( ! (last instanceof HashSetIterator) ) )
      throw new IllegalArgumentException( "Enumeration not a HashSetIterator" );

    if( ( ((HashSetIterator)first).myHashSet != this ) ||
        ( ((HashSetIterator)last).myHashSet != this ) )
      throw new IllegalArgumentException( "Enumeration not for this HashSet" );

    HashSetIterator begin = (HashSetIterator)first;
    HashSetIterator end = (HashSetIterator)last;

    while( !begin.equals( end ) )
      {
      HashSetIterator next = new HashSetIterator( begin );
      next.advance();
      remove( begin );
      begin = next;
      }
    }

  /**
   * Find an object and return its position. If the object
   * is not found, return end().
   * @param object The object to locate.
   */
  public synchronized HashSetIterator find( Object object )
    {
    int hash = object.hashCode() & 0x7FFFFFFF;

    for( HashSetNode node = buckets[ hash % length ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        return new HashSetIterator( node, this );

    return new HashSetIterator( null, this );
    }

  /**
   * Return the number of items that match a particular object.
   * Since a HashSet cannot contain duplicates, this function always
   * returns either 0 or 1.
   * @param object The object to match against.
   */
  public synchronized int count( Object object )
    {
    int hash = object.hashCode() & 0x7FFFFFFF;

    for( HashSetNode node = buckets[ hash % length ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        {
        if ( allowDups )
          {
          int n = 1;
          node = node.next;

          while( node != null && hash == node.hash && comparator.execute( object, node.object ) )
            {
            ++n;
            node = node.next;
            }

          return n;
          }
        else
          {
          return 1;
          }
        }

    return 0;
    }

  /**
   * If the object doesn't exist or duplicates are allowed, add the object and return null,
   * otherwise don't modify the set and return the matching object.
   * @param object The object to be added.
   * @exception NullPointerException If the value of the object is equal to null.
   */
  public Object add( Object object )
    {
    if( object == null )
      throw new NullPointerException();

    int hash = object.hashCode() & 0x7FFFFFFF;
    int probe = hash % length;

    // find if object already exists first
    for( HashSetNode node = buckets[ probe ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        {
        if( allowDups )
          {
          // duplicate key, add this pair to end and return success.
          HashSetNode newNode = new HashSetNode();
          newNode.object = object;
          newNode.hash = hash;
          newNode.next = node.next;
          node.next = newNode;

          if( ++size > limit )
            expand();

          return null;
          }
        else
          {
          // return the object that already exists. DO NOT add
          return node.object;
          }
       }

    // object doesn't exists, add appropriately
    HashSetNode newNode = new HashSetNode();
    newNode.object = object;
    newNode.hash = hash;
    newNode.next = buckets[ probe ];
    buckets[ probe ] = newNode;

    if( ++size > limit )
      expand();

    return null;
    }

  /**
   * Return the first object that matches the given object, or null if no match exists.
   * @param object The object to match against.
   */
  public synchronized Object get( Object object )
    {
    int hash = object.hashCode() & 0x7FFFFFFF;

    for( HashSetNode node = buckets[ hash % length ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        return node.object;

    return null;
    }

  /**
   * If the object doesn't exist, add the object and return null, otherwise replace the
   * first object that matches and return the old object.
   * @param object The object to add.
   * @exception NullPointerException If the value of the object is equal to null.
   */
  public synchronized Object put( Object object )
    {
    if( object == null )
      throw new NullPointerException();

    int hash = object.hashCode() & 0x7FFFFFFF;
    int probe = hash % length;

    // find if object already exists first
    for( HashSetNode node = buckets[ probe ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        {
        // an object matches, replace with new object and return old one.
        Object previous = node.object;
        node.object = object;
        return previous;
        }

    // object doesn't exists, add appropriately
    HashSetNode newNode = new HashSetNode();
    newNode.object = object;
    newNode.hash = hash;
    newNode.next = buckets[ probe ];
    buckets[ probe ] = newNode;

    if( ++size > limit )
      expand();

    return null;
    }

  /**
   * Return a new HashSet that contains all of my elements and all of the elements in
   * a specified HashSet.
   * @param set The HashSet to union myself with.
   */
  public synchronized HashSet union( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "union operation invalid on multisets" );

    HashSet result = new HashSet();
    InsertIterator iterator = new InsertIterator( result );
    Copying.copy( this, iterator );
    Copying.copy( set, iterator );
    return result;
    }

  /**
   * Return a new HashSet that contains the elements that are both in me and in
   * a specified set.
   * @param set The HashSet to intersect myself with.
   */
  public synchronized HashSet intersection( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "intersection operation invalid on multisets" );

    HashSet result = new HashSet();
    HashSetIterator iterator;

    // Loop through the smallest set.
    if( size >= set.size )
      {
      iterator = begin();
      }
    else
      {
      iterator = set.begin();
      set = this;
      }

    while( iterator.hasMoreElements() )
      {
      Object object = iterator.nextElement();

      if( set.count( object ) > 0 )
        result.add( object );
      }

    return result;
    }

  /**
   * Return a new HashSet that contains the elements that are in me but not in a
   * specified set.
   * @param set The HashSet to difference myself with.
   */
  public synchronized HashSet difference( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "difference operation invalid on multisets" );

    HashSet result = new HashSet();
    HashSetIterator iterator = begin();

    while( iterator.hasMoreElements() )
      {
      Object object = iterator.nextElement();

      if( set.count( object ) == 0 )
        result.add( object );
      }

    return result;
    }

  /**
   * Return a new HashSet that contains the elements that are either in me or in
   * a specified HashSet, but not both.
   * @param set The HashSet to symmetric difference myself with.
   */
  public synchronized HashSet symmetricDifference( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "symmetricDifference operation invalid on multisets" );

    HashSet result = new HashSet();
    HashSetIterator iterator = begin();

    while( iterator.hasMoreElements() )
      {
      Object object = iterator.nextElement();

      if( set.count( object ) == 0 )
        result.add( object );
      }

    iterator = set.begin();

    while( iterator.hasMoreElements() )
      {
      Object object = iterator.nextElement();

      if( count( object ) == 0 )
        result.add( object );
      }

    return result;
    }

  /**
   * Return true if every element in me is also in a specified HashSet.
   * @param set The HashSet to test against.
   */
  public synchronized boolean subsetOf( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "subsetOf operation invalid on multisets" );

    HashSetIterator iterator = begin();

    while( iterator.hasMoreElements() )
      if( set.count( iterator.nextElement() ) == 0 )
        return false;

    return true;
    }

  /**
   * Return true if every element in me is also in a specified HashSet and I'm smaller
   * than the specified HashSet.
   * @param set The HashSet to test against.
   */
  public synchronized boolean properSubsetOf( HashSet set )
    {
    if( allowDups || set.allowDups )
      throw new InvalidOperationException( "properSubsetOf operation invalid on multisets" );

    return size < set.size && subsetOf( set );
    }

  /**
   * Return a range whose first element is an iterator positioned
   * at the first occurence of a specific object and whose second element is an
   * iterator positioned immediately after the last occurence of that object.
   * Note that all objects inbetween these iterators will also match the specified
   * object. If no matching object is found, return null.
   * @param object The object whose bounds are to be found.
   */
  public synchronized Range equalRange( Object object )
    {
    int hash = object.hashCode() & 0x7FFFFFFF;

    for( HashSetNode node = buckets[ hash % length ]; node != null; node = node.next )
      if( hash == node.hash && comparator.execute( object, node.object ) )
        {
        HashSetNode begin = node;
        node = node.next;

        while( node != null && hash == node.hash && comparator.execute( object, node.object ) )
          node = node.next == null ? next( node ) : node.next;

        return new Range( new HashSetIterator( begin, this ),
                                 new HashSetIterator( node, this ) );
        }

    return null;
    }

  private HashSetNode first()
    {
    if( size > 0 )
      for( int i = 0; i < length; i++ )
        if( buckets[ i ] != null )
          return buckets[ i ];

    return null;
    }

  private HashSetNode next( HashSetNode node )
    {
    for( int i = ( node.hash % length ) + 1; i < length; i++ )
      if( buckets[ i ] != null )
        return buckets[ i ];

    return null;
    }

  private void expand()
    {
    int newLength = length * 2 + 1;
    HashSetNode[] newBuckets = new HashSetNode[ newLength ];

    for( int i = 0; i < length; i++ )
      {
      HashSetNode node = buckets[ i ];

      while( node != null )
        {
        HashSetNode current = node;
        node = node.next;
        int probe = current.hash % newLength;
        current.next = newBuckets[ probe ];
        newBuckets[ probe ] = current;
        }
      }

    buckets = newBuckets;
    length = newLength;
    limit = (int)( length * ratio );
    }
  }


final class HashSetNode
  {
  Object object;
  int hash;
  HashSetNode next;
  }