class SolutionHashTable {
  public Entry[] table;
  public int capacity;

  /**
   * Constructs a new HashTable.
   *
   * Capacity of the hash table can not be 0 or negative.
   *
   * @param capacity
   *     to be used as capacity of the table.
   * @throws IllegalArgumentException
   *     if the input capacity is invalid.
   */
  public SolutionHashTable(int capacity) {
    if(capacity <= 0){
      throw new IllegalArgumentException();
    }
    this.table = new Entry[capacity];
    this.capacity = capacity;
  }

  /**
   * Add a new Entry to the hash table,
   * uses linear probing to deal with collisions.
   *
   * Returns false, if the key is null or the table is full.
   *
   * @param key
   *     String representing the key of the entry.
   * @param value
   *     String representing the value of the entry.
   * @return true iff entry has been added successfully, else false.
   */
   //might be missing case for when key is already in table.
  public boolean put(String key, String value) {
    if(key == null) return false;

    int hashedKey = hash(key);
    int initHashedKey = hash(key);

    //case for hasedKey > capacity
    if(hashedKey >= capacity) return false;

    //case for no collision
    if(this.table[hashedKey] == null){
      this.table[hashedKey] = new Entry(key, value);
      return true;
    }

    //case for collision
    //going from index = hashedKey to end of array.
    while(hashedKey < capacity){
      //if there is a null index (empty), then just insert
      if(this.table[hashedKey] == null){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      //if there is a defunct, then just insert
      if(this.table[hashedKey].getKey() == null){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      //if there is an entry with the same key, replace the entry
      if(this.table[hashedKey].getKey().equals(key)){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      hashedKey++;
    }

    //going from index = 0 to initial hashedKey
    hashedKey = 0;
    while(hashedKey <= initHashedKey){
      //if there is a null index (empty), then just insert
      if(this.table[hashedKey] == null){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      //if there is a defunct, then just insert
      if(this.table[hashedKey].getKey() == null){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      //if there is an entry with the same key, replace the entry
      if(this.table[hashedKey].getKey().equals(key)){
        this.table[hashedKey] = new Entry(key, value);
        return true;
      }
      hashedKey++;
    }

    //Then the array must be full
    return false;
  }

  /**
   * Retrieve the value of the entry associated with this key.
   *
   * Returns null, if the key is null.
   *
   * @param key
   *     String representing the key of the entry to look for.
   * @return value of the entry as String iff the entry with this key is found in the hash table, else null.
   */
  public String get(String key) {
    if(key == null) return null;

    int hashedKey = hash(key);
    int initHashedKey = hash(key);
    // checking from index = hashedKey to end of array
    while(hashedKey < capacity){
      if(this.table[hashedKey] == null){
        return null;
      }
      // if index is not null, check if the key of that element in index is same as key
      if(this.table[hashedKey].getKey() != null) {
        Entry e = this.table[hashedKey];
        if(e.getKey() == null) return null;
        if(e.getKey().equals(key)){
          return e.getValue();
        }
      }
      // if we find a null index, that means the key is not in the table
      else {
        return null;
      }
      hashedKey++;
    }


    // checking from index = 0 to index = hashedKey
    hashedKey = 0;
      while(hashedKey <= initHashedKey){
      if(this.table[hashedKey] == null){
        return null;
      }
      // if index is not null, check if the key of that element in index is same as key
      if(this.table[hashedKey].getKey() != null) {
        Entry e = this.table[hashedKey];
        if(e.getKey() == null) return null;
        if(e.getKey().equals(key)){
          return e.getValue();
        }
      }
      // if we find a null index, that means the key is not in the table
      else {
        return null;
      }
      hashedKey++;
    }
    return null;
  }

  /**
   * Remove the entry associated with this key from the hash table.
   *
   * Returns false, if the key is null.
   *
   * @param key
   *     String representing the key of the entry to remove.
   * @return true iff the entry has been successfully removed, else false.
   */
  public boolean remove(String key) {
    if(key == null) return false;

    // case : key is not in the table.
    if(get(key) == null) return false;

    int hashedKey = hash(key);
    int initHashedKey = hash(key);

    while(hashedKey < capacity){
      // if index is not null, check if the key of that element in index is same as key
      if(this.table[hashedKey] != null) {
        Entry e = this.table[hashedKey];
        if(e.getKey() == null) return false;
        if(e.getKey().equals(key)){
          setDefunct(hashedKey);
          return true;
        }
        hashedKey++;
      }
    }


    // checking from index = 0 to index = hashedKey
    hashedKey = 0;
      while(hashedKey <= initHashedKey){
      // if index is not null, check if the key of that element in index is same as key
      if(this.table[hashedKey] != null) {
        Entry e = this.table[hashedKey];
        if(e.getKey() == null) return false;
        if(e.getKey().equals(key)){
          setDefunct(hashedKey);
          return true;
        }
        hashedKey++;
      }
    }
    return false;
  }

  /**
   * Takes as input an index and sets the entry in that location as defunct.
   *
   * @param index
   *     The index of the spot that is defunct.
   */
  public void setDefunct(int index) {
    this.table[index] = new Entry(null, null);
  }

  /**
   * Hashes a string representing a key.
   *
   * @param key
   *     String that needs to be hashed.
   * @return the hashcode of the string, modulo the capacity of the HashTable.
   */
  public int hash(String key) {
    return Math.abs(key.hashCode()) % capacity;
  }
}