#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <assert.h>
#include <time.h>
#include "Alberi BST/Tree.h"
#include "Code/queue.h"
#include "Grafi/List.h"
#include "Grafi/Graph.h"
#define HEAP_MAX 128

struct THeap{
    int A[HEAP_MAX];
    int heapsize;
};

typedef struct THeap* Heap;

Heap nuovoHeap(){
    Heap ret = (Heap)malloc(sizeof(struct THeap));
    ret->heapsize = 0;
    return ret;
}

void swapHeap(Heap coda, int x, int y){
    assert(coda != NULL);
    int aux = coda->A[x];
    coda->A[x] = coda->A[y];
    coda->A[y] = aux;
}

void upHeap(Heap coda, int i, int* p){
    assert(coda != NULL && p != NULL);
    if(i <= 0) return;
    int dad = (i-1)/2;
    if (p[coda->A[dad]] > p[coda->A[i]]){
        swapHeap(coda, dad, i);
        upHeap(coda, dad, p);
    }
}

void insertHeap(Heap coda, int i, int* p){
    assert(coda != NULL && p != NULL);
    if (coda->heapsize >= HEAP_MAX) return;
    coda->A[coda->heapsize] = i;
    upHeap(coda, coda->heapsize, p);
    coda->heapsize += 1;
}

void Heapify(Heap coda, int i, int* p){
    assert(coda != NULL && p != NULL);
    int lesser = i;
    int left = (2*i)+1;
    int right = (2*i)+2;
    if (left < coda->heapsize && p[coda->A[left]] < p[coda->A[lesser]])
        lesser = left;
    if (right < coda->heapsize &&  p[coda->A[right]] < p[coda->A[lesser]])
        lesser = right;
    if(i != lesser){
        swapHeap(coda, lesser, i);
        Heapify(coda, lesser, p);
    }
}

int popHeap(Heap coda, int* p){
    assert(coda != NULL && p != NULL);
    if(!coda->heapsize) return 0;
    int ret = coda->A[0];
    coda->heapsize -= 1;
    coda->A[0] = coda->A[coda->heapsize];
    Heapify(coda, 0, p);
    return ret;
}


int err;

int rimuovi(Queue Q);
int* Dijkstra(Graph G, int s);
void  enhead(Queue Q, int value, int *err);
void togli_numero(List lista1, List lista2);

int main(){
    srand(time(NULL
    ));
    Graph G = randomGraph(11, 5, 11);
    printGraph(G);
    printf("\n\n");
    int* pred = Dijkstra(G, 0);
    int cur = 10;
    while(cur != 0 && cur != -1){
        printf("%d << ", cur);
        cur = pred[cur];
    }
    if (cur == 0) printf("%d", cur);
    else printf("irraginugibile");
    return 0;
}

int main1(){
    Queue Q = initQueue();
    enqueue(Q, 7, &err);
    enqueue(Q, 1, &err);
    enqueue(Q, 4, &err);
    enqueue(Q, 3, &err);
    enqueue(Q, 2, &err);
    enqueue(Q, 5, &err);
    printQueue(Q, &err);
    printf("\n\n");
    rimuovi(Q);
    printQueue(Q, &err);
    return 0;
}

int main2(){
    srand(time(NULL));
    List lista1 = randomList(20, 10);
    List lista2 = randomList(20, 10);
    printList(lista1);
    printf("\n\n");
    printList(lista2);
    printf("\n\n");
    togli_numero(lista1, lista2);
    printList(lista1);
    printf("\n\n");
    printList(lista2);
    printf("\n\n");
    return 0;
}

int* Dijkstra(Graph G, int s){
    if(!G) return NULL;
    int dim = G->nodes_count;
    int* pred = (int*)malloc(sizeof(int)*dim);
    int dist[dim];
    Heap coda = nuovoHeap();
    int i;
    for(i=0;i<dim; i++){
        pred[i] = -1;
        if (i == s) dist[i] = 0;
        else dist[i] = INT_MAX;
        insertHeap(coda, i, dist);
    }
    int u, v, alt;
    List curr;
    while(coda->heapsize){
        u = popHeap(coda, dist);
        curr = G->adj[u];
        while(curr){
            v = curr->target;
            alt = dist[u] + curr->peso;
            if( alt < dist[v]){
                dist[v] = alt;
                pred[v] = u;
                upHeap(coda, v, dist);
            }
            curr = curr->next;
        }
    }
    return pred;
}

List removeTutt(List L, int target, int* nop) {
    if (L != NULL) {
        if (L->target == target) {
            List tmp = L->next;
            free(L);
            (*nop) = 1;
            tmp->next = removeTutt(tmp->next, target, nop);
            return tmp;
        }
        L->next = removeTutt(L->next, target, nop);
    }
    return L;
}

void togli_numero(List lista1, List lista2){
    int m, nop = 1;
    List app, l1 = lista1, l2 = lista2;
    while(l1 && l2 && nop){
        nop = 0;
        m = sizeList(l1);
        l2 = removeTutt(l2, m, &nop);
        app = l1;
        l1 = l2;
        l2 = app;
    }
}

int rimuovi(Queue Q){
    if(!Q || emptyQueue(Q)) return INT_MAX;
    int pos = sizeQueue(Q);
    int el;
    el = dequeue(Q, &err);
    int val = rimuovi(Q);

    if(el%2 == 0 && pos%2 == 0 && el > val){}
    else if(el%2 != 0 && pos%2 != 0){}
    else{
        enhead(Q, el, &err);
        //enqueue(Q, el, &err);
    }
    return el;
}

void  enhead(Queue Q, int value, int *err){
    if(!Q || fullQueue(Q)) return;
    int i, el;
    int siz =  sizeQueue(Q);
    enqueue(Q, value, err);
    for(i=0; i< siz; i++){
        el = dequeue(Q, err);
        enqueue(Q, el, err);
    }
//    if (!fullQueue(Q)) {
//        if (Q->A[0] > 1) Q->A[0] -= 1;
//        else Q->A[0] = QUEUE_MAX-1;
//        Q->A[Q->A[0]] = value; // Inserisci valore in coda
//        if (emptyQueue(Q)) {
//            Q->A[0] = 1; // Se e' vuota, sposto la testa in prima posizione
//        }
//        *err = 0;
//    } else {
//        *err = 5;
//    }
}