Curs 4
Colectii

• Ce sunt colectiile ?
• Interfetele de baza care descriu colectii
  • Collection
  • Set
  • List
  • Map
  • SortedSet
  • SortedMap
• Implementari ale colectiilor
• Folosirea eficienta a colectiilor
• Algoritmi
• Iteratori si enumerari
• Exemplu: gestionarea angajatilor unei companii

Definitie

O colectie este un obiect care grupeaza mai multe elemente īntr-o singura unitate. Prin colectii vom avea acces la tipuri de date cum ar fi vectori, multimi, tabele de dispersie, etc. Colectiile sunt folosite pentru memorarea si manipularea datelor, precum si pentru transmiterea datelor de la o metoda la alta.

• Interfete: tipuri abstracte de date ce descriu colectiile. Interfetele permit utilizarea colectiilor independent de detaliile implementarilor.
• Implementari: implementari concrete ale interfetelor ce descriu colectii. Aceste clase reprezinta tipuri de date reutilizabile.
• Algoritmi: metode care efectueaza diverse operatii utile cum ar fi cautarea, sortarea definite pentru obiecte ce implementeaza interfete ce descriu colectii. Acesti algoritmi se numesc si polimorfici deoarece aceeasi metoda poate fi folosita pe implementari diferite ale unei colectii. Aceste tipuri de algoritmii descriu notiunea de functionalitate reutilizabila.

• Reducerea efortului de programare: prin punerea la dispozitia programatorului a unui set de tipuri de date si algoritmi ce modeleaza structuri si operatii des folosite in aplicatii.
• Cresterea vitezei si calitatii programului: implementarile efective ale colectiilor sunt de inalta performanta si folosesc algoritmi cu timp de lucru optim. In scrierea unei aplicatii putem sa ne concentram eforturile asupra problemei in sine si nu asupra modului de reprezentare si manipulare a informatiilor.

Collection

Collection descrie un grup de obiecte numite si elementele sale. Unele implementari ale acestei interfete permit existenta elementelor duplicate, alte implementari nu. Unele au elementele ordonate, altele nu. Modeleaza o colectie la nivelul cel mai general. In JDK nu exista nici o implementare directa a acestei interfete, ci exista doar implementari ale unor subinterfete mai concrete cum ar fi Set sau List.

Set

Modeleaza notiunea de multime īn sens matematic. O multime nu poate avea elemente duplicate.

List

Descrie liste (secvente) de elemente indexate. Listele pot contine duplicate si permit un control precis asupra pozitiei unui element prin intermediul indexului acelui element.
O clasa independenta ce implementeaza o functionalitate asemanatoare este clasa Vector.

Map

Implementarile acestei interfete sunt obiecte ce asociaza fiecarui element o cheie unica. 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.

SortedSet

Este asemanatoare cu interfata Set la care se adauga faptul ca elementele dintr-o astfel de colectie sunt ordonate ascendent. Pune la dispozitie operatii care beneficiaza de avantajul ordonarii elementelor.

SortedMap

Este asemanatoare cu interfata Map la care se adauga faptul ca multimea cheilor dintr-o astfel de colectie este ordonata ascendent.

 
	public interface Collection {
              // Operatii de baza la nivel de element
              int size();
              boolean isEmpty();
              boolean contains(Object element);
              boolean add(Object element);    // Optional
              boolean remove(Object element); // Optional
              Iterator iterator();

              // Operatii la nivel de colectie
              boolean containsAll(Collection c);
              boolean addAll(Collection c);    // Optional
              boolean removeAll(Collection c); // Optional
              boolean retainAll(Collection c); // Optional
              void clear();                    // Optional        

              // Operatii de conversie in vector
              Object[] toArray();
              Object[] toArray(Object a[]);
	}

• acces pozitional
• cautare (aflarea indexului unui element)
• iterare ordonata
• extragerea unei subliste

	public interface List extends Collection {
              // Acces pozitional
              Object get(int index);
              Object set(int index, Object element);            // Optional
              void add(int index, Object element);              // Optional
              Object remove(int index);                         // Optional
              abstract boolean addAll(int index, Collection c); // Optional

              // Cautare
              int indexOf(Object o);
              int lastIndexOf(Object o);

              // Iterare
              ListIterator listIterator();
              ListIterator listIterator(int index);

              // Extragere sublista
              List subList(int from, int to);
	}

	public interface Map {
              // Operatii de baza la nivel de element
              Object put(Object key, Object value);
              Object get(Object key);
              Object remove(Object key);
              boolean containsKey(Object key);
              boolean containsValue(Object value);
              int size();
              boolean isEmpty();

              // Operatii la nivel de colectie
              void putAll(Map t);
              void clear();

              // Vizualizari ale colectiei
              public Set keySet();
              public Collection values();
              public Set entrySet();

              // Interfata pentru manipularea unei inregistrari
              public interface Entry {
                  Object getKey();
                  Object getValue();
                  Object setValue(Object value);
              }
	}

• extragere de subliste
• aflarea primului/ultimului element din lista
• aflarea comparatorului folosit pentru ordonare

          public interface SortedSet extends Set {
              // Subliste
              SortedSet subSet(Object fromElement, Object toElement);
              SortedSet headSet(Object toElement);
              SortedSet tailSet(Object fromElement);

              // Capete
              Object first();
              Object last();

              Comparator comparator();
          }

• extragere de subtabele
• aflarea primei/ultimei chei
• aflarea comparatorului folosit pentru ordonare

          public interface SortedMap extends Map {

              SortedMap subMap(Object fromKey, Object toKey);
              SortedMap headMap(Object toKey);
              SortedMap tailMap(Object fromKey);

              Object first();
              Object last();

              Comparator comparator();
          }

• permit elementul null
• sunt serializabile
• au definita metoda clone
• au definita metoda toString, care returneaza o reprezentare ca sir de caractere a colectiei respective
• permit crearea iteratorilor pentru parcurgere
• implementarea interfetelor este indirecta, īn sensul ca au o

//exemplul 1
import java.util.*;
public class List1 {
	public static void main(String(args[]) {
		List lst = new ArrayList();
		//List lst = new LinkedList();
		final int N = 25000;
		for(int i=0; i < N; i++)
			lst.add(new Integer(i));
		//*
	}
}
//exemplul 2 - List2
Adaugam la exemplul 1 (*) urmatoarea secventa 
		for(int i=0; i < N; i++)
			lst.get(i);
//exemplul 3 - List3
Adaugam la exemplul 1 (*) urmatoarea secventa 
		for(int i=0; i < N; i++)
			lst.remove(0);

	class Entry {
		Object element;
		Entry next;
		Entry previous;
	}

• sunt metode statice
• au un singur argument de tip colectie
• apelul lor va fi de forma Collections.algoritm([colectie])
• majoritatea opereaza pe liste dar si pe colectii arbitrare

boolean hasMoreElements()
Object nextElement()

boolean hasNext()
Object next()
void remove()

boolean hasNext(),hasPrevious()
Object next(), previous()
void add(Object o)	void remove()
void set(Object o)

import java.util.*;
class TestIterator{
	public static void main(String args[]) {
		ArrayList a = new ArrayList();
		for(int i=0; i<10; i++) a.add(new Integer(i));	
		Collections.shuffle(a);	//amestecam elementele colectiei
		System.out.println("Vectorul amestecat: " + a);
		System.out.println("Parcurgem vectorul element cu element:");
		System.out.println("\nvarianta 1: cu while");
		Iterator it = a.iterator();
		while (it.hasNext()) 
			System.out.print(it.next() + " ");
		System.out.println("\nvarianta 2: cu for");
		for(it=a.iterator(); it.hasNext(); )
			System.out.print(it.next() + " ");
	}
}

//clasa Angajat
import java.io.Serializable;
class Angajat implements Serializable {
	String cod;
	String nume;
	int salariu;
	public Angajat(String cod, String nume, int salariu) {
		this.cod=cod;
		this.nume=nume;
		this.salariu=salariu;
	}
	public String toString() {
		return cod + "\t" + nume + "\t" + salariu;
	}
}

//clasa Personal
import java.io.*;
import java.util.*;
class Personal implements Serializable {
	HashMap personal = new HashMap();
	String fisier=null;
	boolean salvat=false;
	
	void load(String fis) throws IOException{
		ObjectInputStream in=null;
		this.fisier=fis;
		try	{
			in=new ObjectInputStream(new FileInputStream(fisier));
			personal = (HashMap)in.readObject();
		} catch(FileNotFoundException e) {
			System.out.println("Fisierul " + fisier + " nu exista!");
		} catch(ClassNotFoundException e) {
			System.out.println("Eroare la incarcarea datelor!");
		}finally {
			if (in != null) 
				in.close();
		}	
	}
	void saveAs(String fis) throws IOException{
		ObjectOutputStream out=null;
		try {
			out=new ObjectOutputStream(new FileOutputStream(fis));
			out.writeObject(personal);
			salvat=true;
			System.out.println("Salvare reusita in fisierul " + fis);
		}catch(IOException e) {
			System.out.println("Salvarea nu a reusit!");	 
		}finally {
			if (out != null)
				out.close();
		}	
	}
	void save() throws IOException {
		if (fisier == null) fisier="personal.txt";
		saveAs(fisier);
	}
	
	Angajat getAngajat(String argumente) {
		String cod="", nume="";
		int salariu=0;
		try {
			StringTokenizer st=new StringTokenizer(argumente);
			cod = st.nextToken();
			nume = st.nextToken();
			salariu = Integer.parseInt(st.nextToken());
		}catch(NoSuchElementException e) {
			System.out.println("Argumente incomplete!");
		}catch(NumberFormatException e) {
			System.out.println("salariul trebuie sa fie numeric!");
		}
		return new Angajat(cod, nume, salariu);
	}
	
	boolean add(String argumente) {
		Angajat a=getAngajat(argumente);
		if (personal.containsKey(a.cod)) {
			System.out.println("Mai exista un angajat cu acest cod!");
			return false;
		}	
		personal.put(a.cod, a);
		salvat=false;
		return true;
	}
	
	boolean delete(String cod) {
		if (personal.remove(cod) == null) {
			System.out.println("Nu exista nici un angajat cu acest cod!");
			return false;
		}
		salvat=false;
		return true;
	}

	void update(String argumente) {
		Angajat a=getAngajat(argumente);
		delete(a.cod);
		add(argumente);
	}

	void list() {
		Iterator it=personal.values().iterator();
		while (it.hasNext()) System.out.println((Angajat)(it.next()));
	}
	
	void executaComenzi() {
		String linie, comanda, argumente;
		try {
			BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
			while (true) {
				linie = stdin.readLine().trim();
				StringTokenizer st=new StringTokenizer(linie);
				comanda=st.nextToken();
				argumente="";
				while (st.hasMoreTokens()) argumente += st.nextToken() + " ";
				argumente=argumente.trim();
				
				if (comanda.startsWith("exit")) break;
				else if (comanda.startsWith("add")) add(argumente);
				else if (comanda.startsWith("del")) delete(argumente);
				else if (comanda.startsWith("update")) update(argumente);
				else if (comanda.startsWith("list")) list();
				else if (comanda.startsWith("load")) load(argumente);
				else if (comanda.startsWith("saveAs")) saveAs(argumente);
				else if (comanda.startsWith("save")) save();
				else System.out.println("what ?");
			}
			if (!salvat) save();
			System.out.println("bye...");
		}catch (IOException e) {
			System.out.println("Eroare I/O:" + e);
			e.printStackTrace();
		}
	}
}

//clasa principala GestiuneAngajati
public class GestiuneAngajati {
	public static void main(String args[]) {
		Personal p = new Personal();
		p.executaComenzi();
	}
}