Transcript Function Objects

CS2110: SW Development Methods
OO Design and the Java
Collections Framework
Part 2
• Topics:
• Comparable and Comparator interfaces in JCF
• Function objects
• Textbook readings:
• More from MSD, Chapter 9
• Pages 641-647
• Pages 650-651 up to 9.4.1;
Pages 666-671.
Overview
• In Part 1 of this Unit, we learned:
• About the Collections framework
• Collection and List interfaces
• Iterator, ListIterator
• Also should now study static methods from the
book or class notes
• Here in Part 2 of this Unit, we will see:
• Defining order for sort(), max(), etc.
• Using an interface and a function-object
Back to Java: Comparable and Comparator
• In computing, we often want to order a set of
items
• Find the max/best or min/worst
• Sort them in order
• Note how this is different than what is needed for
search (where we just need equals)
• Need a way to compare two items
• Want to flexible way to “compare” using different
criteria
• In Java, let’s us use Collection(s) methods to meet
our own special needs. (Powerful!)
Check out the Collections class
• Class Collections
• utility methods for doing operations on Collections,
Lists (that almost always contain homogenous
elements)
• Note very similar Arrays class
• See MSD textbook, Section 9.5, pp. 666f
• Methods (static, mostly for Lists)
• search a list for an item: binarySearch()
• sort(), max(), min() -- uses compareTo() or
Comparator object
• reverse(), fill(), shuffle(), copy(), replaceAll()
• List list2 = Collections.unmodifiableList(list1); // p. 668
Comparable Interface
• First solution: Can we ask an object how it
compares to a second object?
• Sure:
string1.compareTo(string2)
• Programming convention: Return value as follows:
• zero if the same
• negative value if first item strictly less than second
• positive value if first item strictly greater than second
• Java provides a Comparable interface
int compareTo(Object o)
• Note the parameter is an object
• Like equals() and for the same reason
Writing compareTo for Your Classes
• If you ever want to put your own objects in
Collections, and use sort(), max(), min(),…
• Make your class implement Comparable
• Implement the compareTo() method in your class
• How to write compareTo()?
• Think about state-variables that determine natural
order
• Compare them and return proper-value
• Note: For number values, you can subtract.
For object values, call compareTo() on them.
Example: Writing compareTo()
• Imagine something like an entry in a phonebook
• Order by last name, first name, then number
int compareTo( Object o ) {
PhoneBookEntry item2 = (PhoneBookEntry ) o;
int retVal= last.compareTo(item2.last);
if ( retVal != 0 ) return retVal;
retVal = first.compareTo(item2.first);
if ( retVal != 0 ) return retVal;
retVal = phNum - item2.phNum;
return retVal;
}
Under the Hood for Sorting
• How might a sort() or any other method use this?
Imagine:
• Perhaps items stored as a list of Objects:
List theList …;
• Inside a loop, code might look like this:
Comparable item1 = (Comparable) theList.get(i);
Comparable item2 = (Comparable) theList.get(j);
int cmpResult = item1.compareTo(item2);
• Such code will work when the list stores any class that
implements Comparable!
• But, what happens if list-elements are of different classes
(still Comparable, but different)? compareTo() fails!
Flexible Design using Comparators
• Solution #1: Make classes Comparable
• Disadvantage: just one way to compare is possible,
because there’s just one compareTo method per class
• Possible solutions:
• Separate functions: sortByName(), sortByNum(),…
• We can’t predict in advance how you’ll want to sort!
• Pass a parameter to indicate control:
sort(theList, “byName”) or sort(theList, “byNum”);
• Ugh. Same problem as before
• And the internals of sort() will grow to become very ugly
Function Objects
• We need to somehow pass “how to execute”
information as a parameter to sort()
• We pass objects as parameters
• Can we pass a method/operation as an object?
• Many languages support this, but in different
ways:
• C and C++ – pointers to functions
• C# – delegates
• Java – “function objects” that
• implement a specified interface, and
• the one method in that interface does the needed work
Function Objects in Java
• Idea: encapsulate a function inside a class
• Note: not our usual idea of a class
• State? (None.)
• Identity? (Just need one instance.)
• Represents an entity? (Nope! Just a place to stash a
function so it can be passed as a parameter.)
• Warning / caveat!
•
•
•
•
This idea is contrary to many OO principles, but…
Useful if done in limited circumstances
Use it when the libraries make it available
Not often part of your own class-design
• But use it in libraries when it’s part of the framework
Example: Comparator objects
• We want to pass a function-object to a method:
• Collections.sort(someList, function-object-goes-here);
• But what type should this object be?
• Use an Interface:
• Interface name can be used as a type in the parameter list
• Interface defines the method name itself!
• Java’s Comparator interface:
int compare( Object o1, Object o2);
• Notes: not compareTo()! Takes two parameters!
• Define a class for each kind of comparison you want. E.g.
Classes: CmpStudentByGpa, CmpStudentByGpaDesc
Classes: CmpDogByName, CmpDogByBreed
Writing a Comparator Class
• Example on following slides like one from MSD
text, p. 646-647
• We have a Dog class with name, breed and gender
• But see simpler example in Java on website
• list of Student objects
• sort by name, gpa
• Also sort in descending order too
• Look at testSorting1() in TestDriver class
• Look at compareTo() in Student
• Look at use of comparator classes
Writing a Comparator Class
• Example like one from MSD text, p. 647
• We have a Dog class with name, breed and gender
• Compare two doggies by breed and then name
public class CmpDogByBreedAndName implements
Comparator {
public int compare(Object o1, Object o2) {
Dog d1 = (Dog) o1; Dog d2 = (Dog) o2;
int retVal = d1.getBreed().compareTo(d2.getBreed());
if ( retVal != 0 ) return retVal;
return d1.getName().compareTo( d2.getName() );
}
}
Use of Comparator methods
• How to use with Collections.sort()
ArrayList dogList = …;
Collections.sort( dogList, new CmpDogByName() );
Collections.sort( dogList, new CmpDogByBreed() );
• (Do you understand what new does here?)
• Inside sort(), code looks something like this:
sort ( List theList, Comparator cmpObj ) {
// in some loop
Object item1 = list.get(i);
Object item2 = list.get(j);
cmpResult = cmpObj.compare(item1,item2);
End of Comparable/Comparator topics
• Make sure you see slides on Abstraction
• They relate to this material and what follows
Java Aside: Anonymous Classes
• There’s a Java technique called anonymous
classes
• One of several types of nested class definition
• You’ll very often see it in GUI programming (Swing)
and with threads
• Situation:
• Sometimes Java’s design encourages us to create
some thing that might be used just once
• That thing needs to be wrapped up in a class, say
because we need a function object
• What couldn’t we just declare it at the same
place we use it? Why create a separate file?
Creating and Using an Anonymous Class
• Example: sort a list of Strings by their length
Collections.sort ( stringList, new Comparator() {
public int compare( Object o1, Object o2 ) {
return ((String) o1).length() - ((String) o2).length();
}
});
• We’ve created a new Comparator “on the fly”
• new creates a new instance, but what kind?
• Some object that implements Comparator
• Object not named, and its “true” class not named!
• What must a Comparator have? compare()
• We defined it right here, where it’s used!
Anonymous Classes: Comments
• Anonymous classes are unlike other classes
• They have no name
• Typically only implement methods in their interface or
superclass. No new methods!
• Since they have no name, can only define and use them at one
point in your code!
• Hard to understand at first? Sure!
• Naming an abstraction is important for human understanding!
• Sorting, a Collection, Comparing
• Advice
• Keep them very short (and simple)!
• Be ready to understand them when you see them in Swing and
with threads
Note on following slides
• The summary or “Big Picture” slides that follow
may not make complete sense until you know
material on these slides and:
• Slides on abstraction
• Slides on Sets and Maps
• They are repeated at the end of those slide sets,
too, but we’ve left them here just in case
Big Picture on Java Collections Unit
• Java Collections Framework
• A large collections of interfaces and classes
• Includes things we can use “as is” (concrete classes)
and building blocks for new things (abstract classes)
• Classes that exist to contain static methods, e.g.
Collections class (see also Arrays class)
• Power of inheritance, interfaces, polymorphism
• See how “type” Collection and List are used in
parameter lists and in Collections class’ methods (e.g.
sort)
• Be aware of and start to use Java 5.0 generics
with your collections
Big Picture on Java Collections Unit (2)
• Iterators: both concepts and the practice
• Example of procedural abstraction (use, methods) and
data abstraction (what’s really in a iterator object?)
• Using these in Java for Collections, Lists (methods,
cursor, etc.)
• Procedural abstraction: the concepts, examples
• Function-objects and procedural abstraction
• Encapsulating “functionality” or “control” in an object
• Comparator objects (contrast to implementing
Comparable interface)
• Java trick: anonymous classes
Big Picture on Java Collections Unit (3)
• Java skills: Concrete collection classes and
methods for you to use
• ArrayList and ListIterator
• HashSet
• Must over-ride hashCode()
• Collections static methods
• See JavaDoc or p 587 in MSD textbook
• E.g. sort, reverse, binarySearch, fill, shuffle, min, max,…
• Implement Comparable for your collection items
• Define Comparator classes for more powerful, flexible
use