Aula 12 - Coleções

Prévia do material em texto

Projeto de Software / Programação 3 
Coleções em Java 
Márcio Ribeiro 
marcio@ic.ufal.br 
twitter.com/marciomribeiro 
Java	
  Collec*ons	
  
3 
Collec*on	
  
§  An	
  object	
  that	
  groups	
  mul*ple	
  elements	
  into	
  a	
  single	
  unit	
  
§  Used	
  to:	
  
§  Store	
  
§  Retrieve	
  
§  Manipulate	
  
§  Examples	
  
§  Collec*on	
  of	
  cards	
  
§  Collec*on	
  of	
  products	
  (shopping	
  cart)	
  
§  Telephone	
  directory	
  (mapping	
  of	
  names	
  to	
  phone	
  numbers)	
  
4 
Collec*ons	
  framework	
  
§  Interfaces	
  
§  Abstract	
  data	
  types	
  that	
  represent	
  collec*ons	
  
§  Allow	
   collec*ons	
   to	
   be	
   manipulated	
   independently	
   of	
   the	
  
details	
  of	
  their	
  representa*on	
  
§  Implementa*ons	
  
§  Reusable	
  data	
  structures	
  
§  Polymorphic	
  algorithms	
  
§  Sor*ng	
  
§  Searching	
  elements	
  
5 
Benefits	
  
§  Reduces	
  programming	
  effort	
  
§  Increases	
  program	
  speed	
  and	
  quality	
  
§  Interchangeable	
  implementa*ons	
  
§  SoMware	
  reuse	
  
6 
Interfaces	
  
Collection! Map!
List!Set! Queue!
SortedSet!
SortedMap!
7 
Collec*on	
  
§  Root	
  of	
  the	
  collec*on	
  hierarchy	
  
§  Group	
  of	
  objects	
  known	
  as	
  its	
  elements	
  
§  Common	
  denominator	
  that	
  all	
  collec*ons	
  implement	
  (use	
  it	
  
when	
  maximum	
  generality	
  is	
  desired)	
  
§  Some	
  types…	
  
§  …	
  allow	
  duplicates	
  and	
  others	
  do	
  not	
  
§  …	
  are	
  ordered	
  and	
  others	
  are	
  unordered	
  
8 
Collec*on	
  interface	
  
public interface Collection<E> extends Iterable<E> {	
	
 int size();	
 boolean isEmpty();	
 boolean contains(Object element);	
 boolean add(E element);	
 boolean remove(Object element);	
 Iterator<E> iterator();	
	
 boolean containsAll(Collection<?> c);	
 boolean addAll(Collection<? extends E> c); 	
 boolean removeAll(Collection<?> c);	
 boolean retainAll(Collection<?> c);	
 void clear();	
	
 Object[] toArray();	
 <T> T[] toArray(T[] a);	
	
}	
9 
List	
  
§  Ordered	
  collec*on	
  
§  May	
  contain	
  duplicate	
  elements	
  
§  Includes	
  opera*ons	
  to	
  access	
  determined	
  posi*ons	
  
§  Implementa*ons	
  
§  ArrayList	
  
§  LinkedList	
  
§  Vector	
  
10 
List	
  interface	
  
public interface List<E> extends Collection<E> {	
	
 E get(int index);	
 E set(int index, E element);	
 boolean add(E element); 	
 void add(int index, E element);	
 E remove(int index);	
 boolean addAll(int index, Collection<? extends E> c);	
	
 // Search	
 int indexOf(Object o);	
 int lastIndexOf(Object o);	
	
 // Iteration	
 ListIterator<E> listIterator();	
 ListIterator<E> listIterator(int index);	
	
 // Range-view	
 List<E> subList(int from, int to);	
}	
11 
Example	
  
public static void main(String[] args) {	
 	
 Integer i1 = new Integer(7);	
 Integer i2 = new Integer(8);	
 Integer i3 = new Integer(9);	
 Integer i4 = new Integer(10);	
	 		
 List<Integer> list = new LinkedList<Integer>();	
 list.add(i4);	
 list.add(i3);	
 list.add(i2);	
 list.add(i1);	
	 		
 System.out.println(list);	
	
}	
[10, 9, 8, 7]	
12 
Map	
  
§  Map	
  keys	
  to	
  values;	
  cannot	
  have	
  duplicate	
  keys	
  
§  Models	
  the	
  mathema*cal	
  func+on	
  abstrac*on	
  
Andrew 
a@se.com 
… Jones 
j@se.com 
… Yuri 
y@se.com 
0 … 23 … 119 
h(JONES) = 23!
13 
Map	
  interface	
  
public interface Map<K,V> {	
	
 V put(K key, V value);	
 V get(Object key);	
 V remove(Object key);	
 boolean containsKey(Object key);	
 boolean containsValue(Object value);	
 int size();	
 boolean isEmpty();	
	
 // Bulk operations	
 void putAll(Map<? extends K, ? extends V> m);	
 void clear();	
	
 // Collection Views	
 public Set<K> keySet();	
 public Collection<V> values();	
	
}	
14 
Example	
  
public static void main(String[] args) {	
 	
 Map<Integer,String> students = new HashMap<Integer,String>();	
	 		
 students.put(1, "Gabriel");	
 students.put(2, "Leonildo");	
 students.put(3, "Carlos");	
 students.put(4, "Luan");	
 students.put(5, "Tamirys");	
 students.put(6, "Laylla");	
	 		
 System.out.println(students);	
 System.out.println("ID = 1 --> " + students.get(1));	
}	
{1=Gabriel, 2=Leonildo, 3=Carlos, 4=Luan, 5=Tamirys, 6=Laylla}	
ID = 1 --> Gabriel	
15 
Set	
  
§  Models	
   the	
   mathema*cal	
   set	
   abstrac*on:	
   so,	
   duplicated	
  
elements	
  are	
  prohibited	
  
§  Implementa*ons	
  
§  HashSet	
  
•  Hash	
  table	
  
•  No	
  guarantees	
  concerning	
  the	
  order	
  of	
  itera5on	
  
§  TreeSet	
  
•  Red-­‐Black	
  tree	
  
•  Orders	
  its	
  elements	
  based	
  on	
  their	
  values	
  
§  LinkedHashSet	
  
•  Orders	
  elements	
  based	
  on	
  the	
  order	
  in	
  which	
  they	
  were	
  inserted	
  
•  Differs	
   from	
   HashSet:	
   it	
   maintains	
   a	
   doubly-­‐linked	
   list	
   running	
  
through	
  all	
  of	
  its	
  entries	
  
16 
Example	
  
public class FindDups {	
 public static void main(String[] args) {	
 Set<String> s = new HashSet<String>();	
 for (String a : args)	
 if (!s.add(a))	
 System.out.println("Duplicate detected: " + a);	
	
 System.out.println(s.size() + " distinct words: " + s);	
 }	
}	
java FindDups i came i saw i left	
Duplicate detected: i	
Duplicate detected: i	
4 distinct words: [i, left, saw, came]	
17 
Using	
  TreeSet:	
  prints	
  in	
  alphabe*cal	
  order!	
  
public class FindDups {	
 public static void main(String[] args) {	
 Set<String> s = new TreeSet<String>();	
 for (String a : args)	
 if (!s.add(a))	
 System.out.println("Duplicate detected: " + a);	
	
 System.out.println(s.size() + " distinct words: " + s);	
 }	
}	
java FindDups i came i saw i left	
Duplicate detected: i	
Duplicate detected: i	
4 distinct words: [came, i, left, saw]	
Exercises	
  
19 
Genera*ng	
  a	
  JSON	
  file	
  
[	
 {"k11":"v11","k12":"v12","k13":"v13"},	
 {"k22":"v22","k21":"v21","k23":"v23"}	
]	
Map m1 = new LinkedHashMap();	
Map m2 = new HashMap();	
List l1 = new LinkedList();	
	
m1.put("k11", "v11");	
m1.put("k12”, "v12");	
m1.put("k13”, "v13");	
m2.put("k21", "v21");	
m2.put("k22", "v22");	
m2.put("k23", "v23");	
l1.add(m1);	
l1.add(m2);	
20 
Try	
  yourself…	
  
{	
 "k3":["lv1","lv2"],	
 "k1":"v1",	
 "k2":{	
 "mk1":"mv1",	
 "mk2":["lv1","lv2"]	
 }	
}	
Map m0 = new HashMap();	
Map m1 = new LinkedHashMap();	
List l1 = new LinkedList();	
m0.put("k1", "v1");	
m0.put("k2", m1);	
m0.put("k3", l1);	
m1.put("mk1", "mv1");	
l1.add("lv1");	
l1.add("lv2");	
m1.put("mk2", l1);	
21 
Let’s	
  try	
  one	
  more	
  *me…	
  
{	
 name=foo,	
 num=100,	
 balance=1000.21,	
 is_vip=true,	
 nickname=null,	
 list1=[	
 foo,	
 100,	
 1000.21	
 ],	
 list2=[	
 true,	
 null	
 ]	
}	
List list1 = new LinkedList();	
list1.add("foo");	
list1.add(new Integer(100));	
list1.add(new Double(1000.21));	
	
List list2 = new ArrayList();	
list2.add(new Boolean(true));	
list2.add(null);	
	
Map obj = new LinkedHashMap();	
obj.put("name", "foo");	
obj.put("num", new Integer(100));	
obj.put("balance", new Double(1000.21));	
obj.put("is_vip", new Boolean(true));	
obj.put("nickname", null);	
	
obj.put("list1", list1);	
obj.put("list2", list2);	
	
System.out.println(obj);