Arhitectura Java Collection Framework. 1

Implementarea interfeţei Set 8

Implementarea interfeţei Queue. 10

Implementarea interfeţei Map. 11

Aplicaţii laborator 16

Colecţii de obiecte

Arhitectura Java Collection Framework

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:

- Interfeţe: tipuri abstracte de date ce descriu comportamentul colecţiilor. Prin intermediul interfeţelor colecţiile pot fi manipulate fără a ţine cont de detaliile de implementare.

- Implementări: reprezintă implementări concrete ale interfeţelor ce descriu colecţiile.

- Algoritmi: metode care efectuează diverse operaţii utile cum ar fi căutarea, sortarea definite pentru obiecte ce implementeaza interfeţe ce descriu colecţii. Aceşti algoritmi se numesc si polimorfici deoarece aceeaşi metoda poate fi folosita pe implementări diferite ale unei colecţii.

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

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 este clasa HashTable.

Exerciţiu: Studiaţi documentaţia interfeţelor prezentate anterior în jdk 1.5 API.

Figura 1. Arhitectura Java Collection Framework.

Implementări ale colecţiilor

În continuare vor fi prezentate câteva implementări concrete ale interfeţelor definite mai sus şi exemple cu privire la modul în care aceste implementări pot fi folosite.

Implementarea interfeţei 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 schimbe 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);

}

for(Iterator ix=z2.iterator();ix.hasNext();){

String s = (String)it.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 toate obiectele din cadrul colecţie pentru a determina ce obiecte să fie şterse (vor fi şterse acele obiecte care sunt egale cu obiectul o transmis ca argument pentru metoda remove).

EXERCITIU: Stergeţi sau comentaţi metoda equals din cadrul clasei Persoana, rulaţi aplicaţia şi observaţi difernţa.

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.*;

/**

* Exemplificare utilizare colectie LinkedList.

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.

Exerciţiu: Modificaţi aplicaţia anterioară pentru a implementa o regulă de tip 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.

Exerciţiu: Suprascrieţi metoda public boolean equals(Object) din cadrul clasei Object şi implementaţi această metodă în cadrul clasei Persoana din cadrul ultimului exerciţiu.

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.

Exerciţiu: Implementaţi în cadrul aplicaţiei un mecanism de generare automată de obiecte de tip Job cu priorităţi aleatoare în intervalul 1 – 10. Adăugaţi în cadrul cozii 20 astfel de job-uri. Executaţi job-urile introduse în coadă parcurgând coada cu o structură de tip while.

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.");

}

Exerciţiu: Adăugaţi în cadrul aplicaţiei posibilitatea de a şterge un cuvânt din dicţionar.

Î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).

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) {

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();

Cuvant x = new Cuvant(linie);

if( linie.length()>1) {

explic = dict.cautaCuvant(x);

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.");

}

class Cuvant{

String c;

public Cuvant(String c) {

this.c = c;

}

/*public boolean equals(Object obj) {

return c.equals((String)obj);

}

public int hashCode() {

return (int)(Math.random()*c.length()*1000);

}*/

public String toString() {

return c;

}

Exerciţiu: Testaţi aplicaţia de mai sus – adăugaţi cuvinte apoi încercaţi funcţia de căutare. Decomentaţi metodele equals şi hashCode din cadrul aplicaţiei de mai sus şi verificaţi din nou modul de funcţionare.

Aplicaţii laborator

Aplicaţiile din laborator pot fi descărcate de aici.