import java.util.Random;

/**
 * 
 * @author nickgrifasi
 * @version 9/20/21
 * @param <K> generic key value
 * @param <E> generic data value
 *  Inspiration from openDSA-textbook: chapter 18.01
 *  https://canvas.vt.edu/courses/141775/assignments/1272244?module_item_id=1550563
 *  Generic SkipList data structure class. Provides support for
 *  insertion, removal, search by key, and more.
 *
 */
public class SkipList<K extends Comparable<K>, E> {
    private SkipNode<K, E> head;
    private int level;
    private int size;
    static private Random random = new Random();

    /**
     * Default constructor to create new SkipList. Initializes
     * head to a SkipNode containing <null, 1>. Level = 0 and
     * size = 0.
     */
    public SkipList() {
        head = new SkipNode<K, E>(null, 1);
        level = 0;
        size = 0;
    }

    /**
     * Private method that picks a level using a geometric distribution.
     * Useful for insertion.
     * 
     * @return int representing level
     */
    private int randomLevel() {
        int lev;
        for (lev = 0; Math.abs(random.nextInt()) % 2 == 0; lev++) {
            //left empty intentionally
        }
        return lev;
    }

    /**
     * Private method that helps adjust the headNode.
     * Useful for insertion.
     */
    private void adjustHead(int newLevel) {
        SkipNode<K, E> temp = head;
        head = new SkipNode<K, E>(null, newLevel);
        for (int i = 0; i <= level; i++) {
            head.getForward()[i] = temp.getForward()[i];
        }
        level = newLevel;
    }

    /**
     * Insertion method for SkipList. Picks randomly chosen
     * depth of the SkipList. Insertion deals with sorting
     * by utilizing KVPair.compareTo(). Increases size at
     * successful insertion.
     * @param kvpair used to insert new object based on its key
     */
    @SuppressWarnings("unchecked")
    public void insert(KVPair<K, E> kvpair) {
        int randomLevel = randomLevel();

        if (randomLevel > level) {
            adjustHead(randomLevel);
        }
        SkipNode<K, E>[] update = new SkipNode[level + 1];
        SkipNode<K, E> x = head;
        for (int i = level; i >= 0; i--) {
            while ((x.getForward()[i] != null) && (kvpair.getKey().
                    compareTo((x.getForward()[i]).getPair().getKey()) > 0)) {
                x = x.getForward()[i];
            }

            update[i] = x;
        }

        x = new SkipNode<K, E>(kvpair, randomLevel);

        for (int i = 0; i <= randomLevel; i++) {
            x.getForward()[i] = update[i].getForward()[i];
            update[i].getForward()[i] = x;
        }

        size++;

    }

    /**
     * Search method for SkipList
     * @return SkipNode<K, E> returns SkipNode that
     * is being searched for.
     * @param key is a generic object to be searched
     */
    public SkipNode<K, E> search(K key) {
        SkipNode<K, E> x = head;

        for (int i = level; i >= 0; i--) {
            while ((x.getForward()[i] != null) && (x.getForward()[i].key().
                    compareTo(key) < 0)) {
                x = x.getForward()[i];
            }
        }

        x = x.getForward()[0];
        if ((x != null) && (x.key().compareTo(key) == 0)) {
            return x;
        }

        else {
            return null;
        }
    }

    /**
     * Dump method prints out a neatly
     * formatted string of every element in the SkipList
     * to System.out
     */
    public void dump() {
        SkipNode<K, E> x = head;
        String output = "temp";
        while (x != null) {
            if (x.element() == null) {
                output = "null";
            }

            else {
                output = x.getPair().toString();
            }

            System.out.println("Node has depth " + x.getLevel()
                + ", Value (" + output + ")");

            x = x.getForward()[0];
        }

        System.out.println("SkipList size is: " + size);
    }

    /**
     *
     * @return generic object that is being removed from SkipList
     * @param name is generic object to help identify what is
     * to be removed from the SkipList
     * 
     * Remove method that finds the key (name) and deallocates
     * the pointers at that key. Has to navigate through
     * the entire skipList, not just the first level.
     */
    public E removeName(K name) {
        SkipNode<K, E> x = head;
        E removedElement = null;

        for (int i = level; i >= 0; i--) {
            while ((x.getForward()[i] != null)) {
                if (x.getForward()[i].key().compareTo(name) == 0) {
                    removedElement = x.getForward()[i].element();
                    x.getForward()[i] = x.getForward()[i].getForward()[i];
                    break;
                }

                if ((x.getForward()[i].key().compareTo(name) > 0)) {
                    break;
                }

                x = x.getForward()[i];

            }
        }

        if (removedElement != null) {
            size = size - 1;
        }

        return removedElement;
    }

    /**
     * 
     * @param data is generic object to help identify what is
     * to be removed from the SkipList
     * @return generic object that is being removed from SkipList
     * Remove method that finds an equivalent data value as the
     * parameter, and then deallocates it using removeName().
     * Only has to navigate through first level.
     */
    public E removeData(E data) {
        SkipNode<K, E> x = head;

        while (x.getForward()[0] != null) {
            if (x.getForward()[0].element().equals(data)) {
                return removeName(x.getForward()[0].key());
            }

            x = x.getForward()[0];
        }
        return null;
    }

    /**
     * getter method that returns the headNode of the SkipList
     * @return returns SkipNode<K, E>, the head of the SkipList
     */
    public SkipNode<K, E> getNode() {
        return head;
    }

    /**
     * SkipList method created with Rectangles in mind.
     * Utilizes Rectangle.findIntersection() to find intersections
     * between SkipList items. Prints to System.out
     */
    public void intersections() {
        SkipNode<K, E> x = head.getForward()[0];

        for (int i = 0; i < size; i++) {
            SkipNode<K, E> temp = head.getForward()[0];

            for (int k = 0; k < size; k++) {
                if (i != k && ((Rectangle) x.element())
                        .findIntersection(((Rectangle)
                                temp.element()))) {
                    System.out.println("(" + x.getPair().toString() + " " 
                                + "| " + temp.getPair().toString() + ")");
                }
                
                temp = temp.getForward()[0];
            }

            x = x.getForward()[0];
        }
    }

    /**
     * @param rectangle is the rectangle to be analyzed for
     * the regionsearch.
     * 
     * SkipList method created with Rectangles in mind.
     * Utilizes Rectangle.findIntersection() to see if
     * there is an intersection between SkipList rectangles
     * and the given parameter rectangle.
     */
    public void regionsearch(Rectangle rectangle) {
        SkipNode<K, E> x = head.getForward()[0];
        for (int i = 0; i < size; i++) {
            if (((Rectangle) x.element()).findIntersection(rectangle)) {
                System.out.println("(" + x.getPair().toString() + ")");
            }
            x = x.getForward()[0];
        }
    }
}