import java.util.Iterator;

/**
 * Simple hash-table-based dictionary class that uses prime-numbered sized tables and linear probing
 * for collision resolution.
 *
 * @author CS240 Instructors and ...
 *
 */
public class HashDictionary<K, V> implements Dictionary<K, V> {

  public static final int INITIAL_CAPACITY = 16; // must be a power of 2.
  public static final double MAX_LOAD = .5;

  Item[] table; // (Leave this non-private for testing.)
  private int size; // The number of items stored in the table.

  /**
   * HashDictionary constructor.
   */
  @SuppressWarnings("unchecked")
  public HashDictionary() {
    table = new HashDictionary.Item[INITIAL_CAPACITY];
    size = 0;
  }

  /**
   * Reset the hash table to an empty state.
   */
  @SuppressWarnings("unchecked")
  @Override
  public void clear() {
    table = new HashDictionary.Item[INITIAL_CAPACITY];
    size = 0;
  }

  /**
   * Store the provided key/value pair.
   *
   * <p>
   * If the key already exists, its value is updated (size unchanged). If the key is new, it is
   * inserted using linear probing and size increases. Resizing occurs only when adding a new key
   * would exceed MAX_LOAD.
   *
   * @param key the key to store
   * @param value the value to associate with the key
   */
  public void put(K key, V value) {

    // YOU SHOULD NOT NEED TO MODIFY THIS METHOD.

    // Start probing from the hash index
    int index = indexFor(key.hashCode(), table.length);
    int firstDeletedSlot = -1; // Track first tombstone we encounter

    // **Search for the key or an available slot.**
    // This for-loop iterates the full length of the array because that is the
    // absolute upper bound on the number of probe steps we could need to complete.
    // In practice, the loop should never iterate that many times. We could have
    // used a while loop that terminates when we find an available slot, but this
    // way a bug will result in an exception instead of an infinite loop.
    for (int i = 0; i < table.length; i++) {
      Item item = table[index];

      // There are exactly three cases when we check the next available slot:

      // -----------------------------------------------------------------------
      // #1 Empty slot found - key doesn't exist. Add it to the table.
      // -----------------------------------------------------------------------
      if (item == null) {
        // Check if we need to resize before inserting
        if ((size + 1) / ((double) table.length) > MAX_LOAD) {
          resize();
          // After resize, need to recalculate index
          put(key, value); // Recursive call handles insertion
          return;
        }

        // Insert at first deleted slot if we found one, otherwise here
        int insertIndex;
        if (firstDeletedSlot != -1) {
          insertIndex = firstDeletedSlot;
        } else {
          insertIndex = index;
        }
        table[insertIndex] = new Item(key, value);
        size++;
        return;
      }

      // -----------------------------------------------------------------------
      // #2 Deleted slot - The key may or may not exist. We need to keep
      // probing, and we need to record this spot. If it turns out that the
      // key is currently not in the table, this first tombstone is the spot
      // we should replace.
      // -----------------------------------------------------------------------
      if (item.deleted) {
        if (firstDeletedSlot == -1) {
          firstDeletedSlot = index; // Remember first tombstone
        }
        // Continue searching - key might exist later in probe sequence
      }

      // -----------------------------------------------------------------------
      // #3 The key is a match. Replace the existing value with the new value.
      // -----------------------------------------------------------------------
      else if (item.key.equals(key)) {
        // Key exists - just update value (no resize needed)
        item.value = value;
        return;
      }

      // Collision - continue probing
      index = (index + 1) & (table.length - 1);
    }

    // Table is full - should never happen with proper load factor
    throw new IllegalStateException("Hash table is full");
  }

  /**
   * Find the index of a key or return -1 if it can't be found. If removal is implemented, this will
   * skip over tombstone positions during the search.
   */
  private int findKey(K key) {

    // TODO -- THIS METHOD SHOULD BE HELPFUL FOR GET AND REMOVE.

    // IMPLEMENTATION ADVICE: All java classes (including K!) have a hashCode method
    // that returns an integer. This could be ANY integer and probably won't be a
    // valid index into your table array. The hashCode for the key must be mapped to
    // a valid index. This can be done using the **indexFor** method included at the
    // bottom of this file.
    //
    // Your code in this method should handle collisions using simple linear
    // probing.
    //
    // Don't forget -- you shouldn't be iterating over the entire table. You should
    // be able to call indexFor to get the starting index for the key. Only if you
    // encounter a collision should you need to iterate through rest of the table.

    return -1;
  }


  /**
   * Return the value associated with the provided key, or null if no such value exists.
   */
  @Override
  public V get(K key) {

    // TODO

    return null;
  }

  /**
   * Remove the provided key from the hash table and return the associated value. Returns null if
   * the key is not stored in the table.
   */
  @Override
  public V remove(K key) {

    // TODO

    return null;
  }

  /**
   * Double the size of the hash table and rehash all existing items.
   */
  private void resize() {

    // TODO

    // IMPLEMENTATION ADVICE:
    // Start by creating a new table with double the size of the old one. Do not
    // replace the old table just yet. You will need to migrate all of the items from
    // the old table to the new one.
    //
    // Do NOT just copy one array to the other. You will need to rehash each item in
    // the old table and place it in the new table. This is because the size of the
    // table has changed, and the indexFor method will now return different values for
    // the same hashCode.
    //
    // Finally, don't forget to set the new table as the current table.

  }

  @Override
  public Iterator<K> iterator() {

    // TODO
    // You will need to implement a private iterator class. Keep in mind that the user is not
    // interested in tombstones or empty buckets. They only want the actual keys. This means that
    // your iterator will need to skip over unused buckets.
    throw new UnsupportedOperationException("Unimplemented method 'iterator'");
  }

  /**
   * Return the current load factor of the table.
   */
  public double loadFactor() {

    // TODO

    return -1;
  }



  ////////////////////////////////////////////////////////////////////////
  // DO NOT MODIFY THE CODE BELOW THIS LINE

  /**
   * Return the number of items stored in the table.
   */
  public int size() {
    return size;
  }


  /**
   * Returns the index for a given hash code.
   *
   * @param hashCode the hashCode to process
   * @param length the length of your hash table
   */
  private int indexFor(int hashCode, int length) {
    return supplementalHash(hashCode) & (length - 1);
  }

  /**
   * Applies a supplemental hash function to a given hashCode, which defends against poor quality
   * hash functions. This is critical because HashMap uses power-of-two length hash tables, that
   * otherwise encounter collisions for hashCodes that do not differ in lower bits.
   */
  private int supplementalHash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
  }

  /**
   * Return a string representing the internal state of the hash table for debugging purposes.
   */
  public String debugString() {
    String result = "|";
    for (int i = 0; i < table.length; i++) {
      if (table[i] == null) {
        result += "   ";
      } else if (table[i].deleted) {
        result += " 🪦 ";
      } else {
        result += "(" + table[i].key + ": " + table[i].value + ")";
      }
      result += "|";
    }
    return result;
  }

  /**
   * Item class is a simple wrapper for key/value pairs.
   */
  class Item { // leave this non-private for testing.
    private K key;
    private V value;
    private boolean deleted; // tombstone flag

    /**
     * Create an Item object.
     */
    public Item(K key, V value) {
      this.key = key;
      this.value = value;
      this.deleted = false;
    }
  }


}



// The supplementalHash and indexFor methods are taken directly from the Java HashMap
// implementation with some modifications. That code is licensed as follows:

/*
 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved. DO NOT ALTER OR REMOVE COPYRIGHT
 * NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it under the terms of the GNU
 * General Public License version 2 only, as published by the Free Software Foundation. Sun
 * designates this particular file as subject to the "Classpath" exception as provided by Sun in the
 * LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
 * even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version 2 along with this work;
 * if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, CA 95054 USA or visit
 * www.sun.com if you need additional information or have any questions.
 */