Chapter 3 – Data Abstraction : The Walls
Abstract Data Types (ADTs)
A data structure is some construction
(such as an array, a list, etc.) within a program that stores a collection of
data.
An
Abstract Data Type is a collection of data and data structures plus a set of
operations on those data and structures that together can be used to solve a problem.
Typical
operations on a data collection:
1.
Add a datum to the collection
2.
Remove a datum from the collection
3.
Ask questions about the data in the collection
ADTs, in some languages, can
be created via the use of classes and objects (OOP). Objects are more general
that ADTs. An ADT usually defines one data collection for one problem. A class
defines a generic set of structures along with the operations that can be
performed on those structures. The user can then create “objects” of a given
class type. There can be several objects of the same type.
The operations (methods) that one places in an ADT form a wall between the actual data and the user. This is done to protect the data and to provide the user with only what he/she needs in order to access the data.
Suppose your boss is an investor in the stock market and wants you to develop a data structure where he wants to keep a list of stocks that he owns. Before you actually create the data structure, you should ask what kinds of operations we would like to do. Together you develop a set of operations:
1. Create an empty list
2. Determine whether the list is empty
3. Determine the number of items in the list
4. Add an item at a given position in the list
5. Remove an item from a given position
6. Remove all of the items
7. Retrieve an item from a given position in the list
8. Sort the list
9. Search for a particular item in the list
The set of operations could even be larger depending on what your boss requires.
Once you know the operations that are required, you
can then sit down and “design” the ADT. You can decide what kind of data
structure you will need (perhaps an array of some sort) and you can write
specifications for the operations. A sample list of specifications for some of
the operations we discussed above is given on page 113 of your textbook. How would you specify the sorting and searching operations?
Once you have specified
the operations and the data structures, then you can place them into actual
code. You give your ADT a name, aList for example, and then allow your
boss to use it. He may use it something like this:
aList.createList( );
aList.add(1, Microsoft);
aList.add(2,
Cisco);
aList.add(3, USX);
Later on he can use the
aList.remove( ? ) operation and or the aList.get( ? ) operation to maintain it.
Please notice that this is
only one way to make an ADT for a list. Your boss may want something fancier.
He/she may not want to worry about where in the list an item is placed. Perhaps
he/she wants a sorted list, to keep the stocks in alphabetical order. In this
case your set of operations may be different. For example:
1.
createSortedList( )
2.
sortedIsEmpty( )
3.
sortedSize( )
4.
sortedAdd(item)
5.
sortedRemove(item)
6.
sortedGet(index)
7.
locateIndex(item)
In this case your data
structure may stay the same (i.e. an array), but your code will change
dramatically because now you must maintain the list in a sorted order. For
example to add an item you will have to find the position in the array where it
should be placed and move all of the items after it up by one position.
Initial List:
|
4 |
7 |
10 |
14 |
20 |
|
|
|
|
|
List with 12 inserted
|
4 |
7 |
10 |
12 |
14 |
20 |
|
|
|
|
These types of ADTs are
not always as abstract as we mention here. Sometimes they can be quite
specific. Your textbook gives a good example of one for an Appointment Book. In
this example the actual operations may look more like this:
1.
createAppointmentBook ( )
2.
isAppointment(date, time)
3.
makeAppointment(date, time,
purpose)
4.
cancelAppointment(date, time)
5.
checkAppointment(date, time)
How do you think this data
structure might look? What do these method do?
Implementing ADTs
The above discussion was meant to give you and introduction
to designing ADTs and their operations. But, of course, once you design one,
you need to implement it in some language, like Java. When we think of data
plus operations, the Java class should come to mind. It provides the mechanism
we need to define methods (operations) and the data they work on (such as an
array). Remember the “unwritten” rule that data inside of a class should be
declared as “private” thus providing the wall that separates the user from the
data. Let’s look at a fairly simple example. It looks more complex than it
really is:
public
class Sphere {
private double theRadius;
public Sphere() {
// Default constructor: Creates a sphere and
// initializes its radius to a default
value.
// Precondition: None.
// Postcondition: A sphere of radius 1
exists.
setRadius (1.0);
} // end default constructor
public Sphere(double initialRadius) {
// Constructor: Creates a sphere and
initializes
// its radius.
// Precondition: initialRadius is the
desired radius.
// Postcondition: A sphere of radius
initialRadius
// exists.
setRadius (initialRadius);
} // end constructor
public void setRadius(double newRadius) {
// Sets (alters) the radius of an existing
sphere.
// Precondition: newRadius is the desired
radius.
// Postcondition: The sphere’s radius is
newRadius.
if (newRadius >= 0.0) {
theRadius = newRadius;
}
// end if
} // end setRadius
public double radius() {
// Determines a sphere's radius.
// Precondition: None.
// Postcondition: Returns the radius.
return theRadius;
} // end radius
public double diameter() {
// Determines a sphere's diameter.
// Precondition: None.
// Postcondition: Returns the diameter.
return 2.0 * theRadius;
} // end diameter
public double circumference() {
// Determines a sphere's circumference.
// Precondition: None.
// Postcondition: Returns the circumference.
return Math.PI * diameter();
} // end circumference
public double area() {
// Determines a sphere's surface area.
// Precondition: None.
// Postcondition: Returns the surface area.
return 4.0 * Math.PI * theRadius *
theRadius;
} // end area
public double volume() {
// Determines a sphere's volume.
// Precondition: None.
// Postcondition: Returns the volume.
return (4.0*Math.PI * Math.pow(theRadius,
3.0)) / 3.0;
} // end volume
public void displayStatistics() {
// Displays statistics of a sphere.
// Precondition: Assumes System.out is
available.
// Postcondition: None.
System.out.println("\nRadius = "
+ radius() +
"\nDiameter = " +
diameter() +
"\nCircumference =
" + circumference() +
"\nArea = " +
area() +
"\nVolume = " +
volume());
} //
end displayStatistics
}
// end Sphere
- Notice all of the comments and pre- and post- conditions. There is actually very little code in this example.
-
Also notice that this is not the same kind of class that you learned in
CSC-116 and CSC-117. It does not do something as simple as display a circle on
a Java Applet.
-
This was meant to be used in a Java application. Notice the use of
System.out.println in the last method!
Once we have this class defined, we could use it in
a main program like this:
public static void main(String args[]) {
// unitSphere radius is 1.0
Sphere unitSphere = new Sphere( );
// mySphere radius is 5.1
Sphere mySphere = new Sphere(5.1);
unitSphere.displayStatistics( );
mySphere.setRadius(4.2); //resets radius to 4.2
System.out.println(mySphere.diameter() );
}
It would be a good exercise for you to try to get these two program pieces working together!
Inheritance is also a property that we can use when using an OOP language like Java. Here is an example. Suppose we wanted to extend our definition of a sphere so that it would include a color. Let’s examine the following code:
import
java.awt.Color;
public
class ColoredSphere extends Sphere {
private Color color;
public ColoredSphere(Color c) {
// Constructor: Creates a sphere and
initializes its
// radius to 1.
// Precondition: c is the desired color.
// Postcondition: A sphere of radius 1.0
// and color c exists.
super();
color = c;
} //
end default constructor
public ColoredSphere(Color c,
double initialRadius) {
// Constructor: Creates a sphere and
initializes its
// radius.
// Precondition: initialRadius is the
desired radius,
// c is the desired color.
// Postcondition: A sphere of radius
initialRadius
// and color c exists.
super(initialRadius);
color = c;
} // end constructor
public void setColor(Color c) {
// Sets the color of the sphere.
// Precondition: c is the desired color.
// Postcondition: The sphere color is now c.
color = c;
} //
end setColor
public Color getColor() {
// Returns the color of the sphere.
// Precondition: c is the desired color.
// Postcondition: None.
return color;
} //
end getColor
} // end ColoredSphere
Things to note:
-
we are importing the Color class from Java
-
ColoredSphere extends our existing Sphere class. The Sphere class is
the superclass and ColoredSphere is the subclass. Therefore the ColoredSphere
class already knows about “theRadius” item in our Sphere class and all of the
methods there.
-
It uses a method called “super”. This is a reserved word method in Java
that automatically the constructor functions in the Sphere class.
Here is a method that could appear in a main program
that uses the ColoredSphere class. Note that it is NOT a main program, only a
method.
public void
useColoredSphere() {
ColoredSphere ball =
new
ColoredSphere(java.awt.Color.white);
ball.setRadius(5.0);
System.out.println("The ball diameter
is " +
ball.diameter());
System.out.println("The ball color is
" +
ball.getColor());
// other code here...
} // end useColorSphere
Let’s follow the code in the above
example to make sure we understand what happens.
Another item we may have to deal with is object equality. How can we tell when two objects, say two spheres, are “equal”, whatever equal means. This is a little tricky, but Java can help. Java provides a method called “equals” which we can use, but we must be careful.
Sphere
sphere1 = new Sphere();
Sphere
sphere2 = sphere1;
if
(sphere1.equals(sphere2)) {
System.out.println("sphere1 and
sphere2 are the " +
"same
object");
}
else
{
System.out.println("sphere1 and
sphere2 are " +
"different
objects");
} // end if
In the above example, notice that sphere2 was set equal to sphere1. In other words, sphere2 is the SAME object as sphere1. The “equals” method will return a true and the program will print that the are the same object. But now let’s look at another example:
Sphere
sphere1 = new Sphere(2.0);
Sphere
sphere3 = new Sphere(2.0);
if
(sphere1.equals(sphere3)) {
System.out.println("sphere1 and
sphere3 have " +
"the same radius");
}
else
{
System.out.println("sphere1 and
sphere3 have " +
"different
radii");
} // end if
This is a little different. In this case we have two spheres that have been defined with the same radius. But Java still thinks of them as being two separate and distinct objects. Therefore when the “equals” method is called, it will return a false and the program will print that they have different radii, which they do not.
So we have a choice. We can rely on Java’s “equals” method that checks only for Object equality, or perhaps we need something more. Is there a way of defining Spheres that have the same radius, yet are different objects and can we still treat them as equals? In other words, can we “override” Java’s method and create our own? YES!
public
boolean equals(Object rhs) {
return ((rhs instanceof Sphere) &&
(theRadius ==
((Sphere)rhs).theRadius));
} // end equals
Notice:
- The parameter is of type Object because it has to match the equals method already defined in Java.
- The method will only do something if the object passed to it is a Sphere.
- If it is a sphere, then it will check the radius of the passed parameter against the radius of our current object and return a true is the two radii are equal.
Other Java things that you may need:
Java Interfaces
Suppose
you have several classes and you want to apply the same kinds of methods to many
of them. You could create subclasses, but that would be tedious. Java has a
special feature called an “interface”. An interface allows you to specify
methods and constants but does not provide the details of implementation for
any methods. That is left until later. For example, Java has a nice interface
already defined in
java.util.Collection
It provides methods, such as “add” and “contains”
for handling objects that belong to a “collection”. We may not want to use the
methods in this Java class as they are. So perhaps we are dealing with a
collection of cards and need to implement the methods differently. If so we may
do something like the following:
public
abstract class CardCollection implements java.util.Collection {
//...
public boolean add(Object o) {
// implementation of add method
// The following added so code will
compile
return true;
} // end add
public boolean contains(Object o) {
// implementation of contains method
// The following added so code will compile
return true;
} //
end contains
// and so on...
} // end CardCollection
In this case we have a specific collection, say of playing cards. Notice that we say our class will “implement” the methods in the Java Collection class. In other words WE are going to define them. The above code does not actually implement anything however. If you were to do this kind of thing, then there would be more code inside the actual add and contains methods.
You can even define your own interfaces. For
example:
public interface MyInterface {
public final int f1 = 0;
public void method1();
public void method2(int a, int b);
} //end of MyInterface
When someone wants to use your interface, they would start their class definition as follows:
public
class Whatever implements MyInterface{ ….
Java Exceptions:
Of
course, things are bound to go wrong sometimes. This is why Java provides a few
ways to allow the user (programmer) to determine when an error occurs and to do
something about it.
One
way is the “try-catch” approach. In this approach, you try to do something, but
if it doesn’t work, there is code available to “catch” the error and report it
to Java, which then can either stop the program or try to fix the error.
The
other way of doing things is to create your own exceptions and “throw” them to
Java to handle. We will not discuss these error handling techniques in detail
now. But you should read up on them. There are some better example in your old
Java textbook.
An Array-Based Implementation of the ADT List
We
have been talking about lists and the data structures and operations that they
contain as an ADT. Now is time to actually look at an implementation for a
list.
First we need to decide what kind of data structure
to use. It is natural to use an array, but arrays have limitations. For
example, what happens when the array gets full? But we will look at it anyway.
Let’s define the data structure itself.
private final int MAX_LIST = 100;
private int items[MAX_LIST];
private int numItems;
Note:
1.
MAX_LIST is “final”. It cannot be changed.
2.
numItems is NOT an index. For example if numItems is a 10, then the
last element of the array will be at index 9.
Now let’s develop an interface for this data
structure:
//
********************************************************
//
Interface IntegerListInterface for the ADT list.
//
*********************************************************
public
interface IntegerListInterface {
public boolean isEmpty();
// Determines whether a list is empty.
// Precondition: None.
// Postcondition: Returns true if the list
is empty,
// otherwise returns false.
// Throws: None.
public int size();
// Determines the length of a list.
// Precondition: None.
// Postcondition: Returns the number of
items that are
// currently in the list.
// Throws: None.
public void removeAll();
// Deletes all the items from the list.
// Precondition: None.
// Postcondition: The list is empty.
// Throws: None.
public void add(int index, int item)
throws
ListIndexOutOfBoundsException,
ListException;
// Adds an item to the list at position
index.
// Precondition: index indicates the
position at which
// the item should be inserted in the list.
// Postcondition: If insertion is
successful, item is
// at position index in the list, and other
items are
// renumbered accordingly.
// Throws: ListIndexOutOfBoundsException if
index < 1 or
// index > size()+1.
// Throws: ListException if item cannot be
placed on
// the list.
public int get(int index) throws
ListIndexOutOfBoundsException;
// Retrieves a list item by position.
// Precondition: index is the number of the
item to be
// retrieved.
// Postcondition: If 1 <= index <=
size(), the item at
// position index in the list is returned.
// Throws: ListIndexOutOfBoundsException if
index < 1 or
// index > size().
public void remove(int index)
throws ListIndexOutOfBoundsException;
// Deletes an item from the list at a given
position.
// Precondition: index indicates where the
deletion
// should occur.
// Postcondition: If 1 <= index <=
size(), the item at
// position index in the list is deleted,
and other items
// are renumbered accordingly,
// Throws: ListIndexOutOfBoundsException if
index < 1 or
// index > size().
}
// end IntegerListInterface
Notice:
1.
This is only an interface. It does not include the code for the various
methods.
2.
It uses extensive use of comments, especially pre- and post-
conditions.
3.
It specifies which methods will actually try to throw error conditions,
including what kinds of errors it will try to detect and the kinds of
exceptions it will throw under those conditions.
NOW COMES A BIG OOPS!!!!!!!
The direction we are going is fine, but it will only
work for lists of integers, which are not very interesting and not very useful.
We really should be developing this whole thing for a general list of any kind
of object. Hmm. Can we do that? YES!
Here is the interface rewritten for general objects.
Actually all of the comments from the last interface should be included here as
well.
//
********************************************************
//
Interface ListInterface for the ADT list.
//
*********************************************************
public
interface ListInterface {
public boolean isEmpty();
public int size();
public void add(int index, Object item)
throws
ListIndexOutOfBoundsException,
ListException;
public Object get(int index)
throws
ListIndexOutOfBoundsException;
public void remove(int index)
throws ListIndexOutOfBoundsException;
public void removeAll();
} // end ListInterface
And here is the actual class
that defines the array based list and implements all of those functions in the
interface:
//
********************************************************
//
Array-based implementation of the ADT list.
//
*********************************************************
public
class ListArrayBased implements ListInterface {
private static final int MAX_LIST = 50;
private Object items[]; // an array of list items
private int numItems; // number of items in list
public ListArrayBased() {
items = new Object[MAX_LIST];
numItems = 0;
} //
end default constructor
public boolean isEmpty() {
return (numItems == 0);
} // end isEmpty
public int size() {
return numItems;
} //
end size
public void removeAll() {
// Creates a new array; marks old array
for
// garbage collection.
items = new Object[MAX_LIST];
numItems = 0;
} // end removeAll
public void add(int index, Object item)
throws ListIndexOutOfBoundsException {
if (numItems > MAX_LIST) {
throw new
ListException("ListException on add");
}
// end if
if (index >= 1 && index <=
numItems+1) {
// make room for new element by shifting
all items at
// positions >= index toward the end
of the
// list (no shift if index ==
numItems+1)
for (int pos = numItems; pos >=
index; pos--) {
items[translate(pos+1)] =
items[translate(pos)];
} // end for
// insert new item
items[translate(index)] = item;
numItems++;
}
else {
// index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on
add");
}
// end if
} //end add
public Object get(int index)
throws
ListIndexOutOfBoundsException {
if (index >= 1 && index <=
numItems) {
return items[translate(index)];
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on
get");
}
// end if
} // end get
public void remove(int index)
throws
ListIndexOutOfBoundsException {
if (index >= 1 && index <=
numItems) {
// delete item by shifting all items at
// positions > index toward the
beginning of the list
// (no shift if index == size)
for (int pos = index+1; pos <=
size(); pos++) {
items[translate(pos-1)] =
items[translate(pos)];
}
// end for
numItems--;
}
else {
// index out of range
throw new
ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on
remove");
}
// end if
} //end remove
private int translate(int position) {
return position - 1;
} //
end translate
} // end ListArrayBased
public
class ListException extends RuntimeException {
public ListException(String s) {
super(s);
} //
end constructor
} // end ListException
public
class ListIndexOutOfBoundsException
extends IndexOutOfBoundsException
{
public ListIndexOutOfBoundsException(String
s) {
super(s);
} //
end constructor
} // end ListIndexOutOfBoundsException
We will spend a good deal of time going over this code so that we all understand it.
Your next assignment is will actually be
your Midterm Exam. It is based on problems 8 and 9 on pages 147 and 148 in your
text and on problem 8 on page 150 of your text. Please see the link from the
Assignments page for the instructions for your midterm.