Table of Contents

Introducere

Colecţiile sunt clase specializate pentru memorarea şi manipularea grupurilor de obiecte. Limbajul java oferă în cadrul pachetului standard java.util un set de clase şi interfeţe denumit Java Collection Framework specializat pentru lucrul cu colecţii.

In Java colecţiile sunt tratate intr-o maniera unitara, fiind organizate intr-o arhitectura ce cuprinde:

Diagrama din figura 1 prezintă arhitectura Java Collection Framework (JCF). În continuare sunt descrise structurile de date modelate prin intermediul interfeţelor JCF.

Collection Collection descrie un grup de obiecte numite si elemente. Unele implementari ale acestei interfeţe permit existenta elementelor duplicate, alte implementari nu. Unele au elementele ordonate, altele nu. Modelează o colecţie la nivelul cel mai general. In java nu exista nici o implementare directa a acestei interfeţe, exista doar implementări ale unor subinterfeţe mai concrete cum ar fi Set sau List.

Set Modeleaza notiunea de multime în sens matematic. O mulţime nu poate avea elemente duplicate.

List Modelează o colecţie ordonată de elemente. Spre deosebire de Set, List permite existenţa elementelor duplicat. Utilizatorul are control asupra poziţiei elementelor în cadrul listei.

Que Modelează cozi de elemente în cadrul cărora adăugarea şi extragerea elementelor se face în funcţie de anumite reguli (de exemplu regula First In First Out).

Map Implementarile acestei interfete sunt obiecte ce asociaza fiecarui element o cheie unica (perechi de tipul cheie – valoare). Nu pot contine asadar chei duplicate si fiecare chei este asociata la un singur element. O clasa independenta ce implementeaza o functionalitate asemanatoare cu Map este clasa HashTable.

Utilizarea colectiilor de tip List

Două implementări concrete ale interfeţei List sunt clasele ArrayList şi LinkedList.

Construirea unei liste

Construirea unei liste de tip ArrayList se face astfel:

List z1 = new ArrayList();
ArrayList z2 = new ArrayList();

Prima variantă de construire a unui obiect de tip ArrayList oferă felxibilitate mai mare în sensul că dacă se doreşte schimbarea implementării şi folosirea de exemplu a unui obiect de tip LinkedList în loc de ArrayList, este suficient să se inlocuiasca instrucţiunea de construire a obiectului, restul codului rămânând neschimbat.

List z1 = new LinkedList();

Adăugare elemente în listă

Odată construită colecţie de tip ArrayList, in cadrul acesteia pot fi stocate obiecte folosind metodele definite în cadrul interfeţei List.

myList.add(„dog”);
myList.addAll(myList2);
myLisy.set(4,”cat”);

În cadrul listei elementele pot fi adăugate unul câte unu folosind metoda add(Object o) sau pot fi adăugate mai multe elemente localizate într-o altă listă.

În cadrul unei liste poate fi înlocuit un element de pe o poziţie specificată folosind metoda set(int index, Object o).

Parcurgerea elementelor dintr-o listă

Elementele dintr-o listă pot fi extrase folosind metoda get(int index). Această metodă returnează un obiect din cadrul listei fără a-l şterge. Lista poate fi parcursă cu ajutorul unei bucle repetitive conform exemplului de mai jos:

for(int i=0;i<z2.size();i++){
            String animal = (String)z2.get(i);
            System.out.println(animal);
      }

În momentul adăugării unui obiect intr-o listă se pierde infromaţia cu privire la tipul acestuia (metoda get returnează o referinţă de tip Object). Aceasta înseamnă că în momentul extragerii obiectelor trebuie asigurată conversia la tipul corect.

Începând cu versiunea 1.5 Java a fost introdusă structura foreach pentru a oferi un mechanism mai elegat de parcurgere a colectiilor.

for(Object o:z1){
            System.out.println((String)o);
      }

Structura de mai sus parcurge colecţia z1, şi pentru fiecare element o de tip Object din cadrul acesteia executa instrucţiunea de afişare.

O a treia metodă de parcurgere a elementelor unei liste este folosind iteratorii. Un interator este un obiect special ce permite parcurgerea elementelor unei liste.

În cadrul interfeţei Collection care este moştenită şi de interfaţa List este definită metoda iterator(). Această metodă generează şi returnează un obiect de tip Iterator prin intermediul căruia elementele colecţie pot fi parcurse într-un singur sens folosind metoda next(). Verificarea terminării elementelor dintr-o colecţie se face cu metoda hasNext() care returnează true în cazul în mai există elemente în colecţie sau false în caz contrar. Exemplu:

Iterator it = z1.iterator();
      while(it.hasNext()){
            String s = (String)it.next();
            System.out.println(s);
      }

Sau :

for(Iterator ix=z2.iterator();ix.hasNext();){
            String s = (String)ix.next();
            System.out.println(s);
      }

La fel ca orice clasă din java, clasele de tip colecţie moştenesc clasa Object. Din cadrul acestei clase este suprascrisă în cadrul colecţiilor metoda public StringtoString() pentru a afişa toate obiectele din cadrul unei colecţii.

Instrucţiunea System.out.println(colectie) va afişa la ieşirea standard toate obiectele componente ale colecţiei colectie.

Stergerea elementelor dintr-o listă

Interfaţa Collecţion conţine metodele remove(Object o), remove(int index) şi removeAll(Collection c) prin intermediul cărora obiectele pot fi şterse dintr-o listă.

import java.util.*;
public class RemoveExample {
      static void displayAll(List l){
            System.out.println("Display all persons.");
            for (Object p : l) {
                  System.out.println(p);
            }
      }
 
      public static void main(String[] args) {
            List c = new ArrayList();
            Person p1 = new Person("aaa","bbb");
            Person p2 = new Person("ccc","ddd");
            Person p3 = new Person("xxx","yyy");
            Person p4 = new Person("zzz","qqq");
 
            c.add(p1);c.add(p2);c.add(p3);c.add(p4);
            displayAll(c);
            c.remove(p2);
            displayAll(c);
 
            Person p5 = new Person("aaa","bbb");
            c.remove(p5);
            displayAll(c);
 
            c.remove(0);
            displayAll(c);
      }
}
 
class Person{
      String firstname;
      String lastname;
      Person(String f, String l){
            this.firstname = f;this.lastname = l;
      }
 
      public boolean equals(Object obj) {
            if(obj instanceof Person){
                  Person p = (Person)obj;
                  return p.firstname.equalsIgnoreCase(firstname)&&p.lastname.equalsIgnoreCase(lastname);          
            }
            else return false;
      }
 
      public String toString() {
            return "persoana:"+firstname+":"+lastname;
      }
}

Se observă în exemplul anterior că în cadrul clasei Persoana a fost definită metoda equals(Object obs). Această metodă este moştenită din cadrul clasei Object şi suprascrisă în cadrul clasei Persoana pentru a permite compararea a două obiecte de tip Persoana. Este nevoie de această metoda pentru ca metoda remove(Object o) din cadrul colecţiei să funcţioneze corect. Metoda remove(Object o) apelează automat metoda equals(Object obs) pentru obiectele din cadrul colecţie pentru a determina ce obiect să fie şters (va fi sters primul obiect gasit pentru care metoda equals intoarce true).

Liste înlănţuite

Pentru modelarea listelor înlănţuite în cadrul Java Collection Framework este definită clasa LinkedList. Această clasă implementează toate funcţionalităţile definite de interfaţa List şi în plus permite adăugarea, citirea şi ştergerea de elemente de la începutul şi sfârşitul listei. De exemplu pentru a adăuga un element la începutul listei se foloseşte metoda addFirst() iar pentru a extrage un element de la sfârşitul listei se foloseşte metoda removeLast().

import java.util.*;
public class LinkedExample {
      public static void main(String[] args) {
            LinkedList lk = new LinkedList();
            lk.addFirst(new Command("comanda 1"));
            lk.addFirst(new Command("comanda 2"));
            lk.addFirst(new Command("comanda 3"));
 
            Command c = (Command)lk.removeLast();
            c.execute();
            c = (Command)lk.removeLast();
            c.execute();
            c = (Command)lk.removeLast();
            c.execute();           
      }
}
 
class Command{
      String name;
      Command(String n){name = n;}
      void execute(){System.out.println("Execute command:"+name);}
}

În exemplul anterior se foloseşte o lista de tip LinkedList pentru a adăuga şi a extrage obiecte de tip Command după regula First In First Out.

Implementarea interfeţei Set

Un set este o colecţie de obiecte unice. În aplicaţia următoare este exemplificată utlizarea a trei colecţii de tip Set: TreeSet, HashSet şi LinkedHashSet. În momentul rulării aplicaţiei se observă că ordinea de stocare a obiectelor este diferită în cadrul colecţiilor de tip Set – deoarece fiecare dintre ele foloseşte alte reguli pentru memorarea acestora.

import java.util.*;
public class TestSet1 {
 
      static void displayAll(Set list){
            System.out.println("- - - - - - - -");
            Iterator i = list.iterator();
            while(i.hasNext()){
                  String s = (String)i.next();
                  System.out.println(s);
            }
      }
 
      /**
       * @param args
       */
      public static void main(String[] args) {
 
            HashSet set = new HashSet();
            set.add("one");set.add("tow");set.add("six");set.add("six");
            set.add("one");set.add("four");set.add("five");
            displayAll(set);
 
            TreeSet tree = new TreeSet();
            tree.add("one");tree.add("tow");tree.add("six");tree.add("six");
            tree.add("one");tree.add("four");tree.add("five");
            displayAll(tree);
 
            LinkedHashSet lnk = new LinkedHashSet();
            lnk.add("one");lnk.add("tow");lnk.add("six");lnk.add("six");
            lnk.add("one");lnk.add("four");lnk.add("five");      
            displayAll(lnk); 
      }
}

Programul următor exemplifică folosirea colecţiei de tip TreeSet şi utilizarea facilităţii pe care o oferă aceasta de sortare automată a obiectelor componente. Pentru ca obiectele adăugate într-o colecţie de tip TreeSet să fie sortate corect va trebui ca acestea să implementeze interfaţa Comparable.

import java.util.TreeSet;
public class TestSort {
      public static void main(String[] args) {
            TreeSet t = new TreeSet();
            Person p1 = new Person("jon",4);
            Person p2 = new Person("alin",10);
            Person p3 = new Person("dan",8);
            Person p4 = new Person("florin",7);
            t.add(p1);t.add(p2);t.add(p3);t.add(p4);       
            System.out.println(t); 
            System.out.println("firs:"+t.first());
            System.out.println("last:"+t.last());
            System.out.println("subset:"+t.subSet(new Person("x",5),new Person("y",9)));
            System.out.println("headset:"+t.headSet(p3));
      }
}
 
class Person implements Comparable{
      int age;
      String name;
      Person(String n,int a){
            age = a;
            name = n;
      }
 
      public int compareTo(Object o) {
            Person p = (Person)o;
            if(age>p.age) return 1;
            if(age==p.age) return 0;
            return -1; 
      }
 
      public String toString(){
            return "("+name+":"+age+")";
      }
}

În cadrul exemplului anterior s-a definit clasa Person care implementează interfaţa Comparable. Interfaţa Comparable conţine metoda int compareTo(Object o) ce trebui implementată. Această metodă asigură compararea a două obiecte de tipul Persoana (obiectul curent cu un obiect de tip Persoana transmis ca parametru). Metoda trebuie să returneze -1, 0 sau 1 dacă obiectul curent este mai mic, egal sau mai mare decât obiectul transmis ca argument.

Se recomandă ca metoda compareTo(Object o) să fie consistentă cu metoda boolean equals(Object o). Acesta înseamnă că dacă două obiecte sunt egale conform metodei compareTo, atunci cele două obiecte să fie egale si prin compararea prin intermediul metodei equals.

Implementarea interfeţei Queue

Colecţiile de tip Queue moştenesc toate caracteristicile interfeţei Collection şi în plus adaugă facilităţi suplimentare pentru adăugarea, extragerea şi parcurgerea elementelor.

În continuare este exemplificată folosirea colecţiei PriorityQueue ce permite extragerea elementelor pe baza unei ordini stabilite prin implementarea interfeţei Comparable. Colecţia PriorityQueue nu permite adăugarea de obiecte ce nu implementează interfaţa Comparable.

import java.util.PriorityQueue;
public class TestQueue {
public static void main(String[] args) {
      Job j1 = new Job("chek trains on input rail segments",3);
      Job j2 = new Job("chek trains on ouput rail segments",2);
      Job j3 = new Job("chek trains on rail station segments",1);
 
      PriorityQueue que = new PriorityQueue();
      que.offer(j1);
      que.offer(j2);
      que.offer(j3);
 
      while(que.size()!=0){
            Job j = (Job)que.poll();
            j.execute();
      }    
}
}
 
class Job implements Comparable{
 
      int p;
      String name;
 
      public Job(String name,int p) {
            this.p = p;
            this.name = name;
      }
 
      public void execute(){
            System.out.println("Execute job:"+name+" - job p="+p);
      }
 
      public int compareTo(Object o) {   
            Job x = (Job)o;
            if(p>x.p){
                  return 1;
            }else if(p==x.p)
                  return 0;
            else
                  return -1;
      }    
}

Metoda offer(Object o) adaugă un element în coadă. Spre deosebire de metoda add(Object o ), metoda offer poate eşua în adăugarea uni element (de exemplu coada este plină în cazul depăşirii capacităţii maxime) şi returnează false.

Metodele remove() şi poll() returnează elemtul din capul listei. Aceste două metode diferă doar prin modul de comportament în momentul în care lista este goală. Metoda remove() aruncă o excepţie, în timp ce metoda pol() returnează valoarea null.

Metodele element() şi peak() returnează obiectul din capul listei dar fără a-l sterge.

Adăugarea elementelor in coadă se face folosind metoda offer, iar extragerea elementelor din coadă se face folosind metoda poll.

Atenţie: Parcurgerea cozii PriorityQueue cu un Iterator nu garantează parcurgerea intr-o anumită ordine.

Implementarea interfeţei Map

Colecţiile de tip Map sunt colecţii în cadrul cărora se pot stoca perechi de obiecte de tip cheie valoare. Cheile trebuie să fie unice, o cheie fiind asociată la un singură valoare. Această interfaţă este implementată de clasele HashMap, TreeMap, HashTable, LinkedHashMap, WeakhashMap şi IdentityHashMap. Aceste clase diferă din punctul de vedere al eficienţei stocării şi regăsirii informaţiilor.

Elementele sunt adăugate în cadrul acestor colecţii folosind metoda void put(Object key, Object value) asociindu-se astfel la obiectul value cheia key.

În exemplul următor sunt exemplificate principalele operaţii puse la dispoziţie de interfaţa Map.

import java.util.HashMap;
import java.util.Iterator;
 
public class HashMapExample{
 
public static void main(String args[]){
 
HashMap hashMap = new HashMap();
//------
hashMap.put( "One", new Integer(1) ); // adding value into HashMap
hashMap.put( "Two", new Integer(2) );
hashMap.put( "Three", new Integer(3) );
//------
System.out.println("HashMap contains " + hashMap.size() + " key value pair.");
//------
if( hashMap.containsValue( new Integer(1) ) ){
      System.out.println("HashMap contains 1 as value");
}else{
      System.out.println("HashMap does not contain 1 as value");
}
//-------
if( hashMap.containsKey("One") ){
      System.out.println("HashMap contains One as key");
}else{
      System.out.println("HashMap does not contain One as value");
}
//-------
Integer one = (Integer) hashMap.get("One");
System.out.println("Value mapped with key \"One\" is " + one);
//-------
System.out.println("Retriving all keys from the HashMap");
Iterator iterator = hashMap.keySet().iterator();
while( iterator. hasNext() ){
      System.out.println( iterator.next() );
}
//-------
System.out.println("Retriving all values from the HashMap");
iterator = hashMap.entrySet().iterator();
while( iterator. hasNext() ){
      System.out.println( iterator.next() );
}
//-------
System.out.println( hashMap.remove("One") + " is removed from the HashMap.");
}
}

Programul următor exemplifică folosirea clasei TreeMap în cadrul unei aplicaţii de tip dicţionar de cuvinte.

import java.util.*;
import java.io.*;
public class Dictionar {
 
        TreeMap dct = new TreeMap();
 
         public Dictionar() {
         }
 
         public void adaugaCuvant(String cuvant, String definitie) {
 
              if(dct.containsKey(cuvant)){
                    System.out.println("Modific cuvant existent!");
              }
              else
              {
                   System.out.println("Adauga cuvant nou.");
              } 
              dct.put(cuvant, definitie);
 
         }
 
         public String cautaCuvant(String cuvant) {
            return (String)dct.get(cuvant);
         }
 
         public void afisDictionar() {
            System.out.println(this);
         }
 
 
         public static void main(String args[]) throws Exception {
            Dictionar dict = new Dictionar();
            char raspuns;
            String linie, explic;
            BufferedReader fluxIn = new BufferedReader(new InputStreamReader(System.in));
 
            do {
               System.out.println("Meniu");
               System.out.println("a - Adauga cuvant");
               System.out.println("c - Cauta cuvant");
               System.out.println("l - Listeaza dictionar");
               System.out.println("e - Iesi");
 
               linie = fluxIn.readLine();
               raspuns = linie.charAt(0);
 
               switch(raspuns) {
                  case 'a': case 'A':
                     System.out.println("Introduceti cuvantul:");
                     linie = fluxIn.readLine();
                     if( linie.length()>1) {
                        System.out.println("Introduceti definitia:");
                        explic = fluxIn.readLine();
                        dict.adaugaCuvant(linie, explic);
                     }
                  break;
                  case 'c': case 'C':
                     System.out.println("Cuvant cautat:");
                     linie = fluxIn.readLine();
                     if( linie.length()>1) {
                        explic = dict.cautaCuvant(linie);
                        if (explic == null)
                           System.out.println("nu exista");
                        else
                           System.out.println("Explicatie:"+explic);
                     }
                  break;
                  case 'l': case 'L':
                     System.out.println("Afiseaza:");
                     dict.afisDictionar();
                  break;
 
               }
            } while(raspuns!='e' && raspuns!='E');
            System.out.println("Program terminat.");
         }
      }

În cadrul colecţiilor de tip Map, căutarea după cheii este optimizată prin folosirea unui cod special numit hash code. Acest cod este o valoare intreagă unică care trebuie să fie asociată fiecărei chei. Pentru funcţionarea corecta a colecţiilor de tip Map trebuie ca obiectele adăugate ca şi chei să asigure generarea acestor coduri hash. Aceasta se realizează suprascriind metoda int hashCode() din cadrul clasei Objet. În exemplele anterioare nu a fost nevoie de această operaţie pentru ca au fost folosite ca şi chei obiecte de tip String, care are deja suprascrisă această metodă. Odată cu suprascrierea metodei hashCode() trebuie suprascrisă şi metoda equals(Object o).

Important Metoda hashCode() trebuie sa returneze valoare identica pentru doua obiecte a caror comparare prin metoda eqals returneaza true.

 import java.util.*;
import java.io.*;
 
public class Dictionar2 {
 
         HashMap dct = new HashMap();
 
         public void adaugaCuvant(Cuvant c, String definitie) {
 
              if(dct.containsKey(c))
                    System.out.println("Modific cuvant existent!");            
              else              
                   System.out.println("Adauga cuvant nou.");              
              dct.put(c, definitie);        
         }
 
         public String cautaCuvant(Cuvant c) {
        	 System.out.println("Cauta "+c);
        	 System.out.println(dct.containsKey(c));
            return (String)dct.get(c);
         }
 
         public void afisDictionar() {
            System.out.println(dct);
         }
 
 
         public static void main(String args[]) throws Exception {
            Dictionar2 dict = new Dictionar2();
            char raspuns;
            String linie, explic;
            BufferedReader fluxIn = new BufferedReader(new InputStreamReader(System.in));
 
            do {
               System.out.println("Meniu");
               System.out.println("a - Adauga cuvant");
               System.out.println("c - Cauta cuvant");
               System.out.println("l - Listeaza dictionar");
               System.out.println("e - Iesi");
 
               linie = fluxIn.readLine();
               raspuns = linie.charAt(0);
 
               switch(raspuns) {
                  case 'a': case 'A':
                     System.out.println("Introduceti cuvantul:");
                     linie = fluxIn.readLine();
                     if( linie.length()>1) {
                        System.out.println("Introduceti definitia:");
                        explic = fluxIn.readLine();
                        dict.adaugaCuvant(new Cuvant(linie), explic);
                     }
                  break;
                  case 'c': case 'C':
                     System.out.println("Cuvant cautat:");
                     linie = fluxIn.readLine();
                     if( linie.length()>1) {
                    	Cuvant x = new Cuvant(linie);
                    	explic = dict.cautaCuvant(x);
                        if (explic == null)
                           System.out.println("Cuvantul nu a fost gasit!");
                        else
                           System.out.println("Definitie:"+explic);
                     }
                  break;
                  case 'l': case 'L':
                     System.out.println("Afiseaza:");
                     dict.afisDictionar();
                  break;
 
               }
            } while(raspuns!='e' && raspuns!='E');
            System.out.println("Program terminat.");
         }
      }
 
class Cuvant{
      String c;
      public Cuvant(String c) {
            this.c = c;
      }
 
      /*
      @Override
      public boolean equals(Object obj) {
    	  	if(!(obj instanceof Cuvant))
    	  		return false;
    	  	Cuvant x = (Cuvant)obj;
    	  	return c.equals(x.c);
      }
 
      public int hashCode() {
            return (int)(c.length()*1000);
      }
      */
 
      public String toString() {
            return c;
      }    
}