Download Colecciones

Informática III
Colecciones en Java
Lectura adicional:
http://www.javaworld.com/javaworld/jw-09-2001/jw-0921interface.html
Qué son las colecciones?
 La mayoría de los programas usan
colecciones (contenedores) de datos
 Un conjunto de usuarios
 Palabras de un diccionario
 Una lista de números
 Una lista de personas y sus
direcciones de email
 Colecciones de mayor orden: Listas
de conjuntos o conjuntos de listas
Arrays
 Tamaño fijo, definido en la declaración. Una vez
establecido no puede modificarse
 Todos los elementos del array deben ser del
mismo tipo o de algún subtipo
 Se accede a cada elemento mediante un índice
entero
 Cada array tiene un atributo length que almacena
su dimensión
 Acceder a un elemento con índice negativo o
mayor a length lanza una ArrayIndexOutOfBoundsException
 Acceder a un elemento antes de almacenarlo
lanza una NullPointerException
Arrays
 Arrays de referencias a objetos
 Declarar el array
 Dimensionarlo
 Llenar los elementos individuales
con objetos
Paso 2
Paso 1
Empleado [] emps = new Empleado[6];
for (int j = 0; j < emps.length; j++)
{ emps[j] = new Empleado();}
emps[0].setName(“José”);
...
Paso 3
La clase Arrays
 Clase de utilidad (java.util). Sólo métodos
static
 class Arrays
static void sort(Object[ ] a)//orden natural
static int binarySearch(Object[ ] a, Object key)
static boolean equals(Object[ ] a, Object[ ] a2)
static void fill(Object[ ] a, Object val)
static List asList(Object[ ] a)
/* también versiones de los métodos para cada
tipo de datos primitivos*/
Repaso de interfaces
 Cuánto más abstracción se añade se obtiene mayor flexibilidad. El polimorfismo
ayuda a construir programas más flexibles.
 Las interfaces brindan más polimorfismo que el que puede obtenerse usando
familias de clases con relación de herencia.
Ejemplo: interface Talkative { void talk();}
abstract class Animal implements Talkative {
abstract public void talk();}
class Dog extends Animal {
public void talk() {
System.out.println("Woof!"); }}
class Cat extends Animal {
public void talk() {
System.out.println("Meow."); }}
class Interrogator {
static void makeItTalk(Talkative subject) {
subject.talk(); }}
//se puede aún añadir una clase nueva de una familia
// completamente distinta y seguir pasando como argumentos instancias de esta
// nueva clase a makeItTalk( ).
Repaso de interfaces
class Clock {//….}
class CuckooClock extends Clock implements Talkative {
public void talk() {
System.out.println("Cuckoo, cuckoo!"); }}
class Example4 {
public static void main(String[] args) {
CuckooClock cc = new CuckooClock();
Interrogator.makeItTalk(cc); }}
//la interface me permite usar polimorfismo en familias de clases sin relación
// de herencia.
Otro ejemplo:
f(){ LinkedList list = new LinkedList();
//...
g( list );}
g( LinkedList list ){
list.add( ... );
g2( list )}
Repaso de interfaces
Supongo que ahora necesito realizar búsquedas más rápidas y que
LinkedList no resuelve este problema y necesito reemplazarla por HashSet.
En el código anterior los cambios no están localizados sino que necesito
cambiar f(), g() y todos los sitios donde se invoque a g(), puesto que g()
modifica su signatura. Reescribiendo:
f(){ Collection list = new LinkedList();//este código sí haría posible
// reemplazarLinkedList por HashSet y no tener que hacer ningún cambio
//más.
//...
g( list );}
g( Collection list ){
list.add( ... );
g2( list )}
Repaso de interfaces
Otro ejemplo relacionado:
f()
{ Collection c = new HashSet();
//...
g( c );}//paso como argumento una colección
g( Collection c )
{ for( Iterator i = c.iterator(); i.hasNext() ;)//itera en la colección y hace algo
do_something_with( i.next() );}
Comparada con esta otro código:
f2() { Collection c = new HashSet();
//...
g2( c.iterator() );}//paso como argumento un iterador
g2( Iterator i )//Puede iterar en colecciones o Mapas o en lugar de esto
{ while( i.hasNext() )//usar iteradores que generen datos, por ej. que
do_something_with( i.next() );}//alimenten al programa con datos de un
//archivo=>tengo más flexibilidad
Repaso de interfaces
Use interfaces para representar abstracciones que
puedan tener múltiples implementaciones.
Mientras no cambie la interface se pueden hacer
toda clase de cambios a las clases que la
implementan o añadir nuevas implementaciones,
sin que esto tenga ningún impacto en el código
que depende sólo de la interface.
Use interfaces para modelizar todo lo que es
probable que cambie a menudo. El polimorfismo
permite cambiar libremente de una
implementación a otra. El uso de clases concreta
ata al programador a implementaciones
específicas y hace los cambios innecesariamente
difíciles.
Java Frameworks
 Conjunto de clases (interfaces, clases
abstractas y clases concretas) que permiten
implementaciones reusables de conceptos
que suelen encontrarse en programación
 Ejemplos de Java Frameworks:
 Java Collection Framework (JCF)
 Interface gráfica de usuario(GUI)
 Input/Output
Qué es el JCF? (JDK 1.2)
 Arquitectura unificada para representar y
manipular colecciones
 JCF consta de:
 Interfaces (ADTs)
 Implementaciones concretas
(estructuras de datos reusables)
 Algoritmos (funcionalidad reusable)
C++’s Standard
Template Library es
también un framework
de colecciones
Objetivos del proyecto
 API pequeña (java.util)
 Número de interfaces
 Número de métodos por interface
 Bajo “peso conceptual”
 Construido sobre colecciones Java ya
existentes (Vector, Hashtable)
 Conversión de y a arrays
Las interfaces
fundamentales
La interface Collection
 Representa un grupo de objetos
(elementos)
 El JDK no provee ninguna implementación
directa de esta interface
 Es usada para pasar colecciones como
argumentos de métodos o constructores
cuando se desee tener máxima generalidad
La interface Collection
public interface Collection {
// Operaciones basicas
int size();//de query
boolean isEmpty();
boolean contains(Object element);
Iterator iterator();//de modificación o destructivos
boolean add(Object element); // Opcional(*)
boolean remove(Object element);//Opcional (*)
// Operaciones completas
boolean containsAll(Collection c);
boolean addAll(Collection c); // Opcional (*)
boolean removeAll(Collection c); // Opcional (*)
boolean retainAll(Collection c); // Opcional (*)
void clear(); // Opcional (*)
La interface Collection
// Operaciones con arrays
//puente de y hacia arrays
Object[ ] toArray();
Object[ ] toArray(Object a[ ]);
}
(*) retornan (salvo clear) true si la colección
cambia como resultado de aplicar el método,
false en caso contrario. Lanzan
UnsupportedOperationException si la
colección concreta no soporta esta operación.
Interface Iterator
 Provee un mecanismo “genérico” para iterar sobre
cada uno de los elementos de una colección
 Creado por Collection.iterator()
 public interface Iterator {//en java.util
boolean hasNext(); //retorna true si se
//puede invocar a next()
Object next();//retorna el próximo
//elemento en la iteración
void remove(); // Opcional; elimina el
//elemento actual de la colección, sólo
//puede llamarse si antes invoco next()}
 UNICA forma segura de modificar una colección
durante la iteración
Interface Iterator
 Se puede pensar a Iterator como un cursor
ubicado entre los elementos de la colección
Permite iterar sólo hacia delante
hasNext()
true
next()
iterator
hasNext()
false
Un ejemplo de Iterator
 Cálculo del gasto total en sueldos de un depto.
public double gasto(Collection c) {
double gasto=0;
Iterator it = c.iterator();
while (it.hasNext())
gasto +=
((Empleado)it.next()).getsueldo();
}
return gasto; }
/*Sencillo algoritmo polimórfico aplicable a
cualquier colección que implemente
Collection */
La interface Set
 Colección que no puede contener elementos
duplicados. Abstracción del concepto de
matemático de conjunto
 Contiene los métodos heredados de
Collection. Sólo añade restricciones para
impedir añadir elementos duplicados.
 Los elementos no están ordenados
Ejemplo 1: Set
import java.util.*;
public class FindDups {
public static void main(String args[]) {
Set s = new HashSet();//referencia a la interface, no al tipo implementado
for (int i=0; i<args.length; i++)
if (!s.add(args[i]))
System.out.println(" duplicado: "+args[i]);
System.out.println(s.size()+" palabras detectadas: "+s);
}}
java FindDups i came i saw i left
duplicado: i
duplicado: i
4 palabras detectadas: [came, left, saw, i]
Ejemplo 2: Set
import java.util.*;
public class FindDups {
public static void main(String args[]) {
Set s = new TreeSet();//cambio el tipo de implementación
for (int i=0; i<args.length; i++)
if (!s.add(args[i]))
System.out.println(" duplicado: "+args[i]);
System.out.println(s.size()+" palabras detectadas: "+s);
}}
java FindDups i came i saw i left
duplicado: i
duplicado: i
4 palabras detectadas: [came, i, left, saw]
La interface List
 Colección ordenada, también llamada secuencia
 Pueden contener elementos duplicados
 Nuevas operaciones:
 Acceso posicional. “Arrays dinámicos” que
utilizan para el acceso un índice a partir de 0
 Búsqueda
 Iteración. Con ListIterator se puede
iterar hacia atrás o hacia adelante
 Vista de rango
La interface List
public interface List extends Collection {
// Acceso Posicional
Object get(int index);
Object set(int index, Object element); // Opt. (reemplazo)
void add(int index, Object element); // Opt.
Object remove(int index); // Opt.
abstract boolean addAll(int index, Collection c);// Opt.
// Busqueda
int indexOf(Object o);
int lastIndexOf(Object o);
// Iteracion
ListIterator listIterator();
ListIterator listIterator(int index);
List subList(int from, int to); // Vista de rango
Ejemplo: List
La interface Map
 Colección de pares clave/valor (tabla-diccionario)
 No puede contener claves duplicadas
 Una clave puede mapear a lo sumo un valor
 Todo objeto puede ser usado como un clave de
hash
 public int Object.hashcode()
 Objetos iguales (equals()) deben producir el
mismo hashcode
 Distintas vistas como colecciones:
 keySet- Set de claves del mapa
 values- Collection de valores del mapa
 entrySet- Set de pares claves/valor del mapa
La interface Map
Map
// Operaciones básicas
put(Object, Object):Object;
get(Object):Object;
remove(Object):Object;
containsKey(Object):boolean;
containsValue(Object):boolean;
size():int;
isEmpty():boolean;
// Operaciones completas
putAll(Map t):void;
clear():void;
// Vistas como colecciones
keySet():Set;
values():Collection;
entrySet():Set;
Ejemplo 1: Map
 Generar números al azar y contar cuántas veces sale cada uno.
 Clave=nro. Aleatorio generado (int), Valor= frec.
class Estadistico {
private static final Integer UNO = new Integer(1);
public static void main( String args[] ) {
Map tabla = new HashMap();
for(int i=0; i < 10000; i++) {// Generar un número entre 0 y 20
Integer num = new Integer((int)(Math.random()*20));
Integer freq = (Integer) tabla.get(num);
m.put(num,
(freq==null ? UNO : new Integer(freq.intValue( ) + 1)));}
System.out.println(tabla);}}
Ejemplo 1: Map
class Estadistico {
private static final Integer UNO = new Integer(1);
public static void main( String args[] ) {
Map tabla = new HashMap();
for(int i=0; i < 10000; i++) {
// Generar un número entre 0 y 20
Integer num = new Integer((int)(Math.random()*20));
Integer freq = (Integer) tabla.get(num);
tabla.put(num,
(freq==null ? UNO : new Integer(freq.intValue( ) + 1)));}
System.out.println(tabla);
}}
Ejemplo 2: Iterar en un mapa
import java.util.*;
public class Mapa {
public static void main(String[] args) {
HashMap m = new HashMap();
m.put("Alabama", "Montgomery");
m.put("Tennesee", "Nashville");
m.put("Georgia", "Savannah");
// El siguiente valor reemplaza "Savannah":
m.put("Georgia", "Atlanta");
System.out.println(m);
iterate(m);
}
public static void iterate(Map m)
{ System.out.println("Iterando...");
Set s = m.entrySet();
Iterator i = s.iterator();
while (i.hasNext()){//ref.a Map.Entry sólo con un iterador
Map.Entry e = (Map.Entry)(i.next());//par clave-valor
System.out.println(e); } }}
Ejemplo 3: Salida resultante
{Alabama=Montgomery, Georgia=Atlanta,
Tennesee=Nashville}
Iterando...
Alabama=Montgomery
Georgia=Atlanta
Tennesee=Nashville
Ordenamiento de objetos
 Puede definirse un “orden natural” para
una clase haciendo que implemente la
interface Comparable
 Objetos de las clases que la implementen
se pueden ordenar automáticamente
 Muchas clases del JDK la implementan:
Integer
signed numerical
String
lexicographic
Double
signed numerical
Date
chronological
Ordenamiento de objetos
 Interface Comparable
public interface Comparable {
public int compareTo(Object o);
}
Compara el objeto con el que se invoca el método
compareTo con o
Retorna:
<0
si this precede a o
0
si this y o es igual a (equals())
>0
si o precede a this
 Un orden natural no siempre es suficiente
 Es necesario otro orden distinto al “natural”
 Los objetos a ordenar no implementan
Comparable
Ordenamiento de objetos
 Interface Comparator
public interface Comparator {
public int compare(Object o1, Object o2);
}
Ejemplo: Comparable
import java.util.*;
public class Name implements Comparable {
private String firstName, lastName;
public Name(String firstName, String lastName) {
if (firstName==null || lastName==null)
throw new NullPointerException();
this.firstName = firstName;
this.lastName = lastName; }
public String firstName() {return firstName;}
public String lastName() {return lastName;}
public boolean equals(Object o) {
if (!(o instanceof Name)) return false;
Name n = (Name)o;
Ejemplo: Comparable
return n.firstName.equals(firstName) &&
n.lastName.equals(lastName); }
public int hashCode() {
return 31*firstName.hashCode() + lastName.hashCode(); }
public String toString() {return firstName + " " + lastName;}
public int compareTo(Object o) {
Name n = (Name)o;
int lastCmp = lastName.compareTo(n.lastName);
return (lastCmp!=0 ? lastCmp :
firstName.compareTo(n.firstName));
}}
Ejemplo: Comparable
class NameSort {
public static void main(String args[]) {
Name n[] = {
new Name("John", "Lennon"),new Name("Karl", "Marx"),
new Name("Groucho", "Marx"),
new Name("Oscar", "Grouch")};
List l = Arrays.asList(n);
Collections.sort(l);
System.out.println(l);}}
[Oscar Grouch, John Lennon, Groucho Marx,
Karl Marx]
Interface SortedSet
 Conjunto que mantiene los elementos
ordenados en forma ascendente
 los elementos deben implementar
Comparable o,
 se debe suministrar un Comparator en el
momento de la creación
 los elementos deben ser mutuamente
comparables
 el ordenamiento debe ser consistente con
equals
Interface SortedSet
 Operaciones: Iterator atraviesa SortedSet en
orden
 Operaciones adicionales:
 de vista de rango
 se puede retornar el primer o el último
elemento
 acceso al Comparator
Interface SortedMap
 Mapa que mantiene sus claves en orden
ascendente
 las claves deben implementar Comparable
 o, se debe suministrar un Comparator en el
momento de la creación
 las claves deben ser mutuamente
comparables
 el ordenamiento debe ser consistente con
equals
Interface SortedMap
 Operaciones
 Iterator atraviesa el SortedMap en
cualquiera de sus vistas de colección en
orden ascendente de las claves
 Operaciones adicionales:
 vista de rango
 recuperar valores extremos
 acceso al Comparator
Implementaciones
 Son los objetos reales usados para
almacenar los elementos
 Implementan las interfaces
fundamentales del JCF
 Hay tres clases de implementaciones
 de propósito general
 envolturas
 de conveniencia
 Clases abstractas
Implementaciones de
propósito general
Interface
Set
Implementación
HashSet
List
Map
TreeSet
ArrayList
HashMap
Histórico
LinkedList
TreeMap
Vector
Stack
HashTable
Implementaciones
Collection
Map
Set
HashSet
SortedSet
TreeSet
List
ArrayList
Hashtable
LinkedList
Vector
Stack
HashMap
SortedMap
TreeMap
Colecciones y clases
abstractas
Abstract
Collection
Abstract
List
Collection
Abstract
Map
List
Abstract
Set
Map
Set
Colecciones y clases
abstractas
AbstractList
List
ArrayList
Cloneable
Serializable
HashMap
AbstractMap
Map
Constructores
 Cada clase que implementa Collection tiene un
constructor con un argumento de cualquier tipo
que implemente Collection
Ej.: List myVector = new Vector(myTreeSet);
 En forma similar, casi todas las clases que
implementan Map tienen un constructor con
un argumento de cualquier tipo que implemente
Map
Ej.: Map myMap=new TreeMap(myHashtable);
 Por tanto, es muy fácil cambiar un tipo de
colección por otro
Algoritmos
 Algoritmos polimórficos proveen
funcionalidad reusable
 definidos como métodos static en la
clase Collections
 Algoritmos provistos (casi todos para List)
 ordenamiento
 barajado (shuffling)
 manipulación de datos
 inversión, llenado, copia
 búsqueda y valores extremos (min/max)
Elegir una colección
depende de...
 Si es de tamaño fijo o no
 Si los elementos tienen un orden natural o no
 Si se desea insertar/borrar elementos en cualquier
posición o sólo al principio/final
 Si será necesario hacer búsquedas en una
colección con gran cantidad de datos, en forma
rápida
 Si el acceso a los elementos es aleatorio o
secuencial