package DataStructures.HashMap.Hashing;

import java.util.*;

/**
 * This class is an implementation of a hash table using linear probing It uses a dynamic array to
 * lengthen the size of the hash table when load factor > .7
 */
public class HashMapLinearProbing {
 private int hsize; // size of the hash table
 private Integer[] buckets; // array representing the table
 private Integer AVAILABLE;
 private int size; // amount of elements in the hash table

 /**
 * Constructor initializes buckets array, hsize, and creates dummy object for AVAILABLE
 *
 * @param hsize the desired size of the hash map
 */
 public HashMapLinearProbing(int hsize) {
 this.buckets = new Integer[hsize];
 this.hsize = hsize;
 this.AVAILABLE = Integer.MIN_VALUE;
 this.size = 0;
 }

 /**
 * The Hash Function takes a given key and finds an index based on its data
 *
 * @param key the desired key to be converted
 * @return int an index corresponding to the key
 */
 public int hashing(int key) {
 int hash = key % hsize;
 if (hash < 0) {
 hash += hsize;
 }
 return hash;
 }

 /**
 * inserts the key into the hash map by wrapping it as an Integer object
 *
 * @param key the desired key to be inserted in the hash map
 */
 public void insertHash(int key) {
 Integer wrappedInt = key;
 int hash = hashing(key);

 if (isFull()) {
 System.out.println("Hash table is full");
 return;
 }

 for (int i = 0; i < hsize; i++) {
 if (buckets[hash] == null || buckets[hash] == AVAILABLE) {
 buckets[hash] = wrappedInt;
 size++;
 return;
 }

 if (hash + 1 < hsize) {
 hash++;
 } else {
 hash = 0;
 }
 }
 }

 /**
 * deletes a key from the hash map and adds an available placeholder
 *
 * @param key the desired key to be deleted
 */
 public void deleteHash(int key) {
 Integer wrappedInt = key;
 int hash = hashing(key);

 if (isEmpty()) {
 System.out.println("Table is empty");
 return;
 }

 for (int i = 0; i < hsize; i++) {
 if (buckets[hash] != null && buckets[hash].equals(wrappedInt)) {
 buckets[hash] = AVAILABLE;
 size--;
 return;
 }

 if (hash + 1 < hsize) {
 hash++;
 } else {
 hash = 0;
 }
 }
 System.out.println("Key " + key + " not found");
 }

 /** Displays the hash table line by line */
 public void displayHashtable() {
 for (int i = 0; i < hsize; i++) {
 if (buckets[i] == null || buckets[i] == AVAILABLE) {
 System.out.println("Bucket " + i + ": Empty");
 } else {
 System.out.println("Bucket " + i + ": " + buckets[i].toString());
 }
 }
 }

 /**
 * Finds the index of location based on an inputed key
 *
 * @param key the desired key to be found
 * @return int the index where the key is located
 */
 public int findHash(int key) {
 Integer wrappedInt = key;
 int hash = hashing(key);

 if (isEmpty()) {
 System.out.println("Table is empty");
 return -1;
 }

 for (int i = 0; i < hsize; i++) {
 try {
 if (buckets[hash].equals(wrappedInt)) {
 buckets[hash] = AVAILABLE;
 return hash;
 }
 } catch (Exception E) {
 }

 if (hash + 1 < hsize) {
 hash++;
 } else {
 hash = 0;
 }
 }
 System.out.println("Key " + key + " not found");
 return -1;
 }

 private void lengthenTable() {
 buckets = Arrays.copyOf(buckets, hsize * 2);
 hsize *= 2;
 System.out.println("Table size is now: " + hsize);
 }

 /**
 * Checks the load factor of the hash table if greater than .7, automatically lengthens table to
 * prevent further collisions
 */
 public void checkLoadFactor() {
 double factor = (double) size / hsize;
 if (factor > .7) {
 System.out.println("Load factor is " + factor + ", lengthening table");
 lengthenTable();
 } else {
 System.out.println("Load factor is " + factor);
 }
 }

 /**
 * isFull returns true if the hash map is full and false if not full
 *
 * @return boolean is Empty
 */
 public boolean isFull() {
 boolean response = true;
 for (int i = 0; i < hsize; i++) {
 if (buckets[i] == null || buckets[i] == AVAILABLE) {
 response = false;
 break;
 }
 }
 return response;
 }

 /**
 * isEmpty returns true if the hash map is empty and false if not empty
 *
 * @return boolean is Empty
 */
 public boolean isEmpty() {
 boolean response = true;
 for (int i = 0; i < hsize; i++) {
 if (buckets[i] != null) {
 response = false;
 break;
 }
 }
 return response;
 }
}