Partie III – Algorithmes génériques

La classe doit exposée une méthode permettant de déterminer si un élément est plus grand que l'autre. Il peut s'agit soit d'une méthode testant si un élément est plus grand que l'autre :

class Base
{
public: 
    virtual bool isGreater(const Base&) const = 0; 
        // Retourne true si l'objet courant est plus grand.
    ...
};

Nous pouvons ajouter éventuellement des méthodes complémentaires comme :

    virtual bool isGreaterOrEqual(const Base&) const = 0; 
    virtual bool isLess(const Base&) const = 0; 
    virtual bool isLessOrEqual(const Base&) const = 0; 
    virtual bool isEqual(const Base&) const = 0; 
    virtual bool isNotEqual(const Base&) const = 0; 

Voire éventuellement une fonction compareTo:

    virtual int compareTo(const Base&) const = 0;
       // retourne -1 si l'instance courante est plus petite que l'instance passée en paramètre
       // retourne 0 si elles sont égales
       // retourne 1 si l'instance courante est plus grande que l'instance passée en paramètre.

Il suffit d'ajouter la méthode suivante:

class Base
{
    ...
public:
    ...
    virtual void print() const = 0;
 
}

Il suffit d'énumérer les éléments dans le tableau ou dans le containeur.

Nous pouvons faire une version orientée tableau qui ressemblera à cette version.

void print(std::vector<Base*> anArray) {

  std::cout << "[";
  int lastIndex = anArray.size()-1;
  if(lastIndex >= 0)
  {
      for(int i = 0; i < lastIndex; i++)
      {
          anArray[i]->print(); 
          std::cout << ", ";
      }
      anArray[lastIndex]->print(); 
  }
  std::cout << "]";

}

Si nous souhaitons être un peu plus “C++” dans l'esprit, nous accéderons par des itérateurs.

template<typename iterator>
void print(iterator theStart, iterator theEnd)
{
    std::cout << "[";
    if (theStart != theEnd)
    {
        *theStart->print();
        theStart++;
        while (theStart != theEnd)
        {
            std::cout << ", ";
            *theStart->print();
        }
        std::cout << "]";
    }
}

En plus de contenir le champ entier m_value, la classe doit définir le constructeur par défaut, le constructeur de conversion d'une valeur de type int vers l'objet Entier ainsi que la conversion d'un objet Entier vers une valeur de type int.

class Entier : public Base
{
private:
    int m_value;
public:
    Entier() : m_value(0) {}
    Entier(int aValue): m_value(aValue) {}
    operator int() { return m_value; }
 
    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unEntier) const
    {
        return m_value > dynamic_cast<const Entier&>(unEntier).m_value;
    }
};

En plus, il faut définir les fonctions print et isGreater. La fonction print se contente d'afficher le contenu de l'entier sur la console, la fonction isGreater est plus complexe. En effet, l'argument a comme type un type Base et non pas un type Entier. Il va falloir convertir ce type vers un type Entier qui est un type hérité, c'est pour cela que nous faisons un dynamic_cast<const Entier&>(unEntier) qui va essayer de convertir si le paramètre unEntier hérite bien de Entier ou est un Entier. Sinon, un exception std::bad_cast sera lancé si la conversion n'est pas possible.

std::vector<Base*> create_integer_array(size_t theNumberOfValues)
{
    std::vector<Base*> result;
    result.resize(theNumberOfValues);
    for (int i = 0; i < theNumberOfValues; i++)
        result[i] = new Entier(i);
    return result;
}

La fonction initialise un générateur de nombre aléatoire ainsi qu'une distribution uniforme pour des entiers entre theMinValue et theMaxValue. Elle utilise ensuite ce générateur couplé à la distribution pour initialiser les theNumberOfValues éléments du tableau.

La seule ligne à modifier est relative à la comparaison, au lieu d'utiliser l'opérateur de comparaison >, nous faisons un appel à la méthode isGreater, ce qui donne le code suivant :

void insertion_sort(std::vector<Base*>& anArray)
{
    for (int i = 0; i < anArray.size(); i++)
    {
        for (int j = i + 1; j < anArray.size(); j++)
        {
            if (anArray[i]->isGreater(*anArray[j]))
                std::swap(anArray[i], anArray[j]);
        }
    }
}

Pour tester, nous allons écrire la fonction suivante :

void testTriEntier()
{
	std::vector<Base*> entiers = create_random_integer_array(10, -100, 100);
	print(entiers);
	std::cout << std::endl;
	insertion_sort(entiers);
	print(entiers);
	std::cout << std::endl;
}

Par analogie à la classe Entier, nous créons la classe réel comme suit :

class Reel : public Base
{
private:
    double m_value;
public:
    Reel() : m_value(0) {}
    Reel(double aValue) : m_value(aValue) {}
    operator double() { return m_value; }
 
    void print() const { std::cout << m_value; }
    bool isGreater(const Base& unReel) const
    {
        return m_value > dynamic_cast<const Reel&>(unReel).m_value;
    }
};

Pour tester, nous utiliserons une fonction similaire à la fonction suivante:

void testTriReel()
{
	std::vector<Base*> reels = create_random_double_array(10, -1, 1);
	print(reels);
	std::cout << std::endl;
	insertion_sort(reels);
	print(reels);
	std::cout << std::endl;
}