Interfacce

Interfacce

 Un interface è una collezione di firme di metodi (senza implementazione).

Una interfaccia può dichiarare costanti.

Interfacce

C2

C1 I1 I2

Esempio di interfacepackage strutture;

public interface Stack{

public int estrai();

public void insert(int z);

}

package strutture;

public class Pila implements Stack{

…

}

package strutture;

public class Coda extends Pila{

…

}

Interfacce

Le interfacce possono essere usate come “tipi”

I1 x = new C2();// I1 x = new I1(); NO!!

C2

C1 I1 I2

public static void main(String args[]) { try { Stack s=null; int type=0; do { try { type =Integer.parseInt( JOptionPane.showInputDialog( "Pila (1) o Coda (2)?")); } catch (Exception e) {type=0;} } while (type<1 || type>2); switch (type) { case 1: s=new Pila(); break; case 2: s=new Coda(); break; } …}

Usare Pile e Code

Collections

Collections

Una collection è un oggetto che ragguppa elementi multipli (anche eterogenei) in una singola entità.

Collections sono usate per immagazzinare, recuperare e trattare dati, e per trasferire gruppi di dati da un metodo ad un altro.

Tipicamente rappresentano dati che formano gruppi “naturali”, come una mano di poker (una collection di carte), un mail folder (a collection di e-mail), o un elenco telefonico (una collection di mappe nome-numero).

Collections FameworkA collections framework is a unified architecture for representing

and manipulating collections. All collections frameworks contain three things:

Interfaces: abstract data types representing collections. Interfaces

allow collections to be manipulated independently of the details of their representation. In object-oriented languages like Java, these interfaces generally form a hierarchy.

Implementations: concrete implementations of the collection interfaces. In essence, these are reusable data structures.

Algorithms: methods that perform useful computations, like searching and sorting, on objects that implement collection interfaces. These algorithms are said to be polymorphic because the same method can be used on many different implementations of the appropriate collections interface. In essence, algorithms are reusable functionality.

Core Collections Interfaces

Occorre importare java.util.*

Core Collections Interfaces

A Collection represents a group of objects, known as its elements. Some Collection implementations allow duplicate elements and others do not. Some are ordered and others unordered.

Core Collections Interfaces

A Set is a collection that cannot contain duplicate elements

Core Collections Interfaces

A List is an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the List each element is inserted. The user can access elements by their integer index (position).

Core Collections Interfaces

A Map is an object that maps keys to values. Maps cannot contain duplicate keys: Each key can map to at most one value.

Implementations

Hash Table Resizable Array Balanced Tree Linked List

Interfaces

Set HashSet   TreeSet  

List   ArrayList   LinkedList

Map HashMap   TreeMap  

Core Collections Interfaces

Collection: Basic operations

int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); boolean remove(Object element); Iterator iterator();

Collection: basic operations

The add method is defined generally enough so that it makes sense for collections that allow duplicates as well as those that don't. It guarantees that the Collection will contain the specified element after the call completes, and returns true if the Collection changes as a result of the call.

The remove method is defined to remove a single instance of the specified element from the Collection, assuming the Collection contains the element, and to return true if the Collection was modified as a result.

The Iterator interface

public interface Iterator { boolean hasNext(); Object next(); void remove();

} hasNext returns true if there are more elements in

the Collectionnext() returns the next element in the Collection remove() method removes from the underlying

Collection the last element that was returned by next. The remove method may be called only once per call to next, and throws an exception if this condition is violated.

Using Iterators

void filter(Collection x) { Iterator i=x.iterator();

while (i.hasNext()) { if (!cond(i.next())) i.remove(); }

} The code is polymorphic: it works for any

Collection that supports element removal, regardless of implementation. That's how easy it is to write a polymorphic algorithm under the collections framework!

cond(Object o) è un NOSTROmetodo

nel quale noi implementiamoil controllo della condizioneche decide se tenere o meno

l’elemento

Collection: bulk operations

// Bulk operationsboolean containsAll(Collection c); boolean addAll(Collection c); boolean removeAll(Collection c); boolean retainAll(Collection c); void clear(); // Array Operations Object[] toArray(); Object[] toArray(Object a[]);

Collection: bulk operations

addAll: Adds all of the elements in the specified Collection to the target Collection.

removeAll: Removes from the target Collection all of its elements that are also contained in the specified Collection.

retainAll: Removes from the target Collection all of its elements that are not also contained in the specified Collection. That is to say, it retains only those elements in the target Collection that are also contained in the specified Collection.

The addAll, removeAll, and retainAll methods all return true if the target Collection was modified in the process of executing the operation.

containsAll: Returns true if the target Collection contains all of the elements in the specified Collection (c).

clear: Removes all elements from the Collection.

Collection: Array operations

Object[] toArray(); Object[] toArray(Object a[]);

Dump the contents of The Collection c into a newly allocated array of Object whose length is identical to the number of elements in c:

Object[] a = c.toArray();

Suppose c is known to contain only strings. Dump the contents of c into a newly allocated array of String

whose length is identical to the number of elements in String[] a = (String[]) c.toArray(new String[0]);

Perché Object[]? Ricordate il

Principio di sostituzioneDi Liskov!

Notate il cast!

Set: Interface

A Set is a Collection that cannot contain duplicate elements.

Set models the mathematical set abstraction.

The Set interface extends Collection and contains no methods other than those inherited from Collection. It adds the restriction that duplicate elements are prohibited.

Set: bulk operationsThe bulk operations are particularly well suited to Sets: they

perform standard set-algebraic operations. Suppose s1 and s2 are Sets.

s1.containsAll(s2): Returns true if s2 is a subset of s1.

s1.addAll(s2): Transforms s1 into the union of s1 and s2. s1.retainAll(s2): Transforms s1 into the intersection of s1

and s2.

s1.removeAll(s2): Transforms s1 into the (asymmetric) set difference of s1 and s2. (the set difference of s1 - s2 is the set containing all the elements found in s1 but not in s2.) Nota: i metodi sono gli stessi di Collection

Ma la semantica è ridefinita!

List

A List is an ordered Collection (sometimes called a sequence).

Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

Positional Access: manipulate elements based on their numerical position in the list.

Search: search for a specified object in the list and return its numerical position.

List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.

Range-view: perform arbitrary range operations on the list.

NOTA: aggiunge metodi addizionali a Collection!

List: Interface// Positional Access Object get(int index); Object set(int index, Object element); void add(int index, Object element); Object remove(int index); boolean addAll(int index, Collection c);

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

List: Interface

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

// Range-view

List subList(int from, int to);

CollectionsCollections è una classe che contiene metodi di utilità e

costanti di servizio, tra cui sort(List): Sorts a List using a merge sort algorithm, which

provides a fast, stable sort. (A stable sort is one that does not reorder equal elements.)

shuffle(List): Randomly permutes the elements in a List. reverse(List): Reverses the order of the elements in a List. fill(List, Object): Overwrites every element in a List with

the specified value. copy(List dest, List src): Copies the source List into the

destination List. binarySearch(List, Object): Searches for an element in an

ordered List using the binary search algorithm.

List cardDeck=new ArrayList(); …Collections.shuffle(cardDeck);

Empty Collections

The Collections class provides three constants, representing the empty Set, the empty List, and the empty Map

Collections.EMPTY_SETCollections.EMPTY_LISTCollections.EMPTY_MAP

The main use of these constants is as input to methods that take a Collection of values, when you don't want to provide any values at all.

Object ordering

There are two ways to order objects:

The Comparable interface provides automatic natural order on classes that implement it.

The Comparator interface gives the programmer complete control over object ordering. These are not core collection interfaces, but underlying infrastructure.

Object ordering with Comparable

A List l may be sorted as follows: Collections.sort(l);

If the list consists of String elements, it will be sorted into lexicographic (alphabetical) order.

If it consists of Date elements, it will be sorted into chronological order.

How does Java know how to do this? String and Date both implement the Comparable

interface. The Comparable interfaces provides a natural ordering for a class, which allows objects of that class to be sorted automatically.

Comparable Interface

int compareTo(Comparable o) Compares this object with the specified

object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

Definisce l’”ordinamento naturale” per la classe implementante.

Comparable Interface

Class Point implements Comparable { int x; int y; .... int compareTo(Point p) { // ordino sulle y retval=y-p.y; // a partità di y ordino sulle x if (retval==0) retval=x-p.x; return retval;}

p1

p2

p1 <p2

p1 p2

p1 <p2

Comparator Interface

int compare(T o1, T o2)          Compares its two arguments for

order. class NamedPointComparatorByXY implements Comparator { int compare (NamedPoint p1, NamedPoint p2) { // ordino sulle y retval=p1.y-p2.y; // a partità di y ordino sulle x if (retval==0) retval=p1.x-p2.x; return retval;}

Comparator Interface

class NamedPointComparatorByName implements Comparator { int compare (NamedPoint p1, NamedPoint p2) { //usa l’ordine lessicografico delle stringhe return (p1.getName().compareTo(p2.getName())); }}

Comparator Interface

... In un metodo di un altra classe: // sia c una Collection di NamedPoints boolean condition=…; Comparator cmp= null; if (condition)

cmp= new NamedPointComparatorByName(); else

cmp= new NamedPointComparatorByXY(); List x = new ArrayList(c); Collections.sort(x,cmp);

Ordina la collezione usando il comparatore scelto

Lettura di intimport java.util.*; class EmpComparator implements Comparator { public int compare(Object o1, Object o2) { EmployeeRecord r1 = (EmployeeRecord) o1; EmployeeRecord r2 = (EmployeeRecord) o2; return r2.hireDate().compareTo(r1.hireDate()); } } class EmpSort { EmpSort() { Collection employees = ... ; // Employee Database List emp = new ArrayList(employees); Collections.sort(emp, new EmpComparator()); System.out.println(emp); } public static void main(String args[ ]) {new EmpSort();}}