Transcript Object Oriented Programming LP3 2004

Object Oriented
Programming
Lecture 3:
Design Patterns in general, The Singleton
pattern, The Collections Framework,
Abstract Coupling – Iterators &
Enumeration
www2.hh.se/staff/jebe/oop2005/
Last time
 Polymorphism
 Inheritance, Interfaces
 Example with Shapes
 Typesafe enumeration types
 Exceptions
 Important in all large software systems
 First Design Pattern:
 Observer – Observable
Design patterns
 Can be applied in many engineering
disciplines
 A design pattern is a descriptive solution
that can be used systematically to solve a
recurring problem
 Some purposes with design patterns:
 1) A small number of patterns that can be used
as guidance during the design
 2) Reuse of proved solutions for fast and reliable
software development
 3) A common vocabulary to simplify
communication between designers.
The Singleton Design Pattern
 Sometimes we only want to allow one
unique instance of a class
 Examples:
 A global timer
 The top-level object in an Application
 Enumeration types (in lecture 2)
 In Java, we use the static declaration to
create non unique objects
 All accesses to a static object of a kind is made
to the same object in the memory
 Static objects exist without instatiation with the
new operator
Using static is not enough
 We also want to forbid these global
classes to be instantiated more than
once
 How can we overcome this?
 Solution: We hide the constructor
(protected) and provide a public
method to return the unique instance
 Let’s see an example...
Abstract coupling
 Abstract coupling – ”The way objects
connects to another, without the need of
knowing the actual implementation”
 Guide line: Program to interfaces
 The implemenation should be hidden to the user
(encapsulated!)
 The user should only need to know the services
available (public methods), not how they are
implemented
 Abstract coupling accomplished by using an
interface or abstract class.
New 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 classes and we
want to be able to easily change modules (different
representation)
 How can we access the elements from other objects
without exposing the implementation?
 One solution is to use an Iterator


Iterator is a pattern for iterate a sequence of data
An Iterator can be used to generate a sequence of
values without recording them
IntSet
Problem: Suppose we want to record sets of integers
5
1
100
1000
1
17
10
87
2
11
A bounded set of
Integers by the
power of 10
9
13
23
A bounded set of natural numbers
IntSet – The Interface
Public class IntSet{
public IntSet(int bound)
public
public
public
public
public
boolean
void
void
boolean
int
isEmpty()
add(int x)
delete(int x)
contains(int x)
size()
public String toString()
}
Our representation of Integers
recorded in the set
An array of booleans as long as the bound:
f t f f f f f f f f t ........
0
799
true for the integers in the set
false for the rest of the integers below the bound.
This is a sorted set of integers.
The Constructor implementation
Public class IntSet{
private boolean[] theSet;
}
IntSet(int bound){
if(bound < 0)
throw new ArithmeticException(”Out of bounds”)
else{
theSet = new boolean[bound];
for(int i = 0;i<bound;i++){
theSet[i] = false;
}
}
The implementation of size
Public int size(){
int size = 0;
for(int i = 0;i<theSet.length;i+=1){
if(theSet[i])
size += 1;
}
}
return size;
Intset – Representation Invariant
 For IntSet:
 Upperbound >= 0
 All positions in intSet[] = true || false
 We provide repOk() to test the
invariant
 With repOk() we can test anytime
that variables has a legal value
 repOk() doesn’t test functionality
So, what do we want to do with our
Set of Integers?
 Besides from trivial operations as
adding, removing values to the set...
 We might want to compute the sum
of all integers
 Find the maximum integer in the set
 Various ways to examine and analyze
the elements in the set.
 Not a good idea to put all these in the
IntSet collection
How can we do all this without
exposing the IntSet implementation?
A bad example of sum...
Check all non negative integers x:
if x is in IntSet add it to the sum and
remove it from IntSet until IntSet is empty
To restore the IntSet we have to store all the
elements we removed in a temporary array
and add these back to IntSet before
returning
...not very efficient!
A much better solution...
Class IntSet{
...add the following:
private iterIndex;
Points at the
current index
(hidden)
public void reset();
public boolean hasNext();
public int next();
}
Set index to point at
first element, if it
exists
Set index to point at
next element, if it
exists, returns true
else false
Returns the element
pointed by iterIndex,
increase index.
Modified Sum
Public static int sum(IntSet s){
int sum = 0;
Reset the sequence index
s.reset();
while(s.hasNext())
sum = sum + s.next();
return sum;
}
Check if the sequence
reached the end?
Get next!
Now we don’t need to know about the IntSet
representation, it is hidden
An even better solution... separate
the Iterator interface from IntSet
Public interface Iterator{
public boolean hasNext();
public Object next();
public void remove();
}
The Iterator interface is implemented
and available in java.util package!
Let IntSet provide an Iterator
We ”sign a contract”
Public class IntSet{
that we must
...
implement the
public Iterator elements(){
interface methods!!
return new IntSetIterator();
}
private class IntSetIterator() implements Iterator{
private int iterIndex;
}
}
public IntSetIterator(){
...establish the Invariant (like reset)
}
public boolean hasNext(){...as described before}
public Object next(){...as before}
public void remove(Object x)[throw new NotSupported...}
Iterator
 A design pattern to implement
sequential iteration over the elements
in a Collection without exposing the
representation
 The Interface is separated from the
Collection (implementation)
 The Collection should offer a method
to provide an Iterator (private class)
Enumeration
 Java also has another abstract Iterative
interface: Enumeration
 The reason: Some older Classes provided
from Java 1.0 uses Enumeration, the most
common are:
 Vector
 Hashtable
 Method elements() in Vector and Hashtable
returns an Enumeration object
 Location: Java.utils.Enumeration
The Enumeration interface
Public Interface Enumeration{
public Object nextElement();
- same as next() in Iterator.
public boolean hasMoreElements();
- same as hasNext() in Iterator.
}
Iterator - Summation
 Iterating sequentially through a Collection
of data is a rather common problem in
software
 The Collection could be a List, Vector,
Hashtable, Map...
 Through Iterator we have a uniform way
(Design Pattern) to iterate through different
Collections without need for concern about
the implementation!
Application Frameworks
 Cooperating classes for reusable designs in
a specific domain
 Abstract classes and Interfaces that are
part of ”semi complete” applications
 The goal is to reuse designs and
implementations and thereby simplify them
 In this course we mainly look at:
 I/O, Collections, Applets, AWT, Swing
The Collections Framework
 ”A Collection is an object that contains
other objects, which in turn are the
elements of the Collection”
 Collections Interface
 The interface for Collections in Java
 The Collection class
 Static methods operating on Collections
 Collections can be classified in four major
categories of abstract Collections
 Bags, Sets, Lists, Maps
The abstract collections in Java
The collections are available in java.util package
Bag in
Java
Collection
Set
Sorted Set
List
Map
Sorted Map
Bags
 A Bag is an unordered Collection
 Duplicate elements are allowed
 Bags are represented by the
Collection interface in java
 Bags are rarely used directly
Sets
 A Set is also unordered
 No duplicate elements are allowed
 Ex {”Swedish”,”English”,”French”}
 Represented by the Set interface
 There are also Sorted Sets (a subclass to
set)
 Ex {”English”,”French”,”Swedish”}
 Represented by the SortedSet interface
 Examples: HashSet, AbstractSet...
 Elements in a sorted set must implement
Comparable
The compareTo Interface
 This interface impose ordering of the
implementing objects
 Collections with abstract elements can be
sorted Collections.sort
 Only one method that must be defined
 Public int compareTo(Comparable o);
 Return negative if this < o, zero if this == o,
positive if this > o
 Lets take an example....
Lists




List is an indexed sequence
Duplicates are allowed
Elements are not sorted
Two different Lists
 <”Swedish”,”French”,”English”>
 <”French”,”Swedish”,”English”>
 Represented by the List Interface
 Common classes implementing List:
 Vector, LinkedList...
Maps
 Unordered collection of key-> value
pairs
 Keys are used as indexes
 The keys must be unique
 There is also SortedMaps
 The Map is sorted by Key order
 Defined by the Comparable
 Common classes impementing Map
 HashTable,HashMap, TreeMap...