#include <stdio.h>
#include <stdlib.h>
//#include <time.h>
#define DIM 100
#include "list.h"


/*Rappresentazione di liste con array */
typedef struct{
  int key[DIM];
  int next[DIM];
  int prev[DIM];
} Spazio;

/* Variabili globali*/
List freeList;  /*Testa della free List che e' una lista DOPPIAMENTE concatenata*/
Spazio space; /*Spazio utilizzato per memorizzare le liste*/


/*Post: inizializza space in modo che tutti gli elementi siano nella lista libera. La testa della lista libera sara' 0 */
void initFreelist(){
    int i;
    for(i=0;i<DIM;i++)space.prev[i]=(i-1);
    for(i=0;i<DIM;i++)space.next[i]=(i+1);
    space.next[DIM-1]=-1; //indico ultimo elem.
    freeList=0;
}

/*Post: restituisce un oggetto libero. Se lo spazio e' esaurito stampa un messaggio di errore  */
List allocateObject(){
    if(freeList<0){printf("Errore: spazio esaurito!"); return -2;}
    else return freeList;
}

/* Post: restituisce il numero di elementi contenuti nella lista */
int lunghezza(List l){
    int counter=0;
    if(l<0)return 0;
    if(space.next[l]<0)return 1;
    else return 1+lunghezza(space.next[l]);
}


/*Post: stampa il contenuto della lista. Deve essere una funzione RICORSIVA */
void stampa(List l){
    if(l<0){printf("LISTA VUOTA."); return;}
    printf("%d ",space.key[l]);
    if(space.next[l]<0)printf(".");
    else stampa(space.next[l]);
}



/*Post: legge una sequenza di interi inseriti dall'utente e restituisce una lista contenente tale sequenza*/
List caricamento(){

    int i,n,temp;
    List l,pointer;
    l=allocateObject();
    pointer=l;
    printf("Lunghezza Lista: ");
    scanf("%d",&i);

    if(i>=lunghezza(l)){printf("Non c'e' spazio a sufficienza! ERRORE!\n"); return -2;}
    if(i==0)return -1; //lista vuota
    if(i<0){printf("Valore ERRATO!\n"); return -2;}

    space.prev[l]=-1;

    //inserimento valori
    for (n=0;n<i;n++)
  {
    printf ("Inserisci il valore #%d: ",n+1);
    scanf ("%d",&(space.key[l]));
    temp=l;
    l=space.next[l];//l++
  }
  space.next[temp]=-1;

  space.prev[l]=-1;
  freeList=l;

return pointer;
}

/* Stampa la situazione globale */
void debug(){
    int i,j;
    int charperrow=8;
    printf("freeList: %d\n",freeList);
    for(i=0;i<DIM/charperrow;i++){
        printf("N:\t");
        for(j=0;j<charperrow;j++)printf("%d\t",space.next[i*charperrow+j]);
        printf("\nK:\t");
        for(j=0;j<charperrow;j++)printf("%d\t",space.key[i*charperrow+j]);
        printf("\nP:\t");
        for(j=0;j<charperrow;j++)printf("%d\t",space.prev[i*charperrow+j]);
        printf("\n\n");
    }

}


/*Post: rende libero l'oggetto x  */
void freeObject(List x){
    int temp=x;
    space.prev[x]=-1;
    while(space.next[x]>0)x=space.next[x];//scorro a fine lista x per attaccarci la freeList
    space.next[x]=freeList;
    space.prev[freeList]=x;
    freeList=temp;
}


/*Post: dealloca gli elementi contenuti nella lista */
void rimuovi(List l){
return;
}






/*Pre: Si assuma che space abbia m elementi, l sia una lista di n elementi e i rimanenti elementi di space (m -n) siano nella lista libera.
  Post: sposta gli elementi in l in modo che occupino le posizioni 0, 1, ..., n-1 di space e aggiusta la lista libera in modo che essa resti corretta, occupando le posizioni di space n, n+1, ...., m - 1. La funzione restituisce la lista l con gli elementi nelle posizioni specificate.
  Il tempo di esecuzione della funzione e' theta(n) e deve utilizzare SOLO una quantita' costante di spazio extra. */
List compatifyList(List l){
    //BOOOOOOH
    return -7;
}




List caricaListaStronza(){

    space.next[8]=17;
    space.key[8]=1;
    space.prev[8]=-1;

    space.next[17]=1;
    space.key[17]=2;
    space.prev[17]=8;

    space.next[1]=73;
    space.key[1]=3;
    space.prev[1]=17;

    space.next[73]=51;
    space.key[73]=4;
    space.prev[73]=1;

    space.next[51]=50;
    space.key[51]=5;
    space.prev[51]=73;

    space.next[50]=63;
    space.key[50]=6;
    space.prev[50]=51;

    space.next[63]=7;
    space.key[63]=7;
    space.prev[63]=50;

    space.next[7]=-1;
    space.key[7]=8;
    space.prev[7]=63;

space.next[0]=2;
space.prev[2]=0;

space.next[6]=9;
space.prev[9]=6;

space.next[16]=18;
space.prev[18]=16;

space.next[49]=52;
space.prev[52]=49;

space.next[62]=64;
space.prev[64]=62;

space.next[72]=74;
space.prev[74]=72;

return 8;
}