Transcript Chapter 3

Hail
of
University
ICS 202

2011 spring

Data Structures and Algorithms

1
University
of
Hail
Outline
1. Abstract Data Types
2. Design Patterns
•
Class Hierarchy
•
Java Objects and the Comparable Interface
•
Wrappers for the Primitive Types
•
Containers
•
Visitors
•
Enumerations
•
Searchable Containers
•
Associations
2
University
of
Hail
Lec 1
1. Abstract Data Types
Hail
• The abstraction comprises a number of attributes: name, address,
of
• Each attribute has an associated value (int x: the attribute name is x
University
• A variable in a procedural programming language is an abstraction.
and the attribute type has value int)
value, lifetime, scope, type, and size.
• Assigning a value to an attribute is called binding(covering).
• The binding can be static or dynamic
• In Java the type of a variable is determined at compiler time –
static binding however, the value of a variable is usually not
determined until run time – dynamic binding
4
1. Abstract Data Types
University
of
Hail
• In this chapter we are concerned primarily with the type attribute of a
variable
• The type of a variable specifies two sets:
• a set of values, and
• a set of operations.
• For int x, we know that x can represent an integer in the range [-231,
231-1] and that we can perform operations on x such as addition,
subtraction, multiplication, and division.
• The type int is an abstract data type (we don’t need to know how ints
are represented or how the operations are implemented to be able to
use them).
5
of
• Object oriented programs need an appropriate collection of
abstractions, and abstract data types to represent the abstracts.
University
Hail
1. Abstract Data Types
• The abstract data types requires the specification of both a set of
values and a set of operations on those values.
• In Java the class construct creates both a set of values and an
associated(link) set of operations(Methods).
6
Hail
been designed as a hierarchy of Java classes.
University
• In this section we will show how a set of basic abstract data type has
of
2. Design Patterns
• This section presents an overview of the class hierarchy and lays the
ground-work for the following chapters.
7
2. Design Patterns: Class hierarchy
Concrete Class
University
of
Hail
Abstract Class
Interface
“extends” relation
between classes and
between interfaces
“implements” relation
between a class and
the interface(s) it
implements
8
2. Design Patterns: Class hierarchy
• An interface doesn’t supply implementations for the methods it declares.
of
• In effect, an interface identifies the set of operations provided by every
class that implements the interface.
University
Hail
• A Java interface comprises a set of method declaration.
• An abstract class in Java is a class that defines only part of an
implementation.
• It’s not possible to create object instances of abstract classes.
• In Java, an abstract class typically contains one or more abstract
methods.
• An abstract method is one for which no implementation is given (method
with out implementation).
9
University
of
Hail
2. Design Patterns: Class hierarchy
• An abstract class is intended to be used as the base class from which
other classes are derived.
• By declaring abstract methods in the base class, it is possible to access
the implementations provided by the derived classes through the baseclass methods.
• there for , no need to know how a particular object instance is
implemented or of which derived class it is instance.
• This design pattern uses the idea of polymorphism (having many forms)
10
2. Design Patterns: Class hierarchy
Hail
and the set of operations – the abstract data type.
of
• The main idea is that a Java interface is used to define the set of values
be made.
University
• Then, various different implementations (many forms) of the interface can
11
2. Design Patterns: Java Objects and the Comparable Interface
University
of
Hail
• All the Java classes, including arrays, are derived from the base class
called Object.
public class Object
{
public final Class getClass () ;//
public String toString () ;
//
public boolean equals (Object obj) ; // to test if two objects are equals
public int hashCode () ;
// …
}
• The equals method is overridden in the Integer class as follows: if obj1 and
obj2 are Integers, then obj1.equals(obj2) is true when obj1.intValue() is equal
to obj2.intValue().
12
2. Design Patterns: Java Objects and the Comparable Interface
or “greater than” another object.
• The Comparable interface solves this problem.
public interface Comparable
{
University
of
Hail
• Java objects don’t provide a mean to test whether one object is “less than”
boolean isLT (Comparable object); // less than
boolean isLE (Comparable object); // less than or equal
boolean isGT (Comparable object); // greater than
boolean isGE (Comparable object); // greater than or equal
boolean isEQ (Comparable object); // equals
boolean isNE (Comparable object); // not equal
int compare (Comparable object);
// obj1.compare(obj2) = (0) if
// obj1= obj2; (<0) if obj1<obj2; (>0) if obj1>obj2
}
13
University
of
Hail
2. Design Patterns: Java Objects and the Comparable Interface
• The abstract class at the top of the class hierarchy is called
AbstractObject
• All the other classes in the hierarchy are derived from this class.
• The AbstractObject implements the Comparable interface.
• All the methods defined in AbstractObject are final (they can’t be
overridden).
• All the methods defined in AbstractObject except the method equals call
the compare method.
14
2. Design Patterns: Java Objects and the Comparable Interface
public abstract class AbstractObject implements Comparable
{
Hail
public final boolean isLT (Comparable object)
{ return compare (object) < 0; }
public final boolean isLE (Comparable object)
{ return compare (object) <= 0; }
public final boolean isGT (Comparable object)
of
{ return compare (object) > 0; }
public final boolean isGE (Comparable object)
University
{ return compare (object) >= 0; }
public final boolean isEQ (Comparable object)
{ return compare (object) == 0; }
public final boolean isNE (Comparable object)
{ return compare (object) != 0; }
public final boolean equals (Object object)
{
if (object instanceof Comparable)
return isEQ ((Comparable) object);
else
return false;
}
// ...
}
15
2. Design Patterns: Java Objects and the Comparable Interface
{
protected abstract int compareTo (Comparable arg); // abstract method
public final int compare (Comparable arg) // call like obj1.compare(obj2)
{
of
Hail
public abstract class AbstractObject implements Comparable
University
if (getClass () == arg.getClass ()) // are obj1 and obj2 instances of
// the same class
return compareTo (arg); // called to do the comparison
else
return getClass().getName().compareTo(
arg.getClass ().getName ()); // comparison based on the names
} // of the 2 classes. Ex. If obj1 is instance of Opus5.StackAsArray and obj2 is
// instance of Opus5.QueueAsLinked then obj1 < obj2
}
16
University
of
Hail
Lec 2
2. Design Patterns: Wrappers for the Primitive Types
and double.
of
• For each primitive type, the Java language defines a class that wraps the
primitive.
University
Hail
• The primitive types in Java are void, boolean, char, short, int long, float,
• The wrapper classes are Void, Boolean, Char, Short, Int Long, Float, and
Double.
• The wrapper classes are derived from the Object class.
• They provide an equals method to test for equality.
• The methods isLT, isGT, IsGE, isEQ, isNE are not supported by the
wrapper classes because they don’t implement the Comparable interface.
18
2. Design Patterns: Wrappers for the Primitive Types
{
// Comparable interface
protected char value;
of
public Chr (char value)
{ this.value = value; }
University
Hail
public class Chr extends AbstractObject // wrapper class to implement the
{ return value; }
public char charValue ()
protected int compareTo (Comparable object)
{
Chr arg = (Chr) object;
return (int) value - (int) arg.value;
}
// ...
}
19
University
of
Hail
2. Design Patterns: Wrappers for the Primitive Types
public class Int extends AbstractObject
{
protected int value;
public Int (int value)
{ this.value = value; }
public int intValue ()
{ return value; }
protected int compareTo (Comparable object)
{
Int arg = (Int) object;
long diff = (long) value - (long) arg.value;
if (diff < 0)
return -1;
else if (diff > 0)
return +1;
else
return 0;
}
}
20
University
of
Hail
2. Design Patterns: Wrappers for the Primitive Types
public class Dbl extends AbstractObject
{
protected double value;
public Dbl (double value)
{ this.value = value; }
public double doubleValue ()
{ return value; }
protected int compareTo (Comparable object)
{
Dbl arg = (Dbl) object;
if (value < arg.value)
return -1;
else if (value > arg.value)
return +1;
else return 0;
}
// ...
}
21
2. Design Patterns: Wrappers for the Primitive Types
public class Str extends AbstractObject
Hail
{
protected String value;
public Str (String value)
of
{ this.value = value; }
University
public String stringValue ()
{ return value; }
protected int compareTo (Comparable object)
{
Str arg = (Str) object;
return value.compareTo (arg.value);
}
// ...
}
22
2. Design Patterns: Containers
University
of
Hail
• A container is an object that contains within it other objects
• An interface Container is defined to be implemented by the various data
structure classes
public interface Container extends Comparable
{
int getCount (); // returns the number of objects in the container
boolean isEmpty (); // returns true if the container is empty
boolean isFull (); // returns true if the container is full
void purge (); // deletes the objects of the container
void accept (Visitor visitor); // will be discussed later
Enumeration getEnumeration (); // will be discussed later
}
23
University
of
Hail
2. Design Patterns: Containers
public abstract class AbstractContainer
extends AbstractObject implements Container
{ // base class from which actual container are derived
protected int count; // to count the number of items in the container
public int getCount () // returns the number of items in the container
{
return count;
}
public boolean isEmpty ()
{
return getCount () == 0;
}
public boolean isFull ()
{
return false; // by default the container has an infinity capacity
}
// ...
}
24
Hail
{
University
public interface Visitor // a visitor is an object that has two methods visit and
of
2. Design Patterns: Visitors
// isDone
void visit (Object object);
boolean isDone (); // to determine whether a visitor has finished its
// work
}
25
University
of
Hail
2. Design Patterns: Enumerations
public interface Enumeration
{
// a class to access one-by-one all of the objects in a container
boolean hasMoreElements () ; // returns true if the container
// has more elements
Object nextElement ( ) throws NoSuchElementException ;
// returns the pointer of the next element of the container
}
26
2. Design Patterns: Searchable Container
{
boolean isMember (Comparable object);
// to test whether the given object instance is in the container
University
of
Hail
public interface SearchableContainer extends Container
void insert (Comparable object);
// to put an object in the container
void withdraw (Comparable obj);
// to remove an object from the container
Comparable find (Comparable object);
// to locate an object in a container and to return its reference
}
27
University
of
Hail
2. Design Patterns: Associations
• An association is an ordered pair of objects.
• The first element is called the key.
• The second element is the value associated with the given key.
• Associations are useful for storing information in a data base.
• A data base can be viewed as a container that holds key-and-
value pairs.
28
2. Design Patterns: Associations
{
protected Comparable key;
protected Object value;
of
Hail
public class Association extends AbstractObject
public Association (Comparable key, Object value)
University
{ this.key = key; this.value = value; }
public Association (Comparable key) { this (key, null); }
public Comparable getKey ()
{ return key; }
public Object getValue ()
{ return value; }
// ...
}
29
2. Design Patterns: Associations
public class Association extends AbstractObject
{
Hail
protected Comparable key;
protected Object value;
protected int compareTo (Comparable object)
of
{
// used to compare associations
Association association = (Association) object;
University
return key.compare (association.getKey ( ) ) ;
}
public String toString ( )
{
// used to return the textual representation of the association
String result = "Association {" + key;
if (value != null)
result += ", " + value;
return result + "}";
}
// ...
}
30
University
of
END
Hail