import java.util.LinkedList;
import java.util.Queue;

public class Q3_1_3 {

    public class table<Key extends Comparable<Key>, Value> {

        private class Node {
            private Key key;
            private Value value;
            private Node next;

            public Node(Key key, Value value, Node next) {
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }

        private Node first;
        private int size;

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void put(Key key, Value value) {

            if (value == null) {
                delete(key);
                return;
            }

            if (isEmpty()) {
                first = new Node(key, value, null);
                size++;
                return;
            }

            //Check first node
            if (first.key.compareTo(key) == 0) {
                first.value = value;
                return;
            } else if (first.key.compareTo(key) > 0) {
                first = new Node(key, value, first);
                size++;
                return;
            }

            //Check all other nodes
            for(Node node = first; node != null; node = node.next) {
                if (node.next != null) {
                    if (node.next.key.compareTo(key) == 0) {
                        node.next.value = value;
                        return;
                    } else if (node.next.key.compareTo(key) > 0) {
                        Node newNode = new Node(key, value, node.next);
                        node.next = newNode;
                        size++;
                        return;
                    }
                } else {
                    Node newNode = new Node(key, value, null);
                    node.next = newNode;
                    size++;
                    return;
                }
            }
        }

        public Value get(Key key) {

            for(Node node = first; node != null; node = node.next) {
                if (node.key.compareTo(key) == 0) {
                    return node.value;
                }
            }

            return null;
        }

        public void delete(Key key) {


            if (isEmpty()) {
                return;
            }

            //Check first node
            if (first.key.compareTo(key) == 0) {
                first = first.next;
                size--;
                return;
            }

            //Check all other nodes
            for(Node node = first; node != null; node = node.next) {
                if (node.next != null && node.next.key.compareTo(key) == 0) {
                    node.next = node.next.next;
                    size--;
                    return;
                }
            }
        }

        public boolean index(Key key) {
            for(Node node = first; node != null; node = node.next) {
                if (node.key.compareTo(key) == 0) {
                    return true;
                }
            }

            return false;
        }

        public int size(Key low, Key high) {
            int size = 0;
            boolean inTheRange = false;

            for(Node node = first; node != null; node = node.next) {
                if (!inTheRange) {
                    if (node.key.compareTo(low) == 0
                            || node.key.compareTo(low) > 0) {
                        size++;
                        inTheRange = true;
                    }
                } else {
                    if (node.key.compareTo(high) == 0
                            || node.key.compareTo(high) < 0) {
                        size++;
                    } else {
                        return size;
                    }
                }
            }

            return size;
        }

        public Iterable<Key> keys(Key low, Key high) {
            Queue<Key> keys = new LinkedList<>();
            boolean inTheRange = false;

            for(Node node = first; node != null; node = node.next) {
                if (!inTheRange) {
                    if (node.key.compareTo(low) == 0
                            || node.key.compareTo(low) > 0) {
                        keys.add(node.key);
                        inTheRange = true;
                    }
                } else {
                    if (node.key.compareTo(high) == 0
                            || node.key.compareTo(high) < 0) {
                        keys.add(node.key);
                    } else {
                        return keys;
                    }
                }
            }

            return keys;
        }

        public Iterable<Key> keys() {
            Queue<Key> keys = new LinkedList<>();

            for(Node node = first; node != null; node = node.next) {
                keys.add(node.key);
            }

            return keys;
        }

    }

    public static void main(String[] args) {
        Q3_1_3 exercise3 = new Q3_1_3();
        table<Integer, String> table = exercise3.new table<>();

        //Test put() and get() and keys()
        //unsorted to show sort
        table.put(5, "Value 4");
        table.put(1, "Value 8");
        table.put(9, "Value 1");
        table.put(2, "Value 12");
        table.put(0, "Value 0");
        table.put(99, "Value 99");

        System.out.println();

        for(Integer key : table.keys()) {
            System.out.println("Key " + key + ": " + table.get(key));
        }
        System.out.println();
        //delete key 2 from the list
        System.out.println("Delete key 2");
        table.delete(2);
        for(Integer key : table.keys()) {
            System.out.println("Key " + key + ": " + table.get(key));
        }

        System.out.println();

        //index a key that does not exist, and a key that does
        System.out.println("index key 98: " + table.index(98));
        System.out.println("index key 99: " + table.index(99) );

        //check if it is empty
        System.out.println("Is empty: " + table.isEmpty() );

        //check the size of the list
        System.out.println("Size: " + table.size() );


    }

}