Transcript Some Java API

Algorithm Programming 1
89-210
Java API and Containers
Bar-Ilan University
2007-2008 ‫תשס"ח‬
by Moshe Fresko
“Object” class


“java.lang.Object” class is the root of all class
hierarchy
Methods of “Object” that can be overridden:





public boolean equals(Object obj)
public String toString()
public int hashCode()
protected void finilize() throws Throwable
protected Object clone()
throws CloneNotSupportedException
“Object” class

Other methods of “Object” class

public final Class getClass( )
Runtime class information

public final void wait(…)
Causes current thread to wait

public final void notify( )
Wakes up a single thread that is waiting on this object’s monitor

public final void notifyAll( )
Wakes up all threads that are waiting
“Object” class methods

Overriding Object methods

public String toString( )
String representation of this object

protected void finilize( ) throws Throwable
This function is called by the Garbage Collector before the physical
destruction of the object.

public int hashCode( )

Hash Code to be used by containers like HashSet or HashMap.
1. It must be consistent within an object:
x.hashCode()==x.hashCode()
2. It must be the same for “equal” objects.
If x.equals(y), then x.hashCode()==y.hashCode()
“Object” class methods

Overriding Object methods

protected Object clone() throws CloneNotSupportedException

When overriding, be aware that …
1.
2.
3.

x.clone() != x
x.clone().getClass() == x.getClass()
x.clone().equals(x)
public boolean equals(Object obj)

When overriding, be aware to keep these characteristics
1.
2.
3.
4.
5.
Reflexive: x.equals(x) == true
Symmetric: x.equals(y) == y.equals(x)
Transitive: if (x.equals(y)) and (y.equals(z)) then z.equals(x)
Consistent: x.equals(y) returns the same value for the same unchanged object
references x and y.
x.equals(null) == false
Algorithm Programming 1
Exception Handling
Moshe Fresko
Basic Exceptions




float div(float x,float y) throws ArithmeticException {
if (y==0.0f) throw new ArithmeticException(“Division by zero in div()”) ;
}
void apply(Object t) throws NullPointerException {
if (t==null) throw new NullPointerException(“Null pointer in apply()”) ;
}
“throw” returns up the newly created object immediately from the function (or
scope), even many levels …
“Throwable” : Exception root class.





Throwable()
Throwable(String)
“Exception” extends “Throwable”
All program exception classes must directly/indirectly inherit from “Exception”
Information on exception might be both in the object’s class, or in the String
information inside (or other internal data).
Catching Exception

The “try” Block
try {
// Code that might generate exception
}

Exception Handlers
try {
// Code that might generate exceptions
} catch(Type1 id1) {
// Handle exceptions of Type1
} catch(Type2 id2) {
// Handle exceptions of Type2
} catch(Type3 id3) {
// Handle exceptions of Type3
}
Custom Exceptions
// SimpleExceptionDemo.java
class SimpleException extends Exception { }
public class SimpleExceptionDemo
{
public void f() throws SimpleException {
System.out.println("Throw SimpleException from f()") ;
throw new SimpleException();
}
public static void main(String[] args) {
SimpleExceptionDemo sed = new SimpleExceptionDemo() ;
try {
sed.f() ;
} catch (SimpleException e) {
System.err.println("Caught it!") ;
}
}
}
// Output
Throw SimpleException from f()
Caught it!
Catching Exception

Catching any exception
catch(Exception e) {
System.err.println("Caught an exception");
}

Getting information on Exception (“Throwable” methods)





String getMessage()
String toString()
void printStackTrace()
void printStackTrace(PrintStream)
Etc.
Exception Specification

Exception Specification
void f() throws TooBig, TooSmall, DivZero { //...

Checked Exceptions
Either you must take care of exceptions in your code or specify it in Exception
Specification

When you don’t tell of any exception, only RuntimeException can be
thrown
void f() { //…

Re-throwing an exception
catch(Exception e) {
System.err.println("An exception was thrown");
throw e;
}
Standard Java Exceptions
Object
Throwable
Error
Exception
MyException1 MyException2

RuntimeException
Throwable : Root of all Exceptions/Errors
“Error” : We don’t need to take care of it
“Exception” : The Root of all exceptions

Unchecked Exceptions

“RuntimeException”
“finally” keyword

Performing clean-up
try {
// The guarded region: Dangerous activities
// that might throw A, B, or C
} catch(A a1) {
// Handler for situation A
} catch(B b1) {
// Handler for situation B
} catch(C c1) {
// Handler for situation C
} finally {
// Activities that happen every time
}
Algorithm Programming 1
89-210
Containers in Java
Bar-Ilan University
2006-2007 ‫תשס"ז‬
by Moshe Fresko
Array utilities

In “java.utils.Arrays” class there are some static
utility functions:

List asList(Object[] a) ;

boolean equals(char[] a, char[] b)
boolean equals(Object[] a, Object[] b)

void fill(char[] a, char val)
void fill(Object[] a, Object val)
void fill(char[] a, int fromIdx, int toIdx, char val)
void fill(Object[] a, int fromIdx, int toIdx, Object val)
Array Utilities
int binarySearch(char[] a, char key)
int binarySearch(Object[] a, Object key)
int binarySearch(Object[] a, Object key, Comparator c)
void sort(char[] a)
void sort(Object[] a)
void sort(Object[] a, Comparator c)
void sort(char[] a, int fromIdx, int toIdx)
void sort(Object[] a, int fromIdx, int toIdx)
void sort(Object[] a, int fromIdx, int toIdx, Comparator c)
Array Utilities

For sort and binarySearch of Objects




Either a new Comparator c must be given
Or the given objects must implement Comparable
In both cases the comparison function returns
Less then 0, if left object is smaller
Greater then 0, if left object is greater
0, if both objects are equal
In java.utils.Comparator
interface Comparator {
int compare(Object o1, Object o2) ;
}

In java.lang.Comparable
interface Comparable {
int compareTo(Object o) ;
}
Design Pattern : “STRATEGY”

“Strategy” Pattern:



Define a family of algorithms, encapsulate each
one, and make them interchangeable.
Strategy lets the algorithm vary independently from
clients that use it.
Example:


Arrays.sort(Object[] a, Comparator c)
binarySearch(Object[] a, Object key, Comparator c)
Example : sort()
import java.util.* ;
class A { public final int i ;
A(int i) { this.i = i ; }
}
class Ascending implements Comparator {
public int compare(Object o1, Object o2)
{ A a1=(A)o1, a2=(A)o2 ;
if (a1.i<a2.i) return -1 ;
if (a1.i>a2.i) return +1 ;
return 0 ; }
}
class Descending implements Comparator {
public int compare(Object o1, Object o2)
{ A a1=(A)o1, a2=(A)o2 ;
if (a1.i<a2.i) return +1 ;
if (a1.i>a2.i) return -1 ;
return 0 ; }
}
Example “sort()”
public class S {
public static void main(String[] args) {
A[] asc = { new A(1), new A(5), new A(3), new A(2) } ;
A[] dsc = (A[]) asc.clone() ;
Arrays.sort(asc,new Ascending()) ;
Arrays.sort(dsc,new Descending()) ;
System.out.println("Ascending : "+arrStr(asc)) ;
System.out.println("Descending: "+arrStr(dsc)) ;
}
static String arrStr(A[] a) {
String s = "[" + a[0].i ;
for (int i=1;i<a.length;++i)
s += ","+a[i].i ;
s+="]" ;
return s ;
}
}
// Output : Ascending : [1,2,3,5]
//
Descending: [5,3,2,1]
Java Containers

In Java two types of Containers

Collection : A group of individual elements



List : Keeps elements in a particular sequence.
Set : Cannot have duplicate elements
Map : A set of key-value pairs.
( Also known as Associative arrays)
Simplified Collections Diagram
Collection methods
boolean add(Object o) : Adds element to the collection
boolean add(Collection c) :
void clear() : Clears the collection. Size will be 0.
boolean contains(Object o) :
boolean containsAll(Collection c) :
boolean isEmpty() : Returns true if collection is empty.
Iterator iterator() :
boolean remove(Object o) : Removes the element.
boolean removeAll(Collection c) :
boolean retainAll(Collection c) :
int size() : Returns the number of elements in collection
Object[] toArray() :
Object[] toArray(Object[] a) :
List and Set implementations

“Collection” interface

“List” interface : ( Order of insertion is kept )

ArrayList : Implemented as an array of elements.
Fast Random Access, but slow insertion and deletion from the middle.

LinkedList : Implemented as a double linked list.
Insertion and Deletion in the middle is fast, but Slow in Random Access.

“Set” interface : ( Unique elements )

HashSet :
For sets where look-up time is important.
Inserted objects must implement hashCode() method.

TreeSet :
A sorted list can easily be extracted
List and Set methods

interface “List” : Addition to “Collection”
Object get(int index)
Object set(int index, Object element)
void add(int index, Object element)
Object remove(int index)
int indexOf(Object o)
…

Interface “Set” : Addition to “Collection”
…
Map methods
Object put(Object key, Object value) : Adds key-value pair to map
void putAll(Map t) :
Object get(Object key) : Get the value for the given key
void clear() : Clears the map. Size will be 0.
boolean containsKey(Object key) : Checks if the key exists.
boolean containsValue(Object value) :
boolean isEmpty() : Returns true if map is empty
Object remove(Object key) : Removes the key from map
int size() : Returns the number of elements in the map
Set entrySet() :
Set keySet() :
Collection values() :
Map implementations

“Map” interface

HashMap : Implemented using hash tables.
Key objects must implement hashCode() method.

LinkedHashMap :
Like HashMap., but keeps the order of insertion

TreeMap : Implemented by a red-black tree.
You get the results in sorted order. (Determined by
Comparable or Comparator)
Iterator Pattern

Intent


Provide a way to access the elements of an aggregate
object sequentially without exposing its underlying
representation.
Motivation



An aggregate object such as a list should give you a way
to access its elements without exposing its internal
structure. Moreover you might want to traverse the list in
different ways.
We cannot fill the List interface with different traversals
we can need.
We may want a couple of traversals pending on the same
time.
Iterator
Iterator – Example Structure
Iterator

Use iterator pattern …



To access an aggregate object’s contents without exposing
its internal representation.
To support multiple traversals of aggregate objects.
To provide a uniform interface for traversing different
aggregate structures (to support polymorphic iteration).
Iterator – General Structure
Iterator

Participants

Iterator


ConcreteIterator



Implements the iterator interface
Keeps track of the current position in the traversal
Aggregate


Defines an interface for accessing and traversing elements
Defines an interface method that creates an iterator object
ConcreteAggregate

Implements the iterator creation method, and returns an instance
of the proper ConcreteIterator
Iterator

Consequences




It supports variants in the traversal of an aggregate
Iterators simplify the Aggregate interface
More then one traversal can be pending on an aggregate
Implementation

Who controls the iteration?



Who defines the traversal algorithm?



Client controls the iteration. (called External Iterator)
Iterator controls the iteration. (called Internal Iterator)
The aggregate: This is called a cursor.
The iterator.
How robust is the iterator?


Modifying an aggregate while traversing it will be dangerous for
iterator.
Robust iterator will not be effected by changes.
Java Iterators
interface Collection {
…
Iterator iterator();
…
}
Interface Iterator {
boolean hasNext() ;
Object next() ;
void remove() ;
}
interface Set extends Collection {
…
Iterator iterator();
…
}
Interface ListIterator extends Iterator {
boolean hasNext() ;
Object next() ;
boolean hasPrevious() ;
Object previous() ;
int nextIndex() ;
int previousIndex() ;
void remove() ;
void set(Object o) ;
void add(Object o) ;
}
interface List extends Collection {
…
Iterator iterator();
ListIterator listIterator();
ListIterator listIterator(int index);
…
}
Java Iterator Example
import java.util.*;
public class IteratorExample {
public static void main(String[] args) {
List ints = new ArrayList();
for(int i = 0; i < 10; i++)
ints.add(new Integer(i));
Iterator e = ints.iterator();
while(e.hasNext())
System.out.println(((Integer)e.next()).intValue());
}
}