1More on theJava Collections FrameworkCS211Fall 20002java.util.SortedSet (an interface)■ SortedSet extends Set■ For a SortedSet, the iterator( ) returns the elements in sorted order■ Methods (in addition to those inherited from Set):public Object first ( );Returns the first (lowest) object in this setpublic Object last ( );Returns the last (highest) object in this setpublic Comparator comparator ( );Returns the Comparator being used by this sorted set if there is one; returns null if the natural order is being used…3java.lang.Comparable (an interface)public int compareTo (Object x);Returns a value (< 0), (= 0), or (> 0)▲ (< 0) implies this is before x▲ (= 0) implies this.equals(x) is true▲ (> 0) implies this is after x■ Many existing classes implement Comparable● String, Double, Integer, Char, java.util.Date,…● If a class implements Comparable then that is considered to be the class’s natural ordering4java.util.Comparator (an interface)public int compare (Object x1, Object x2);Returns a value (< 0), (= 0), or (> 0)▲ (< 0) implies x1 is before x2▲ (= 0) implies x1.equals(x2) is true▲ (> 0) implies x1 is after x2■ Can often use a Comparator when a class’s natural order is not the one you want● String.CASE_INSENSITIVE_ORDER is a predefined Comparator● java.util.Collections.reverseOrder( ) returns a Comparator that reverses the natural order5SortedSet Implementations■ java.util.TreeSet ● This is the only class that implements SortedSet● TreeSet’s constructorspublic TreeSet ( );public TreeSet (Collection c);public TreeSet (Comparator comp);public TreeSet (SortedSet set);(uses the same sorting order as that used by set)■Write a method that prints out a SortedSet of words in order■ Write a method that prints out a Set of words in order6java.util.List (an interface)■ List extends Collection■ Items in a list can be accessed via their index (position in list)■ The add( ) method always puts an item at the end of the list■ The iterator( ) returns the elements in list-order■ Methods (in addition to those inherited from Collection)public Object get (int index);Returns the item at position index in the listpublic Object set (int index, Object x);Places x at position index, replacing previous item; returns the previous itempublic void add (int index, Object x);Places x at position index, shifting items to make roompublic Object remove (int index);Remove item at position index, shifting items to fill the space; returns the removed itempublic int indexOf (Object x);Return the index of the first item in the list that equals x (x.equals())…27List Implementations■ java.util.ArrayList (an array; expands via array-doubling)● Constructorspublic ArrayList ( );public ArrayList (int initialCapacity);public ArrayList (Collection c);■ java.util.LinkedList (a doubly-linked list)● Constructorspublic LinkedList ( );public LinkedList (Collection c);■ Both include some additional useful methods specific to that class ■ Both are Cloneable8Efficiency Depends on Implementation■ Object x = list.get(k);● O(1) time for ArrayList● O(k) time for LinkedList■ list.remove(0);● O(n) time for ArrayList● O(1) time for LinkedList■ If (set.contains(x))…● O(1) expected time for HashSet● O(log n) for TreeSet■ Write a Stack class■ Write a Queue class■ Write a PriorityQueue class that works on Comparable objects9SummaryCollectionsizeisEmptycontainsiteratortoArrayaddremoveSetSortedSetcomparatorfirstlast…ListgetsetaddremoveindexOf…HashSetTreeSetArrayListLinkedList10java.util.Map (an interface)■ Map does not extend Collection■ A Map contains key/value pairs instead of individual elements■ Methodspublic Object put (Object key, Object value);Associates value with key in the map; returns the old value associated with key or null if the key did not previously appear in the mappublic Object get (Object key);Returns the object to which this key is mapped or null if there is no such keypublic boolean containsKey (Object key);True iff Map contains a pair using the given keypublic boolean containsValue (Object value);True iff there is at least on pair with this valuepublic Object remove (Object key);Removes any mapping for the key; returns old value associated with key if there was one (null otherwise)11More Map Methods■ Other methodspublic int size ( );Return the number of key/value pairs in the Mappublic boolean isEmpty ( );True iff Map holds no pairs■ Bulk methodspublic void putAll (Map otherMap);Puts all the mappings from otherMap into this mappublic void clear ( );Removes all mappings■ Sets/Collections derived from a Mappublic Set keySet ( );Returns a Set whose elements are the keys of this mappublic Collection values ( );Returns a Collection whose elements are all the values of this mappublic Set entrySet( );Returns a Set of Map.Entry objects (can use getKey() and getValue())12java.util.SortedMap (an interface)■ Extends the Map contract: requires that keys are sorted■ The iterators for keySet( ), values( ), and entrySet( ) all return items in order of the keys■ Methods (in addition to those inherited from Map):public Comparator comparator ( );Returns the comparator used to compare keys for this map; null is returned if the natural order is being usedpublic Object firstKey ( );Returns the first (lowest value) key in this mappublic Object lastKey ( );Returns the last (highest value) key in this map…313Set and SortedSet Implementations■ java.util.HashMap (a class; implements Map)● Constructorspublic HashMap ( );public HashMap (Map map);public HashMap (int initialCapacity);public HashMap (int initialCapacity, float loadFactor);■ java.util.TreeMap (a class; implements SortedMap)● Constructorspublic TreeMap ( );public TreeMap (Map map);public TreeMap (Comparator comp);public TreeMap (SortedMap map);14Efficiency & Some Comments■ Both TreeMap and HashMap are meant to be accessed via keys● get, put, containsKay, remove are all fast▲ O(1) expected time for HashMap▲ O(log n) worst-case time for TreeMap● containsValue is slow▲ O(n) for both HashMap and TreeMap■ Both HashSet and TreeSet are actually implemented by building a HashMap and a TreeMap, respectively■ Given a Map that maps student ID number to student name, print out a list of students sorted by ID number and another list sorted by name (assume no duplicate names)15The java.util.Arrays Utility Class■ Provides useful static methods for
View Full Document
Unlocking...