Transcript Slides - University of Virginia, Department of Computer Science

CS2110: SW Development Methods
OO Design and the Java
Collections Framework
(part 1)
• Textbook readings:
• MSD: parts of Chapter 9
• We’ll skip some of this now and come back to it later
• Read these:
• Page 611 through Section 9.3.3
• Pages 641-647
• More pages here soon…
The Big Picture for this Unit
• See how inheritance concepts are useful
• Perhaps for you as you build classes
• Definitely for Java class libraries that you use
• Learn more about Java Collections Framework
• ArrayList is part of this
• Built on principles we just studied (inheritance,
interfaces, etc.)
• Learn how to make use of these reusable
components, and
the good OO principles behind their design
• Along the way, learn more about class design
Application Framework
• What’s an OOP framework?
• A large set of classes developed by someone else
• Partially complete: we add to it to make a complete working
program
• MSD text: a unified architecture, works together, seamless,
common interface
• Examples:
• GUI frameworks: Java Swing, Microsoft WinForms and MFC (for
C++)
• Others: Java Collections
• Often: the “main” program control is built into the
framework
• Not ours to worry about!
• We’ll see this for Swing later
The Java Collections Framework
• A common set of operations for “abstract” data
structures
• List interface: operations available on any kind of list
• Set interface: operations available on any kind of set
• A set of useful concrete classes that we can use
• E.g. ArrayList, LinkedList, HashSet, TreeSet
• A common set of operations for all Collections
• Collection interface: operations we can do on any kind
of Collection object
• Collections class: contains static methods that can
process Collection and List objects
Reminder
• You will want to use:
• Concrete classes (e.g. ArrayList)
• Collections operations (e.g. sort, shuffle, max)
• References to interfaces when it makes sense
• You are less likely to
• Design a new Collection
• But still, seeing how it’s been done will teach
you good OO design principles
Real Collection Interfaces in Java
• All collections meet Collection interface:
boolean add(E obj);
Iterator iterator();
int size();
boolean isEmpty();
boolean contains(E obj);
boolean containsAll (Collection other);
…
• See Java API documentation for all methods
Collections and Abstract Classes
• To define a new Collection, one must implement all
methods -- a pain!
• Better: define a skeletal implementation class
• Leaves primitives undefined: add(), iterator()
• Defines other methods in terms of those
• Concrete collection class inherits from skeletal class
• Defines “primitives”
• Overrides any methods it chooses too
• Java library: AbstractCollection
• Implements Collection interface
• You inherit from it to roll your own Collection
Abstract Class Methods
• Some collection methods can be defined
“abstractly”
• Method from abstract class below uses other
methods like add(), iterator methods, etc.
• All of those defined in concrete subclass
public boolean addAll (Collection from) {
Iterator iterFrom = from.iterator();
boolean modified = false;
while ( iterFrom.hasNext() )
if ( add(iterFrom.next()) ) modified = true;
return modified;
}
Who is most likely to use Abstract Collection?
1. You, a regular
programming
building applications
2. Someone developing
new classes for a
library for others to
use
List Interface in Java
• Two concrete classes for lists:
• ArrayList, LinkedList
• Both implement the List interface
• Which extends the Collection interface and adds:
E get(int index);
E set(int index, E element);
E remove(int index);
void add(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
List<E> subList(int from, int to);
…
• See Java API documentation for all methods
Set Interface in Java
• Two concrete classes for sets:
• HashSet, TreeSet
• Both implement the Set interface
• Which is actually the same as the Collection interface
but some methods have more specific meaning. E.g.:
boolean add(E element); // return false if duplicate
• See p. 625 for methods that take a Collection as a
parameter to do a contains/add/retain/remove
• See Java API documentation for all methods
• More on Sets later!
Which are legal?
1.
2.
3.
4.
5.
List<E> x = new ArrayList<E>();
List<E> x = new List<E> ();
ArrayList<E> x = new List<E>();
Collection<E> x = new ArrayList<E>();
Set<E> x = new ArrayList<E>();
Inheritance and Design
• Why would we do: List<E> x = new ArrayList<E>();
• One of three reasons we gave about why inheritance is
used: Flexible design
• We said (earlier):
• Gives us more flexibility at run-time in calling operations on
objects that might be of different types
• Recall we use reference variables to “point to” objects
• You know how polymorphism supports this
• Now, two ideas about what makes a good design
• Abstraction; Hiding Design Decisions
Important Principle: Abstraction
• Inheritance is an example of the principle of
abstraction
• http://en.wikipedia.org/wiki/Abstraction_%28computer_science%29
• Inheritance of implementation (IS-A)
• You can think of a subclass item as a type of some
more general type of object
• Same state, some common behavior
• Inheritance of interface (e.g. Java interfaces)
• You can think of an object as an instance of
something that can be used or operated on in a
certain defined way
• E.g. it’s comparable, printable, playable, drawable
Hiding Design Decisions
• The “black box” idea is important in design
• Some “component” X, i.e. part of the system, is like a
black box
• The rest of the system knows how to interact with it
through its interface (“interface” in general sense)
• We swap in many different components for X as long
as each has the same interface as X
Hiding Design Decisions in OO
• In OO software:
• We reference components by type, I.e. an objectreference ref defined by:
• Interface or Superclass (perhaps abstract superclass)
• Examples:
PlayableItem p; // abstract class
TimePiece t; // interface
public void syncTimeWith(TimePiece t) {…}
ArrayList<PlayableItem> thePlayList;
• What kind of object is the reference really
pointing at?
• The client-code doesn’t have to know.
• But it does know what interface is supported.
Hiding Design Decisions
• A term for hiding design decisions this way is:
information hiding
• But information means more than data here
• It means how things are designed or implemented
• An object-reference to a Java interface or a
superclass is a use of abstraction
• Coding using abstractions makes systems more
flexible, easy to change, easier to re-use parts
• Could rephrase this as “coding to abstractions”
• Result: better software design
• (Seems vague? Too “abstract”? Don’t worry.
You’ll see more later!)
Iterators
• “Iteration” means moving through a set of items
• Most basic example: using a for or while loop
with an array or ArrayList
• We usually use an index variable i to access each item
• Major point:
• We can think of iteration at a higher level of
abstraction…
• where details of implementation are hidden
• Have “something” that helps us get first item, next
time, are there any left, etc.
• Generally applies to any collection
Iterator objects in Java
• In OO languages like Java we use iterator
objects to move through any Collection
• Question: How do we get an iterator object?
Answer: We get it from the Collection itself!
• Question: What exactly does the Collection give us?
Answer: We don’t really need to know! All we need
to know is the Iterator interface this object
implements.
• Method in Collection:
Iterator<E> iterator();
• Iterator is an interface, so we can use it as a type and
then call methods on objects of that type
Iterator Interface
• Three fundamental methods:
E next(); // where E is Collection’s element type
boolean hasNext();
void remove();
• remove() is “optional” (not always defined).
• removes the item we last passed over
• can be called once per call to next()
• the only safe way to remove an item while an
iteration is taking place
Example Iterator Code
• Traverse a collection of Widgets named c and get
each object, then remove it.
Iterator<Widget> iter = c.iterator();
while ( iter.hasNext() ) {
Widget w = iter.next();
// do something with w
iter.remove();
}
Generics and foreach
• A simpler way (since Java 5.0)
• A “foreach” statement simplifies that the
previous idiom
• Generics:
• When you define a collection, you associate it with a
particular type it will store
• Think of every collection as having a “two-part type”
• ArrayList<String> has type “ArrayList-of-Strings”
• Also can define methods etc. using this bound-type
Example:
• Example of generic collections and foreach in
use:
List<Double> myList = new ArrayList<Double>();
for (Double item : myList ) { // “foreach” stmt
System.out.println(“List myList contains ” + item);
}
• Advantages:
• Concise, easy to understand
• Disadvantage: no iterator, so cannot call iterator
methods on an item as you visit each one
• Can’t call iter.remove()
ListIterator
• Any type of Collection can have an Iterator
• A List is a specialized form of Collection
• A List collection can give you a ListIterator
object that has a richer set of methods than a
“plain” iterator
• See pages 630-633 in MSD textbook
• To get one, call the listIterator() method on a List
• Can get one that starts at last item by calling:
ListIterator<E> itr = lst.listIterator(lst.size()-1);
• We’ll see you can move “backwards” through a List
ListIterator Methods
• Additional methods (beyond those in Iterator):
boolean hasPrevious();
E previous();
int nextIndex(); // index from 0 to size()-1
int previousIndex();
void set(E o);
void add(E o);
void remove() // overrides the one in Iterator
• These last three are based on the cursor!
ListIterator and the “cursor”
• Study pp. 631 in MSD textbook for details
• Cursor “points to” a position between items
• Or before the first item, or after the last item
• Not the same as an item’s index!
• remove() and set()
• Affects the item just returned by next() or previous()
• Can’t change an item without moving over it!
• add() – adds an item in between two items
• before the item just returned by next(), and
• after the item just returned by previous()
• All this is useful but tricky!
Step Back for the Big Picture
• Why learn and use Iterators and ListIterators?
Why not just use a for-loop and index value with
an ArrayList or array?
• Practical reasons:
• Iterators and ListIterators work with any
Collection/List class (e.g. LinkedLists, sets, maps,
trees, etc.)
• If you change from one Collection to another, there is
much less code to change
• “Theoretical”:
• This is an example of procedural abstraction
Abstraction in CS
• What’s the concept of abstraction again?
• Wikipedia (general def.): An abstraction is an idea,
conceptualization, or word for the collection of
qualities that identify the referent of a word used to
describe concrete objects or phenomena.
• Wikipedia (CS): In computer science, abstraction is
a mechanism and practice to reduce and factor out
details so that one can focus on a few concepts at a
time.
• Allows us to group things that “are the same”
• Process of abstraction vs. an abstraction (a
thing)
Procedural vs. Data Abstraction
• Data Abstraction
• An abstraction that hides details of how a data object
is stored, represented, etc.
• Procedural Abstraction
• An abstraction that hides details associated with
executing an operation or task
• Sometimes people refer to Iteration Abstraction
• Note that giving something a name is an
important part of abstraction
• I can refer to it. We understand it. We agree on it.
You Already Understand Data Abstraction!
• Example 1: Floating point numbers:
• Details we care about: sign, whole-part, fractional
part, operations
• In a computer:
• How large/small can the whole-part be? How many digits in
the fraction? (IEEE 754 standard?)
• In Java, we can represent NaN (“not a number”)
double d = doSomeOperation(…);
if ( Double.isNaN(d) ) … // invalid double returned!
(Note use of static method defined in class Double)
You Already Understand Data Abstraction! (2)
• Example 2: Classes and Objects
• What’s a string? A sequence of characters
• Has a size. We concatenate them. Other operations.
• But what is it “inside”? (Do we care?)
• Example 3: Classes and Superclasses (and
Interfaces)
• Manager extends Employee extends Person
• We can treat a set of people-objects using type
Person, ignoring details about subclasses
You Already Understand Procedural Abstraction!
• Simple Methods, e.g. a sqrt() method
• Hides the details of how it works
• “Exposes” an interface we can use
• We think of it and use it in terms of its purpose and
interface
• Loops and Iteration
• We often think/design at a level higher than
implementation
• “I need a loop to do that.” (For-loop, while-loop?
Does it matter?)
• “I need to do this operation for each item.”
• An iteration or repetition is implied.
End of Part 1 on this topic. What’s Next?
• Controlling execution with “function objects”
• Comparator classes: passing an instance to sort()
• Another example of procedural abstraction
• Oh wait! We did this earlier! But let’s talk about this:
Why are Comparator objects a good example of
abstraction? Which kind?
• Java collections for Sets and Maps