Deque

#include<iostream>

#include<assert.h>

 

//Alors oui le fichier s'appelle MonDeque et la classe MaDeque, bon, personne n'est parfait !

//T un type g�n�rique, TAILLEA la taille allou�e � un bloc de m�moire de la deque (parmis les n qu'elle peut avoir)

template<typename T, int TAILLEA>

class MaDeque

{

public:

        MaDeque();

        ~MaDeque();

        void push_back(T elem);

        void pop_back();

        T operator[](const T& num) const;

private:

        //Nombre de blocs allou�s

        int nbBloc;

        //Taille des blocs (nombre r�el d'�l�ment dedans, la taille allou�e en m�moire �tant TAILLEA en template)

        int* tailleBloc;

        //Tableau de pointeur pointant (nan sans blague) sur la zone m�moire o� sont stock�s les �l�ments T

        T* * ptrBlocs;

};

 

template<typename T, int TAILLEA>

MaDeque<T, TAILLEA>::MaDeque(){

        //Initialisation d'un bloc d'�l�ments, du premier pointeur pointant sur ce bloc et du nombre d'�l�ments et nombre de bloc

        ptrBlocs = new T*[TAILLEA];

        ptrBlocs[0] = new T[TAILLEA];

        tailleBloc = new int[TAILLEA];

        tailleBloc[0] = 0;

        nbBloc = 1;

}

 

template<typename T, int TAILLEA>

MaDeque<T, TAILLEA>::~MaDeque(){

        delete[] * ptrBlocs;

        //Manque delete de tailleBloc, je bloque la dessus

}

 

template<typename T, int TAILLEA>

void MaDeque<T, TAILLEA>::push_back(T elem){

        //V�rification de la place dispo, si pas assez de place, recherche d'un nouveau bloc de m�moire

        if (this->tailleBloc[nbBloc - 1] >= TAILLEA){

                nbBloc++;

                tailleBloc[nbBloc - 1] = 0;

                ptrBlocs[nbBloc - 1] = (T*)malloc(sizeof(T) * TAILLEA);

        }

        //R�cup�ration du ptr contenu dans ptrBlocs pour savoir o� sont rang�s les T

        T* debut = ptrBlocs[nbBloc - 1];

        //Saut au ni�me �l�ment

        debut += tailleBloc[nbBloc - 1];

        //Modification de l'�l�ment

        *debut = elem;

        //Incr�mentation du compteur d'�l�ment

        tailleBloc[nbBloc - 1]++;

}

 

template<typename T, int TAILLEA>

T MaDeque<T, TAILLEA>::operator[](const T& num) const{

        //Calcule de l'indice du bloc dans lequel l'�l�ment est recherch�

        int indiceBloc = num / TAILLEA;

        //V�rification d'acc�s � un bloc existant

        if (indiceBloc < nbBloc){

                //R�cup�ration du ptr contenu dans ptrBlocs pour savoir o� sont rang�s les T

                T* debut = ptrBlocs[indiceBloc];

                //V�rification d'acc�s � un �l�ment existant

                if (num - TAILLEA * indiceBloc <= tailleBloc[nbBloc - 1]){

                        //Calcule de l'indice de l'�lement recherch� dans le "tableau"

                        debut += num - TAILLEA * indiceBloc;

                        return *debut;

                }

        }

        throw std::logic_error("L'element specifie n'existe pas !");

}

 

template<typename T, int TAILLEA>

void MaDeque<T, TAILLEA>::pop_back(){

        //Supprime le bloc m�moire si celui-ci ne contient qu'un �l�ment

        if (tailleBloc[nbBloc - 1] == 1){

                delete ptrBlocs[nbBloc - 1];

                nbBloc--;

        }

        //Sinon copie le tableau d'�l�ment dans un tableau temp, le supprimer puis recopie le temp dans un nouveau tableau contenant 1 case de moins qu'avant (la derni�re est supprim�e !)

        else{

                T* debut = ptrBlocs[nbBloc - 1];

                T* temp = new T[TAILLEA];

                //Copie du tableau dans le temp

                for (int i = 0; i < tailleBloc[nbBloc - 1]; i++){

                        temp[i] = *debut + i;

                }

                delete ptrBlocs[nbBloc - 1];

                T* nveauTab = new T[TAILLEA];

                //Recopie dans le tabeau sans le dernier �l�ment

                for (int i = 0; i < tailleBloc[nbBloc - 1] - 1; i++){

                        nveauTab[i] = *temp + i;

                }

                //Insertion du pointeur du nouveau tableau dans notre sauvegarde de pointeurs

                ptrBlocs[nbBloc - 1] = nveauTab;

                //Sans oublier de d�crementer le nombre d'�l�ments de 1

                tailleBloc[nbBloc - 1]--;

        }

}