package djw1005;

import java.util.Iterator;
import java.util.ArrayList;

public class FibHeap<T extends FibHeap.Storable<T>> {

    // The main FibHeap routines all operate directly on objects,
    //   push(x), decreaseKey(x), x = popmin()
    // Here x is meant to be a native object for the problem domain, e.g. a Vertex in a graph.
    // For this to work, x has to provide "storage" to allow FibHeap to store the pointers it needs.
    // We can achieve this by requiring Vertex to implement Storable.

    interface Storable<T> {
        Node<T> asFibNode();
        double key();
    }
    public static class Node<T> {
        private int degree = 0;
        private boolean isLoser = false;
        private T parent = null;
        private T child = null;
        private T prevSibling = null;
        private T nextSibling = null;
        private double key = Double.POSITIVE_INFINITY;
        private boolean inHeap = false; // to support FibHeap.contains(x)
    }


    T minroot = null;

    void push(T value) {
        value.asFibNode().key = value.key();
        value.asFibNode().inHeap = true;
        if (minroot == null) {
            value.asFibNode().prevSibling = value;
            value.asFibNode().nextSibling = value;
            minroot = value;
        }
        else {
            addSibling(minroot, value, value);
            if (value.key() < minroot.key())
                minroot = value;
        }
    };

    void decreaseKey(T value) {
        T n = value;
        n.asFibNode().key = value.key();
        if (n.asFibNode().parent==null || n.asFibNode().key >= n.asFibNode().parent.asFibNode().key) return;
        while (n.asFibNode().parent != null) {
            makeOrphan(n);
            T u = n.asFibNode().parent;
            n.asFibNode().parent = null;
            n.asFibNode().isLoser = false;
            addSibling(minroot, n, n);
            if (n.asFibNode().key < minroot.asFibNode().key) minroot = n;
            if (u.asFibNode().parent == null) break;
            if (!u.asFibNode().isLoser) { u.asFibNode().isLoser=true; break; }
            n = u;
        }
    }

    T popmin() {
        if (minroot == null)
            throw new IndexOutOfBoundsException("Pop from empty heap");
        T res = minroot;
        T u = minroot.asFibNode().prevSibling;
        T v = minroot.asFibNode().nextSibling;
        // Let u -- minroot -- v
        // If minroot is the only node in the heap, nothing much to do.
        if (u == minroot && minroot.asFibNode().child==null) {
            minroot = null;
            return res;
        }
        // Else, splice out minroot and promote any children
        if (minroot.asFibNode().child != null)
            for (T n : siblings(minroot.asFibNode().child)) {
                n.asFibNode().parent = null;
                n.asFibNode().isLoser = false;
            }
        if (u == minroot) // i.e., if this is the only tree in the rootlist
            minroot = minroot.asFibNode().child;
        else {
            T child = minroot.asFibNode().child;
            u.asFibNode().nextSibling = v;
            v.asFibNode().prevSibling = u;
            if (child != null) addSibling(u, child, child.asFibNode().prevSibling);
            minroot = u;
        }
        // Merge any trees of equal degree
        ArrayList<T> rootArray = new ArrayList<T>(10);
        for (T t : siblings(minroot)) {
            t.asFibNode().prevSibling = t;
            t.asFibNode().nextSibling = t;
            T x = t;
            while (x.asFibNode().degree <= rootArray.size()-1 && rootArray.get(x.asFibNode().degree) != null) {
                u = rootArray.get(x.asFibNode().degree);
                rootArray.set(x.asFibNode().degree, null);
                x = merge(x, u);
            }
            rootArray.ensureCapacity(x.asFibNode().degree + 1);
            while (x.asFibNode().degree > rootArray.size()-1) rootArray.add(null);
            rootArray.set(x.asFibNode().degree, x);
        }
        // Put everything back into a circular rootlist
        T head = null;
        T tail = null;
        for (T t : rootArray) {
            if (t == null) continue;
            if (head == null) {
                head = t;
                tail = t;
            }
            else {
                tail.asFibNode().nextSibling = t;
                t.asFibNode().prevSibling = tail;
                tail = t;
            }
            if (t.asFibNode().key <= minroot.asFibNode().key)
                minroot = t;
        }
        head.asFibNode().prevSibling = tail;
        tail.asFibNode().nextSibling = head;
        // All done!
        res.asFibNode().inHeap = false;
        return res;
    }

    boolean isEmpty() { return (minroot == null); }

    boolean contains(T x) { return x.asFibNode().inHeap; }

    //------------------------------------------------------
    // Assorted utility methods

    private void addSibling(T item, T sib1, T sib2) {
        T next = item.asFibNode().nextSibling;
        item.asFibNode().nextSibling = sib1;
        sib1.asFibNode().prevSibling = item;
        sib2.asFibNode().nextSibling = next;
        next.asFibNode().prevSibling = sib2;
    }

    private void makeOrphan(T item) {
        Node<T> n = item.asFibNode();
        Node<T> p = n.parent.asFibNode();
        T u = n.prevSibling;
        T v = n.nextSibling;
        if (u == item) {
            p.child = null;
            p.degree = 0;
        }
        else {
            if (p.child == item) p.child = v;
            p.degree--;
            u.asFibNode().nextSibling = v;
            v.asFibNode().prevSibling = u;
        }
    }

    private T merge(T x, T y) {
        boolean isXRoot = x.asFibNode().key <= y.asFibNode().key;
        T parent = isXRoot ? x : y;
        T child =  isXRoot ? y : x;
        parent.asFibNode().degree++;
        child.asFibNode().parent = parent;
        if (parent.asFibNode().child == null)
            parent.asFibNode().child = child;
        else
            addSibling(parent.asFibNode().child, child, child);
        return parent;
    }

    // Iterating over the siblings of a node
    private Siblings siblings(T item) { return new Siblings(item); }
    private class Siblings implements Iterable<T> {
        private T start;
        Siblings(T item) { start=item; }
        public Iterator<T> iterator() { return new SiblingsIterator(); }
        private class SiblingsIterator implements Iterator<T> {
            private T cursor;
            private T nextItem = null;
            private boolean done = false;
            SiblingsIterator() { cursor = Siblings.this.start; }
            public boolean hasNext() { return !done; }
            public T next() {
                if (nextItem == null) nextItem = cursor.asFibNode().nextSibling;
                T res = cursor;
                cursor = nextItem;
                nextItem = nextItem.asFibNode().nextSibling;
                done = (cursor == Siblings.this.start);
                return res;
            }
        }
    }

    //------------------------------------------------------
    // OPTIONAL: pretty printing, to produce output that looks like lecture notes

    @Override
    public String toString() {
        if (minroot == null)
            return "<empty heap>";
        ArrayList<String> res = new ArrayList<String>();
        res.add(".");
        for (T t : siblings(minroot)) {
            String childStr = nodeToString(t);
            String[] lines = childStr.split("\\r?\\n");
            for (String line : lines)
                res.add("|" + line);
        }
        res.add("'");
        return String.join("\n", res);
    }

    private String nodeToString(T item) {
        Node<T> n = item.asFibNode();
        String selfStr = item.toString() + "(" + item.asFibNode().key + ")";
        if (n.isLoser) selfStr = "{" + selfStr + "}";
        if (n.child == null) return selfStr;
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String[]> children = new ArrayList<String[]>();
        for (T child : siblings(n.child)) {
            String childStr = nodeToString(child);
            String[] lines = childStr.split("\\r?\\n");
            children.add(lines);
        }
        int imax = children.size() - 1;
        for (int i=0; i<children.size(); i++) {
            int jmax = children.get(i).length - 1;
            for (int j=0; j<children.get(i).length; j++) {
                char pipe = 'X';
                if (j>0 && i==imax) pipe = ' ';
                else if (j>0) pipe = '|';
                else if (imax==0) pipe = '-';
                else if (i<imax) pipe = '+';
                else pipe = '\\';
                String line = selfStr + pipe + children.get(i)[j];
                res.add(line);
                if (i==0 && j==0) selfStr = selfStr.replaceAll(".", " ");
            }
        }
        return String.join("\n", res);
    }
}