import material.u03.IMaxHeap;
import java.lang.reflect.Array;


public class MaxHeap<T extends Comparable<T>> implements IMaxHeap<T> {

    private boolean init=true;
    private T[] array;
    private int capacity;

    public MaxHeap(int capacity){
        this.capacity=capacity+1;
    }

    @Override
    public int capacity() {
        if(init){
        return 0;
        }else
        return array.length-1;
    }

    @Override
    public T extractMax() {
        int n = size();
        if(size()<=(capacity()/4) && n>0){//Halbieren falls zu leer
            this.capacity=((capacity+1)/2);
            int elements = size();
            T[] smallarray = (T[]) Array.newInstance(array[1].getClass(), this.capacity);
            System.arraycopy(array, 1, smallarray, 1, elements);
            array = (T[]) Array.newInstance(smallarray[1].getClass(), this.capacity);
            System.arraycopy(smallarray, 1, array, 1, elements);
        }
        if(n>0){
            T a = array[1];
            array[1]=array[n];
            array[n]=null;
            n--;
            int i=1;
            T b = array[i];
            int j =2*i;
            while(j<=n){
                if((j<n)&&(array[j+1].compareTo(array[j])>0)){
                    j++;
                }
                if(b.compareTo(array[j])<0){
                    array[i]=array[j];
                    i=j;
                    j=2*i;
                }else{
                    j=n+1;
                }
            }
            array[i]=b;
            return a;
        }else{
            System.out.println("Heap ist leer");
            return null;
        }
    }

    @Override
    public T insert(T t) {
        if(init){
        array = (T[]) Array.newInstance(t.getClass(), this.capacity);
        init=false;
        }
        int i = size()+1;
        if(i>capacity()){ //Array vergrößern falls voll
            this.capacity=(capacity*2)-1;
            int elements = size();
            T[] bigarray = (T[]) Array.newInstance(t.getClass(), this.capacity);
            System.arraycopy(array, 1, bigarray, 1, elements);
            array = (T[]) Array.newInstance(t.getClass(), this.capacity);
            System.arraycopy(bigarray, 1, array, 1, elements);
        }
        while(i>1 && (array[(int) Math.floor(i/2)].compareTo(t)<0)){
            array[i]=array[(int) Math.floor(i/2)];
            i=(int) Math.floor(i/2);
        }
        array[i]=t;
        return array[i];
    }

    @Override
    public boolean isEmpty() {
        if(init){
            return true;
        }else
        for(int i=1;i<array.length;i++){
            if(array[i]!=null){
                return false;
            }
        }
        return true;
    }

    @Override
    public T max() {
        if(init){
            return null;
        }else
        return array[1];
    }

    @Override
    public int size() {
        if(init){
            return 0;
        }else

        for(int i=1;i<array.length;i++){
            if(array[i]==null){
                return i-1;
            }
        }
        return array.length-1;
    }

}