Data Abstraction

Copyright © 1996-97 Kenneth J. Goldman

Just as procedural abstraction lets us think about a series of computational steps as an abstract unit, data abstraction lets us think about collections of data as abstract entities. This is useful for:

The product of procedural abstraction is a procedure. Similarly, the product of data abstraction is an abstract data type (ADT). In object-oriented languages (like Java), ADT's are implemented as classes.

An abstract data type (ADT) consists of:

  1. An interface -- a set of operations that can be performed (also known as an abstraction barrier).
  2. The allowable behaviors -- the way we expect instances of the ADT to respond to operations.
The implementation of an ADT consists of:
  1. An internal representation -- data stored inside the object's instance variables.
  2. A set of methods implementing the inerface.
  3. A set of representation invariants, true initially and preserved by all methods
Let's revisit some classes we've already built and think about them as implementations of ADT's, and then see some new examples.
Bank account
Interface: create, deposit, withdraw, transfer
Legal behaviors: any deposit is OK, but withdrawals and transfers must have sufficient funds
deposits and withdrawals accumulate over time
Internal representation: balance
Representation invariant: balance >= 0

Does this hold for our implementation? What about a negative balance?

Sphere object
Interface: create, move, resize, check if a point is within sphere, volume
Legal behaviors: any position is OK, most recent position is used
resize OK as long as r>=0
Internal representation: x, y, z (center) and r (radius)
Representation invariant: r >= 0
Does this hold for our implementation? Yes, this is enforced by resize; recall that resize is the only way to set the radius.
To reiterate:

Example: CS101Canvas

For many of the assignments in this course, you will use a class called CS101Canvas as a way to draw graphics objects on the screen, put up textual messages, and get user input.

The CS101Canvas is an implementation of a graphics display window ADT. In order to use it, you will not need to understand (or even look at) the internal implementation. You'll only need to understand the interface and the associated behaviors.

When you instantiate the CS101Canvas, you get something that might look like this (the actual appearance depends on what type of machine you use):

CS101Canvas screen = new CS101Canvas();


The interface to the CS101Canvas class includes the following methods:

More complete documentation for the class is also available.
Graphics objects added to the canvas remain there until removed.
Instructions, labels, and text settings replace previous values.
click() returns only after the mouse button is clicked in the graphics area.
The quit button, when clicked, terminates the entire program.
In your labs, you will create graphics objects, add them to the canvas, provide user instructions, and accept mouse input entirely through this interface, knowing only the expected behavior. You can program to this abstraction barrier and not need to know the internal representation. In fact, we could change the internal representation, and you'd never know. This is important because it means you wouldn't have to change your program even if a better implementation of the CS101Canvas comes along.

Example: Baseball Scorekeeper

Suppose we want a device that keeps track of the current "count" in a baseball game. For each pitch, there are six possibilities: In addition, other runners might produce these possibilities: The rules for scoring are: Let's design a scorekeeper object that will keep track of We'll keep these values as our internal representation and write one method for each of the ADT operations. (Think of each operation as being invoked by a button press on a hand-held scorekeeper.)

Method Parameters Mutates Returns
constructor team names stores team names and initializes all counts
hit reset count (balls and strikes) for new batter
ball increment balls; if 4, walk
strike increment strikes; if 3, batter out
foul strike if less than 2 strikes so far
walk reset count for new batter
batterOut reset count and record an out
out increment outs; if 3, start a new half inning
run increment current team's score (home if bottom of inning or visitors if top)
toString description of game status

Notice that some things are done several times or involve significant work, such as resetting the count or going to a new half. We will create internal (non-public) methods for these.

public class Scorekeeper {

   String homeTeam, visitingTeam;

   int inning;

   boolean topOfInning; 

   int home, visitors;         // score

   int balls, strikes, outs;   // count

   boolean gameOver;

   Scorekeeper(String homeTeam, String visitingTeam) {

      this.homeTeam = homeTeam;

      this.visitingTeam = visitingTeam;

      inning = 1;

      topOfInning = true;

      home = visitors = balls = strikes = outs = 0;

      gameOver = false;


   void resetBallsAndStrikes() {

      balls = strikes = 0;


   public void hit() {



   public void ball() {


      if (balls == 4)



   public void strike() {


      if (strikes == 3)



   public void foul() {

      if (strikes < 2)



   public void walk() {



   public void batterOut() {




   public void out() {


      if (outs == 3)



   public void run() {

      if (topOfInning)


      else {


         gameOver = ((inning >= 9) && (home > visitors));



   void newHalf() {


      outs = 0;

      if ((inning > 8) && (topOfInning == false) && (home != visitors))

        gameOver = true;

      else {

         if (!topOfInning)


         topOfInning == !topOfInning;



   public String toString() {

      if gameOver

         return ("Final Score after " + inning + " innings: " + score());

      else {

         String topBot;

         if topOfInning

           topBot = "top"


           topBot = "bottom"

         return ("In the " + topBot + " of inning " + inning + "with " +

                 balls + " balls, " + strikes + " strikes, and "

                 + outs + " outs, it's " + score());




   String score() {

      if (home > visitors)

         return (homeTeam + " over " + visitingTeam + ", "

                 + home + " to " + visitors + ".");

      else if (visitors > home)

         return (visitingTeam + " over " + homeTeam + ", "

                 + visitors + " to " + home + ".");


         return (visitingTeam + " and " + homeTeam + " tied "

                 + home + " to " + visitors + ".");



Notice that some methods are not public (for internal use only). Also notice several examples of reduction; for example, hit and walk both use resetCount.

Notice several cases where we use other methods conditionally:

Sometimes this just makes the code more readable, not necessarily saving time, space, or lines of code.

Notice that nearly all the methods return void -- they are strictly mutators. In this object, all information is gained using the toString method. If this code were embedded in a hand-held umpire's device, some of the state information (values of instance variables) might be displayed using LCDs.

Example: Rational Number ADT

Let's look at another ADT example. In this example, a typical program using the ADT would create many instances of the class, not just one object, and many of the methods of this class will create new instances of the class.

We could implement a simple class that holds a pair of integers. The instance variables could be public, meaning that we can access them directly without using a method call.

public class IntPair {

   public int a;

   public int b;

   public IntPair(int a, int b) {

      this.a = a;

      this.b = b;


   public String to String() {

      return ("(" + a + "," + b + ")");



Example use:

IntPair p1 = new IntPair(3, 4);

p1.a = 6;      // External assignment to public instance variable

Terminal.println("Pair p1 contains " + p1);

The output from the last line would be "Pair p1 contains (6,4)".

We could store the numerator and denominator of a rational number in a and b. However, this is NOT an ADT -- it's just a type of compound data object that could be used to hold some values and treated as a single entity.

We could use an IntPair to represent a rational number like 3/4 by assigning a=3 and b=4, but we would like to be able to operate on rational numbers at a higher level. For example, we'd like an add operation that would sum two rational numbers to produce a new rational number.

Let's design an interface for our rational number ADT:
Method Parameters Mutates Returns
constructor numer, denom stores numerator and denominator object reference
getNumer value of numerator
getDenom value of denominator
plus Rational r new Rational: sum of this and the given parameter r
minus Rational r new Rational: this - r
times Rational r new Rational: this * r
over Rational r new Rational: this / r
negate new Rational: -this
invert new Rational: 1 / this
toString a String of the form numer/denom

Note that we never change the value of the rational number once it's constructed. Most methods return new rational numbers.

Before proceeding with the implementation, recall:

n1/d1 + n2/d2 = (n1*d2+n2*d1) / (d1*d2)
n1/d1 * n2/d2 = (n1*n2) / (d1*d2)
-(n/d) = (-n)/d
1 / (n/d) = d/n
The following operations can be implemented in terms of the above:
r1 - r2 = r1 + -r2
r1 / r2 = r1 * (1/r2)
These are two examples of reduction, modifying one problem to use the solution of another. Here, we're reducing subtraction to addition, and division to multiplication. Reduction helps us save development time by reusing existing code.

public class Rational {

   int n;  // numerator

   int d;  // denominator

   Rational(int numerator, int denominator) {

      n = numerator;

      d = denominator;


   public int getNumer() {

      return n;


   public int getDenom() {

      return d;


   public Rational plus(Rational r2) {

      int n2 = r2.getNumer;

      int d2 = r2.getDenom;

      return(new Rational(n*d2 + n2*d, d*d2));


   public Rational minus(Rational r2) {

      return plus(r2.negate());


   public Rational times(Rational r2) {

      int n2 = r2.getNumer;

      int d2 = r2.getDenom;

      return(new Rational(n*n2, d*d2));


   public Rational over(Rational r2) {

      return times(r2.invert());


   public Rational negate() {

      return (new Rational(-n, d));


   public Rational invert() {

      return (new Rational(d, n));


   public String toString() {

      return ("" + n + "/" + d);



Example uses of the Rational number class:

Rational oneHalf = new Rational(1, 2);

Rational threeFourths = new Rational(3, 4);

Terminal.println("Adding " + oneHalf + " and " + threeFourths + ":");

Terminal.println("The result is " +;

Terminal.println("Now, subtraction:");






The output is:

Adding 1/2 and 3/4:

The result is 10/8

Now subtraction:






Notice that the fractions are not reduced. After a while, this could get out of hand. How can we fix this?

One possible solutions is to divide the numerator and denominator by the GCD inside the constructor. But how can we compute the GCD? More about this later...

Kenneth J. Goldman
Last modified: Mon Feb 10 23:44:34 CST