2.3 (esercitazione 2 esercizio 3 incompleto)

#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); space.key[i]=0; 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)
{
    int aux=freeList;
    /*Ho ancora posizioni libere*/
    if(space.next[freeList]!=-1)
        {
            freeList=space.next[freeList];
            space.prev[freeList]=-1;
            space.next[aux]=-1;
        }
    else
        {
        /*Sono sull'ultima posizione libera*/
            freeList=-1;
    }
    return aux;
}
else
    {
        printf("\nSpazio esaurito\n");
        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: rende libero l'oggetto x  */
void freeObject(List x){
    int temp=x;
    space.prev[x]=-1;
    space.key[x]=0;
    space.next[x]=freeList; /* lo butto in testa alla freelist */
    space.prev[freeList]=x;
    freeList=temp;
}

/*Post: dealloca gli elementi contenuti nella lista */
void rimuovi(List l){
    int temp;
    while(l>=0)
    {
        temp=space.next[l];
        freeObject(l);
        l=temp;
    }
    l=-1;
    return;
}

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

    int temp,value,first,next;
    List l, pointer;

    temp=-1; first=1; value=1;/*valore positivo insignificante solo x entrare nel ciclo*/
    printf("Caricamento nuova lista, inserisci 0 per terminare.\n");

    while(value){
        l=allocateObject();
        printf("l vale %d\n",l);
        printf("Inserisci valore: ");
    scanf("%d",&value);
        if(first){pointer=l;/* puntatore alla testa, NON AGGIORNARE */ first=0;
            if(!value){freeObject(l); return -1; }
        }

    space.next[l]=-1;
    space.key[l]=value;
    space.prev[l]=temp;
    temp=l;
   }
   temp=space.prev[l];//ultimo elemento
   printf("temp vale=%d\n",temp);
   freeObject(l);
   value=-1;
   //scorro all'indietro lista e assegno i next
   while(temp>=0){
    space.next[temp]=value;
    value=temp;
    temp=space.prev[temp];
   }
return pointer;
}

/* Stampa la situazione globale */
void debug(){
    int i,j;
    int charperrow=10;
    printf("Spazio Libero: %d (da %d in poi).\n",lunghezza(freeList),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");
    }

}


void auxcompat(List l, int pointerList, int pointerFree,int lunghezza){
    int temp;
    if((pointerList<0)||(pointerFree<0))return;
    else{
        if(pointerFree>lunghezza){
            auxcompat(l,pointerList,space.next[pointerFree],lunghezza);
            return;
        }
        if(pointerList<=lunghezza){
            auxcompat(l,space.next[pointerList],pointerFree,lunghezza);
            return;
        }

        temp=space.next[pointerFree];
        space.next[pointerFree]=space.next[pointerList];
        space.next[pointerList]=temp;
        temp=space.prev[pointerFree];
        space.prev[pointerFree]=space.prev[pointerList];
        space.prev[pointerList]=temp;
        temp=space.key[pointerFree];
        space.key[pointerFree]=space.key[pointerList];
        space.key[pointerList]=temp;

        if(freeList==pointerFree)freeList=pointerList;
        if(l==pointerList)l=pointerFree;

        if(space.prev[pointerList]>=0)space.next[space.prev[pointerList]] = pointerList;
        if(space.next[pointerList]>=0)space.prev[space.next[pointerList]] = pointerList;
        if(space.prev[pointerFree]>=0)space.next[space.prev[pointerFree]] = pointerFree;
        if(space.next[pointerFree]>=0)space.prev[space.next[pointerFree]] = pointerFree;

        auxcompat(l,space.next[pointerFree],space.next[pointerList],lunghezza);
        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){
    int lunghez;
    lunghez=lunghezza(l)-1;
    auxcompat(l,l,freeList,lunghez);
    return l;
}