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. (2p) În scheletul de laborator, aveți un fișier cu o clasă (Student), care are trei membri: name (String), surname (String), id (long) și averageGrade (double) - media unui student.
   • Clasa Student va implementa interfața Comparable<Student>, folosită la sortări, implementând metoda compareTo. În metoda compareTo, studenții vor fi comparați mai întâi după medie, apoi după numele de familie, apoi dupa prenume (adică dacă doi studenți au aceeași medie, ei vor fi comparați după numele de familie și dacă au același nume de familie, atunci vor fi comparați după prenume). Recomandăm să suprascrieți metoda toString, pentru a putea afișa datele despre un student.
2. (1p) Creați 5 obiecte de tip Student și adăugați-le într-un ArrayList, pe care să îl sortați (hint: Collections.sort), apoi afisați conținutul din ArrayList.
3. (2p) Adăugați ArrayList-ul definit la subpunctul anterior într-un PriorityQueue (hint: Collection.addAll), care folosește un Comparator, unde elementele sunt sortate crescător după id (aici puteti folosi Long.compare ca să comparați două numere de tip long).
4. (1p) Suprascrieți metodele equals și hashCode în clasa Student (hint: puteți folosi generatorul de cod din IntelliJ).
5. (2p) Folosiți un HashMap<Student, LinkedList<String», în care se vor adăuga perechi de tipul (Student, lista de materii pe care le are studentul respectiv), iar apoi afisați conținutul colecției (hint: Map.Entry și entrySet()).
6. (2p) Extindeți clasa LinkedHashSet<Integer>, cu o clasă în care se vor putea adăuga doar numere pare. Vor fi suprascrise metodele add și addAll, în așa fel încât să nu fie permise adăugarea de numere impare în colecție. Pentru testare, adăugați numere pare și impare, iar după aceea iterați prin colecție, folosind Iterator (tipizat cu Integer) sau folosind forEach, afișând elementele din colecție. Inlocuiți LinkedHashSet cu HashSet - ce observați cu privire la ordinea de inserare a elementelor? Dar dacă ați înlocui cu TreeSet?

• Schelet
• Soluție
• Exerciții din alți ani

• Streams, introduse din Java 8, pot fi folosite și pentru a aplica operații pe colecții. Nu le folosim momentan la laborator însă le puteți utiliza la teme:
  • Java streams
  • Filter streams examples