package DataStructures.HashMap.Hashing;

public class HashMap {
 private int hsize;
 private LinkedList[] buckets;

 public HashMap(int hsize) {
 buckets = new LinkedList[hsize];
 for (int i = 0; i < hsize; i++) {
 buckets[i] = new LinkedList();
 // Java requires explicit initialisaton of each object
 }
 this.hsize = hsize;
 }

 public int hashing(int key) {
 int hash = key % hsize;
 if (hash < 0) hash += hsize;
 return hash;
 }

 public void insertHash(int key) {
 int hash = hashing(key);
 buckets[hash].insert(key);
 }

 public void deleteHash(int key) {
 int hash = hashing(key);

 buckets[hash].delete(key);
 }

 public void displayHashtable() {
 for (int i = 0; i < hsize; i++) {
 System.out.printf("Bucket %d :", i);
 System.out.println(buckets[i].display());
 }
 }

 public static class LinkedList {
 private Node first;

 public LinkedList() {
 first = null;
 }

 public void insert(int key) {
 if (isEmpty()) {
 first = new Node(key);
 return;
 }

 Node temp = findEnd(first);
 temp.setNext(new Node(key));
 }

 private Node findEnd(Node n) {
 if (n.getNext() == null) {
 return n;
 } else {
 return findEnd(n.getNext());
 }
 }

 public Node findKey(int key) {
 if (!isEmpty()) {
 return findKey(first, key);
 } else {
 System.out.println("List is empty");
 return null;
 }
 }

 private Node findKey(Node n, int key) {
 if (n.getKey() == key) {
 return n;
 } else if (n.getNext() == null) {
 System.out.println("Key not found");
 return null;
 } else {
 return findKey(n.getNext(), key);
 }
 }

 public void delete(int key) {
 if (!isEmpty()) {
 if (first.getKey() == key) {
 first = null;
 } else {
 delete(first, key);
 }
 } else {
 System.out.println("List is empty");
 }
 }

 private void delete(Node n, int key) {
 if (n.getNext().getKey() == key) {
 if (n.getNext().getNext() == null) {
 n.setNext(null);
 } else {
 n.setNext(n.getNext().getNext());
 }
 }
 }

 public String display() {
 return display(first);
 }

 private String display(Node n) {
 if (n == null) {
 return "null";
 } else {
 return n.getKey() + "->" + display(n.getNext());
 }
 }

 public boolean isEmpty() {
 return first == null;
 }
 }

 public static class Node {
 private Node next;
 private int key;

 public Node(int key) {
 next = null;
 this.key = key;
 }

 public Node getNext() {
 return next;
 }

 public int getKey() {
 return key;
 }

 public void setNext(Node next) {
 this.next = next;
 }
 }
}