====== Partie II – Fonction spécialisée======

[[in204:tds:sujets:td3|TD3]]

===== Question n°1 =====

Nous considérons la fonction suivante que nous ajoutons à l’espace de nom ''generic''. 
Expliquez ce qu’elle fait et tester là.

<code cpp>

#include <stdio.h>
#include <random>

....

template<>
void populate_with_randoms(std::vector<std::string>& theVector,
    int theNumberOfValues, int theMinValue, int theMaxValue)
{
    // Initialise le générateur de nombres aléatoires
    // et définit la loi de distribution uniforme.
    std::random_device rd; 
    std::mt19937 generator(rd())
    std::uniform_int_distribution<int> 
        distribution(theMinValue, theMaxValue);

    char buffer[20];

    int width = theMaxValue - theMinValue;
    for(; 
        theNumberOfValues > 0; 
        theNumberOfValues--)
    {
        
        int randValue = distribution(generator);
        std::sprintf(buffer,"%d",randValue);
        std::string stringValue = buffer;
	theVector.push_back(stringValue);
    }
}

</code>

<hidden Correction>

Supposons d'abord que nous souhaitons appelé la fonction ''generic::populate_with_randoms'' en lui passant un tableau de type ''std::string'' avec le code suivant :

<code cpp>
#include <iostream>
#include"simple_sort.hpp"
#include<string>

using namespace std;

int main()
{
    {
        using namespace generic;
        std::vector<std::string> stringValues;

        populate_with_randoms(stringValues, 10, 'A', 'Z');
        print_vector(stringValues);
        simple_sort(stringValues);
        print_vector(stringValues);
    }
    return 0;

</code>

La compilation de ce code génère une erreur à la ligne :

<code cpp>
namespace generic
{
    template<typename T, typename genType = int>
    void populate_with_randoms(
        std::vector<T>& theVector,
      	int theNumberOfValues, genType theMinValue, genType theMaxValue)
    {
        ...
        theVector.push_back(
            (T)distribution(gen));
    }
}
</code>
</hidden>
===== Question n°2 =====
Nous souhaitons pouvoir choisir la fonction de comparaison utilisée dans le ''simple_sort''. Pour l’instant, la fonction de comparaison fait toujours appel à l’opérateur ''>''.

Nous souhaitons utiliser une classe ''traits'' qui fournira l’opération de comparaison. Par défaut, cette opération de comparaison est ''>''.

==== Question n°2.1 ====

Ecrire la classe ''greater_traits'' en complétant ce qui manque dans la classe suivante:

<code cpp>
template<typename T>
struct greater_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
     ...
    }
};
</code>

<hidden Correction>

La classe ''greater_test'' teste si ''aValue > anotherValue'' et retourne ''true'' si la condition est vérifiée et ''false'' si cette condition n'est pas vérifiée.

<code cpp>
template<typename T>
struct greater_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
        return aValue > anotherValue;
    }
};
</code>

La méthode ''is_greater'' est précédée du mot clé ''static'', ce qui signifie que cette méthode est une méthode statique aussi appellée méthode de classe. A la différence des méthodes habituelles de l'objet, cette méthode ne peut accéder qu'aux champs statique statiques de la classe. En conséquence, cette méthode n'a pas besoin qu'un objet soit créé pour pouvoir être appelé. Elle peut simplement être appellée selon la syntaxe suivante :

<code cpp>

int main()
{
    greater_traits<int>::is_greater(3, 2);
}
</code>

</hidden>



==== Question n°2.2 ====

Modifier la fonction ''simple_sort'' pour qu’elle prenne un paramètre de type supplémentaire 
qui est la classe fournissant l’opération de comparaison.

<hidden Correction>

Nous ajoutons à la liste des paramètres de types de la fonction, un paramètre supplémentaire ''sortTraits'' qui correspond au type d'une classe qui doit exposer une méthode statique permettant de tester si une valeur est plus grande qu'une autre valeur pour des valeurs de types ''T'' et ayant pour nom ''is_greater''.

Cependant, ce paramètre de type est facultatif, par défaut, nous considérons que ce paramètre est initialisé à ''greater_traits<T>''.

Maintenant, nous avons un premier souci. Au moins un paramètre de la fonction doit faire référence à un paramètre de types. Cependant, nous n'avons aucun paramètre qui n'a le type ''sortTraits''. Enfin, nous ne créons aucun objet de type ''sortTraits'' que nous allons passer en paramètre. Pour contourner ce problème, nous allons ajouter un paramètre supplémentaire à la fonction qui sera un pointeur sur un objet de type ''sortTraits'' et qui sera initialisé à ''NULL''. 
<code cpp>
    void simple_sort(std::vector<T>& theValues, sortTraits* = NULL)
</code>

Comme nous n'utilisons jamais ce paramètre, nous ne donnons même pas de nom à ce paramètre ! Il n'est là que pour respecter la règle qui impose que tout paramètre de type doit être référencé directement ou undirectement par au moins un paramètre de la fonction.

Nous modifions ensuite l'opération de comparaison pour désormais faire appel à la méthode statique ''is_greater'' de la classe de type ''sortTraits''.

<code cpp>
namespace generic
{
    ...
 
    template<typename T, typename sortTraits = greater_traits<T>> 
    void simple_sort(std::vector<T>& theValues, sortTraits* = NULL)
    {
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(sortTraits::is_greater(theValues[i], theValues[j]))
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
    ...
}
</code>
</hidden>

==== Question n°2.3 ==== 

Proposer une classe ''lower_traits'' qui inverse l’ordre de tri.

<hidden Correction>

Il suffit de dupliquer la classe ''greater_traits'' et de remplacer l'opérateur ''>'' par l'opérateur ''<''.

<code cpp>
template<typename T>
struct lower_traits
{
public:
    static bool is_greater(T aValue, T anotherValue) 
    {
        return aValue > anotherValue;
    }
};
</code>
</hidden>

==== Question n°2.4 ====

Tester votre code sur l’exemple suivant :

<code cpp>

#include"generic_sort.hpp"
#include<iostream>

int main()
{
    std::vector<int> array;
    generic::populate_with_randoms(array, 10, 1, 10);
    generic::print_vector(array);
    std::cout << "\n";
    generic::simple_sort(array);
    generic::print_vector(array);
    std::cout << "\n";
    generic::simple_sort<int, generic::lower_traits<int>>(array);
    generic::print_vector(array);
    return 0;
}
</code>

<hidden Compléments>

Nous avons vu comment paramètrer la fonction ''simple_sort'' par un opérateur de comparaison. Cependant, l'opérateur de comparaison est un opérateur qui expose une méthode ''statique''. Nous ne pouvons pas choisir un opérateur de conversion dynamique, ie. dont nous pouvons au moment de l'exécution décider de l'ordre, si c'est un tri ascendant ou descendant. Nous pourrions imagine une telle classe.

<code cpp>
template<typename T>
struct greater_or_lower_traits
{
private:
    bool m_isAscending;
    
public:
    greater_or_lower_traits():
        m_isAscending(false) {}
    explicit greater_or_lower_traits(bool isAscending):
        m_isAscending(isAscending) {}
    
    set(bool isAscending) { m_isAscending = isAscending; }
    get() const { return m_isAscending ; }
    
    bool is_greater(T aValue, T anotherValue) 
    {
        if(!m_isAscending)
            return aValue < anotherValue;
        return aValue > anotherValue;
    }
};
</code>

Sauf que dans ce cas, il est nécessaire d'avoir un champ. Donc la méthode ''is_greater'' ne peut pas être une méthode de classe. 

Pour ce faire, nous modifions le contrat relatif à la classe ''traits'' définissant l'ordre sur les valeurs de type ''traits'' comme suit :
  * la méthode ''is_greater'' n'est plus une méthode de classe.
  * l'objet expose __**un constructeur par défaut**__.
  * l'objet supporte la recopie.

Nous devons modifier en conséquence les classes ''greater_traits'' et ''lower_traits'' pour transformer la méthode ''statique'' en méthode standard :

<code cpp>
template<T>
struct greater_traits
{
    public bool is_greater(T aValue, T anotherValue) const
    {
        return aValue > anotherValue;
    }
};
template<T>
struct lower_traits
{
    public bool is_lower(T aValue, T anotherValue) const
    {
        return aValue < anotherValue;
    }
};
</code>

Avec ces deux conditions, il est possibles de redéfinir la définition de la fonction ''simple_sort'' comme suit :

<code cpp>
namespace generic
{
    ...
 
    template<typename T, typename sortTraits = greater_traits<T>> 
    void simple_sort(std::vector<T>& theValues,
        sortTraits traits = sortTraits())
    {    
        int length = theValues.size();
        for(int i = 0; i < length-1; i ++)
        {
            for(int j= i+1; j < length; j++)
            {
                if(traits.is_greater(theValues[i], theValues[j]))
                    std::swap(theValues[i], theValues[j]);
            }
        }
    }
    ...
}
</code>

Nous ajoutons un paramètre supplémentaire à la fonction ''simple_sort'' qui est le paramètre ''traits''. Ce paramètre a pour type ''sortTraits'' et correspond normalement à une instance d'une classe traits qui fournit la méthode ''is_greater'' tel que définit précédemment. Cependant, il n'est pas nécessaire de passer ce paramètre quand nous utilisons les classes traits ''greater_traits'' ou ''lower_traits''. Dans ce cas, nous affectons à ce paramètre l'objet de type ''sortTraits'' qui est initialisé par le constructeur par défaut. 

<code cpp>
    std::vector<int> vector;
    ...
    simple_sort(vector);       
</code>

Dans ce cas, quand le compilateur compile le code ''simple_sort'', il peut inférer que :
  * T dénote le type entier ''int'',
  * aucun argument n'est passé pour le paramètre ''traits'', le type n'est pas résolu.
Il reste donc à résoudre le type ''sortTraits''.
  * aucun type n'est passé en paramètre à la fonction ''simple_sort''
  * un type par défaut est spécifié pour le type ''sortTraits''. Dans ce cas, le compilateur affecte à ''sortTraits'' le type par défaut, c'est-à-dire ''greater_traits<T>'' avec ''T==int'' qui se transforme en ''greater_traits<int>''.
Une fois le type ''sortTraits'' inféré, il ne reste plus qu'à affecter à ''traits'' la valeur par défaut. Cette valeur par défaut est défini comme étant égal une instance d'objet de type ''sortTraits'' initialisé par son constructeur par défaut : ''sortTraits()''. Ce qui dans le cas correspond à ''greater_traits<int>()''. Le compilateur génère donc l'appel suivant :

<code cpp>
    std::vector<int> vector;
    ...
    simple_sort<int, greater_traits<int>)(vector, greater_traits<int>());       
</code>

Considérons désormais l'appel suivant:

<code cpp>
    std::vector<int> vector;
    ...
    simple_sort<int, lower_traits<int>>(vector);       
</code>

Dans ce cas, quand le compilateur compile le code ''simple_sort'', il peut inférer que :
  * T dénote le type entier ''int'',
  * aucun argument n'est passé pour le paramètre ''traits'', le type n'est pas résolu.
Il reste donc à résoudre le type ''sortTraits''.
  * le type ''lower_traits<int>'' est passé en paramètre à la fonction ''simple_sort''. Dans ce cas, le compilateur affecte à ''sortTraits'' le type par défaut, c'est-à-dire ''lower_traits<int>''.

Une fois le type ''sortTraits'' inféré, il ne reste plus qu'à affecter à ''traits'' la valeur par défaut. Cette valeur par défaut est défini comme étant égal une instance d'objet de type ''sortTraits'' initialisé par son constructeur par défaut : ''sortTraits()''. Ce qui dans le cas correspond à ''lower_traits<int>()''. Le compilateur génère donc l'appel suivant :


<code cpp>
    std::vector<int> vector;
    ...
    simple_sort<int, lower_traits<int>>(vector, lower_traits<int>());       
</code>


Enfin, si je souhaite effectuer un appel en passant une instance de l'objet ''greater_or_lower_traits'', il suffit d'écrire le code suivant :

<code cpp>
    std::vector<int> vector;

    greater_or_lower_traits traits(true);
    simple_sort(vector, traits);
    traits.set(false);       
    simple_sort(vector, traits);
</code>

Mais il est tout à fait possible d'écrire aussi :

<code cpp>
    std::vector<int> vector;

    simple_sort<int, greater_or_lower_traits <int>>(vector);
</code>

qui deviendra au moment de la compilation :

<code cpp>
    std::vector<int> vector;

    simple_sort<int, greater_or_lower_traits <int>>(vector, 
        greater_or_lower_traits<int>());
</code>


</hidden>