package alda.dheap;

public class DHeap<AnyType extends Comparable<? super AnyType>> {

    /**
     * Construct the binary heap.
     */
    int children; //Number of children allowed (d)
    private static final int DEFAULT_CAPACITY = 10;
    private int currentSize;      // Number of elements in heap
    private AnyType[] array; // The heap array

    public DHeap() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Construct the binary heap.
     *
     * @param capacity the capacity of the binary heap.
     */
//    public DHeap( int capacity )
//    {
//        currentSize = 0;
//        array = (AnyType[]) new Comparable[ capacity + 1 ];
//    }
    public DHeap(int d) {
        if (d > 1) {
            this.children = d;
        } else {
            throw new IllegalArgumentException();
        }
        array = (AnyType[]) new Comparable[d];
    }

    /**
     * Construct the binary heap given an array of items.
     */
    public DHeap(AnyType[] items) {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];

        int i = 1;
        for (AnyType item : items) {
            array[ i++] = item;
        }
        buildHeap();
    }

    /**
     * Insert into the priority queue, maintaining heap order. Duplicates are
     * allowed.
     *
     * @param x the item to insert.
     */
    //om mindre än parent perculate annars lägg till som child
    //lägg till children tills children= max nr av children i ett subträd

    public void insert(AnyType x) {

        if (currentSize == array.length - 1) {
            enlargeArray(array.length * children+1);


        }
        // Percolate up
        //currentSize++ OCH hole = currentSize+1
        int hole = ++currentSize;
        for (array[ 0] = x; hole >= 1 && x.compareTo(array[ parentIndex(hole)]) < 0; hole = parentIndex(hole)) {
                //System.out.println("current hole" + hole);
        	System.out.println("HOLE:"+hole);
            //System.out.println("divided by" + (parentIndex(hole)));
            //System.out.println("is" + (hole / parentIndex(hole)));
//            System.out.println(x.compareTo(array[ parentIndex(hole)]));
            array[ hole] = array[ parentIndex(hole)];
        }
        array[ hole] = x;

    }

    private void enlargeArray(int newSize) {

        AnyType[] old = array;
        array = (AnyType[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[ i] = old[ i];
        }

    }
//    private void decreaseArray(int newSize) {
//    	System.out.println("h"+array.length);
//    	System.out.println("h"+newSize);
//        AnyType[] old = array;
//        array = (AnyType[]) new Comparable[newSize];
//        for (int i = 0; i < old.length&&i<array.length; i++) {
//            array[ i] = old[ i];
//        }
//        System.out.println("h"+array.length);
//    }

    /**
     * Find the smallest item in the priority queue.
     *
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType findMin() {
        if (isEmpty()) {
            throw new UnderflowException();
        }
        return array[ 1];
    }

    /**
     * Remove the smallest item from the priority queue.
     *
     * @return the smallest item, or throw an UnderflowException if empty.
     */
    public AnyType deleteMin() {
        if (isEmpty()) {
            throw new UnderflowException();
        }

        AnyType minItem = findMin();
//        System.out.println("nowsize" + size());
        array[1] = array[ currentSize];
        array[currentSize] = null;
        currentSize--;
//        System.out.println("aftersize" + size());
        percolateDown(1);


        return minItem;
    }

    /**
     * Establish heap order property from an arbitrary arrangement of items.
     * Runs in linear time.
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    /**
     * Test if the priority queue is logically empty.
     *
     * @return true if empty, false otherwise.
     */
    public int size() {
        return currentSize;
    }

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

    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty() {
        currentSize = 0;
    }

    /**
     * Internal method to percolate down in the heap.
     *
     * @param hole the index at which the percolate begins.
     */
    private void percolateDown(int hole) {
        int child = 0;
        AnyType tmp = array[ hole];
//        System.out.println("tmp"+tmp);

        // firstchildindex istället för hole * children då hole * 2 är 2i, alltså formeln för vänstra barnet i en binär heap
        for (; firstChildIndex(hole) <= currentSize; hole = child) {
//            System.out.println("new iter");
            child = firstChildIndex(hole)+1;
            //eftersom det är många barn måste vi ha en nestlad for loop, i d=2 är ju ett barn alltid större eller
            //mindre än ett annat, i vårt fall måste vi hitta det minsta barnet (som kan vara d många)
            int smallestChild = firstChildIndex(hole);
            for (int i = 0; i < children-1; i++) {
                if (array[child]!=null&& array[smallestChild].compareTo(array[ child]) < 0) {
//                    System.out.println(" value of child+1 (" + array[child + 1] + ") is less than value of child (" + array[child] + ")");
                    child++;
                } else {
                	smallestChild=child;
                }
            }
            child=smallestChild;
//            System.out.println("child after checking: "+child);
//            System.out.println("child value after checking: "+array[child]);
            //problemet jag är på nu är att jag inte förstår hur det värdet vi ska ta bort "försvinner".
            //vi placerar ju om värdena så att det första värdet är helt borta, men när vi når det allra sista värdet
            //vi ändrar på måste det ju tas bort, annars får man samma värde två gånger
            //det finns ingen ta bort metod i arrays, och man kan inte sätta det till null och man kan heller inte
            //bara ändra length hos arrayen eftersom när vi insertar lägger vi till en hel rad med nya platser i arrayen
            //MEN det blir exakt samma grej i BinaryHeap som vi fick av boken,
            //så det kanske inte ska tas bort ett värde, men då undrar jag hur det blir när man sedan ska lägga till värden
            //när det ligger ett spökvärde där samt det stämmer inte överrens med föreläsningsbilderna när träd illustrerades
            //att värdet ligger kvar
            if (array[child]!=null&&array[ child].compareTo(tmp) < 0) {
//                System.out.println("value of child(" + array[child] + ") is less than value of temp(" + tmp + ")");
                array[ hole] = array[ child];
//                System.out.println("hole:" + array[hole]);
            } else {
                break;
            }
        }
//        int k = 0;
//        for(int i = 0; i<array.length;i++){
//        	if(array[i]==null) {
//        		k++;
//        	}
//        }
//        decreaseArray(array.length-k-1);
//        System.out.println("hole:"+hole);
        array[ hole] = tmp;
//        System.out.println("size"+array.length);
//        System.out.println("current size value"+array[currentSize]);
    }

    //generiska get-metoder för att hitta first child och parent
    public int firstChildIndex(int parent) {
        if (parent == 0) {
            throw new IllegalArgumentException();
        }
        return parent * children - (children - 2);
        //return 2 + (children *(parent-1));
    }

    public int parentIndex(int child) {
        if (child < 1) {
            throw new IllegalArgumentException();
        }
        //return (child - 2) / children + 1;
        return (child + children - 2) / children;
    }

    public AnyType get(int i) {
        return array[i];
    }

//    public AnyType getIndex(int i){
//    	AnyType yeah = array[i];
//    	return yeah;
//    }
    // Test program
//    public static void main( String [ ] args )
//    {
//        int numItems = 10000;
//        BinaryHeap<Integer> h = new BinaryHeap<>( );
//        int i = 37;
//
//        for( i = 37; i != 0; i = ( i + 37 ) % numItems )
//            h.insert( i );
//        for( i = 1; i < numItems; i++ )
//            if( h.deleteMin( ) != i )
//                System.out.println( "Oops! " + i );
//    }
}