Transcript Tirgul 11

Tirgul no. 11
Topics covered:




Wrapper Classes
Interfaces
The list data structure.
Iterators/Enumerators
1
Wrapper classes
Recall
that in java there are 8 primitive data types:
byte, short, int, long, float, double, char and boolean.
All other types in java are references to objects from
different classes.
Suppose we want to use the Vector class in order to
store a list of characters:
2
Wrapper classes (cont.)
The
Vector class is implemented with an Object ref array:
Object[] elements array;
The add method of Vector allows to add an Object of any
kind to the vector:
public void add(Object o);
Problem: a char is-not a ref to an object, it is a primitive data
type.
Solution: Wrapper class: define the following class -
3
Wrapper classes (cont.)
class Character {
private char ch;
public Character(char ch){
this.ch= ch;
}
public String toString(){
return(new String(ch));
}
//more methods…(some static)
}
4
Wrapper classes (cont.)
Each primitive type in the java language has a
Wrapper class defined for it in the java API:
Primitive Type
Wrapper Class
byte
short
int
long
Byte
Short
Integer
Long
char
Character
float
double
Float
Double
boolean
Boolean
5
Wrapper classes (cont.)
Each Wrapper class contains a single data member
of its primitive type.
 Apart from that it hold useful consts such as
MAX_INT.
 It also contains useful static methods. Examples:
toString()
Integer.parseInt(String str)
Character.isDigit(char ch)
…

6
Interface
(letting someone else do all the work)
*Taking the notion of abstract classes one step further is the interface,
a type definition that doesn't implement ANY method.
*An interface may contain data members but they are implicitly declared as
static final, this is the reason they are declared and initialized in the
same statement.
* An interface defines a type just like any class in java.
This means you can use interface names wherever you used primitive or object
types.
7
Interface Example
[public] interface MyInterface {
int data = 10;
IPoint pnt = new IPoint(0,3);
void move(int x,int y);
String say();
void think();
}
8
How to use interfaces
general scheme:
public class MySubClass extends MySuperClass implements MyInterface1,
MyInterface2,MyInterface3 {
//implement the three interfaces here
}
Example (without inheritance):
public interface Singer {
void move();
int sing();
}
public interface Dancer {
String talk();
void dance();
}
public class Performer implements Singer,Dancer {
void move() {//implementation goes here}
int sing() {//implementation goes here}
String talk() {//implementation goes here}
void dance() {//implementation goes here}
}
9
Inheritance within interfaces
* Inheritance within interfaces is just like with regular classes.
public interface MyInterface1 {
void method1();
String method2();
}
public interface MyInterface2 extends MyInterface1 {
void method3();
}
If you write a class that implements MyInterface2 you will have to implement
method1() ,method2() and method3() .
10
Interfaces as ViewPoints
(Polymorphism)




Java only supports Single Inheritance – each class can only
inherit/extend one class.
However: Each class can Implement an unlimited number
of interfaces.
Although interfaces can’t be created (there is nothing to
create), we can define ref. From of their type, and use them
as alternative viewpoints for the classes that implement
them.
This way we can point to a set of objects that are not from
the same inheritance tree, with a single ref.
11
Interfaces as ViewPoints – Flyer
Example



Suppose we wish to write a program that controls
the autopilot landing of planes in an airport.
(Today planes are landed almost automatically
using computer guidance from the airport tower).
Problem: There are many different planes from
many different makes – and they DO NOT share
the same interface (they are competing each
other).
Solution: Use and interface!
12
Flyer Example (cont.)
We
define an interface GuidanceSupportedFlyer:
public interface GuidanceSupportedFlyer {
public void lockOnBeacon();
public void openLandingGear();
public void reduceSpeed(int newSpeed);
public void reduceAltitude(long newAltitude).
…
}
We notify all plane manufacturers that if they want their
planes to land using our guidance software, they should
implement the GuidanceSupportedFlyer interface.
13
Flyer Example (cont.)
We
can now write the following code:
public void LandPlane(GuidanceSupportedFlyer flyer){
flyer.lockOnBeacon();
flyer.openLandingGear();
//…etc.
}
Notice that we do not have to know anything about the plane we
are landing except that it must implement the required interface.
We can land any plane that supports the interface using the same
method. This is another good example of polymorphism.
14
Dynamic data structures

Motivation:
Suppose you want to read a file of words, and store all
words in for later processing them.

Basic solution: use an array of String ref.
• The problem is: what size should the array be?
(10,100,1000…)

Better Solution: use a dynamic data structure, which allows
to allocate memory dynamically when needed. For
example: Linked-List.
15
Dynamic data structures

Dynamic structures are useful in many situations,
the main one being when we can’t anticipate the
amount of memory that our program will use
when it is run.

The basic idea is simple: define a data structure
that dynamically allocates memory when needed.
16
Abstract Data Types (ADT’s)


Each ADT defines a data structure. The structure
may have certain properties (for example: LIFO,
FIFO, RANDOM ACCESS etc.) and also has
some methods that it supports.
Each ADT is actually an interface which can be
implemented in many ways. Example: a LinkedList may be implemented with an array (static or
dynamic) and with node structures.
17
Basic Linked-List Structure
* What we want to implement is a basic linked list structure/functionality.
This does not explicitly mean that the implementation is the standard one,
links with data inside each one and a reference to the next node.
* The implementation you will see is the standard one , a list composed of nodes
that can hold data that is comparable (meaning we can compare two objects of
this type, there is an ordering on the data type).
dummy
head
data1
data2
data3
dataN
tail
18
Basic Linked-List Structure



The list will be built of Nodes (Links, Elements)
Each node will contain some data, and a next ref
which allows it to point to another node of the
same type.
The data which the node will hold will be a ref to
a Comparable object, which is an object that
implements the Comparable interface (shown
later).
19
Node / Link
public class Node {
protected Comparable data;
protected Node next;
public Node(Comparable data) {
data = data;
next = null;
}
public Comparable getData() {
return data;
}
}//end of class Node
public void setNext(Node node) {
next = node;
}
public Node getNext() {
return next;
}
20
Comparable interface
(used as the data object in our list)
/**
* This interface defines the way two objects should be compared.
*/
public interface Comparable {
/**
* This function does the comparison between two objects.
* @return negative integer second object is greater than this one.<br>
*
positive integer second object is smaller than this one.<br>
*
zero second object is equal to this one.
* @param o the object to which we compare.
*/
public int compareTo(Object o);
}
21
Class List (with a dummy node)
//import so we can use the Enumeration
//interface
import java.util.*;
public class List {
protected Node head;
protected Node tail;
protected int size;
public List() {
tail = head = new Node(null);
size=0;
}
public void add(Comparable data) {
Node temp = new Node(data);
head.addNext(temp);
head=temp;
size++;
} //cont on next slide…
22
Class List (cont.)
public boolean isEmpty() {
return size == 0;
}
public void removeLast() {
if(isEmpty())
return;
Node helper= head; //start of list.
while(helper.getNext().getNext() != null)
helper= helper.getNext();
helper.setNext(null);
tail= helper;
size--;
//new concept ITERATORS
public Enumeration elements() {
return new ListEnumeration(this);
}
}//end of class List
23
Iterator/Enumeration
Problem:
We want to go over all the elements of a data structure, (in our case a list)
without actually knowing how it is implemented.
Solution:
We will implement an interface which has methods that tell us if there are
more elements and returns the data according to our request.
Notes:1. This is part of our effort to hide the implementation from
the user/client programmer.
2. What happens if the user adds/removes elements from the
data structure while he is using an Enumeration.
24
List iterator/Enumeration
import java.util.*;
public class ListEnumeration implements Enumeration {
private List list;
private Node place;
protected ListEnumeration(List lst) {
list = lst;
place = list.tail;
}
public boolean hasMoreElements() {
return (place != list.head);
}
public Object nextElement() throws NoSuchElementException {
if(place == list.head)
throw new NoSuchElementException();
place = place.getNext();
return place.getData();
}
}
25
Extending the list
public class OrderedList extends List {
//constructors …
public void add(Comparable data) {
Node temp = new Node(data);
Node ptr = head;
while((ptr.getNext() != null) &&
((ptr.getNext()).getData().compare(data) == -1))
ptr = ptr.getNext();
temp.setNext(ptr.getNext());
ptr.setNext(temp);
if(tail == ptr)
tail = temp;
size++;
}
}
26