×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Text
Posted by: Massi Massi
Added: Sep 22, 2016 10:53 AM
Views: 2
Tags: no tags
  1. #include<iostream>
  2. #include<assert.h>
  3.  
  4. //Alors oui le fichier s'appelle MonDeque et la classe MaDeque, bon, personne n'est parfait !
  5. //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)
  6. template<typename T, int TAILLEA>
  7. class MaDeque
  8. {
  9. public:
  10.         MaDeque();
  11.         ~MaDeque();
  12.         void push_back(T elem);
  13.         void pop_back();
  14.         T operator[](const T& num) const;
  15. private:
  16.         //Nombre de blocs allou�s
  17.         int nbBloc;
  18.         //Taille des blocs (nombre r�el d'�l�ment dedans, la taille allou�e en m�moire �tant TAILLEA en template)
  19.         int* tailleBloc;
  20.         //Tableau de pointeur pointant (nan sans blague) sur la zone m�moire o� sont stock�s les �l�ments T
  21.         T* * ptrBlocs;
  22. };
  23.  
  24. template<typename T, int TAILLEA>
  25. MaDeque<T, TAILLEA>::MaDeque(){
  26.         //Initialisation d'un bloc d'�l�ments, du premier pointeur pointant sur ce bloc et du nombre d'�l�ments et nombre de bloc
  27.         ptrBlocs = new T*[TAILLEA];
  28.         ptrBlocs[0] = new T[TAILLEA];
  29.         tailleBloc = new int[TAILLEA];
  30.         tailleBloc[0] = 0;
  31.         nbBloc = 1;
  32. }
  33.  
  34. template<typename T, int TAILLEA>
  35. MaDeque<T, TAILLEA>::~MaDeque(){
  36.         delete[] * ptrBlocs;
  37.         //Manque delete de tailleBloc, je bloque la dessus
  38. }
  39.  
  40. template<typename T, int TAILLEA>
  41. void MaDeque<T, TAILLEA>::push_back(T elem){
  42.         //V�rification de la place dispo, si pas assez de place, recherche d'un nouveau bloc de m�moire
  43.         if (this->tailleBloc[nbBloc - 1] >= TAILLEA){
  44.                 nbBloc++;
  45.                 tailleBloc[nbBloc - 1] = 0;
  46.                 ptrBlocs[nbBloc - 1] = (T*)malloc(sizeof(T) * TAILLEA);
  47.         }
  48.         //R�cup�ration du ptr contenu dans ptrBlocs pour savoir o� sont rang�s les T
  49.         T* debut = ptrBlocs[nbBloc - 1];
  50.         //Saut au ni�me �l�ment
  51.         debut += tailleBloc[nbBloc - 1];
  52.         //Modification de l'�l�ment
  53.         *debut = elem;
  54.         //Incr�mentation du compteur d'�l�ment
  55.         tailleBloc[nbBloc - 1]++;
  56. }
  57.  
  58. template<typename T, int TAILLEA>
  59. T MaDeque<T, TAILLEA>::operator[](const T& num) const{
  60.         //Calcule de l'indice du bloc dans lequel l'�l�ment est recherch�
  61.         int indiceBloc = num / TAILLEA;
  62.         //V�rification d'acc�s � un bloc existant
  63.         if (indiceBloc < nbBloc){
  64.                 //R�cup�ration du ptr contenu dans ptrBlocs pour savoir o� sont rang�s les T
  65.                 T* debut = ptrBlocs[indiceBloc];
  66.                 //V�rification d'acc�s � un �l�ment existant
  67.                 if (num - TAILLEA * indiceBloc <= tailleBloc[nbBloc - 1]){
  68.                         //Calcule de l'indice de l'�lement recherch� dans le "tableau"
  69.                         debut += num - TAILLEA * indiceBloc;
  70.                         return *debut;
  71.                 }
  72.         }
  73.         throw std::logic_error("L'element specifie n'existe pas !");
  74. }
  75.  
  76. template<typename T, int TAILLEA>
  77. void MaDeque<T, TAILLEA>::pop_back(){
  78.         //Supprime le bloc m�moire si celui-ci ne contient qu'un �l�ment
  79.         if (tailleBloc[nbBloc - 1] == 1){
  80.                 delete ptrBlocs[nbBloc - 1];
  81.                 nbBloc--;
  82.         }
  83.         //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 !)
  84.         else{
  85.                 T* debut = ptrBlocs[nbBloc - 1];
  86.                 T* temp = new T[TAILLEA];
  87.                 //Copie du tableau dans le temp
  88.                 for (int i = 0; i < tailleBloc[nbBloc - 1]; i++){
  89.                         temp[i] = *debut + i;
  90.                 }
  91.                 delete ptrBlocs[nbBloc - 1];
  92.                 T* nveauTab = new T[TAILLEA];
  93.                 //Recopie dans le tabeau sans le dernier �l�ment
  94.                 for (int i = 0; i < tailleBloc[nbBloc - 1] - 1; i++){
  95.                         nveauTab[i] = *temp + i;
  96.                 }
  97.                 //Insertion du pointeur du nouveau tableau dans notre sauvegarde de pointeurs
  98.                 ptrBlocs[nbBloc - 1] = nveauTab;
  99.                 //Sans oublier de d�crementer le nombre d'�l�ments de 1
  100.                 tailleBloc[nbBloc - 1]--;
  101.         }
  102. }
  103.