package map;

import java.util.List;
import container.*;
import java.math.BigInteger;

public class HashDictionary implements Dictionary {

  protected EqualityTester eqtest;   
  protected int size;        // total number of items in all buckets
  protected List[] buckets;  // number of buckets is buckets.length

  protected static final float maxLoadFactor = 0.9f;

  // ----------- CONSTRUCTORS ------------
  
  /** comment ... */
  public HashDictionary() {    // version with default values
    // start with a small capacity to make sure that rehashing gets tested
    this(new DefaultEqualityTester(), 4);  
  }

  /** comment ... */
  public HashDictionary(EqualityTester eqtest, int initialCapacity) {
    ...
  }

  // ---------- METHODS OF DICTIONARY INTERFACE -----------
  // (see the dictionary interface for documentation -- 
  // duplicate documentation is hard to maintain, like duplicate code)

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return (size == 0);
  }

  public Entry insert(Object k, Object v) throws InvalidKeyException {
    ...
  }

  public Entry find(Object k) throws InvalidKeyException {
    ...
  }

  public Entry remove(Object k) throws InvalidKeyException {
    ...
  }

  public Iterator removeAll(Object k) throws InvalidKeyException {
    ...	
  }

  public Iterator findAll(Object k) throws InvalidKeyException {
    return new KeyedListIterator(...);
  }

  public Iterator entries() {
    return new EntryIterator();
  }

  public Object replaceValue(Entry e, Object v) {
    ...
  }

  // ----------- HELPER METHODS -------------

  /** Throws an exception if this key won't work for this dictionary.
   */
  protected void checkKey(Object key) throws InvalidKeyException {
    // Warning: The book's implementation of this one makes no sense.
    // Better to look at what you did in HeapPriorityQueue.
    ...
  }

  /** Throws an exception if we detect a problem with this entry,
   * e.g., it couldn't be an entry in this dictionary.
   */
  protected void checkEntry(Entry e) throws InvalidEntryException {
    // Perhaps similar to what you did in HeapAdaptablePriorityQueue.
    ...
  }

  rehashing ...
  bucketOf ...
  others? ...
  
  // -------------- UTILITY METHODS -------------

  /** Returns the first probably-prime number that is >= i. */
  static private int nextProbablePrime(int i) {

    // while i definitely isn't a prime, keep adding 1
    while (!BigInteger.valueOf(i).isProbablePrime(20))  
      i++;  

    // we quit the loop, so isProbablePrime must have thought i was probably a prime 
    //   (isProbablePrime(20) has error probability of 
    //   1 in 2^20, i.e., about 1 in a million)
    return i;
  }
 
  // ----------- NESTED CLASS  -------------

  protected static class MyEntry implements Entry {
    protected Object key, value;
    public MyEntry(Object k, Object v) { key = k; value = v; }
    public Object key() { return key; }
    public Object value() { return value; }
    protected Object replaceValue(Object v) { Object temp=value; value=v; return temp; }
    public String toString() { return key()+"/"+value(); }
  }

  // ----------- NESTED CLASS  -------------

  protected static class DefaultEqualityTester implements EqualityTester {
    ...
  }

  // ----------- NESTED CLASS  -------------

  /** An iterator over all the entries in a particular list 
   * that have a particular key. */
  protected class KeyedListIterator implements Iterator {
    private Iterator iter;  // iterates over ALL entries in the list
    private Object key;     // we will return all elements of the list that have this key
    private Object next;    // next element to return, or null if we're all done

    public KeyedListIterator(List l, Object k) {
      iter = l.iterator();  
      key = k;
      setNext();   // initializes next
    }

    public boolean hasNext() {
      ...
    }

    public Object next() {
      ...
    }
	
    public void remove() {
      // We'd have to do a bit of redesign to support this.
      // We can't simply call iter.remove(), because that 
      // would remove the last thing that iter returned
      // when we called iter.next() inside setNext(),
      // rather than the last thing that *we* returned.
      throw new UnsupportedOperationException();
    }

    private void setNext() {
      ...
    }
  }

  // ----------- NESTED CLASS  -------------

  /** An iterator over ALL the entries in the hash table.
   * Since this nested class is NOT declared static, an 
   * instance of EntryIterator is able to access the fields
   * and methods of the HashDictionary instance that created it,
   * such as the buckets[] array.
   */
  protected class EntryIterator implements Iterator {
    private int i;         // the bucket we're currently looking at
    private Iterator iter; // an iterator over entries in bucket i.
    int remaining;         // total number of entries left to iterate over; 
                           //   makes it easy to write hasNext() and remove()

    public EntryIterator() {
      ...
    }

    public boolean hasNext() {
      ...
    }

    public Object next() {
      ...
    }

    public void remove() {  // can be called after next()
      ...  (easy to implement if you choose)
    }
  }

  // -------------- TEST METHOD -------------

  public static void main(String[] args) {
    if (args.length==0)
      args = new String[] {"apple", "banana", "cherry", "date", 
			   "elderberry", "fig", "grape", "huckleberry", 
			   "illama", "jackfruit", "kiwi", "lime",
			   "mango", "nectarine", "orange", "papaya", 
			   "quince", "raspberry", "starfruit", "tamarind",
			   "uglifruit", "virtual", "watermelon", "xylem", 
			   "yam", "zucchini"};

    Dictionary d = new HashDictionary();
    Iterator iter;

    System.out.println("Adding each string to the dictionary with "
		       +"3 different elements (positive, zero, negative)");
    for (int i=0; i < args.length; i++)
      d.insert(args[i], new Integer(i));
    for (int i=0; i < args.length; i++)
      d.insert(args[i], new Integer(0));
    for (int i=0; i < args.length; i++)
      d.insert(args[i], new Integer(-i));

    System.out.println("Adding extra element for first key "+args[0]
		       +" (will make things more interesting later).");
    d.insert(args[0], "Extra element for first key");  

    System.out.println("Removing all elements for last key "+args[args.length-1]
		       +" (to test removeAll()).  Elements removed:");
    iter = d.removeAll(args[args.length-1]);
    while (iter.hasNext()) 
      System.out.println("   "+iter.next());

    // Keep looping until we're all empty.
    while (!d.isEmpty()) {
      System.out.println("======================================================================");
      System.out.println("------ Printing all "+d.size()+" entries -------");
      System.out.println("------ Hopefully you'll see a bucket with multiple keys -------");
      iter = d.entries();
      while (iter.hasNext()) {
	Entry e = (Entry) iter.next();
	System.out.println("Entry "+e+" in bucket "
			   +((HashDictionary)d).bucketOf(e.key()));  // private method
      }

      System.out.println("------- Messing around with each key's entries --------");
      for (int i=0; i < args.length; i++) {
	Entry e = d.find(args[i]);     
	System.out.println(args[i]);
	if (e != null && e.value() instanceof Integer) {
          System.out.println("\tIncrementing an entry "+e);
	  int j = ((Integer)e.value()).intValue();
	  d.replaceValue(e, new Integer(j+1));
	} 

	System.out.print("\tAll entries: ");
	iter = d.findAll(args[i]);
	while (iter.hasNext())
	  System.out.print(" "+(Entry)iter.next());
	System.out.println();

	System.out.println("\tRemoving an entry: "+d.remove(args[i]));
      }
    }        
  }
}