Transcript Object Oriented Programming LP3 2004

Object Oriented
Programming
Lecture 10:
Recapitulation of the course
www.hh.se/staff/jebe/oop2005
Recapitulation: Lecture 1
 Creating new objects and abstract
data types
 Representation Invariants
 We did two exercises:
 Rational Numbers
 Complex Numbers
 In the Search Engine, Doc and
DocCnt are immutable objects
The Rational Class
The implementation:
Class Rational{
private int num;
private int den;
}
State representation,
hidden!
public Rational(){
this(0,1);
}
public Rational(int num, int den){
if(den == 0) throw ArithmeticException(”Zero denominator”);
else{
this.num = den<0 ? –num,num
this.den = Math.abs(den);
simplify();
}
}
Make sure the
invariant is
established!!
Extending to Complex Numbers
public class Complex extends Rational{
//State representation
private Rational real; private Rational imag;
We need Rational
arithmetic for Complex
numbers, so we inherit
Rational
/** * Constructor for injecting Rational Complex vector components */
public Complex(Rational re, Rational im){
real = re;
imag = im;
}
}
/** * Arithmetic Plus for Complex valued numbers */
public Complex plus(Complex c1, Complex c2){
return new Complex(plus(this.real,c.real()),plus(this.im,c.im()));
}
...
...
Plus in Complex
overloads the inherited
plus in Class Rational
Summary of exercise 1 & 2
 Immutable objects – Rational and Complex
 Inheritance
 We can do Complex arithmetic using Rational (+-*/)
 Method Overloading
 ”Same method name, but different arguments”
 Representation Invariant
 We want to be sure that an object always have legal
values when we use them anywhere in a program
 Ex1 Doc Object: Whenever we use a document, it
always has a valid title and a valid body
 Ex2 Query: The User Interface use a Query to get
information from Engine , it must always be a valid
Query.
Recapitulation: Lecture 2
 The Exception mechanism, how to throw
and catch exceptions
 Classes and Class Abstractions
 Interfaces, Abstract classes, Polymorphism
 Type casting
 Narrowing and Widening
 A first Design Pattern:
 Observer - Observable
 Two exercises:
 The Pen & Paper exercise (Model - View)
 Simple I/O exercise (Serializable and Object
Streams)
The Pen Object
What functionality do we want when using a pen(interface)?
Constructor
pen()
Methods for changing the state of a pen(instance methods)
void lift()
void push()
Mutators!
void move(double d)
void turn(double alpha)
Methods for assigning a drawing area to our pen
void setPaper(Paper p)
The Paper Class: Observable
public class Paper extends Observable{
private Vector lines;
private int width, height;
…
public Paper(int width, int height){
this.width = width;
this.height = height;
lines = new Vector();
}
A paper has Lines and
it has a width and a
height
public void drawLine(int a, int b, int c, int d){ We have added a line...
lines.add(new Line(a,b,c,d));
setChanged();
Register the change in
notifyObservers();
Observer!
}
Notify the Observers!
...
The PaperView Class - Observer
public class PaperView extends Canvas implements Observer{
private Paper paperModel;
public PaperView(Paper p){
paperModel = p;
paperModel.addObserver(this);
…
}
public void update(Observable o, Object arg){
try{Thread.sleep(200);}catch(Exception e){}
repaint();
}
}
public void paint(Graphics g){
Iterator iter = paperModel.iterator();
while(iter.hasNext()){
Line line = (Line)iter.next();
g.drawLine(line.v, line.w, line.x, line.y);
}
}
We add the Paperview as
an observer of the Paper
Called when
Observable is
notifying observers!
How we paint the lines!
Typesafe Enumeration types –
based on the same technique
Class Day{
public static final Day Mon = new Day(”Mon”);
private static final Day Tue = new Day(”Tue”);
...
private static final Day Sun = new Day(”Sun”);
private final String day;
private Day(String day){
this.day = day;
}
}
public String toString(){return day;}
Recapitulation: Lecture 3




Singleton Design Pattern
Iterator Design Pattern
The Collection Framework
Two exercises
 IntSet
 Count words
The Singleton Design Pattern
 When we only want to allow one instance
of an object
 Examples:
 A application using a global timer
 The top-level object in an Application (Engine)
 In Java, we use the static declaration for
creating non unique objects (static objects refer
to the same memory reference!)
 The trick: ”Hide the Constructor”
Singleton Pattern
Class MyClass{
static public MyClass getInstance(){
return theClass;
}
private MyClass(){
//...init possible variables
}
private static MyClass theClass = new
MyClass();
}
Design pattern: Iterator
 Many problems require different kinds of data
structures to record elements of data - A Collection of
objects
 We want to be able to reuse these collections and we
want to be able to easily change collections (different
representation)
 How can we access the elements from other objects
without exposing the implementation?
 One solution is to use an Iterator interface
 An Iterator can also be used to generate values
without recording them
One solution: let the Collection
provide an Iterator
Public class IntSet{
...
public Iterator elements(){
return new IntSetIterator();
}
private class IntSetIterator() implements Iterator{
private int iterIndex;
We ”sign a contract”
that we must
implement the
interface methods!!
public IntSetIterator(){
... Set index to point at first element, if it exists
}
public boolean hasNext(){
... Set index to point at next element, if it exists, returns true or false
}
public Object next(){
}
}
}
Returns the element pointed by iterIndex, increase index.
public void remove(Object x)[throw new NotSupported...}
Sum the Intset using Iterator
Public static int sum(IntSet s){
int sum = 0;
Reset the sequence index
Iterator i = elements();
Check if the sequence
while(i.hasNext())
reached the end?
sum = sum +((Integer)i.next()).intValue();
return sum;
}
Get next!
Now we don’t need to know about the IntSet
representation, it is hidden.
Collections
Two collections containing different objects
Title:
1
100
1000
Body:
Title:
Body:
10
Title:
Body:
Title:
Body:
A bounded set of
Integers by the
power of 10
Title:
Body:
Title:
Body:
Unbounded set of documents!
Exercise 6 Countwords:
Representing counted words
How can we represent word count?
static class Counter {
int i;
Counter(int x){i=x;}
public int value(){return i;}
public void add(){++i;}
}
Exercise - Countwords
Map words = new HashMap();
try{
while ((line = in.readLine()) != null) {
StringTokenizer st = new StringTokenizer(line, delim);
while (st.hasMoreTokens()) {
word = st.nextToken().toLowerCase();
if (words.containsKey(word)){
((Counter)words.get(word)).add();
}
else{
count = new Counter(1);
words.put(word, count);
}
}
}
}catch(IOException e){}
Sorting the words
SortedSet s = new TreeSet(new EntryComparator());
s.addAll(words.entrySet());
//Modified Comparator - The rule is to sort: 1. By frequency 2. By alphabetic order.
static class EntryComparator implements Comparator {
public int compare(Object o1, Object o2) {
if ( o1 != null && o2 != null && o1 instanceof Map.Entry && o2 instanceof Map.Entry){
Counter c1 = (Counter)((Map.Entry) o1).getValue();
Counter c2 = (Counter)((Map.Entry) o2).getValue();
String s1 = (String)((Map.Entry) o1).getKey();
String s2 = (String)((Map.Entry) o2).getKey();
if(c2.value() == c1.value()){return s1.compareTo(s2);}
return c2.value() < c1.value() ? -1:1;
}else {return 0;}
}
}
Recapitulation: Lecture 4




Refactoring techniques
The Applet Framework
Animation Applets Idiom
Two exercises:
 Clock Animation
 Double Buffered Animation Applet
BouncingBall Animator using
Double buffering
 We developed the Double buffered
Animation Applet
 We Separated the ball from the
Animator (Refactoring by delegation)
 Then we made it more generic, we
created a Ball template (Abstract
Ball)
A Generic Function Plotter
 Plots single-variable functions using a
2D drawingspace
 A Common ”behavior” (invariant) drawing function values on 2D canvas
 A varying part (abstract) - how we
calculate the single-variable function
value
 This matches the Template Pattern
Recapitulation: Lecture 6
 Template Pattern
 Strategy Pattern
 Two exercises:
 Function Plotter
 Extending the Function plotter
First Iteration –
Using the template pattern
 The plotter should be run as an
applet
 The concrete part: A template class
with drawing space, paint
method,method to calculate and draw
coordinate axes
 The abstract part: Calculating
function values for single-variable
function
The Concrete Part
public abstract class Plotter extends javax.swing.JApplet {
...
protected abstract double func(double x);
public void init(){
// read parameters HTML parameters:
}
public void paint(java.awt.Graphics g){
drawCoordinates(g);
plotFunction(g);
}
private void drawCoordinates(java.awt.Graphics g){
//Draw X- and Y-Axis
}
}
private void plotFunction(java.awt.Graphics g){
for(int px = 0; px < dim.width; px ++){
try{
double x = (double)(px - xorigin)/(double)xratio;
double y = func(x);
int py = yorigin - (int)(y * yratio);
g.fillOval(px-1,py-1,3,3);
}catch(Exception e){}
}
}
Extending the Plotter template
public class SinPlotter extends Plotter{
public double func(double x){
return Math.sin(x);
}
}
Generic Multiple Function Plotter
 Solution: We can refactor the code
and move the function into a separate
Class
 We can create an array of function
objects, containing the functions we
want to plot
 New Design Pattern: Strategy
Design Pattern: Strategy
The plotter
The function interface
Context
Strategy
ContextMethod()
algorithm()
ConcreteStrategyA()
ConcreteStrategyB()
algorithm()
algorithm()
Concrete implementations
Multiplotter
public abstract class MultiPlotter extends
javax.swing.JApplet{
...
private
private
private
private
int
maxFunctions;
java.awt.Color[] colors;
Function[]
functions;
int
numOfFunctions;
…
public void paint(java.awt.Graphics g){
drawCoordinates(g);
plotFunctions(g);
}
private void drawCoordinates(java.awt.Graphics g){
...
}
public void init(){
...
maxFunctions = new
Integer(getParameter("numOfFunctions")).intValu
e();
numOfFunctions = 0;
colors
= new java.awt.Color[maxFunctions];
functions
= new Function[maxFunctions];
initMultiPlotter();
}
protected abstract void initMultiPlotter();
public void addFunction(Function f, java.awt.Color c){
functions[numOfFunctions] = f;
colors[numOfFunctions] = c;
numOfFunctions++;
}
….
}
private void plotFunctions(java.awt.Graphics g){
for(int i = 0; i < numOfFunctions; i++){
g.setColor(colors[i]);
for(int px = 0; px < dim.width; px ++){
try{
double x = (double)(px xorigin)/(double)xratio;
double y = functions[i].apply(x);
int py = yorigin - (int)(y * yratio);
g.fillOval(px-1,py-1,3,3);
}catch(Exception e){}
}
}
}
Instantiating the MultiPlotter
public class LogSqrtAntiLogPlotter extends MultiPlotter{
protected void initMultiPlotter(){
addFunction(new Log(),java.awt.Color.red);
addFunction(new Sqrt(),java.awt.Color.blue);
addFunction(new AntiLog(),java.awt.Color.green);
}
}
Passing abstract functions as
parameters
class Comp implements Function{
Function f1,f2;
Comp(Function f1, Function f2){
this.f1 = f1;
this.f2 = f2;
}
}
public double apply(double x){
return f1.apply(f2.apply(x));
}
Function Composition
public class CompSinSquarePlotter extends MultiPlotter{
protected void initMultiPlotter(){
addFunction(new Sin(),java.awt.Color.red);
addFunction(new Square(),java.awt.Color.green);
addFunction(new Comp(new Sin(),
new Square()),java.awt.Color.blue);
}
}
Recapitulation: Lecture 7
 Abstract Algorithm Animation
 Factory, Strategy and Observer –
Observable pattern
 Exercise:
 Animating sorting algorithms
Animation of Sorting Algorithms
 Applet to visualize
execution of sorting
algorithms
 It should be easy to
adapt using:
 Different sort
algorithms
 Different displays
 Demonstrates usage of
Factory, Strategy and
Observer - Observable
patterns
Sorting Algorithms
 Input to the Algorithm Sorter: an array of
Integers
 Choosing different sorting algorithms
executinging with different complexities




Bubble Sort
Quick Sort
Insertions Sort
...
O(n2)
n*O(log n)
O(n2)
 The framework should adapt to different
algorithms and different display strategies
Generic Algorithm Animation –
Design Issues
 Algorithm Abstraction?
 Problem: How can we easily change between
different algorithms?
 Integration of Animation during sorting?
 Problem: The screen should be redrawn after
each iterative step, running the algorithm
 Display Abstractions?
 Problem: We will also need a modular way to
hook different graphical displays
The Algorithm Animator Template
public abstract class AlgorithmAnimator extends
javax.swing.JApplet implements Runnable,Observer{
...
public void setDisplay(SortDisplay d){
sortDisplay = d;
}
protected SortAlgorithm theAlgorithm;
protected int [] arr;
protected SortDisplay sortDisplay;
public final void init() {
...
setDisplay(new HorizontalDisplay());
public void start(){
...
}
}
public void stop(){
...
}
/* Default */
scramble();
initAnimator();
theAlgorithm.addObserver(this);
protected abstract void initAnimator();
protected void scramble() {
arr = new int[sortDisplay.getArraySize(this.getSize())];
for (int i = arr.length; --i >= 0;) {
arr[i] = i;
}
for (int i = arr.length; --i >= 0;) {
int j = (int)(i * Math.random());
SortAlgorithm.swap(arr, i, j);
}
}
public void run(){
theAlgorithm.sort(arr);
}
final public void update(Observable obs, Object o) {
if (!finished) {
try {
Thread.currentThread().sleep(delay);
} catch (InterruptedException e) {}
repaint();
}
}
public void paint(Graphics g) {
sortDisplay.display(arr,g,this.getSize());
}
}
The Abstract Sorting Algorithm
public abstract class SortAlgorithm extends java.util.Observable {
abstract void sort(int a[]);
protected void pause(){
setChanged();
notifyObservers();
}
}
protected static void swap(int a[], int i, int j) {
int T;
T = a[i]; a[i] = a[j]; a[j] = T;
}
Bubble Sort Algorithm
class BubbleSortAlgorithm extends SortAlgorithm{
void sort(int a[]) {
for (int i = a.length; --i>=0; )
for (int j = 0; j<i; j++) {
if (a[j] > a[j+1])
swap(a, j, j+1);
pause();
}
}
}
}
Concrete Sort Display
public class HorizontalDisplay implements SortDisplay{
HorizontalDisplay(){
}
public int getArraySize(Dimension d){
return (int)(d.width/2);
}
}
public void display(int[] arr, Graphics g, Dimension d){
g.setColor(Color.white);
g.fillRect(0, 0, d.width, d.height);
g.setColor(Color.black);
int y = d.height - 1;
double f = d.width / (double) arr.length;
for (int i = arr.length; --i >= 0; y -= 2)
g.drawLine(0, y, (int)(arr[i] * f), y);
}
Recapitulation: Lecture 8
 Using Factory Pattern to Improve
Algorithm Animator??? Flytta Factory
hit..
 StaticAlgoFactory
 Produces SortAlgorithms
 The Adapter Pattern
 The Command Pattern
The Factory Design Pattern
Algorithm Animator
SortingAlgorithm
Sortalgorithm()
sort()
Using
Strategy to
decouple the
algorithms
BubbleSort
QuickSort
sort()
sort()
Algorithm Factory
StaticAlgoFactory
makeSortAlgorithm()
makeSortAlgorithm()
The
concrete
Factory
Abstract Algorithm Factory and Sort
Display
public interface SortAlgorithmFactory {
public SortAlgorithm makeSortAlgorithm(String algName);
SortDisplay makeSortDisplay(String displayName);
}
public interface SortDisplay{
public int getArraySize(Dimension d);
public void display(int[] a, Graphics g, Dimension d);
}
Concrete Factory Implementation
public class StaticAlgoFactory implements SortAlgorithmFactory {
public SortAlgorithm makeSortAlgorithm(String algName) {
if ("BubbleSort".equals(algName))
return new BubbleSortAlgorithm();
else if ("QuickSort".equals(algName))
return new QuickSortAlgorithm();
else
return new BubbleSortAlgorithm();
}
}
public SortDisplay makeSortDisplay(String displayName){
if("horizontal".equals(displayName))
return new HorizontalDisplay();
else if("vertical".equals(displayName))
return new VerticalDisplay();
else
return new HorizontalDisplay();
}
Recapitulation: Lecture 9
 Graphical User Interfaces:
 Two frameworks in Java
 AWT
 SWING
 A design case study:
 The MAXIT Game
 View – Model - Controller
Design Patterns that we have seen
in the course








Observer – Observable Pattern
Iterator Pattern
Singleton Pattern
Template Pattern
Strategy Pattern
Factory Pattern
Adapter Pattern
The Command Pattern