C++: Correction Collections simples

 

1 La classe Tableau

1.1 Interface de la classe Tableau

Voici l'entête de la classe : 


#ifndef __TABLEAU_H__
#define __TABLEAU_H__

#include <stddef.h>
#include <iostream.h>

class Tableau {
  friend ostream & operator << (ostream &, const Tableau &);

  void ** arr_;
  size_t  nb_;

 public:
  Tableau (size_t _nb = 128);
  ~Tableau ();

  size_t size() const; // le nombre d'elements
  const void * const * elements() const; // le tableau d'elements

  // positionne un element dans le tableau
  void atPut (size_t _pos, void * _ptr);
  
  // retourne l'element d'indexe _pos
  void *& at (size_t _pos); 

  // retourne l'element d'indexe _pos
  void * at (size_t _pos) const; 

  // retourne l'indexe d'un élément
  size_t indexOf (const void * _ptr) const; 

  // retourne l'indexe du premier élément pour lequel _fcmp()
  // retourne true
  size_t indexOf (bool (*_fcmp) (const void * _ptr, void *), const void * _data) const; 

  // recherche les indexes de _ptr, les place dans le tableau _indexes
  // et retourne le nombre d'indexes trouves
  size_t indexesOf (const void * _ptr, size_t * _indexes) const;

  // recherche les indexes des elements pour lesquel _fcmp retourne true, 
  // les place dans le tableau _indexes et retourne le nombre d'indexes
  // trouves
  size_t indexesOf (bool (*_fcmp)(const void * _ptr, void *), 
		    const void * _data, 
		    size_t * _indexes) const;

};

#endif // __TABLEAU_H__

 

1.2 Mise en oeuvre de la classe

Voici une mise en œuvre de la classe Tableau : 


// Auteurs : Stéphane Demurget et Nicolas Chauvin
// Etudiants de l'IUP d'informatique de Brest, 3ième Année, 
// 09/2001

#include <assert.h>
#include "tableau.h"

// On initialise les variables membres nb_ et arr_
Tableau::
Tableau (size_t _nb = 128) : arr_(new void *[_nb]), nb_(_nb)
{ 
}

// On desalloue arr_ (on est sur qu'il a ete alloue car
// passage oblige par le constructeur)
// Par contre, on ne desalloue par les addresses contenues.
// Elles n'ont peut etre pas ete allouees ou elle peuvent
// etre partagees par plusieurs tableaux
Tableau::
~Tableau ()
{
  delete arr_;
}

size_t Tableau::
size () const
{
  return nb_;
}

const void * const * Tableau::
elements () const
{
  return arr_;
}

// On place _ptr dans arr_
// a la position _pos
void Tableau::
atPut (size_t _pos, void  *_ptr)
{
  assert(_pos < nb_);
  at(_pos) = _ptr;
}

void *& Tableau::
at (size_t _pos)
{
  assert(_pos < nb_);
  return arr_[_pos];
}

void * Tableau::
at (size_t _pos) const
{
  assert(_pos < nb_);
  return arr_[_pos];
}

// Ok, pour reutiliser indexesOf [*] dans indexesOf [**]
// et indexOf [+] dans indexOf [++]
static bool default_fcmp (const void *_ptr1, void *_ptr2)
{
  return (_ptr1 == _ptr2);
}

// ++
size_t Tableau::
indexOf (const void *_ptr) const
{
  return indexOf (default_fcmp, _ptr);
}

// +
// On execute _fcmp(_ptr,arr_[i]) pour i de 0 à nb_
size_t Tableau::
indexOf (bool (*_fcmp) (const void *_ptr1, void *_ptr2), const void *_ptr) const
{
  for (size_t i = 0; i < nb_; i++)
    if (_fcmp (_ptr, arr_[i]))
      return i;
  return ~0; 
}

// **
size_t Tableau::
indexesOf (const void *_ptr, size_t * _indexes) const
{
  return indexesOf (default_fcmp, _ptr, _indexes);	
}

// *
// On execute _fcmp(_ptr,arr_[i]) pour i de 0 à nb_
size_t Tableau::
indexesOf (bool (*_fcmp) (const void *_ptr1, void *_ptr2), const void *_ptr, size_t *_indexes) const
{
  size_t count = 0;
  for (size_t i = 0; i < nb_; i++)
    if (_fcmp (_ptr, arr_[i])) {
      _indexes[count] = i;
      count++;
    }
  return count; 	
}

ostream& operator << (ostream &os, const Tableau &tab)
{
  if (!tab.nb_) return os << "[vide]";
  size_t i;
  for (i = 0; i < tab.nb_ - 1; i++)
    os << tab.arr_[i] << " - ";
  return os << tab.arr_[i];
}

#ifdef _TEST_

#include <stdio.h>
#include <string.h>

const size_t max = 10;

static bool fcmp1 (const void *_ptr1, void *_ptr2)
{
  return (strcmp((const char*)_ptr1, (const char *)_ptr2) == 0);
}

int
main ()
{
  Tableau tint(max);
  for (size_t n = 0; n < tint.size(); n++) {
    tint.at(n) = (void*) n;
  }
  cout << "> Premier tableau avec des entiers : " << tint << endl << endl;

  Tableau tchars(max);
  for (size_t n = 0; n < tchars.size(); n++) {
    char buf[100];
    sprintf(buf, "%d", n); 
    tchars.atPut(n, strdup(buf));
  }
  cout << "> Deuxieme tableau avec des char * alloues : " << tchars << endl;
  for (size_t n = 0; n < tchars.size(); n++) {
    cout << (char*) tchars.at(n) << " ";
  }
  cout << endl;

  const char * s = (const char *) tchars.at(2);
  cout << "> Numéro de la cellule contenant l'adresse " << (void*) s 
       << " : " << tchars.indexOf(s) << endl;
  cout << "> Numéro de la cellule contenant la chaine \"3\" : ";
  cout << tchars.indexOf (fcmp1, "3") << endl;

  Tableau tchars2(max);
  for (size_t n = 0; n < tchars2.size() / 2; n++) {
    char buf[100];
    sprintf(buf, "%d", n); 
    tchars2.atPut(n, strdup(buf));
  }

  size_t n2 = 0;
  for (size_t n = tchars2.size() / 2; n < tchars2.size(); n++, n2++) {
    char buf[100];
    sprintf(buf, "%d", n2); 
    tchars2.atPut(n, strdup(buf));
  }
  cout << "> Troisieme tableau avec des char * alloues : " << tchars2 << endl;
  for (size_t n = 0; n < tchars2.size(); n++) {
    cout << (char*) tchars2.at(n) << " ";
  }
  cout << endl;

  size_t pos3[max];
  size_t nb3 = tchars2.indexesOf (fcmp1, (void*)"3", pos3);
  cout << "> Numéro des cellules contenant la chaine \"3\" : ";
  for (size_t n = 0; n < nb3; n++) {
    cout << pos3[n] << " ";
  }
  cout << endl;


  // On oublie pas de desallouer tout ca
  for (size_t n = 0; n < tchars.size(); n++) {
    delete (char*)tchars.at(n);
  }
  for (size_t n = 0; n < tchars2.size(); n++) {
    delete (char*)tchars2.at(n);
  }

  return 0;
  exit(0);
}

#endif // _TEST_

 

2 La classe Collection

Par comparaison avec l'énoncé donné en TP, l'interface et la mise en oeuvre données ici sont plus complètes. Le constructeur par copie et l'opérateur d'affectation ont en effet été ajoutés.

 

2.1 Interface de la classe Collection

Voici l'entête de la classe : 


#ifndef __COLLECTION_H__
#define __COLLECTION_H__

#include <stddef.h>

class Collection
{
public:
  friend ostream & operator << (ostream &, const Tableau &);

  Collection();
  ~Collection();
  Collection(const Collection &); // le constructeur par copie
  const Collection & operator = (const Collection &);

  size_t size() const; // le nombre d'elements
  const void * const * elements() const; // le tableau d'elements

  // positionne un element dans le tableau
  void atPut(size_t _pos, void * _ptr);
  
  // retourne l'element d'indexe _pos
  void *& at(size_t _pos); 

  // retourne l'element d'indexe _pos
  void * at(size_t _pos) const; 

  // retourne l'element d'indexe _pos
  void *& operator [] (size_t _pos); 

  // retourne l'element d'indexe _pos
  void * operator [] (size_t _pos) const; 

  // Ajoute un element et retourne sa position
  size_t append(void *);

  // Extrait un element du tableau et retourne le pointeur extrait
  void * extractAt(size_t _pos);

  // retourne l'indexe d'un élément
  size_t indexOf(const void * _ptr) const; 

  // retourne l'indexe du premier élément pour lequel _fcmp() retourne true
  size_t indexOf(bool (*_fcmp)(void * _ptr, void *), void * _data) const; 

  // recherche les indexes de _ptr, les place dans le tableau _indexes et retourne
  // le nombre d'indexes trouves
  size_t indexesOf(const void * _ptr, size_t * _indexes) const;

  // recherche les indexes des elements pour lesquel _fcmp retourne true, 
  // les place dans le tableau _indexes et retourne le nombre d'indexes trouves
  size_t indexesOf(bool (*_fcmp)(void * _ptr, void *), 
		   void * _data, 
		   size_t * _indexes) const;

private:
  void ** arr__;
  size_t size__;
};


#endif

 

2.2 Mise en oeuvre de la classe

Voici une mise en œuvre de la classe Collection : 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "collection.h"

ostream& operator << (ostream &os, const Collection &tab)
{
  for (size_t i = 0; i < tab.size__; i++)
    os << tab.arr_[i] << " ";
  return os;
}

Collection::
Collection()
  : arr__(0),
    size__(0)
{
}

Collection::
~Collection()
{
  delete arr__;
}

Collection::
Collection(const Collection & _other)
  :  arr__(new void * [_other.size__]),
     size__(_other.size__)
{
  memcpy(arr__, _other.arr__, sizeof(void*) * size__);
}

const Collection & Collection::
operator = (const Collection & _other)
{
  if (this != &_other) {
    delete arr__;
    arr__ = new void * [_other.size__];
    size__ = _other.size__;
    memcpy(arr__, _other.arr__, sizeof(void*) * size__);
  }
  return *this;
}

size_t Collection::
size() const
{
  return size__;
}

const void * const * Collection::
elements() const
{
  return arr__;
}

void Collection::
atPut(size_t _pos, void * _ptr)
{
  assert(_pos < size__);
  arr__[_pos] = _ptr;
}
  
void *& Collection::
at(size_t _pos)
{
  assert(_pos < size__);
  return arr__[_pos];
}

void * Collection::
at(size_t _pos) const
{
  assert(_pos < size__);
  return arr__[_pos];
}

void *& Collection::
operator [] (size_t _pos)
{
  return at(_pos);
}

void * Collection::
operator [] (size_t _pos) const
{
  return at(_pos);
}

size_t Collection::
indexOf(const void * _ptr) const
{
  size_t n = ~0;
  while (++n < size__) {
    if (arr__[n] == _ptr) {
      return n;
    }
  }
  return ~0;
}

size_t Collection::
indexOf(bool (*_fcmp)(void * _ptr, void *), void * _data) const
{
  size_t n = ~0;
  while (++n < size__) {
    if (_fcmp(arr__[n],_data) == true) {
      return n;
    }
  }
  return ~0;
}

size_t Collection::
indexesOf(const void * _ptr, size_t * _indexes) const
{
  size_t n = ~0;
  size_t nbFound = 0;
  while (++n < size__) {
    if (arr__[n] == _ptr) {
      _indexes[nbFound++] = n;
    }
  }
  return nbFound;
}

size_t Collection::
indexesOf(bool (*_fcmp)(void * _ptr, void *), void * _data, size_t * _indexes) const
{
  size_t n = ~0;
  size_t nbFound = 0;
  while (++n < size__) {
    if (_fcmp(arr__[n],_data) == true) {
      _indexes[nbFound++] = n;
    }
  }
  return nbFound;
}

size_t Collection::
append(void * _ptr)
{
  void ** narr = new void * [size__+1];
  memcpy(narr, arr__, sizeof(void*) * size__);
  narr[size__] = _ptr;
  size__++;
  delete arr__;
  arr__ = narr;
  return size__-1;
}

void * Collection::
extractAt(size_t _pos)
{
  assert(_pos < size__);
  void * oldptr = arr__[_pos];
  if (size__ > 0) {
    for (size_t n = _pos; n < size__-1; n++) {
      arr__[n] = arr__[n+1];
    }
  }
  size__--;
  return oldptr;
}


#ifdef _TEST_
#include <string>

const size_t NTest = 20;

bool recPrefix (void * _ptr, void * _data)
{
  string * s = (string*) _ptr;
  if (s) {
    const char * p = (const char *) _data;
    if (strncmp(s->data(), p, strlen(p)) == 0) {
      return true;
    }
  }
  return false;
}

int main()
{
  // Un tableau de chaines de car.
  Collection tabOfString;

  // remplissage du tableau
  for (size_t i = 0; i < NTest; i++) {
    char buf[512];
    sprintf(buf, "#%d", i);
    tabOfString.append(new string(buf));
  }

  // sortie sur stdout
  for (size_t i = 0; i < NTest; i++) {
    string * s = (string*) tabOfString.at(i);
    cout << s->data() << endl;
  }

  // Recherche de la premiere chaine qui commence par "#1"
  size_t nfound = tabOfString.indexOf(recPrefix, (void*) "#1");
  if (nfound != ~0u) {
    cout << "La premiere chaine qui commence par '#1' est à la position " 
	 << nfound << endl;
  } else {
    cout << "Aucune chaine ne commence par '#1'" << endl;
  }

  // Recherche de toutes les chaines qui commencent par "#1"
  size_t * indexes = new size_t[tabOfString.size()];
  size_t nbfound = tabOfString.indexesOf(recPrefix, (void *) "#1", indexes);
  for (size_t i = 0; i < nbfound; i++) {
    cout << "{" << ((string*) tabOfString.at(indexes[i]))->data() 
	 << "}" << " ";
  }
  cout << endl;

  // nettoyage du tableau
  for (size_t i = 0; i < NTest; i++) {
    delete (string*) tabOfString.at(i);
  }
}

#endif