Transcript CS110

CS110 Lecture 12
Tuesday, March 9, 2004
• Announcements
– hw5 due Thursday
– Spring break next week
• Agenda
– questions
– ArrayList
– TreeMap
Lecture 12
1
ArrayList
•
•
•
•
A Collection class in the Java API
Like an array: stores elements at positions 0,1,…
Can grow as needed!
Unlike an array in other ways too
–
–
–
–
stores only objects (not primitive types)
can store different kinds of objects simultaneously
you must cast when retrieving
send explicit messages instead of using [ ] for access
• Read ArrayListDemo.java
Lecture 12
2
Casting
• Syntax: (Bar)foo tells the compiler to treat object
foo as something of type Bar
• ArrayList get returns an anonymous Object
for (int i = 0; i<myList.size(); i++ ){
SimpleObject foo =
(SimpleObject)myList.get(i);
System.out.println
(i + "\t" + foo.name);
}
• Perhaps the compiler ought to know, but it doesn’t
Lecture 12
3
ArrayList API
•
•
•
•
•
•
•
•
•
•
can store: any Object, not primitive types
declaration: ArrayList myList
creation:
myList = new ArrayList( )
put at end: myList.add( obj )
put at index: myList.add( index, obj )
– moves later entries down the list
get:
(Type)myList.get( index )
– cast to proper Type after get
replace:
myList.set( index, obj )
remove:
myList.remove( index )
size:
myList.size( )
looping:
for( ; ; )
Lecture 12
4
Boxes and arrows for ArrayList
ArrayList
myList:
ArrayList
Object
0:
Object
SimpleObject
String
name:
"zero"
SimpleObject
1:
String
Object
"one"
name:
2:
•••
SimpleObject
String
name:
Lecture 12
"two"
5
hw5
• array practice (sorting)
• ArrayList practice: modify Bank.java so
that it uses an ArrayList of BankAccounts
instead of an array
– BankAccounts have numbers 0, 1, 2, …
– Banker can open as many accounts as she likes!
Lecture 12
6
Maps
• arrays and ArrayLists locate entries by index
– index is an integer position, starting at 0
• A Map locates entries by key
– key is often a String (think dictionary, phone book)
• A map stores key-value pairs
– key: “Java”
value:
“a modern OO language”
PhoneNumber
areaCode: 617
exchange: 287
number: 5000
– key: “UMass” value:
Lecture 12
7
Duplicates?
• The same value may appear more than once in a
collection (array, ArrayList or Map)
– my wife and I have the same phone number
– “field” and “instance variable” have the same definition
– in an array, foo[3] may == foo[7]
• In a Map, keys are unique
• If you want to arrange for one person to have more
than one phone number or one word to have more
than one definition you need to work harder
(see last slides, JOI Chapter4)
Lecture 12
8
TreeMap
• Java API provides class TreeMap
• Don’t ask why it’s called that
• Key can be any Object
(but our keys will always be String objects)
• TreeMaps, like ArrayLists
– can grow
– store Objects (references, not primitive types)
– are heterogeneous
• can hold objects of different types
• need to cast what you get from a TreeMap
Lecture 12
9
Directory
• Model windows folder
• Contains TextFiles
(not other Folders - wait for Chapter 5)
• API: create, add file to, get file from, get
size, get owner, get create/mod date
• Design: Directory object has a TreeMap
field storing TextFile objects keyed by
String filename
• You write this for homework
Lecture 12
10
Dictionary
• Model a real dictionary
• A collection of definitions of words
– A word is a String
– A definition will be an instance of class
Definition
• Design: Dictionary object has a TreeMap
field storing Definition objects keyed by
String words
• API: create, add entry, look up entry, get
size, arrange for printing the whole
Dictionary
Lecture 12
11
Dictionary.java
• Architecture: a Dictionary object is a thin wrapper
around a TreeMap
• Prepare to use classes in java.util package (line 6)
• private TreeMap instance variable
– declared on line 18
– created in constructor (line 26)
• Put a Definition in this Dictionary: addEntry
method (36)
– parameters: String word, reference to Definition
instance
– delegate to TreeMap put method
Lecture 12
12
Dictionary (continued)
• Look up a Definition: getEntry (line 48)
– delegate to TreeMap get method, passing String word
as the argument (line 50)
– cast retrieved anonymous object to Definition
– return the Definition (null if not found)
• How large is this Dictionary? getSize (line 61)
– delegate to TreeMap size method
• What’s a Definition?
– just one String field, set in constructor, access by
public getter (toString)
– would be richer in a real dictionary (pronunciation,
etymology, …)
Lecture 12
13
TreeMap boxes and arrows
Dictionary
entries:
entries:
TreeMap
"a geometric object in a plane"
TreeMap
Object Object
"shape"
Definition
String
definition:
entries:
Object Object
•••
"quadrilateral"
Definition
String
definition:
entries:
"a shape with four sides"
Lecture 12
14
Class Lookup
• Dictionary has no unit test
• Class Lookup is a client for Dictionary
(and tests it thoroughly)
• All of Lookup is static
> java Lookup <word> <word> … all
• Lookup.java sends toString messages to a
Definition object (line 53) and to a
Dictionary object (line 103)
Lecture 12
15
Looping on a TreeMap
• To print the whole Dictionary, Lookup sends a
toString message, invoking Dictionary
toString method (line 70)
• Subtle, since there’s no index to loop with
• Uses an Iterator object Java tool custom designed for looping
• Iterator API has just two methods:
– boolean hasNext()
– Object next()
Lecture 12
16
Getting an Iterator
Set allWords = entries.keySet();
Iterator wordIterator =
allWords.iterator();
•
•
•
•
ask the entries field (a TreeMap) for its keySet
ask the keySet to give you an Iterator
wI is like a list of the keys in the entries Map
You can infer from this code that
– Set and Iterator are classes in the Java API
– keySet is a method in class TreeMap; it returns a Set
– iterator is a method in class Set; it returns an Iterator
Lecture 12
17
Using an Iterator
while ( wordIterator.hasNext() ) {
word = (String)wordIterator.next();
definition = this.getEntry( word );
str += word + ":\n" +
definition.toString() + "\n";
}
• hasNext() returns false when at end of list
• next() returns a reference to the next Object in
the list
• cast that to a String since that’s what the key is
Lecture 12
18
Building a multiline String
while ( wordIterator.hasNext() ) {
word = (String)wordIterator.next();
definition = this.getEntry( word );
str += word + ":\n" +
definition.toString() + "\n";
}
• use the key to look up a Definition
• send the Definition a toString message
• add two lines to the String str we are building to
represent the whole Dictionary
Lecture 12
19
TreeMap summary
•
•
•
•
declaration: TreeMap mapName;
creation:
new TreeMap( );
put:
mapName.put(Object key, Object obj)
get:
(Type)mapName.get(Object key)
cast to proper Type
• length:
mapName.size( )
• looping:
use Iterator
mapName.keySet( ).iterator( )
Lecture 12
20
Collections of collections
• Dictionary might map a word to an
ArrayList of definitions
• Screen maintains a private field that’s an
array of arrays of char:
private char[][] pixels;
Lecture 12
21
Figure 4.5
Object structure of a 2x3 Screen
Screen
int
width:
2
0: ‘ ‘
1: ‘ ‘
2: ‘ 5‘
char[][]
int
height:
char[]
0:
3
1:
char[][]
pixels:
char[]
0: ‘ ‘
1: ‘ ‘
2: ‘ 5‘
Lecture 12
22
hw6
• Due Thursday after Spring break
• TreeMap practice
– class Directory
– little Bank, using a TreeMap
Lecture 12
23