// File: HashSet.java

// Cay Horstmann program that implements a Hash Set using a Hash Table
// (i.e. an array of Nodes).  
// Internal documentation added

import java.util.Iterator ;
import java.util.NoSuchElementException ;

/**
   A hash set stores an unordered collection of objects, using
   a hash table.
*/
public class HashSet
{
   // instance variables
   private Node[] buckets ;	// array of Node object variables
   private int size ;		// number of objects in the set
  
   /**
      Constructs a hash table.
      @param bucketsLength the length of the buckets array
   */
   public HashSet(int bucketsLength)
   {
      buckets = new Node[bucketsLength] ;
      size = 0 ;		// no objects added yet
   }

   /**
      Tests for set membership.
      @param x an object
      @return true if x is an element of this set
   */
   public boolean contains(Object x)
   {
      // compute reduced hash code
      int h = Math.abs(x.hashCode()) % buckets.length ;
      
      Node current = buckets[h] ;	// element where object would be
      while (current != null)		// while more nodes on list...
      {
         if (current.data.equals(x))	// object found, we're done
            return true ;
         current = current.next ;	// otherwise, check next node		
      }
      return false ;			// object was not found
   }

   /**
      Adds an object to this set.
      @param x the object to be added
      @return true if x is a new object, false if x is already in the set
   */
   public boolean add(Object x)
   {
      // if x already in set, we're done
      if (this.contains(x))
      	return false ;
      
      // here if x not in set
      
      // compute reduced hash code
      int h = Math.abs(x.hashCode()) % buckets.length ;
      
      // create new Node containing object and place it at head of list
      Node newNode = new Node() ;
      newNode.data = x ;
      newNode.next = buckets[h] ;       // points to 1st node in bucket or null
      buckets[h] = newNode ;            // array element points to new node
      size++ ;
      return true ;
   }

   /**
      Removes an object from this set.
      @param x an object
      @return true if x was removed from this set, false
      if x was not an element of this set
   */
   public boolean remove(Object x)
   {
      // compute reduced hash code
      int h = Math.abs(x.hashCode()) % buckets.length ;
      
      Node current = buckets[h] ;	// element that should contain object
      Node previous = null ;		// the "trailing pointer"
      while (current != null)		// while more nodes on list...
      {
         if (current.data.equals(x)) 	// if current node has object...
         {
            if (previous == null) 		// if first object on list...
               buckets[h] = current.next ;	// ...adjust "head" pointer
            else 				// if not first object...
               previous.next = current.next ;	// ..."delete after" previous
            size-- ;
            return true ;               // we're done
         }
         // here if current node does not contain object - advance to next node
         previous = current ;
         current = current.next ;
      }
      // here if object not on list
      return false ;			
   }
   
  /**
      Gets the number of elements in this set.
      @return the number of elements
   */
   public int size()
   {
      return size;
   }
   
   /**
      Returns an iterator that traverses the elements of this set.
   */
   public Iterator iterator()
   {
      return new HashSetIterator() ;	// private inner class (below)
   }

   class Node   // inner class implements a Node with "friendly" access
   {
      public Object data ;
      public Node next ;
   }

   // inner class implements an iterator for the hash set   
   class HashSetIterator implements Iterator
   {
      // instance vars 
      private int bucket ;       // index of current element
      private Node current ;     // points to current node in current bucket
      
      /**
         Creates a hash set iterator that will point to the 
         first element of the hash set after advancing (i.e. after
         the first call to method next())
      */
      public HashSetIterator()
      {
         current = null;
         bucket = -1;
      }
      
      /**
       * Is there at least one more object past the current iterator position
       * in the set?
       * @return true if iterator is NOT pointing to the last object in the 
       * set; otherwise returns false
       */
      public boolean hasNext()
      {
         // return true if iterator is pointing at an object which is not
         // the last object in the current bucket...
         if (current != null && current.next != null)
            return true ;
            
         // otherwise, iterator has either just been created or is at 
         // the last node of the current bucket.  So see if there is a 
         // non-empty bucket at some element following the current one
         
         for (int b = bucket + 1 ; b < buckets.length ; b++)
         {         
            if (buckets[b] != null)     // found non-empty bucket...
              return true ;             // ...we'e done
         }
         return false ;                 // all subsequent buckets are empty!
      }
       
      /**
       * Move iterator to the next Object in the set and return it.
       * WARNING: throws exception if no more Objects in set, so make sure 
       * hasNext() returns true before calling this method!
       * @return the Object following the one currently pointed to by iterator
       */
      public Object next()
      {
         // if current is pointing to an object and that object is not the 
         // last object in current bucket...
         if (current != null && current.next != null) 
         {
            current = current.next ;    // move to next object in bucket
         }
         else  // current is null or pointing to last node in bucket
         {
            do  // move to next bucket
            {
               bucket++ ; 
               if (bucket == buckets.length) // no more buckets!
               {
                  throw new NoSuchElementException() ;  // hasNext, anyone?
               }
               current = buckets[bucket] ;  // first node of next bucket
            }
            while (current == null) ;
         }
         return current.data ;              // object at new iterator position
      }

      /** 
       * Remove object at current iterator position.
       * 
       * Note: We don't need to call this method since HashSet has a remove()
       * method, but it is required to implement the Iterator interface
       */      
      public void remove()
      {
         throw new UnsupportedOperationException();
      }
   }
}