février
2010
Un article de phertzog
Ce billet est la suite de mon exploration de la démarche TDD appliquée au problème de recherche de l’équilibrium. La première partie (qui décrit aussi en quoi consiste la recherche de l’équilibrium) peut être trouvée sur mon blog :
Démarche TDD – Une première tentative
Lors du dernier billet, nous en étions resté aux cas basiques. Voyons maintenant d’autres tests qui vont nous permettre d’arriver à une solution complète.
Cas du tableau à 2 éléments
Dans le cas d’un tableau à 2 éléments, il y aura un équilibrium si et seulement si il y a au moins un des 2 éléments qui est égal à 0. Le cas ou les 2 éléments sont à 0 est particulier car il repose sur notre convention de prendre l’équilibrium le plus petit en cas de plusieurs équilibriums. On a dons les cas suivants:
- i – 0 => 0
- 0 – j => 1
- i – j => -1
- 0 – 0 => 0
avec i != 0 et j != 0.
Test 04
Au lieu d’écrire 4 tests séparés, nous allons utiliser une fonctionnalité des tests MS Tests qui permet de fournir un jeu de données et de réponses en entrée du test. Le test sera donc exécuté autant de fois qu’il y a de jeux de données. Dans notre cas la source en entrée est un fichier XML. Les autres possibilités offertes sont un fichier CSV soit une base de donnée. Voici le fichier de tests (désolé pour l’affichage, je n’ai pas réussi à le rendre plus lisible sur le blog) :
<?xml version="1.0" encoding="utf-8" ?><tests><test><name>0-0</name> <data>0,0</data> <expected>0</expected> </test><test><name>1-0</name> <data>1,0</data> <expected>0</expected> </test><test><name>0-1</name> <data>0,-1</data> <expected>1</expected> </test><test><name>1-1</name> <data>1,1</data> <expected>-1</expected> </test></tests>
Le Test
Le test en lui même est assez simple
[DeploymentItem("ProblemsTests\\Equilibrium\\TestsData\\2_Elelments_Arrays.xml"), DataSource("Microsoft.VisualStudio.TestTools.DataSource.XML", "|DataDirectory|\\2_Elelments_Arrays.xml", "test", DataAccessMethod.Sequential), TestMethod]
public void Simple_Array_With_2_Elements()
{
string[] input = TestContext.DataRow[1].ToString().Split(new char[]{','});
int[] inputArray = Array.ConvertAll<string, int>(input, delegate(string s) { return int.Parse(s); });
int expected = Convert.ToInt32(TestContext.DataRow[2]);
int actual;
actual = Problems.Equilibrium.Equilibrium.FindEquilibrium(inputArray);
Assert.AreEqual(expected, actual,"Test failed for case {0}", TestContext.DataRow[0]);
}
On remarque quelques nouveautés par rapport au tests précédents.
- Le nom de la méthode est décoré avec « DeploymentItem » qui indique ou se trouve le fichier xml source et d’autres paramètres. Ceci permet d’indiquer que nous avons un test « dirigé par les données » ou « data driven test ». Pour plus de détails concernant la façon de mettre cela en place je vous renvoie au blog suivant :
|VS 2008] Jeux de données XML et CSV pour tests unitaires - Le tableau en entrée et créé à partir de la valeur du noeud « data » que nous convertissons en tableau d’entiers grâce à « Array.ConvertAll ».
- Le résultat attendu est lu à partir du noeud « expected ».
En exécutant le test on a un échec car les cas 3 et 4 ne sont pas correct (ce qui est logique puisque notre implémentation actuelle ne retourne que la valeur 0 pour un tableau non nul. Corrigeons donc notre code?
Le code
Voici une première version du code qui passe tous les tests et qui est naïvement simple.
public static int FindEquilibrium(int[] inputArray)
{
if ((inputArray == null) || (inputArray.Length == 0))
{
return -1;
}
else
{
if (inputArray.Length == 1)
{
return 0;
}
else
{
if (inputArray[1] == 0)
{
return 0;
}
else if (inputArray[0] == 0)
{
return 1;
}
else
{
return -1;
}
}
}
}Ce code fonctionne mais l’imbrication de conditions donne un sentiment de code mal écrit. Tentons d’améliorer les choses. Tant que le tableau n’avait pas plus d’un élément il était possible de donner le résultat en un seul test. A partir de 2 éléments, on voit qu’il faut plusieurs tests. Il est donc temps, je pense, de réfléchir à un algorithme plus proche de la définition. Voici le résultat auquel j’arrive :
public static int FindEquilibrium(int[] inputArray)
{
if (inputArray == null)
{
return -1;
}
else
{
for (int i = 0; i<inputArray.Length; i++)
{
var sommeGauche = 0;
for (int j = 0; j<i; j++)
{
sommeGauche += inputArray[j];
}
var sommeDroite = 0;
for (int k = i + 1; k<inputArray.Length; k++)
{
sommeDroite += inputArray[k];
}
if (sommeGauche == sommeDroite)
{
return i;
}
}
return -1;
}
}Nous avons implémenter le définition de l’équilibrium presque mot pour mot. Nous parcourons les éléments du tableau et additionnons les éléments à gauche de l’élément courant avec les éléments à droite de l’élément courant. On remarquera ici que je n’utilise pas une taille fixe pour le tableau mais bien la taille réelle? Ceci n’est pas une anticipation d’un test futur mais bien une volonté de ne pas utiliser de constante « magique » dans le code. Utiliser directement la valeur « 2 » aurait masqué le fait qu’il s’agit de la taille de mon tableau.
En première intention j’avais mis le bloc implémentant l’algorithme (c’est à dire les 2 boucles imbriquées) le bloc « else » correspondant au cas (taille du tableau > 1). En prenant ensuite un peu de recul j’ai remarqué que les cas tableau à 0 et 1 élément étaient également couverts par la boucle imbriquée. Je pouvais donc retirer les tests « inputArray.Length == 0″ et « inputArray.Length == 1″ ce qui simplifie encore le code.
Cas du tableau à 3 éléments
L’étape suivant consiste à traiter les tableaux à 3 éléments. Cette fois la partie ardue à consister à déterminer les cas de tests pertinents pour éviter d’avoir à faire toutes les combinaisons possibles. J’en suis arrivé à isoler 4 cas qui couvrent (sauf erreur de ma part) toutes les configurations pour un tableau (i,j,k) :
- Somme droite nulle (j+k = 0) : résultat = 0
- Somme droite non nulle (j+k != 0) et somme gauche nulle (i + j = 0) : résultat = 2
- Somme droite non nulle (j+k != 0) et somme gauche non nulle (i+j != 0) et symétrie centrale (i = k) : résultat = 1
- Somme droite non nulle (j+k != 0) et somme gauche non nulle (i+j != 0) et pas de symétrie centrale (i != k) : résultat = ?1
On obtient le jeu de test suivant :
<?xml version="1.0" encoding="utf-8" ?><tests><test><name>Cas 1: somme droite nulle (j+k = 0)</name> <data>145887,14770,-14770</data> <expected>0</expected> </test><test><name>Cas 2: Symetrie centrale (i == k) avec somme droite non nulle (j+k != 0)</name> <data>-54,1,-54</data> <expected>1</expected> </test><test><name>Cas 3 somme gauche nulle (i+j = 0) et somme droite non nulle (j+k != 0)</name> <data>-15,15,1024</data> <expected>2</expected> </test><test><name>Cas 4: aucune symetrie (i != k), somme droite non nulle, somme gauche non nulle </name><data>1,2,3</data> <expected>-1</expected> </test></tests>
Le test
Le code du test est le même que celui du test précédent. Seul le fichier source va changer.
Le code
Ici on constate que tous les cas passent avec succès. Le code fonctionne donc très bien sur les tableaux à 3 éléments.
La suite …
A partir des différents tests mené, j’assume que les combinaisons avec des tableaux de tailles > 3 peuvent se ramener à un des cas de tableau à 3 éléments. Par exemple pour un tableau à 4 éléments (i, j, k, l) si i est l’équilibrium, il sera aussi l’équilibrium du tableau (i, j, k+l) ou (i, j+k, l). Et ainsi de suite. Par sécurité j’ai tout de même rajouté un test avec un fichier contenant quelques tests de tableaux supérieurs à 3. Aucune modification de code n’a été nécessaire. Je vous laisse essayer des cas avec le code fournis. Si vous trouvez une configuration qui n’est pas couverte n’hésitez pas à m’en faire part.
Je considère donc qu’il n’est pas nécessaire de faire plus de tests pour valider le bon fonctionnement du code. Par contre il nous reste quelques tests un peu plus subtils à écrire. Nous verrons cela dans le dernier article de la série.