Problema 1: Test FillAlg [Lab 14, 150E]

Un program implementeaza un algoritm de umplere (fill) a unei retele. Programul creeaza o retea (matrice) patratica de dimensiune NxN. Fiecare celula din retea este initializata cu un numar pozitiv. Algoritmul de umplere incepe cu celula din centrul retelei. Aceasta este marcata ("filled"). Dupa aceea programul cauta in mod repetat un vecin al celulelor marcate care sa aiba cea mai mica valoare si il marcheaza. Un vecin este o celula adiacenta orizontal sau vertical cu o celula marcata. In cazul in care exista mai multi vecini cu valoare minima, este ales unul dintre ei.

Procesul continua pana cand regiunea marcata atinge granitele matricei (ultima celula marcata se gaseste pe prima linie, prima coloana, ultima linie sau ultima coloana).

Exemplu: presupunem ca programul ruleaza pe o retea de dimensiuni 5x5 avand valorile de mai jos.

Este "umpluta" celula din centru (marcata cu un "X"):

          V
+---+---+---+---+---+
| 2 | 1 | 2 | 2 | 0 |
+---+---+---+---+---+
| 3 | 4 | 1 | 1 | 3 |
+---+---+---+---+---+
| 1 | 3 | X | 4 | 0 | <
+---+---+---+---+---+
| 0 | 2 | 3 | 1 | 4 |
+---+---+---+---+---+
| 4 | 0 | 4 | 2 | 4 |
+---+---+---+---+---+

In prima iteratie, cea mai mica valoare adiacenta unui "X" este cea de deasupra centrului, deci celula corespunzatoare va fi "umpluta":

          V
+---+---+---+---+---+
| 2 | 1 | 2 | 2 | 0 |
+---+---+---+---+---+
| 3 | 4 | X | 1 | 3 | <
+---+---+---+---+---+
| 1 | 3 | X | 4 | 0 |
+---+---+---+---+---+
| 0 | 2 | 3 | 1 | 4 |
+---+---+---+---+---+
| 4 | 0 | 4 | 2 | 4 |
+---+---+---+---+---+

Acum sunt sase celule adiacente celulelor "umplute" (diagonalele nu se iau in considerare). Dintre acestea, celula aflata la dreapta ultimei celule marcate are cea mai mica valoare, deci va fi urmatoarea marcata.

                                                                          
              V
+---+---+---+---+---+
| 2 | 1 | 2 | 2 | 0 |
+---+---+---+---+---+
| 3 | 4 | X | X | 3 | <
+---+---+---+---+---+
| 1 | 3 | X | 4 | 0 |
+---+---+---+---+---+
| 0 | 2 | 3 | 1 | 4 |
+---+---+---+---+---+
| 4 | 0 | 4 | 2 | 4 |
+---+---+---+---+---+

Acum trebuie luate in considerare sapte celule: doua cu valoarea "4", trei cu valoarea "3" si doua cu valoarea "2". Programul alege in mod arbitrar una dintre celulele care contin valoarea "2".

          V
+---+---+---+---+---+
| 2 | 1 | X | 2 | 0 | <
+---+---+---+---+---+
| 3 | 4 | X | X | 3 |
+---+---+---+---+---+
| 1 | 3 | X | 4 | 0 |
+---+---+---+---+---+
| 0 | 2 | 3 | 1 | 4 |
+---+---+---+---+---+
| 4 | 0 | 4 | 2 | 4 |
+---+---+---+---+---+

Deoarece regiunea umpluta atinge acum granitele retelei, algoritmul se opreste si returneaza numarul celulelor umplute, adica 4.

Vi se propun mai multe implementari java pentru algoritmul de umplere (FillA..FillF). Fiecare dintre acestea implementeaza interfata IFill. Clasa World implementeaza reteaua. Testati implementarile FillA, FillB...FillF si identificati greselile (bug-urile) existente in fiecare. Bug-urile trebuie doar identificate, nu si corectate.

Pentru testare folositi JUnit. Punctul de plecare il constituie clasa FillTest. Extindeti aceasta clasa prin adaugarea de noi cazuri de test astfel incat sa scoateti in evidenta bug-urile.

Clasa FillTest primeste un parametru in linia de comanda care specifica care dintre implementari va fi testata. De exemplu

FillTest A

va avea ca efect testarea implementarii FillA.

Creati un fisier numit fillbugs.txt care sa descrie bug-urile descoperite. O descriere a unui bug trebuie sa fie o singura propozitie si trebuie sa includa la sfarsit, intre paranteze, numele metodei/metodelor de test care au descoperit bug-ul. Exemplu:

FillF
-pozitia de inceput este (0,0) si nu centrul retelei (testFillOneDirection)

Bug-urile corespunzatoare unei implementari vor fi grupate:

FillA
-descriere bug 1
-descriere bug 2
...

FillB
-descriere bug 1
-descriere bug 2
...

...

Fisiere:

• FillTest.java
• World.java
• IFill.java
• FillA.class
• FillB.class
• FillC.class
• FillD.class
• FillE.class
• FillF.class
  
• [all-files]

Notarea va lua in considerare cat de temeinic au fost testate cele 6 clase, precum si calitatea generala a codului. Puteti pierde puncte pentru functii de test care duplica acelasi caz de test. Scopul este crearea unui numar minim de functii de test care sa testeze temeinic cele 6 clase.

De predat: o arhiva zip care sa contina fisierele FillTest.java si fillbugs.txt.