Object-Oriented Programming Concepts in Java

PJ Dillon CS401

Slides adapted from Dr. Ramirez

Instance Variables
Lets look again at StringBuffer
Instance Variables
These are the data values within an object
Used to store the objects information

As we said previously, when using data abstraction we dont need to know explicitly what these are in order to use a class For example, look at the API for StringBuffer
Note that the instance variables are not even shown there

In actuality it is a variable-length array with a counter to keep track of how many locations are being used and is actually inherited from AbstractStringBuilder
See source in StringBuffer.java and AbstractStringBuilder.java cool!!!

Instance Variables
Many instance variables are declared with the keyword private
This means that they cannot be directly accessed outside the class itself Instance variables are typically declared to be private, based on the data abstraction that we discussed earlier
Recall that we do not need to know how the data is represented in order to use the type Therefore why even allow us to see it?

In AbstractStringBuilder the value variable has no keyword modifier

This makes it private to the package

Class Methods vs. Instance Methods

Recall that methods we discussed before were called class methods (or static methods)
These were not associated with any object

Now, however we WILL associate methods with objects (as shown with Polygon) These methods are called instance methods because they are associated with individual instances (or objects) of a class
StringBuffer B = new StringBuffer(this is ); B.append(really fun stuff!); System.out.println(B.toString());

Class Methods vs. Instance Methods

Class methods have no implicit data to act on
All data must be passed into them using arguments

Class methods are called using:

ClassName.methodName(param list)

Instance methods have implicit data associated with an Object

Other data can be passed as arguments, but there is always an underlying object to act upon

Instance methods are called using:

VariableName.methodName(param list)

Inheritance
Alternatively, our NewClass can directly inherit the properties of OldClass
Just then need to add the new properties

Eliminates the need to redefine identical functionality in NewClass

The OldClass public interface can be access directly by the user

Can still augment the inherited interface Semantically defines a logical relationship between the two objects

Inheritance and is a
We can understand this better by considering the is a idea
A subclass object is a superclass object However, some extra instance variables and methods may have been added and some other methods may have been changed

Note that is a is a one way operation

Subclass is a superclass (specific "is a" general)
With modifications / additions

Superclass is NOT a subclass (general not "is a" specific

Missing some properties

Ex: Bird is a Animal

Inheritance and is a
Animal is a Bird is a is a Human Fish

Bird, Human and Fish are all Animals However, an Animal is not necessarily a Bird, Human or Fish

Extending Classes
Inheritance in Java is implemented by extending a class
public class NewClass extends OldClass {

We then continue the definition of NewClass as normal However, implicit in NewClass are all data and operations associated with OldClass
Even though we dont see them in the definition

private, public and protected

We already know what public and private declarations mean The protected declaration is between public and private
Protected data and methods are directly accessible in the base class and in any subclasses and in the current package However, they are not directly accessible anywhere else

Note that private declarations are STILL PART of subclasses, but they are not directly accessible from the subclass point of view
See SuperClass.java, SubClass.java and ex18.java

Inheritance Example
As another example
Compare MixedNumber class and MixedNumber2 class Both utilize the authors' RationalNumber class to do most of the "work" Both also have the same functionality, but MixedNumber uses composition and MixedNumber2 uses inheritance
Note simplicity of MixedNumber2 methods Read over the comments carefully! See RationalNumber.java, MixedNumber.java and MixedNumber2.java

Java Class Hierarchy

In Java, class Object is the base class to all other classes
If we do not explicitly say extends in a new class definition, it implicitly extends Object The tree of classes that extend from Object and all of its subclasses are is called the class hierarchy All classes eventually lead back up to Object This will enable consistent access of objects of different classes, as we shall see shortly

Polymorphism
Idea of polymorphism
See internet definition:
On Google type definition polymorphism and see the results
This search works for many CS terms that you may be curious about
http://www.wordiq.com/definition/Polymorphism_%28computer_science%29

Generally, it allows us to mix methods and objects of different types in a consistent way

Method Overloading
This is called ad hoc polymorphism, or method overloading
In this case different methods within the same class or in a common hierarchy share the same name but have different method signatures (name + parameters)
public static float max(float a, float b) public static float max(float a, float b, float c) public static int max(int a, int b)

When a method is called, the call signature is matched to the correct method version
Note: This is done during program COMPILATION

Method Overloading
If an exact signature match is not possible, the one that is closest via widening of the values is used
Widening means that values of smaller types are cast into values of larger types Ex: int to long int to float float to double Fewer widenings provides a "closer" match

If two or more versions of the method are possible with the same amount of widening, the call is ambiguous, and a compilation error will result

See ex20.java Note: This type of polymorphism is not necessarily object-oriented can be done in non-object-oriented languages

Polymorphism
Subclassing Polymorphism
Sometimes called true polymorphism Consists basically of two ideas: 1) Method overriding
A method defined in a superclass is redefined in a subclass with an identical method signature Since the signatures are identical, rather than overloading the method, it is instead overriding the method
For subclass objects, the definition in the subclass replaces the version in the superclass

Polymorphism
2) Dynamic (or late) binding
The code executed for a method call is associated with the call during run-time The actual method executed is determined by the type of the object, not the type of the reference

Allows superclass and subclass objects to be accessed in a regular, consistent way

Array or collection of superclass references can be used to access a mixture of superclass and subclass objects This is very useful if we want access collections of mixed data types (ex: draw different graphical objects using the same draw() method call for each)

Polymorphism
Ex. Each subclass overrides the move() method in its own way Animal [] A = new Animal[3]; A[0] = new Bird(); A[1] = new Person(); A[2] = new Fish(); for (int i = 0; i < A.length; i++) A[i].move(); References are all the same, but objects are not Method invoked is that associated with the OBJECT, NOT with the reference move()

move()

move()

Object, Method and Instance Variable Access

When mixing objects of difference classes, some access rules are important to know:
Superclass references can always be used to access subclass objects, but NOT vice versa
Animal A = new Bird(); // this is ok Bird B = new Animal(); // this is an ERROR

Given a reference R of class C, only methods and instance variables that are defined (initially) in class C or ABOVE in the class hierarchy can be accessed through R
They still exist if defined in a subclass, but they are not accessible through R

Object, Method and Instance Variable Access

Ex:
Suppose class Fish contains a new instance variable waterType and a new method getWaterType()
Fish F = new Fish(); Animal A = new Fish(); System.out.println(F.getWaterType()); // ok System.out.println(A.getWaterType());

The above is NOT legal, even though the method exists for class Fish. The reason is that the method is not visible from the references point of view (A is an Animal reference so it can only see the data and methods defined in class Animal)
System.out.println(((Fish) A).getWaterType());

This is ok, since we have now cast the reference to the Fish type, which CAN access the method

Object, Method and Instance Variable Access

Note that we can access these methods or instance variables INDIRECTLY if an overridden method accesses them
So, for example, if the move() method as defined in class Fish called the getWaterType() method, and we called A.move(); It would work fine See ex21.java for an example

Object Methods
Weve already seen that every class automatically inherits from Object Class Object defines a set of methods that every class inherits
public String toString() public boolean equals() public int hashCode() protected Object clone() //well ignore this

Each of these forms a contract to which all objects must adhere Object has a default implementation for each of these methods
Unless our classes override them, they inherit this behavior May or may not be what our classes require

toString()
toString() returns a string representation of the object The string should be a concise but informative representation that is easy for a person to read RULE: All classes should override this method Default implementation from the Object class constructs a string like:
ClassName@30E50DA3 Name of the class, @ character, followed by the HashCode for the class

equals()
Indicates whether two objects are logically equal to each other
Ex. string1.equals(done)

Seems simple, but there is some subtlety here equals() must satisfy the definition of an equivalence relation
Reflexive Symmetric Transitive

Default implementation from the Object class is equivalent to ==

For any two references, x and y:
x.equals(y) is true if and only if x == y

The references must point to the same object for equals() to return true

Contract of equals()
equals() must be:
Reflexive: for any non-null reference variable, x:
x.equals(x) must be true

Symmetric: for any two non-null reference variables, x and y:

If x.equals(y) is true, then y.equals(x) must be true

Transitive: for any non-null reference variables, x, y, and z:

If x.equals(y) is true and y.equals(z) is true, then x.equals(z) must be true

Consistent: for any two non-null references, x and y, mutliple calls to x.equals(y) must consistently return true or consistently return false unless the data stored in either x or y changes between calls to equals(). Safe: for non-null reference x and null reference y:
x.equals(y) must return false i.e. x.equals(null) must return false equals() should not generate a NullPointerException, or ClassCastException

Contract of equals()
Consider a class SubClass
Extends SuperClass

Has the following equals() method

public boolean equals(Object o) { SubClass sub = (SubClass) o; return (name.equals(sub.name) && type.equals(sub.type)); }

Whats wrong with this?

Object o could be null Need to check if(o == null) return false;

Contract of equals()
Now consider the super class, SuperClass
Has its own equals method
public boolean equals(Object o) { if(o == null) return false; SuperClass sup = (SuperClass) o; return name.equals(sup.name); }

Whats wrong here?

Object o may be an instance of SubClass The cast will succeed, though, since SubClass extends SuperClass What about symmetry: o.equals(this) wont return true
ClassCastException will result

In general, an instance cannot be equal to any instance of a subclass

This may be desirable in some cases Extremely difficult to maintain a working contract of equals()

Template for equals()

For any class, the general form of the equals() method should be:
public class MyClass { public boolean equals(Object o) { if(o == null) return false; if(o instanceof MyClass) { MyClass my = (MyClass) o; //perform comparison } return false; } }

hashCode()
Returns a integer index value for the object
Used by hashtables to store objects

Contract
Multiple calls to hashCode() during one execution of the program must return the same integer
Assuming no data contained in the object changes between calls

For any two non-null references, x and y:

If x.equals(y), then x.hashCode() == y.hashCode() If they are logically equal, they must have the same hashCode() If they arent equal, it doesnt matter what the hashCode() returns

Composition or Inheritance
Caveats like those we just discussed arise often with Inheritance Also, In heritance permanently associates a superclass with our class at compile time
We can only inherit from a single class Composition allows our class the flexibility to wrap around different superclasses at run-time

Composition is generally preferred over Inheritance We loose polymorphism and dynamic binding with Composition though
In many cases, we need those capabilities We use abstract classes and Interfaces to help solve these problems

Exceptions in Java
Run-time errors happen
User enters incorrect input Resource is not available (ex. file) Logic error (bug) that was not fixed

For Production software

Having a program "crash" is a HIGHLY UNDESIRABLE thing
Users think software is no good Lose confidence

Exceptions in Java
Exception:
An occurrence of an erroneous, unusual or unexpected event in a program execution In older languages
Code the handling of exceptions into each area of the program that needed it Some exceptions could not even be handled by the HLL
ex. standard Pascal cannot handle I/O errors or division by 0 Ask for integer and user enters a text string what do you do?

Exceptions in Java
In newer languages
Exception handling built into the language We can separate exception handling from the "main line" code

Java uses an exception handling model similar to that used in C++

Exceptions are objects that are thrown and catched Some exceptions are built into the language Others can be created and thrown by the programmer

Exceptions in Java
Java exception handling
Exceptions are handled using try-catch blocks
try { // code that will normally execute } catch (ExceptionType1 e) { // code to "handle" this exception } catch (ExceptionType2 e) { // code to "handle" this exception } ... // can have many catches finally { // code to "clean up" before leaving try block }

Exceptions in Java
If all goes well (no exceptions occur)
Code in try block is executed, followed by code in (optional) finally block

If an exception occurs anywhere in the try block

Execution immediately jumps out of the try block An exception handler is sought in a catch block If exception is handled in a catch block, that block executes; if not, exception is propagated

Whether exception is handled or propagated, finally block is executed

Exceptions in Java
If an exception is handled
Execution resumes immediately AFTER try/catch block in which it was handled, and does NOT return to throw point termination model of exception handling
As opposed to a resumption model, where execution resumes from where the exception occurred

If an exception is propagated
A handler is searched for by backing up through the call chain on the run-time stack This is dynamic exception propagation If no handler is ever found
Console applications crash and report exception GUI applications will continue to execute, but may be in an inconsistent state more soon

Exceptions in Java
Checked vs. Unchecked exceptions
Checked exceptions
If a method does NOT handle these, the method MUST state that it throws them
Done in a throws clause in the method header

These include IOException, and InterruptedException (and their subclasses)

Unchecked exceptions
Method not required to explicitly "throw" these These include RunTimeException and Error

Exceptions in Java
Catching exceptions
Catching a superclass of an exception will catch subclass exception objects
catch (Exception e)

"catch all" if no other exceptions match

Should list exceptions in order of most specific to most general

If catch above is first NO OTHER catches in the block could ever execute

It is better style to be as specific as possible with the exceptions that are caught
See ex22.java

Abstract Classes
Abstract classes
Sometimes in a class hierarchy, a class may be defined simply to give cohesion to its subclasses
No objects of that class will ever be defined But instance data and methods will still be inherited by all subclasses

This is an abstract class

Keyword abstract used in declaration One or more methods declared to be abstract and are thus not implemented No objects may be instantiated

Abstract Classes
Subclasses of an abstract class must implement all abstract methods, or they too must be declared to be abstract Advantages
Can still use superclass reference to access all subclass objects in polymorphic way
However, we need to declare the methods we will need in the superclass, even if they are abstract

No need to specifically define common data and methods for each subclass - it is inherited Helps to organize class hierarchy

See ex23.java Lets look at MusicCD and CompilationCD again too

Interfaces
Java allows only single inheritance
A new class can be a subclass of only one parent (super) class There are several reasons for this, from both the implementation (i.e. how to do it in the compiler and interpreter) point of view and the programmer (i.e. how to use it effectively) point of view However, it is sometimes useful to be able to access an object through more than one superclass reference

Interfaces
We may want to identify an object in multiple ways:
One based on its inherent nature (i.e. its inheritance chain)
Ex: A Person

Others based on what it is capable of doing

Ex: An athlete Ex: a pilot

 A Java interface is a named set of methods

However, no method bodies are given just the headers Static constants are allowed, but no instance variables are allowed No static methods are allowed

Interfaces

Any Java class (no matter what its inheritance) can implement an interface by implementing the methods defined in it A given class can implement any number of interfaces

 Ex:

Interfaces

public interface Laughable { public void laugh(); } public interface Booable { public void boo(); }

Any Java class can implement Laughable by implementing the method laugh() Any Java class can implement Booable by implementing the method boo()

Interfaces
Ex:
public class Comedian implements Laughable, Booable { // various methods here (constructor, etc.) public void laugh() { System.out.println(Ha ha ha); } public void boo() { System.out.println(You stink!); } }

Interfaces
An interface variable can be used to reference any object that implements that interface
Note that the same method name (ex: laugh() below) may in fact represent different code segments in different classes Also, only the interface methods are accessible through the interface reference

Ex:
Laughable L1, L2, L3; L1 = new Comedian(); L2 = new SitCom(); // implements Laughable L3 = new Clown(); // implements Laughable L1.laugh(); L2.laugh(); L3.laugh();

Interfaces
Polymorphism and Dynamic Binding also apply to interfaces
the interface acts as a superclass and the implementing classes implement the actual methods however they want

An interface variable can be used to reference any object that implements that interface
However, only the interface methods are accessible through the interface reference

Recall our previous example:

Laughable [] funny = new Laughable[3]; funny[0] = new Comedian(); funny[1] = new SitCom(); // implements Laughable funny[2] = new Clown(); // implements Laughable for (int i = 0; i < funny.length; i++) funny[i].laugh();

See ex24.java

"Generic" Operations
How does it benefit us to be able to access objects through interfaces?
Sometimes we are only concerned about a given property or behavior of a class
The other attributes and methods still exist, but we don't care about them for what we want to do

For example: Sorting

We can sort a lot of different types of objects Various numbers People based on their names alphabetically Movies based on their titles Employees based on their salaries Each of these classes can be very different However, something about them all allows them to be sorted

Generic Operations
They all can be compared to each other
So we need some method that invokes this comparison

In order to sort them, we don't need to know or access anything else about any of the classes
Thus, if they all implement an interface that defines the comparison, we can sort them all with a single method that is defined in terms of that interface

Huh? Qu?
Perhaps it will make more sense if we develop an examplebut first we will need some background!

Simple Sorting
What does it mean to sort our data?
Consider an array, A of N items:
A[0], A[1], A[2], , A[N-1]

A is sorted in ascending order if

A[i] < A[j] for all i < j

A is sorted in descending order if

A[i] > A[j] for all i < j

Q: What if we want non-decreasing or non-increasing order?

What does it mean and how do we change the definitions?

Simple Sorting
How do we sort?
There are MANY ways of sorting data
Sorting has been widely studied in computer science

Some algorithms are better than others

The most useful measure of better here is how long it takes to run The better algorithms run a lot more quickly than the poorer algorithms

However, some very simple algorithms are ok if N is not too large

We will look at a simple algorithm here
In CS 0445 you will see other, better ways of sorting

SelectionSort
SelectionSort is very intuitive:
Idea:
Find the smallest item and swap it into index 0 Find the next smallest item and swap it into index 1 Find the next smallest item and swap it into index 2 Find the next smallest item and swap it into index N-2 What about index N-1?

Lets trace it on the board for the following data:

35

50

20

40

75

10

15

60

SelectionSort
Lets look at the code
SortInt.java and ex25.java Note:
Done in a modular way utilizing methods Trace it on the example from previous slide Done here in terms of only one type int

So how can we sort arrays of other types, for example objects?

We could write a version of SelectionSort for each Lots of typing, where everything other than the types involved is the same for each one Is there a better way?

Comparable Interface
Consider the Comparable interface:
It contains one method: int compareTo(Object r); Returns a negative number if the current object is less than r, 0 if the current object equals r and a positive number if the current object is greater than r Look at Comparable in the API Not has restrictive as equals() can throw ClassCastException

Consider what we need to know to sort data:

is A[i] less than, equal to or greater than A[j]

Thus, we can sort Comparable data without knowing anything else about it
Awesome! Polymorphism allows this to work

Using Comparable
Think of the objects we want to sort as black boxes
We know we can compare them because they implement Comparable We dont know (or need to know) anything else about them

Thus, a single sort method will work for an array of any Comparable class
Lets write it now, altering the code we already know from our simple sort method See Sorting.java and ex26.java
Also see SortingT.java and ex26T.java

Binary Search
Consider Sequential Search again
See Procedural Programming slides and ex8.java

Note that in the worst case we look at every item in the array
We say this is a linear run-time or time proportional to N, the number of items in the array

Can we do better?
If the data is unsorted, no
It could be any item, so in the worst case well have to try them all

What if we sort the data? Will that help?

Consider example: Guess number from 1-1000

Binary Search
Idea of Binary Search:
Searching for a given key, K Guess middle item, A[mid] in array
If A[mid] == K, we found it and are done If A[mid] < K then K must be on right side of the array If A[mid] > K then K must be on left side of the array
Either way, we eliminate ~1/2 of the remaining items with one guess Search for 40 below

10

15

20

35

40

50

60

75

Binary Search
What if item is not in array? We need a stopping condition in the not found case

Think about what is happening with each test

Either we move left index to the right or We move right index to the left Eventually they will cross in this case the item is not found
Idea is there is nothing left in the array to search Search previous array for 25

How to code this? Not difficult!

See author's code: Searching.java, PhoneList2.java
Trace execution

Binary Search
So is Binary Search really an improvement over Sequential Search
Each guess removes ~ of the remaining items Thus the total number of guesses cannot exceed the number of times we can cut the array in half until we reach 0 items
Ex: 32 16 8 4 2 1 => 6 Generally speaking, for N items in the array, in the worst case we will do ~log2N guesses This is MUCH better than Sequential Search, which has ~N guesses in the worst case You will discuss this more in CS 0445 and CS 1501

Collections
Sorting and Searching are used often With Generics, the code only needs written once
Can then be used in any situation Provided were dealing with Comparable objects

Java has predefined these methods for us

Arrays.sort() Arrays.binarySearch() Operate on arrays

There are other ways of storing a group of related objects

Offer performance benefits over arrays in some situations Offer a conceptual implementation of some container
e.g. a Set
Doesnt contain duplicates Can Add or Remove objects Can perform Union, Intersection, Difference operations An object is either in the Set or it isnt

Collections
Java refers to these as Collections
Containers of other data objects Collect related objects into a single object

Provides conceptual view of the container

Consider a File System for example
Directory Tree of Files Independent of Storage media (Hard Disk, CD, Flash Drive) Collections are similar

Separate Interface with which we access the stored objects from the Implementation

Used often enough that Java provides standard implementation of each type of Collection
Collection
List (Vector) Set
SortedSet

Queue

Map (Hashtable)
SortedMap

Stack

See Java API

List
What is a List?
Lets consider lists we make in every day life What kinds are there? What information does each store? How can we access and change each? A container of them Implied arbitrary order of the elements Size shrinks and grows with the number of items in the list We can access an element if we know its position in the List We can insert an item to any position We can remove an item from any position

A List is a sequence of items or objects

List Implementation
We now have a concept of a List
A scheme by which we store and access elements in the List This is defined by the List Interface in Java
See Java API Notice add(), get(), remove(), contains() Assumes objects have well defined equals() method

This defines the behavior of a List

In order to use a list, though, we need implement it

There are two common concrete implementations

ArrayList
Uses a private array to store and order the elements

LinkedList
Uses a chain of nodes, each of which stores a single item

When to use each requires knowledge of the implementation

ArrayList
We use an array to store the items in the List
Arrays have a fixed size List has an arbitrary size If our list has n elements, we need an array of size n or MORE
We can leave extra empty spaces to store elements added later We can resize the array if we need more space

List needs to maintain an order to the elements

Array does this for us

But consider
Inserting or adding an element
Need free the index where the element is to be stored Need to keep maintain the same order with the new element added Requires shifting some elements to higher indices

Removing an element
Array now has an unused index Have to shift elements to lower indices to keep ordering

A lot of shifting!!!

NOTE: The Vector class provides the same implementation, but provides synchronization for multithreaded applications (slower)

LinkedList
The strict array indexing causes this need for shifting
Can we avoid this?

Consider this class

public class Node { private Object value; private Node next; }

Each Node contains a reference to another Node

Forms a chain of Nodes

If we keep a reference to the first Node, we can access any of them by repeatedly accessing the next reference
Show on board Getting element at position I requires us to traverse the chain
Disadvantage over an array

Consider adding, and removing elements again

Which and How to Use

ArrayList when
Add and remove mostly from end of list Perform a lot of additions

LinkedList when
Frequent additions and removals at arbitrary positions, especially beginning

This is discussed further in CS 0445 We want to hide the implementation of a collection as much as possible
We only care that we have List List Interface provides this abstraction See ex27.java

Set
Similar to a List except
No order to the elements Cannot contain duplicate objects

A Set is a collection of objects that cannot contain duplicates

No two objects o1 and o2 in a Set can exist such that o1.equals(o2) is true Care must be taken when storing mutable objects
Cannot change data in an object that makes o1.equals(o2) true after theyve been added to the Set

Operations on a Set
Add an element add() Remove an element remove() Test for inclusion contains() Union (combine elements from two Sets) addAll() Intersection (keep elements two Sets have in common) retainAll() Difference (keep elements not found in a second Set) removeAll()

Implementations
HashSet stores elements in a Hashtable LinkedHashSet: similar to HashSet TreeSet stores elements in a Binary Tree

HashSet
Imagine implementing a Set with an array
To maintain the constraint that the Set doesnt contain duplicates, wed have to do something like: for(int i = 0; i < count; i++) if(array[i].equals(newElement)) return; //dont add new element array[count++] = newElement; We have to check each item before knowing if a duplicate existed in the array

What if we could know the index where a duplicate would be stored if it was in the Set?
Just check the element(s) at that index with equals() Add the new Element if not there

This is how a Hashtable works

Uses newElement.hashCode() to find index

Notice the need for the contract of equals() and hashCode()

Why?

Iterators
Weve seen two types of Collections so far
List Set

Recall how often weve used the following code with arrays
for(int i = 0; i < array.length; i++) {} Loop for each element of the array Use variable i to keep track of position in the array

This is a common and needed operation for any Collection

How do we do this when a Collection has no implied order? How do we do this in a common way for any type of Collection?

An Iterator is a object that can traverse over and provide access to each element
User doesnt know how it finds the next element

Using Iterators
Iterator class defines two methods
hasNext()
returns true if there is another element to examine

next()
returns the current element as an Object Prepares the iterator to return the next element

Loop then looks like:

for(Iterator i=collect.iterator(); i.hasNext();) { MyClass item = (MyClass) i.next(); //Process the item }

Java provides a shorthand version of this, called foreach loop:

for(Object o : collect) { MyClass item = (MyClass) o; // Process the item } No need to explicitly declare an Iterator collect variable must be an instance of a class that implements Iterable interface

See ex28.java

Order in Sets
The HashSet Class is the simplest implementation of the Set interface
Iterator can return the elements in any particular order Can be chaotic

It can be advantageous to ensure an Iterator returns the elements is some consistent order Two implementations of the Set Interface do this
LinkedHashSet
Like HashSet Iterator returns elements in the order in which they were added to the Set

TreeSet
Iterator returns elements in sorted order Requires stored objects to be Comparable Elements actually stored in sorted order in a binary tree

See ex28b.java

Queue
We often dont need to be able to modify all a Collections elements
Can even be advantageous to prevent access to every element Force modification of the Collection according to specific rules

A queue is an ordered collection of objects that:

Allows new items to be added only to the end Allows items to be removed only from the front Similar to a waiting line First item added to the end is the first item removed from the front (FIFO ordering First In, First Out) No other item can be removed until the first item is removed

Implementation
How could we implement a Queue? An array could impose the needed ordering
Would require a lot of shifting Circular array is still cumbersome

LinkedList class also implements the Queue interface

Ideal for a Queue Why?

See ex28c.java

Stack
Consider a stack of plates on a spring in a bin in a cafeteria
When a plate is added, spring compresses, hiding all plates below Only plate that can be removed is the top plate
The last one that was added

This is the behavior of a Stack

A Stack is a data structure where objects can only be added to or removed from the top
Last item added is the first to be removed LIFO ordering Last In, First Out

Stack Implementation
How would this best be implemented?
Array Linked list

Either would be efficient Array doesnt require the extra storage of saving a reference to each object java.util.Stack is a concrete class
Can create instances of it Ex: Collection collection = new Stack(); Stack stack = new Stack();

See ex28d.java

Map
The Map Interface differs from a Collection Defines a mapping from one set of objects to another
Like a function in Mathematics: y = f(x) Given an object, x, the map returns an object, y Refer to x as the key

An array fits this description

Maps an int to an object stored in the array Each int uniquely identifies and is associated with one of the objects

A Map allows us to impose a logical relationship between an object and its index (key)
Ex:
The title a CD could be the index of our AbstractCD class A Persons name could index their phone number (Phone Book)

Map Implementation
Recall our discussion of a Set
Used hashCode() to store object in array Used compareTo() to order object in tree

We now have two objects

One is the key for other Use hashCode() of key to find location to store the other object Use compareTo() of key to order second object in a binary tree Indexing object then needs to have well defined equals(), hashCode(), and compareTo() Stored object doesnt have to be as strictly implemented HashMap LinkedHashMap TreeMap
Implements SortedMap Interface

Analogous Map Implementations to Set

See ex29.java

Iterating over a Map

A Map is a complex data structure
Keys Values

The keySet() method returns a Set containing all the keys stored in the Map
Map cannot contain duplicate keys Iterate over this Set

The values() method returns a Collection of all objects that have an associated key
May contain duplicate objects Iterate over this collection

The entrySet() method returns a Set of all the (key, value) pairs
Each object in the Set is of the type Map.Entry Iterate over this Set

Generics
From the previous slides
Each collection or Iterator returns an Object Necessary since it is designed to work for any kind of object Requires us to cast the reference to an instance that we need Ex: List list = new LinkedList(); list.add(Some Pig); String s = (String) list.get(0); String t = (String) list.iterator().next();

The cast can be annoy The list may also not really contain Strings Wed like to force the List to only contain specific types
We wouldnt need the cast We could be sure what type of objects the List contained

This is where Generics works well

Generics
We parameterize the instance of our List with the type of object we expect it to contain using the <> syntax
Ex List<String> list = new LinkedList<String>(); list.add(Some Pig); String s = list.get(0); String t = list.iterator().next(); Declares a List of Strings instead of a simple List Compiler can now ensure only Strings are added to this particular list We no longer need the casts

Writing a Generic Class

Use the <> syntax in the class defintion public interface List<E> { void add(E x); } This is similar to declaring parameters in a method
Called Formal Type Parameters

The <E> declares that a type must be used when an instance is created
The type is then used in place of anywhere the E is used in the class definition
e.g. add(E x);

Subtyping with Generics

Consider the following code: List<String> listS = new ArrayList<String>(); List<Object> listO = listS; Is this legal?
A String is an Object A list of Strings is a list of Objects

What if we call: listO.add(new Object());

Weve added something to the list that isnt a String Compiler thinks its a List of Object, though Cant allow assignment statement

If class Foo extends Bar, List<Foo> is not a List<Bar>

This is kind of restrictive

Wildcards in Generics
Ex: In ex28, we had the method:
public void printCollection(Collection c) { for(Object o : c) System.out.println(o); }

To Parameterize this code, we might try:

public void printCollection(Collection<Object> c) { for(Object o : c) System.out.println(o); }

With the subtype restriction, we cant pass anything other than List<Object>
Not very helpful We can handle any type of List, though

Use Wildcard, ?, in this situation

Wildcards in Generics
Ex:
public void printCollection(Collection<?> c){ for(Object o : c) System.out.println(o); }

Call this a Collection of unknown type

Any type of Collection can now match this Can iterate with type Object
Any type can be cast to Object this is safe

This lets read from the Collection but not modify

e.g. c.add(new Object()); will fail to compile Not sure of the actual type of the Collection

See ex30.java

Bounded Wildcards
Recall our Animal, Fish, Bird, Person classes Wed like to write a method like:
public void printAnimals(Collection<Animal> c) { for(Animal a : c) { a.characteristics(); a.move(); } }

This can then only accept a Collection of Animal If we use a wildcard (?), we lose access to the move() and characteristics() methods

Bounded Wildcards
The solution is a bounded wildcard:
printAnimals(Collection<? extends Animal> c) { for(Animal a : c) { a.characteristics(); a.move(); } }

Stated as a Collection of any subtype of Animal

Can pass a List of Person

Know that the objects in the Collection are at least Animals

Iterator can then be a reference to Animal Polymorphism will call the appropriate instance method

Unable to add any new objects to the Collection See ex31.java

Bounded Wildcards
The ? extends MyClass syntax defines an upper bound Likewise, ? super MyClass can define a lower bound
Means any class that is a superclass of class T E.g. Comparable<? super T>
Dealing with a comparable object that can compare itself with any superclass of T

See next example

Generic Methods
Suppose we want to write a method copies an array into a Collection: public void fromAtoC(Object[] a, Collection<?> c) { for(Object o : a) c.add(o);} Weve already learned that we cant do this with the wildcard We can use generic methods public <T> void fromAtoC(T[] a, Collection<T> c) { for(T o : a) c.add(o);} All the same wildcard rules apply public <T> listCopy(List<? extends T> source, List<T> dest){} When to use:
Notice the dependency between the types in the parameters If the dependency does not exist, you should use wildcards instead Also used if the return type of the method is type dependent

See again SortingT.java, ex26T.java, and also ex32