Java's Collection Framework - University Of Arizona

11m ago
588.90 KB
23 Pages
Last View : 3m ago
Last Download : n/a
Upload by : Anton Mixon

Java's Collection FrameworkAnother use of polymorphism via interfacesRick Mercer1

More useful Polymorphismw Where we are at?—Considering examples of Java’s polymorphismvia interfacesw Where are we going?—Consider a framework that is Full of examples of polymorphism throughinterfaces Reusable– Note: Some of you have seen a few of these slides2

Outlinew Java's Collection Framework—w Collection framework containsInterfaces (ADTs): specification not implementationConcrete implementations as classesPolymorphic Algorithms to search, sort, find, shuffle, .———w Unified architecture for representing and manipulatingcollectionsAlgorithms are polymorphic:—the same method can be used on many differentimplementations of the appropriate collection interface.In essence, algorithms are reusable functionality.3

The Core Collection interfacesthere are othersImage from the Java Tutorial4

Abstract Data Typew Abstract data type (ADT) is a specificationof the behaviour (methods) of a type———Specifies method names to add, remove, findSpecifies if elements are unique, indexed,accessible from only one location, mapped,.An ADT shows no implementation no structure to store elements, no implementedalgorithmsw What Java construct nicely specifies ADTs?5

List E , an ADT written as aJava interfacew interface List E defines a collection witha first element, a last, and distinct predecessorsand successors, can insert anywhere—duplicates that "equals" each other are allowedList String list new ArrayList ();list.add("Abc");list.add(0, "Def");assertEquals("Def", list.get(0));assertEquals("Abc", list.get(1));6

Iteratorsw Iterators provide a general way to traverseall elements in a collectionList String list new ArrayList dd("3-ThIrD");Iterator String itr list.iterator();while erCase());Output1-first2-second3-third7

New way to visit elements:Java's Enhanced for Loopw General formfor (Type element : collection) {element is the next thing visited each iteration}for (String str : list)System.out.println(str.toLowerCase());8

Polymorphic Algorithmsw Java has polymorphic algorithms to providefunctionality for different types of collectionsvoid sort(List T list)void reverse(List T list)void swap(List T list, int i, int j)boolean replaceAll(List T list, T oldVal, T newVal)void rotate(List ? list, int distance) // ? any typew And since List extends interface Collectionint frequency(Collection ? c, Object o)public static T Collection T // T is lower boundunmodifiableCollection(Collection ? extends T c)9

Lower Bound / Upper Bound / Wild Cardw E extends Comparable E ——Extends is used as an upper bound of the given typeE must be Comparable or anything that implementsComparable or extends that interfacew ? super Integer ———The wildcard ? is any typesuper, means a superclass or super interfacePossible types for Integer: Number and Objectw This topic will NOT be on the test10

But this willintuitive enough?// Assume list has these added: A, B, C, then AassertEquals("[A, B, C, A]", list.toString());assertEquals("A", Collections.min(list));assertEquals("C", Collections.max(list));assertEquals(2, Collections.frequency(list, "A"));Collections.swap(list, 0, 1);assertEquals("[B, A, C, A]", ls("[A, A, B, C]", list.toString());assertEquals(2, Collections.binarySearch(list, "B"));int index Collections.binarySearch(list, "A");assertTrue(index 0 index 1);Collections.rotate(list, 2);assertEquals("[B, C, A, A]", list.toString());11

Set and SortedSetw interface Set E —add addAll remove size but no get!w Two classes that implement Set E —TreeSet: values stored in order, O(log n)—HashSet: values in a hash table, no order, O(1)w SortedSet extends Set by adding methods EE first() ESortedSet E SortedSet E SortedSet E last()tailSet(E fromElement),headSet(E fromElement)subSet(E fromElement, E toElement)12

TreeSet elements are in orderSet String names new TreeSet d("Chris");names.add("Chris"); // not addedfor (String name : names)System.out.print(name " "); // Chris Dakota DevonWhat if change to HashSet ()Chris Devon Dakota13

The Map Interface (ADT)w Map describes a type that stores a collectionof elements that consists of a key and a valuew A Map associates (maps) a key the it's valuew The keys must be unique——the values need not be uniqueput destroys one with same key14

interface Map K, V public V put(K key, V value)—associates key to value and stores mappingpublic V get(Object key)—associates the value to which key is mapped or nullpublic boolean containsKey(Object key)—returns true if the Map already uses the keypublic V remove(Object key)—returns previous value associated with specifiedkey, or null if there was no mapping for key.Collection V values()—get a collection you can iterate over15

keySet and ValuesMap String, Integer rankings new HashMap ();rankings.put("M", 1);rankings.put("A", 2);Change to Treerankings.put("P", 3);Set String keys ());System.out.println(keys);// [P, A, M]Collection Integer values ss());System.out.println(values);// [3, 2, 1]Outputclass java.util.HashMap KeySet[P, A, M]class java.util.HashMap Values[3, 2, 1]class java.util.TreeMap KeySet[A, M, P]class java.util.TreeMap Values[2, 1, 3]16

interface Queue E boolean add(E e) Inserts e into this queueE element() Retrieves, but does not remove, the head ofthis queueboolean offer(E e) Inserts e into this queueE peek() Retrieves, but does not remove, the head of thisqueue, or returns null if this queue is emptyE poll() Retrieves and removes the head of this queue, orreturns null if this queue is emptyE remove() Retrieves and removes the head of this queue17

A thread safe FIFO queueArrayBlockingQueue Double numberQ new ArrayBlockingQueue ls(3.3, numberQ.peek(), 0.1);assertEquals(3.3, numberQ.remove(), 0.1);assertEquals(2.2, numberQ.remove(), 0.1);assertEquals(5.5, numberQ.peek(), 0.1);assertEquals(3, numberQ.size());18




There’s more w Previous slides have a lot, but not til/Collection.htmlw Should the Java array object be considered?w And then, what if you want a graphical viewof a list and we will —Use interface ListModel E 22

Interface ListModelpublic interface ListModel E {public int getSize();public String toString();public E getElementAt(int index);public void addListDataListener(ListDataListener l);public void removeListDataListener(ListDataListener l);}w The argument type for JList—A graphical view of a listsetModel(ListModel String model)23

3 Outline ! Java's Collection Framework — Unified architecture for representing and manipulating collections ! Collection framework contains — Interfaces (ADTs): specification not implementation — Concrete implementations as classes — Polymorphic Algorithms to sear