package com.thealgorithms.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;
    }
}