package adt.heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MinHeapImpl<T extends Comparable<T>> implements MinHeap<T> {

    private static final int INITIAL_SIZE = 20;
    private static final int INCREASING_FACTOR = 10;

    T[] heap = (T[]) new Comparable[INITIAL_SIZE];
    int size = 0;

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

    @Override
    public void insert(T element) {
        if (size >= heap.length) { //Heap cheia, aumentamos a capacidade
            heap = Arrays.copyOf(heap, heap.length + INCREASING_FACTOR);
        }
        else if (isEmpty()) {
            heap[0] = element;
            size++;
            return;
        }

        int aux = size;
        while (aux > 0 && heap[parent(aux)].compareTo(element) > 0) {
            heap[aux] = heap[parent(aux)];
            aux = parent(aux);
        }

        heap[aux] = element;
        size++;
    }

    @Override
    public T extractRootElement() {
        if (size < 1){
            return null; //Vazia
        }
        T min = rootElement();
        Util.swap(heap, 0, size-1);
        size--;
        minHeapify(0);
        return min;
    }

    @Override
    public T rootElement() {
        if (!isEmpty()) {
            return heap[0]; //Raiz da heap
        }
        return null;
    }

    @Override
    public T[] heapsort(T[] array) {
        List<T> result = new ArrayList<T>();
        buildHeap(array);
        while(!isEmpty()){
            result.add(extractRootElement());
        }
        return (T[]) result.toArray(new Comparable[0]);
    }

    @Override
    public void buildHeap(T[] array) {
        size = array.length;
        heap = (T[]) new Comparable[array.length];

        for (int i = 0; i < array.length; i++) {
            heap[i] = array[i];
        }

        for (int i = ((array.length-1) / 2); i > 0; i--) {
            minHeapify(i);
        }
        minHeapify(0);
    }


    protected void minHeapify(int index){
        int left = (2*index)+1; // Indice do no da Esquerda
        int right = (2*index)+2; // Indice do no da direita
        int minimum = index; // Topo da heap

        if ( (left <= size-1) ) {
            if (heap[left].compareTo(heap[index]) < 0){
                    minimum = left;
            }else{
                    minimum = index;
            }
        }

        if ((right <= size-1)) {
            if (heap[right].compareTo(heap[minimum]) < 0){
                minimum = right;
            }
        }

        if (minimum != index){
            Util.swap(heap, index, minimum);
            minHeapify(minimum);
        }
    }

    @Override
    public T[] toArray() {
        T[] result = (T[]) new Comparable[size];
        for(int i = 0; i < result.length; i++){
            result[i] = heap[i];
        }
        return result;
    }

    protected int parent(int i) {
        return (i-1)/2;
    }

    protected int left(int i) {
        return (2*i) +1;
    }

    protected int right(int i) {
        return (2*i) + 2;
    }

}