/*
 *
 * Copyright (C) 2008 Fontaine Clément
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * this program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "liste.h"

void* listeAjouterFin(liste *liste, size_t taille)
{
        chaine *nouveau = NULL;
        
        void *contenu = malloc(taille);
        nouveau = malloc(sizeof(chaine)); /* création du nouvelle élément */
        
        if(nouveau == NULL) /* gestion des exception */
        {
                /* l'allocation dynamique a échouée */
                return NULL;
        }
        /* initialisation des champs de la nouvelle structure */
        nouveau->contenu = contenu;
        nouveau->pred = NULL;
        nouveau->succ = NULL;
        
        /* ajout du nouvelle élément en fin de liste */
        if(liste->debut == NULL)
        {
                /* la liste est vide */
                liste->debut = nouveau; /* on crée le début de la liste chaînées */
                liste->fin = nouveau; /* et la fin */
        }
        else
        {
                liste->fin->succ = nouveau; /* la succession du dernier élément pointe maintenant sur le nouveau */
                nouveau->pred = liste->fin; /* le prédécesseur du nouvelle élément pointe maintenant sur le dernier */
                liste->fin = nouveau; /* on met à jour la fin de la liste chaînées */
        }
        (liste->taille)++;
        return contenu;
}

void* listeAjouterDebut(liste *liste, size_t taille)
{
        chaine *nouveau = malloc(sizeof(chaine));
        void *contenu = malloc(taille);
        
        if(nouveau == NULL)
        {
                return NULL;
        }
        nouveau->contenu = contenu;
        nouveau->pred = NULL;
        nouveau->succ = NULL;
        
        /* ajout du nouvelle élément en début de liste */
        if(liste->fin == NULL)
        {
                /* la liste est vide */
                liste->fin = nouveau;
                liste->debut = nouveau;
        }
        else
        {
                liste->debut->pred = nouveau; /* le prédécesseur du premier élément pointe maintenant sur le nouveau */
                nouveau->succ = liste->debut; /* le successeur du nouvelle élément pointe maintenant sur le premier */
                liste->debut = nouveau;
        }
        (liste->taille)++;
        return contenu;
}

void* listeAjouter(liste *liste, int position, size_t taille)
{
        int i = 0;
        chaine *avant = NULL, *apres = NULL;
        chaine *nouveau = malloc(sizeof(chaine));
        void *contenu = malloc(taille);
        
        if(nouveau == NULL)
        {
                return NULL;
        }
        nouveau->contenu = contenu;
        nouveau->pred = NULL;
        nouveau->succ = NULL;
        
        /* si on veut insérer à la fin */
        if(liste->taille == position)
        {
                nouveau->pred = liste->fin;
                liste->fin->succ = nouveau;
                liste->fin = nouveau;
        }
        else
        {
                apres = listeValeur(*liste, position);
                
                if(apres == liste->debut) /* insertion en début de liste */
                {
                        nouveau->succ = liste->debut;
                        liste->debut->pred = nouveau;
                        liste->debut = nouveau;
                }
                else /* chaînage entre deux éléments */
                {
                        avant = apres->pred;
                        avant->succ = nouveau;
                        nouveau->pred = avant;
                        nouveau->succ = apres;
                        apres->pred = nouveau;
                }
        }
        (liste->taille)++;
        return contenu;
}

void listeSupprimer(liste *liste, int position)
{
        int i = 0, j = liste->taille;
        chaine *element = NULL;
        chaine *avant = NULL, *apres = NULL;
        
        if(position >= j)
        {
                return;
        }
        element = liste->debut;
        
        while(i++ < position)
        {
                element = element->succ;
        }
        if(element == liste->debut) /* suppression du premier élément */
        {
                apres = liste->debut->succ;
                apres->pred = NULL;
                liste->debut = apres;
        }
        else if(element == liste->fin) /* suppression du dernier élément */
        {
                avant = liste->fin->pred;
                avant->succ = NULL;
                liste->fin = avant;
        }
        else /* suppression dans la liste */
        {
                avant = element->pred;
                apres = element->succ;
                avant->succ = apres;
                apres->pred = avant;
        }
        (liste->taille)--;
        /* destruction de l'élément extrait de la liste */
        //free(element->contenu);
        //free(element);
}

void listeSupprimerTout(liste *liste)
{
        chaine *courant = NULL;
        chaine *freeCourant = NULL;
        
        for(freeCourant = liste->debut; freeCourant != NULL; freeCourant = courant)
        {
                courant = freeCourant->succ;
                //free(freeCourant->contenu);
                //free(freeCourant);
        }
        /* remet à zéro */
        liste->debut = NULL;
        liste->fin = NULL;
        liste->taille = 0;
}

void* listeValeur(liste liste, int position)
{
        int i = 0, j = liste.taille;
        chaine *courant = NULL;
        
        if(position >= j)
        {
                return NULL;
        }
        
        /*
         *
         * on parcourt la liste jusqu'à l'élément à la position demandé si possible
         * tout en réduisant le nombre d'itérations. Si l'ont veut un élément vers
         * la fin, on commencera plutôt vers la fin et inversement, c'est ce qui fait
         * la différence avec les listes simplement chaînées.
         *
         */
        
        if(position < (j / 2))
        {
                courant = liste.debut;
                
                while(i++ < position)
                {
                        courant = courant->succ;
                }
        }
        else
        {
                courant = liste.fin;
                
                while(--j > position)
                {
                        courant = courant->pred;
                }
        }
        return courant->contenu;
}

void* listeDepiler(liste *liste)
{
        chaine *element = liste->fin;
        chaine *avant = NULL, *apres = NULL;
        void *contenu = element->contenu;
        
        /* il reste plus d'un élément */
        if(liste->fin != liste->debut)
        {
                avant = liste->fin->pred;
                avant->succ = NULL;
                liste->fin = avant;
                
                /* destruction de l'élément extrait de la liste */
                free(element->contenu);
                free(element);
        }
        return contenu;
}

void* listeDefiler(liste *liste)
{
        chaine *element = liste->debut;
        chaine *avant = NULL, *apres = NULL;
        void *contenu = element->contenu;
        
        if(liste->fin != liste->debut)
        {
                apres = liste->debut->succ;
                apres->pred = NULL;
                liste->debut = avant;
                
                free(element->contenu);
                free(element);
        }
        return contenu;
}

erreur tableauCreer(hauteur *hauteur, coordonnees etendu, size_t taille)
{
        int i, j;
        tableau *nouveau = NULL;
        liste ligne;
        
        for(i = 0; i < etendu.y; i++)
        {
                /* création de la ligne */
                ligne.debut = NULL;
                ligne.fin = NULL;
                ligne.taille = 0;
                
                for(j = 0; j < etendu.x; j++)
                {
                        listeAjouterFin(&ligne, taille);
                }
                
                /* création du pointeur vers la ligne */
                
                nouveau = malloc(sizeof(tableau));
                
                if(nouveau == NULL)
                {
                        return ERR_MALLOC;
                }
                nouveau->ligne = ligne;
                nouveau->pred = NULL;
                nouveau->succ = NULL;
                
                if(hauteur->debut == NULL)
                {
                        hauteur->debut = nouveau;
                        hauteur->fin = nouveau;
                }
                else
                {
                        hauteur->fin->succ = nouveau;
                        nouveau->pred = hauteur->fin;
                        hauteur->fin = nouveau;
                }
        }
        hauteur->taille = etendu;
        return OK;
}

void* tableauValeur(hauteur hauteur, coordonnees position)
{
        tableau *ordonnees = NULL;
        chaine *absicce = NULL;
        int i = 0, j = hauteur.taille.x;
        
        /* on se déplace sur la verticale */
        
        if(position.y >= hauteur.taille.y)
        {
                return NULL;
        }
        else
        {
                if(position.y < (hauteur.taille.y / 2))
                {
                        ordonnees = hauteur.debut;
                        
                        while(i++ < position.y)
                        {
                                ordonnees = ordonnees->succ;
                        }
                }
                else
                {
                        ordonnees = hauteur.fin;
                        
                        while(--j > position.y)
                        {
                                ordonnees = ordonnees->pred;
                        }
                }
        }
        
        /* on se déplace sur l'horisontal */
        
        return listeValeur(ordonnees->ligne, position.x);
}

void tableauSupprimerTout(hauteur *hauteur)
{
        tableau *courant = NULL;
        tableau *freeCourant = NULL;
        liste ligne = {NULL, NULL, 0};
        
        for(freeCourant = hauteur->debut; freeCourant != NULL; freeCourant = courant)
        {
                courant = freeCourant->succ;
                /* on supprime la ligne */
                ligne.debut = freeCourant->ligne.debut;
                listeSupprimerTout(&ligne);
                /* et l'élément de la colonne */
                free(freeCourant);
        }
        /* remet à zéro */
        hauteur->debut = NULL;
        hauteur->fin = NULL;
}