CS61B Lecture #15Administrative:• Test Review Session• Reminder: auto-grader run sometime tonight.Today:• Asymptotic complexity (from last time)• Iterators, ListIterators• Containers and maps in the abstract• ViewsReadings for Today:Data Structures,Chapter 2.Readings for next Topic:Data Structures,Chapter 3.Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 1Some Intuition on Meaning of Growth• How big a problem can you solve in a given time?• In the following table, left column shows time in mi-croseconds to solve a given problem as a function ofproblem size N.• Entries show thesize of problemthat can be solvedin a second, hour, month (31 days), and century, forvarious relationships between time required and prob-lem size.• N = problem sizeTime (µsec)Max N Possible in1 second 1 hour 1 month 1 centurylg N 1030000010109108·1011109·1014N 1063.6 · 1092.7 · 10123.2 · 1015N lg N63000 1.3 · 1087.4 · 10106.9 · 1013N21000 60000 1.6 · 1065.6 · 107N3100 1500 14000 1500002N20 32 41 51Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 2Data Types in the Abstract• Most of the time, shouldnotworry about implemen-tation of data structures, search, etc.• What they do for us—their specification—is impor-tant.• Java has several standard types (in java.util) torepresent collections of objects– Six interfaces:∗ Collection: General collections of items.∗ List: Sequences with duplication∗ Set, SortedSet: Collections without duplication∗ Map, SortedMap: Dictionaries (key 7→ value)– Concrete classes that provide actual instances:LinkedList, ArrayList, HashSet, TreeSet.– To make change easier, purists would use the con-crete types only for new, interfaces for parame-ter types, local variables.Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 3Collection Structures in java.utilCollectionList SetSortedSetLinkedList ArrayList Vector HashSet TreeSetStackinterfaceclassMapSortedMapHashMap WeakHashMap TreeMapLast modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 4The Collection Interface• Collection interface. Main functions promised:– Membership tests: contains (∈), containsAll(⊆)– Other queries: size, isEmpty– Retrieval: iterator, toArray–Optionalmodifiers: add, addAll, clear, remove,removeAll (set difference), retainAll (intersect)• Design point: Optional operations may throwUnsupportedOperationExceptionWhy not separate interfaces?• Answer: avoid proliferation of lower types, inter-faces (Vector, readonly Vector, add-only remove Vec-tor).Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 5Problem: How to Retrieve?• Collections don’t always have an order—no first, nonth• So how to get things out?• Even for types of Collection thatdohave an order-ing, indexing (as for arrays) not always best (fastest)way to get elements.• Abstraction to the rescue: define retrieval inter-face:package java.util;public interface Iterator {/** True iff there’s more. */boolean hasNext ();/** Return next item and then move on. */Object next ();/** Remove last item returned by next() from underlying* Collection. May throw exception if unsupported. */void remove ();}• Iterator is a kind of “moving finger” through a Col-lection.Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 6The List Interface• Extends Collection• Intended to representindexed sequences(like ar-rays, but more general).• Adds new methods to those of Collection:– Membership tests: indexOf, lastIndexOf.– Retrieval: get(i), listIterator, sublist(B, E).– Modifiers: add and addAll with additional indexto saywhereto add. Likewise for removal opera-tions. set operation to go with get.• Type ListIterator extends Iterator:– Adds previous and hasPrevious.– nextIndex gives position in list.– add, remove, and set allow one to iterate througha list, inserting, removing, or changing as you go.Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 7Examples of Use I: Linear SearchProblem: Find an element in list satisfying predicate.• Assume following definition:/** A one-argument predicate (true/false valued).* Calling ’test’ applies the predicate. */interface Predicate {/** True iff ARG passes the test. */boolean test (Object arg);}• Solution I:/** The first element of L that satisfies P,* or null if none. */static Object exists (List L, Predicate P) {for (int i = 0; i < L.size (); i += 1)if (P.test (L.get (i))) return L.get (i);return null;}• Disadvantage: On some Lists, get(k) can be a Θ(k)operation, leading to Θ(N2) algorithm, for lists ofsize N .Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 8Faster Linear Search• The iterator method is intended to return an iter-ator that is tuned to the data structure, and gener-ally O(1) in time.• With ordered collection (like List), iterator is alsoordered.// [NOTE: Changed from the paper version// handed out in lecture.]/** The first element of L that satisfies P,* or null if none. */static Object exists (List L, Predicate P) {for (Iterator i = L.iterator ();i.hasNext (); ) {Object obj = i.next ();if (P.test (obj))return obj;}return null;}Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 9Example of Use II: Inserting New ElementsProblem: After first instance of one object, insert anew object./** Insert OBJ after AFTER in L. */static void insertAfter (List L, Object obj, Object after){for (ListIterator i = L.listIterator (); i.hasNext (); ) {Object x = i.next ();if (after.equals (x)) {i.add (obj);break;}}}Last modified: Fri Oct 5 10:21:28 2001 CS61B: Lecture #15 10Sublists and ViewsProblem: Delete items K, K + 1, . . . , M from List L.• The sublist operation is supposed to yield a “viewof” part of an existing list.• Aviewis an alternative presentation of (interfaceto) an existing object.• Changes in original list reflected in sublist view, andvice-versa.• For example, could solve problem like this:L.sublist (K, M+1).clear ();which modifies L by removing the elements in thesublist consisting of items K through M+1.• Another example of a view: a Map is a kind of modi-fiable function:Object get (Object key); // Value at KEY.Object put (Object key, Object value);// Set get(KEY) -> VALUE• Provides three views, which change as the Map changes:Set keySet (); // The set of all keysCollection values (); // The multiset of mapped-to valuesSet entrySet (); // The set of all (key, value) pairsLast modified: Fri Oct 5 10:21:28 2001 CS61B:
View Full Document
Unlocking...