Download colecciones

Informática III
Colecciones en Java
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
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 uno 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
José
emps
[0]
[1]
Estela
[2]
Nora
[3]
[4]
[5]
Mariano
Javier
Gracia
Arrays
 Arrays de referencias a objetos
 Declarar el array
 Dimensionarlo
 LLenar los elemenentos individuales
con
Paso 2
Paso 1 referencias
Empleado [] emps = new Empleado[6];
for (int j = 0; j < emps.length; j++)
{ emps[j] = new Empleado();}
emps[0].setName(“José”);
...
Paso 3
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)
C++’s Standard
 Algoritmos (funcionalidad Template
reusable)
Library es
también un framework
de colecciones
Beneficios del uso del JCF
 Reduce esfuerzos de programación
 Produce un incremento en velocidad y
calidad del programa
 Permite la interoperabilidad entre APIs
no
relacionadas
 Reduce los esfuerzos de aprendizaje
 Reduce los esfuerzos de diseño
Objetivos del proyecto
 API pequeña
 Número de interfaces
 Número de métodos por interface
 Bajo “peso conceptual”
 Construído 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();
boolean isEmpty();
boolean contains(Object element);
boolean add(Object element); // Opcional(*)
boolean remove(Object element);//Opcional (*)
Iterator iterator();
// 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
Object[] toArray();
Object[] toArray(Object a[]);
}
(*) retornan true si la colección cambia como
resultado de aplicar el método, false en
caso contrario
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
 Filtrado de elementos que no cumplen una
condición
static void filter(Collection c) {
Iterator it = c.iterator();
while (it.hasNext())
if (!cond(it.next()))//Object
it.remove();}
/*Código genérico para cualquier
colección que admita la eliminación
de elementos */
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 prohibir
elementos duplicados.
 Los elementos no están ordenados
Ejemplo: Set
import java.util.*;
public class FindDups {
public static void main(String args[]) {
Set s = new HashSet();
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]
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.
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
private static void swap(List a, int i, int j) {
Object tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);}
public static void shuffle(List list, Random rnd) {
for (int i=list.size(); i>1; i--)swap(list, i-1, rnd.nextInt(i));}
//which is included in the JDK's Collections class
import java.util.*;
public class Shuffle {
public static void main(String args[]) {
List l = new ArrayList();
for (int i=0; i<args.length; i++) l.add(args[i]);
Collections.shuffle(l, new Random());
System.out.println(l);}}
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
 Métodos que permiten ver al mapa como
colección:
 keySet- Set de claves del mapa
 values- Collection de valores 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
void putAll(Map t):void;
void clear():void;
// Vistas como colecciones
keySet():Set;
values():Collection;
entrySet():Set;
Ejemplo: Map
import java.util.*;
public class Frecuencia {
private static final Integer UNO = new Integer(1);
public static void main(String args[]) {
Map m = new HashMap();
for (int i=0; i<args.length; i++) {//inicializa tabla de línea de cmd
Integer freq = (Integer) m.get(args[i]);
m.put(args[i],
(freq==null ? UNO : new Integer(freq.intValue() + 1)));}
System.out.println(m.size()+" pal. distintas");
System.out.println(m);}}
% java Freq if it is to be it is up to me to delegate
8 pal. distintas
{to=3, me=1, delegate=1, it=2, is=2, if=1, be=1, up=1}
Ordenamiento de objetos
 Puede definirse un “orden natural” para
una
clase haciendo que implemente la interface
Comparable
 Objetos de las clases que la implementen
pueden ordenarse 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 ordenan 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
 Operaciones: Iterator atraviesa SortedSet en
orden
 Operaciones adicionales:
 de vista de rango
 se puede retornar el primer o el último
elemento
Interface SortedMap
 Mapa que mantiene sus entradas en orden
ascendente
 los elementos deben implementar Comparable
o
 se debe suministrar un Comparator en el
momento de la creación
 Operaciones: Iterator atraviesa el SortedMap en
cualquiera de sus vistas de colección en orden de
las claves
 Operaciones adicionales:
 vista de rango
 puntos finales (claves)
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
Implementations
Hash
Table
Interfaces
Set
HashSet
List
Map
Resizeab Balanced
le Array
Tree
TreeSet
ArrayList
HashMap
Linked
List
LinkedList
TreeMap
Implementaciones
Collection
Map
Set
HashSet
SortedSet
TreeSet
List
ArrayList
Hashtable
LinkedList
Vector
Stack
HashMap
SortedMap
TreeMap
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
argumentos de cualquier tipo que implemente
Map
Ej.: Map myMap=new TreeMap(myHashtable);
 Por tanto, es muy fácil convertir de un tipo de
colección a otra
Algoritmos
 Algoritmos polimórficos proveen
funcionalidad
reusable
 definidos como métodos static en la
clase Collections
 Algoritmos provistos
 ordenamiento
 barajado (shuffling)
 manipulación de datos
 inversión, llenado, copia
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
Implementaciones más
viejas
 El JCF fue introducido con el JDK 1.2
 Versiones más viejas incluían
 java.util.Vector
 java.util.Hashtable
 Estas implementaciones fueron
extendidas
para implementar las interfaces
fundamentales del JCF pero aún tienen
todas sus operaciones heredadas
Arrays
 Los arrays no forman parte del JCF pero no
fueron ignorados
 class Arrays
static
static
static
static
static
void sort(Object[] a)
int binarySearch(Object[] a, Object key)
boolean equals(Object[] a, Object[] a2)
void fill(Object[] a, Object val)
void fill(Object[] a, Object val,
int from, int to)
static List asList(Object[] a)