Kĩ thuật lập trình - The java collections framework

The Java Collections Frameworkmap.put(20, "Chapter"); Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn a subset of the Java collections frameworkPractice working on a realistic software project as a team2OverviewFramework (in software): a general system of components and architectural solutions that provides development tools to programmers for use with a relatively wide range of applications.Collection: (hmm...) any collection of elements3Overview (cont’d)Collection, IteratorLists, ListIteratorListArrayListLinkedListStackQueue, PriorityQueueSetsSetTreeSetHashSetMapsMapTreeMapHashMapAll these interfaces and classes are part of the java.util package. Names of interfaces are in italics.4Overview (cont’d)5Overview (cont’d)A collection holds references to objects (but we say informally that it “holds objects”).A collection can contain references to two equal objects (a.equals (b)) as well as two references to the same object (a == b).An object can belong to several collections.An object can change while in a collection (unless it is immutable).6Overview (cont’d)Starting with Java 5, a collection holds objects of a specified type. A collection class’s or interface’s definition takes object type as a parameter:CollectionListStackSetA map takes two object type parameters:MapBecause collections work with different types, these are called generic collections or generics7Collection, IteratorCollection interface represents any collection.An iterator is an object that helps to traverse the collection (process all its elements in sequence).A collection supplies its own iterator(s), (returned by collection’s iterator method); the traversal sequence depends on the collection.«interface»Collection«interface»Iterator8Collection Methods boolean isEmpty ( ) int size ( ) boolean contains (Object obj) boolean add (E obj) boolean remove (E obj) Iterator iterator ( ) // ... other methodsSupplies an iterator for this collection«interface»Collection«interface»Iterator9Iterator Methods boolean hasNext ( ) E next ( ) void remove ( )«interface»Collection«interface»IteratorWhat’s “next” is determined by a particular collectionRemoves the last visited element10Iterator  “For Each” Loop Iterator iter = words.iterator( ); while (iter.hasNext ( )) { String word = iter.next ( ); } Collection words = new ArrayList(); ... for (String word : words) { }A “for each” loop is a syntactic shortcut that replaces an iterator11Lists, ListIteratorA list represents a collection in which all elements are numbered by indices:a0, a1, ..., an-1java.util:List interfaceArrayList LinkedListListIterator is an extended iterator, specific for lists (ListIterator is a subinterface of Iterator)12Lists (cont’d)«interface»Collection«interface»Iterator«interface»ListIteratorArrayListLinkedList«interface»Set«interface»Listetc.13List Methods«interface»Collection«interface»Iterator«interface»ListIterator«interface»List // All Collection methods, plus: E get (int i) E set (int i, E obj) void add (int i, E obj) E remove (int i) int indexOf (Object obj) ListIterator listIterator ( ) ListIterator listIterator (int i)These methods are familiar from ArrayList, which implements ListReturns a ListIterator that starts iterations at index i14ListIterator Methods«interface»Collection«interface»Iterator«interface»ListIterator«interface»List // The three Iterator methods, plus: int nextIndex ( ) boolean hasPrevious ( ) E previous ( ) int previousIndex ( ) void add (E obj) void set (E obj)Can traverse the list backwardCan add elements to the list (inserts after the last visited element)Can change elements (changes the last visited element)15ListIterator “Cursor” Positioning(Reverse links not shown)iter.add(obj);16ArrayListRepresents a list as a dynamic array (array that is resized when full)Provides random access to the elementsImplements all the methods of List«interface»Iterator«interface»ListIterator«interface»ListArrayListLinkedLista1a2an-1...a017LinkedListRepresents a list as a doubly-linked list with a header node (Chapter 21)Implements all the methods of Lista0a1a2an-1...«interface»Iterator«interface»ListIterator«interface»ListArrayListLinkedListheader18LinkedList (cont’d)Additional methods specific to LinkedList:«interface»Iterator«interface»ListIterator«interface»ListArrayListLinkedList void addFirst (E obj) void addLast (E obj) E getFirst ( ) E getLast ( ) E removeFirst ( ) E removeLast ( )19 ArrayList vs. LinkedListImplements a list as an array+ Provides random access to the elements- Inserting and removing elements requires shifting of subsequent elements- Needs to be resized when runs out of spaceImplements a list as a doubly-linked list with a header node- No random access to the elements — needs to traverse the list to get to the i-th element+ Inserting and removing elements is done by rearranging the links — no shifting+ Nodes are allocated and released as necessary20ArrayList vs. LinkedList (cont’d)ArrayListLinkedListget(i) and set(i, obj)O(1)O(n)add(i, obj) and remove(i)O(n)O(n)add(0, obj)O(n)O(1)add(obj)O(1)O(1)contains(obj)O(n)O(n)21ArrayList vs. LinkedList (cont’d)Works well for an ArrayList  O(n)inefficient for a LinkedList  O(n2) for (int i = 0; i class23Stacks (cont’d)Stack24Stack Methods boolean isEmpty ( ) E push (E obj) E pop ( ) E peek ( )StackReturns obj; use as voidReturns the top element without removing it from the stack25QueuesA queue provides temporary storage in the FIFO (First-In-First-Out) mannerUseful for dealing with events that have to be processed in order of their arrivaljava.util:Queue interfaceLinkedList (implements Queue)26Queues (cont’d)LinkedList«interface»Queue27Queue MethodsLinkedList«interface»Queue boolean isEmpty ( ) boolean add (E obj) E remove ( ) E peek ( )Returns the first element without removing it from the queue28Queues (cont’d) Queue q = new LinkedList ( );Methods have been added to LinkedList to implement the Queue interface: add == addLast remove == removeFirst peek == getFirstAll of the above work in O(1) time29Priority QueuesIn a priority queue, items are processed NOT in order of arrival, but in order of priority.java.util:Queue interfacePriorityQueue (implements Queue)30PriorityQueue«interface»QueuePriority Queues (cont’d)The same methods as in Queue: isEmpty, add, remove, peek.31PriorityQueue ClassWorks with Comparable objects (or takes a comparator as a parameter).The smallest item has the highest priority.Implements a priority queue as a min-heap (Chapter 26).Both add and remove methods run in O(log n) time; peek runs in O(1) time.PriorityQueue«interface»Queue32SetsA set is a collection without duplicate valuesWhat is a “duplicate” depends on the implementationDesigned for finding a value quicklyjava.util:Set interfaceTreeSet HashSet33Sets (cont’d)«interface»Collection«interface»IteratorTreeSetHashSet«interface»SetMethods of Set are the same as methods of CollectionSet’s semantics are different from Collection (no duplicates), but Set does not add any new methods.34TreeSetWorks with Comparable objects (or takes a comparator as a parameter)Implements a set as a Binary Search Tree (Chapter 24)contains, add, and remove methods run in O(log n) timeIterator returns elements in ascending orderTreeSetHashSet«interface»Set35HashSetWorks with objects for which reasonable hashCode and equals methods are definedImplements a set as a hash table (Chapter 25)contains, add, and remove methods run in O(1) timeIterator returns elements in no particular orderTreeSetHashSet«interface»Set36MapsA map is not a collection; it represents a correspondence between a set of keys and a set of valuesOnly one value can correspond to a given key; several keys can be mapped onto the same value37Maps (cont’d)java.util:Map interfaceTreeMap HashMapTreeMapHashMap«interface»Map38Map MethodsTreeMapHashMap«interface»Map boolean isEmpty ( ) int size ( ) V get (K key) V put (K key, V value) V remove (K key) boolean containsKey (Object key) Set keySet ( )Returns the set of all keys39TreeMapWorks with Comparable keys (or takes a comparator as a parameter)Implements the key set as a Binary Search Tree (Chapter 24)containsKey, get, and put methods run in O(log n) timeTreeMapHashSet«interface»Map40HashMapWorks with keys for which reasonable hashCode and equals methods are definedImplements the key set as a hash table (Chapter 25)containsKey, get, and put methods run in O(1) timeTreeMapHashMap«interface»Map41Example:traversing all key-value pairs in a mapimport java.util.*; ... Map presidents = new TreeMap ( ); presidents.put (1, “George Washington”); ... for (Integer key : presidents.keySet( ) ) { String name = presidents.get (key); System.out.println (key + " : " + name); }42Review:Why Java collections are called “generic”?Name several methods of Collection.What is an iterator?How can we obtain an iterator for a given collection?Guess what happens when we call iter.next() when there is no next element.43Review (cont’d):What are the properties of a list?Name the key methods of the List interface.How is ArrayList implemented?How is LinkedList implemented?What is the big-O for the average run time for get(i) in an ArrayList and a LinkedList?44Review (cont’d):Name a few methods specific to LinkedList.Name a few methods specific to ListIterator.Can you start iterations at any given position in a list?How is a set different from a list?Name a few methods of the Set interface.45Review (cont’d):What is the order of values returned by a TreeSet iterator?What is a map?In a map, can the same key be associated with several different values?46Case Study: Stock ExchangeImplements a toy stock exchangeCan be structured as a team development projectUses TreeSet, TreeMap, HashMap, Queue, and PriorityQueue classesA chance to practice structural and object-oriented design47Stock Market BasicsStocks are listed on a stock exchange, such as NYSE (New York Stock Exchange)A particular stock is identified by its trading symbol (for example, GOOG for Google or MSFT for Microsoft)Stocks are usually traded in multiples of 100Stock prices are in dollars and cents (can include fractions of cents in the real world)Online brokerage firms allow customers to trade stocks online from their computers48Stock Market TermsBuy order — an order to buy shares of stockSell order — an order to sell shares of stockLimit order — specifies the maximum price for a buy or a minimum price for a sellAsk — asking price for a sell orderBid — offer to buy at a certain priceMarket order — an order to buy or sell at the market price (the lowest “ask” or the highest “bid,” respectively)49SafeTrade ProgramRegistered users “trade” shares.A user must login first.The program can register a new user.A logged in user can place buy and sell orders and get price quotes for stocks.Users receive messages when their orders are executed50SafeTrade Program (cont’d)Runs on a single computer; each active user opens a separate trading window.Does not keep track of cash or of the number of shares available on each user’s account.51SafeTrade Program (cont’d)52SafeTrade Program DesignStructural DesignOO DesignDetailed DesignClasses and objects Data structures used Fields, constructors, and methods 53SafeTrade Structural DesignDatainterface => classRegistered tradersMap => TreeMapLogged-in tradersSet => TreeSetMailbox for each traderQueue => LinkedListListed stocksMap => HashMapSell orders for each stockQueue => PriorityQueue (with ascending price comparator)Buy orders for each stockQueue => PriorityQueue (with descending price comparator)54Structural Design — TradeoffsRegistered users: large number (100,000s) access time is not criticalBinary Search Tree (TreeMap)Listed stocks: relatively small number fast access time is criticalHash table (HashMap)OK to sacrifice some wasted space for better performance55SafeTrade OO Design56SafeTrade OO Design (cont’d)Part 1: Trader registration and loginA small main classKeeps track of registered and logged in traders57SafeTrade OO Design (cont’d)Part 2: Stocks and ordersKeeps track of listed stocksRepresents one stock; keeps track of all ordersRepresents one order58SafeTrade Detailed DesignDescribes constructors, fields, and methods.Documentation was generated automatically from javadoc comments in the source code. See JM\Ch20\SafeTrade\SafeTradeDocs.zip59SafeTrade Program (cont’d)GUI (supplied by us)Your job(2-5 team members)60Review:Name a few collections classes used in SafeTrade.What is a limit order?What is a market order?What data structures are used to hold sell and buy orders for a given stock? Why?Why is HashMap a good choice to represent listed stocks?61Review (cont’d):What data structure would be appropriate for keeping track of stock holdings for each trader?Explain the role of the Login interface in the SafeTrade project.62