Pe parcursul laboratoarelor și temelor ați folosit structuri de date oferite de API-ul Java. În cadrul acestui laborator le vom aprofunda.

• lucrul cu cele trei tipuri principale de colecții din Java: List, Set, Map
• cunoașterea diferențelor dintre implementările colecțiilor (eficiență, sortare, ordonare etc)
• compararea elementelor unor colecții
• contractul equals-hashcode

În pachetul java.util (pachet standard din JRE) existǎ o serie de clase pe care le veti găsi folositoare. Collections Framework este o arhitectură unificată pentru reprezentarea şi manipularea colecţiilor. Ea conţine:

• interfeţe: permit colecţiilor sǎ fie folosite independent de implementǎrile lor
• implementǎri
• algoritmi metode de prelucrare (căutare, sortare) pe colecţii de obiecte oarecare. Algoritmii sunt polimorfici: un astfel de algoritm poate fi folosit pe implementări diferite de colecţii, deoarece le abordeazǎ la nivel de interfaţǎ.

Colecţiile oferǎ implementǎri pentru urmǎtoarele tipuri:

• Set (elemente neduplicate)
• List (o mulțime de elemente)
• Map (perechi cheie-valoare)

Existǎ o interfaţǎ, numitǎ Collection, pe care o implementeazǎ majoritatea claselor ce desemneazǎ colecţii din java.util. Explicaţii suplimentare gǎsiţi pe Java Tutorials - Collection

Exemplul de mai jos construieşte o listǎ populatǎ cu nume de studenţi:

Collection names = new ArrayList();
names.add("Andrei");
names.add("Matei");

Colecţiile pot fi parcurse (element cu element) folosind:

• iteratori
• o construcţie for specialǎ (cunoscutǎ sub numele de for-each)

Un iterator este un obiect care permite traversarea unei colecţii şi modificarea acesteia (ex: ştergere de elemente) în mod selectiv. Puteţi obţine un iterator pentru o colecţie, apelând metoda sa iterator(). Interfaţa Iterator este urmǎtoarea:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); // optional
}

Exemplu de folosire a unui iterator:

Collection<Double> col  = new ArrayList<Double>();
Iterator<Double> it = col.iterator();
 
while (it.hasNext()) {
    Double backup = it.next();
    // apelul it.next() trebuie realizat înainte de apelul it.remove()
    if (backup < 5.0) {
        it.remove();
    }
}

Apelul metodei remove() a unui iterator face posibilă eliminarea elementului din colecţie care a fost întors la ultimul apel al metodei next() din acelaşi iterator. În exemplul anterior, toate elementele din colecţie mai mici decât 5 for fi şterse la ieşirea din bucla while.

Aceastǎ construcţie permite (într-o manierǎ expeditivǎ) traversarea unei colecţii. for-each este foarte similar cu for. Urmǎtorul exemplu parcurge elementele unei colecţii şi le afişeazǎ.

Collection collection = new ArrayList();
for (Object o : collection)
    System.out.println(o);

Construcţia for-each se bazeazǎ, în spate, pe un iterator, pe care îl ascunde. Prin urmare nu putem şterge elemente în timpul iterǎrii. În aceastǎ manierǎ pot fi parcurşi şi vectori oarecare. De exemplu, collection ar fi putut fi definit ca Object[].

Fie urmǎtoarea porţiune de cod:

c.add("Test");
 
Iterator it  = c.iterator();
 
while (it.hasNext()) {   
    String s = it.next();         // ERROR: next() returns an Object and it's needed an explicit cast to String
    String s = (String)it.next(); // OK
}

Am definit o colecţie c, de tipul ArrayList (pe care îl vom examina într-o secţiune urmǎtoare). Apoi, am adǎugat în colecţie un element de tipul String. Am realizat o parcurgere folosind un iterator, şi am încercat obţinerea elementului nostru folosind apelul: String s = it.next();. Funcţia next însǎ întoarce un obiect de tip Object. Prin urmare apelul va eşua. Varianta corectǎ este String s = (String)it.next();. Am fi putut preciza, din start, ce tipuri de date dorim într-o colecţie:

Collection<String> c = new ArrayList<String>();
c.add("Test");
c.add(2);      // ERROR!
Iterator<String> it = c.iterator();
 
while (it.hasNext()) {   
     String s = it.next();
}

Mai multe detalii despre acest subiect găsiți in laboratorul următor: Genericitate

O listǎ este o colecţie ordonatǎ. Listele pot conţine elemente duplicate. Pe langǎ operaţiile moştenite de la Collection, interfaţa List contine operaţii bazate pe pozitie (index), de exemplu: set, get, add la un index, remove de la un index.

List<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Orange", "Grape"));
fruits.add("Apple");               // metodă moștenită din Collection 
fruits.add(2, "Pear");             // [Apple, Orange, Pear, Grape, Apple]
System.out.println(fruits.get(3)); // Grape
fruits.set(1, "Cherry");           // [Apple, Cherry, Pear, Grape, Apple]
fruits.remove(2);
System.out.println(fruits);        // [Apple, Cherry, Grape, Apple]

Alǎturi de List, este definitǎ interfaţa ListIterator, ce extinde interfaţa Iterator cu metode de parcurgere în ordine inversǎ. List posedǎ douǎ implementǎri standard:

• ArrayList - implementare sub formǎ de vector. Accesul la elemente se face în timp constant: O(1)
• LinkedList - implementare sub formǎ de listǎ dublu înlǎnţuitǎ. Prin urmare, accesul la un element nu se face în timp constant, fiind necesarǎ o parcurgere a listei: O(n).

Printre algoritmii implementaţi se numără:

• sort - realizeazǎ sortarea unei liste
• binarySearch - realizaeazǎ o cǎutare binarǎ a unei valori într-o listǎ sortatǎ

În general, algoritmii pe colecţii sunt implementaţi ca metode statice în clasa Collections.

Iatǎ un exemplu de folosire a sortǎrii:

List<Integer> l = new ArrayList<Integer>();
l.add(5);
l.add(7);
l.add(9);
l.add(2);
l.add(4);
 
Collections.sort(l);
System.out.println(l);

Mai multe detalii despre algoritmi pe colecţii gǎsiţi pe Java Tutorials - Algoritmi pe liste

Rularea exemplului de sortare ilustrat mai sus aratǎ cǎ elementele din ArrayList se sorteazǎ crescator. Ce se întâmplǎ când dorim sǎ realizǎm o sortare particularǎ pentru un tip de date complex? Spre exemplu, dorim sǎ sortǎm o listǎ ArrayList<Student> dupǎ media anilor. Sǎ presupunem cǎ Student este o clasǎ ce conţine printre membrii sǎi o variabilǎ ce reţine media anilor. Acest lucru poate fi realizat folosind interfeţele:

• Comparable
• Comparator

Un Set (mulţime) este o colecţie ce nu poate conţine elemente duplicate. Interfaţa Set conţine doar metodele moştenite din Collection, la care adaugǎ restricţii astfel încât elementele duplicate sǎ nu poatǎ fi adǎugate. Avem trei implementǎri utile pentru Set:

• HashSet: memoreazǎ elementele sale într-o tabelǎ de dispersie (hash table); este implementarea cea mai performantǎ, însǎ nu avem garanţii asupra ordinii de parcurgere. Doi iteratori diferiţi pot parcurge elementele mulţimii în ordine diferitǎ.
• TreeSet: memoreazǎ elementele sale sub formǎ de arbore roşu-negru; elementele sunt ordonate pe baza valorilor sale. Implementarea este mai lentǎ decat HashSet.
• LinkedHashSet: este implementat ca o tabelǎ de dispersie. Diferenţa faţǎ de HashSet este cǎ LinkedHashSet menţine o listǎ dublu-înlǎnţuitǎ peste toate elementele sale. Prin urmare (şi spre deosebire de HashSet), elementele rǎmân în ordinea în care au fost inserate. O parcurgere a LinkedHashSet va gǎsi elementele mereu în aceastǎ ordine.

Explicaţii suplimentare gǎsiti pe Java Tutorials - Set.

Un Map este un obiect care mapeazǎ chei pe valori. Într-o astfel de structurǎ nu pot exista chei duplicate. Fiecare cheie este mapatǎ la exact o valoare. Map reprezintǎ o modelare a conceptului de funcţie: primeşte o entitate ca parametru (cheia), şi întoarce o altǎ entitate (valoarea). Cele trei implementǎri pentru Map sunt:

• HashMap
• TreeMap
• LinkedHashMap

Particularitǎţile de implementare corespund celor de la Set. Exemplu de folosire:

class Student {
    String name;
    float avg;
 
    public Student(String name, float avg) {
        this.name = name;
        this.avg  = avg;
    }
 
    public String toString() {
        return "[" + name + ", " + avg + "]";
    }
}
 
public class Test {
    public static void main(String[] args) {
 
        Map<String,Student> students = new HashMap<String, Student>();
 
        students.put("Matei",  new Student("Matei",  4.90F));
        students.put("Andrei", new Student("Andrei", 6.80F));
        students.put("Mihai",  new Student("Mihai",  9.90F));
 
        System.out.println(students.get("Mihai"));
 
        // adaugăm un element cu aceeași cheie
        System.out.println(students.put("Andrei", new Student("", 0.0F))); 
        // put(...) întoarce elementul vechi
 
        // si îl suprascrie
        System.out.println(students.get("Andrei"));
 
        // remove(...) returnează elementul șters
        System.out.println(students.remove("Matei"));
 
        // afișăm structura de date
        System.out.println(students);
    }
}

Interfaţa Map.Entry desemneazǎ o pereche (cheie, valoare) din map. Metodele caracteristice sunt:

• getKey: întoarce cheia
• getValue: întoarce valoarea
• setValue: permite stabilirea valorii asociatǎ cu aceastǎ cheie

O iterare obişnuitǎ pe un map se va face în felul urmǎtor:

for (Map.Entry<String, Student> entry : students.entrySet())
    System.out.println(entry.getKey() + " has the following average grade: " + entry.getValue().getAverage());

În bucla for-each de mai sus se ascunde, de fapt, iteratorul mulţimii de perechi, întoarse de entrySet. Explicaţii suplimentare gǎsiţi pe Java Tutorials - Map.

Queue defineşte operaţii specifice pentru cozi:

• inserţia unui element
• ştergerea unui element
• operaţii de “inspecţie” a cozii

Implementǎri utilizate frecvente pentru Queue:

• LinkedList: pe lângǎ List, LinkedList implementeazǎ şi Queue
• PriorityQueue;

Explicaţii suplimentare gǎsiţi pe Java Tutorials - Queue

• Pachetul java.util oferă implementări ale unor stucturi de date și algoritmi pentru manipularea lor: ierarhiile Collection și Map și clasa cu metode statice Collections.
• Parcurgerea colecţiilor se face în două moduri:
  • folosind iteratori (obiecte ce permit traversarea unei colecţii şi modificarea acesteia)
  • folosind construcţia speciala for each (care nu permite modificarea colecţiei in timpul parcurgerii sale)
• Interfaţa List - colecţie ordonată ce poate conţine elemente duplicate.
• Interfaţa Set - colecţie ce nu poate conţine elemente duplicate. Există trei implementǎri utile pentru Set: HashSet (neordonat, nesortat), TreeSet (set sortat) și LinkedHashSet (set ordonat)
• Interfaţa Map - colecţie care mapează chei pe valori. Într-o astfel de structurǎ nu pot exista chei duplicate. Cele trei implementǎri pentru Map sunt HashMap (neordonat, nesortat), TreeMap (map sortat) și LinkedHashMap (map ordonat)
• Contractul equals - hashcode: dacă obj1 equals obj2 atunci hashcode obj1 == hascode obj2. Dacă implementați equals implementați și hashcode daca doriți să folosiți acele obiecte în colecții bazate pe hashuri (e.g. HashMap, HashSet).

1. (1p) Instanţiati o colecţie care sǎ nu permitǎ introducerea elementelor duplicate, folosind o implementare corespunzǎtoare din bibliotecă. La introducerea unui element existent, semnalaţi eroare. Colecţia va reţine String-uri şi va fi parametrizatǎ.
2. (2p) Creaţi o clasǎ Student.
   1. Adǎugaţi urmǎtorii membri:
      • câmpurile nume (de tip String) şi medie (de tip float)
      • un constructor care îi iniţializeazǎ
      • metoda toString.
   2. Folosiţi codul de la exerciţiul anterior şi modificaţi-l astfel încât colecţia aleasǎ de voi sǎ reţinǎ obiecte de tip Student. Testaţi prin adǎugare de elemente duplicate, având aceleaşi valori pentru toate câmpurile, instanţiindu-le, de fiecare datǎ, cu new. Ce observaţi?
   3. Prelucraţi implementarea de mai sus astfel încât colecţia sǎ reprezinte o tabelǎ de dispersie, care calculează codul de dispersie al elementelor dupǎ un criteriu ales de voi (puteţi suprascrie funcţia hashCode).
      • În Student suprascrieți metoda equals astfel încât să se ţină cont de câmpurile clasei, şi încercaţi din nou. Ce observaţi?
   • Hint: Set.add, Object.equals, Object.hashCode
3. (2p) Plecând de la implementarea exerciţiului anterior, realizaţi urmǎtoarele modificǎri:
   • Supraîncǎrcaţi, în clasa Student, metoda equals, cu o variantǎ care primeşte un parametru Student, şi care întoarce întotdeauna false.
   • Testaţi comportamentul prin crearea unei colecţii ce conţine instanţe de Student şi iteraţi prin această colecţie, afişând la fiecare pas element.equals(element) şi ((Object)element).equals(element) (unde element este numele de variabilă ales pentru fiecare element al colecţiei). Cum explicaţi comportamentul observat? Dacă folosiţi un iterator, acesta va fi şi el parametrizat.
4. (3p) Creați clasa Gradebook, de tip Map, pentru reţinerea studenţilor dupǎ medie: cheile sunt mediile și valorile sunt liste de studenți. Gradebook va menţine cheile ordonate descrescǎtor. Extindeţi o implementare potrivitǎ a interfeţei Map, care sǎ permitǎ acest lucru.
   1. Caracteristicile clasei definite sunt:
      1. Cheile pot avea valori de la 0 la 10 (corespunzǎtoare mediilor posibile). Verificați acest lucru la adăugare.
      2. Valoarea asociată fiecǎrei chei va fi o listǎ (List) care va reţine toţi studenţii cu media rotunjitǎ egalǎ cu cheia. Considerǎm cǎ un student are media rotunjitǎ 8 dacǎ media sa este în intervalul [7.50, 8.49].
   2. Implementați un Comparator pentru stabilirea ordinii cheilor. Gradebook va primi un parametru de tip Comparator în constructor și îl va da mai departe constructorului clasei moștenite.
   3. Definiţi în clasǎ metoda add(Student), ce va adǎuga un student în lista corespunzǎtoare mediei lui. Dacǎ, în prealabil, nu mai existǎ niciun student cu media respectivǎ (rotunjitǎ), atunci lista va fi creatǎ la cerere.
   4. Testați clasa:
      1. instanțiați un obiect Gradebook și adăugați in el câţiva studenţi.
      2. iteraţi pe Gradebook şi sortaţi alfabetic fiecare listǎ de studenţi pentru fiecare notă. Pentru a sorta, se va folosi metoda Collections.sort, iar clasa Student va implementa o interfață care specifică modul în care sunt comparate elementele.
         • clasa Student va implementa interfaţa Comparable, suprascriind metoda compareTo.
5. (2p) Creaţi o clasǎ care moşteneşte HashSet<Integer>.
   • Definiţi în aceastǎ clasǎ o variabilǎ membru care reţine numǎrul total de elemente adǎugate. Pentru a contoriza acest lucru, suprascrieți metodele add şi addAll. Pentru adǎugarea efectivǎ a elementelor, folosiţi implementǎrile din clasa pǎrinte (HashSet).
   • Testaţi, folosind atât add cât şi addAll. Ce observaţi? Corectaţi dacǎ este cazul.
   • Modificaţi implementarea astfel încât clasa voastrǎ sǎ moşteneascǎ LinkedList<Integer>. Ce observaţi? Ce concluzii trageţi?
   • Hint: Collection.add, Collection.addAll.
   • Hint: implementarea addAll din sursele pentru HashSet şi LinkedList.

• PDF laborator