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:

- Grouping related pieces of information.
- Defining and understanding what meaningful operations can be performed on the data.
- Enforcing certain restrictions on the use of the data.
- Simplifying the task of reasoning about the data.
- Separating the implementation from the abstraction itself, so we can change the internal representation and/or implementation without changing the abstract behavior, and so people can use the abstraction without needing to understand the internal implementation.

An abstract data type (ADT) consists of:

- An interface -- a set of operations that can be performed
(also known as an
**abstraction barrier**). - The allowable behaviors -- the way we expect instances of the ADT to respond to operations.

- An internal representation -- data stored inside the object's instance variables.
- A set of methods implementing the inerface.
- A set of representation invariants, true initially and preserved by all methods

**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>=0Internal representation: x, y, z (center) and r (radius) Representation invariant: r >= 0 `resize`

; recall that`resize`

is the only way to set the radius.

- ADT's let people rely on the interface without having to
know the internal details. This simplifies
**use**of the ADT. - The ADT interface forms an abstraction barrier that
**enforces proper use**of the data. This simplifies**implementation**of the ADT, since we can rely on the truth of the representation invariants in each method.

`CS101Canvas`

`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:

`add(g)`

-- adds a graphics object`g`

such as a`Rect`

,`Line`

,`Oval`

,`Text`

, etc.`remove(g)`

-- removes graphics object`g`

from the graphics area`setInstruction(s)`

-- displays`String s`

in the instruction text area`setLabel1(s)`

-- sets the label for the middle text area to`String s`

`setLabel2(s)`

-- sets the label for the bottom text area to`String s`

`setLabelText1(s), setLabelText2(s)`

-- display`String s`

in the middle or bottom text area, respectively`Position click()`

-- waits for the user to click a mouse button in the graphics area and returns the position of the mouse`int getWidth()`

-- returns the width of the drawing area as a`Rectangle`

object.`int getHeight()`

-- returns the height of the drawing area as a`Rectangle`

object.`sleep(t)`

-- causes a delay of`t`

milliseconds, useful for controlling the speed of animations

**Behavior:**- 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.

`CS101Canvas`

comes along.
- hit -- batter hits the ball and gets on base
- ball -- batter doesn't swing at pitch not in strike zone
- strike -- batter misses pitch in the strike zone
- foul -- batter hits the ball, but it goes foul (this counts as a strike, unless the batter already has 2 strikes)
- walk -- 4 balls or the pitcher hits the batter with the ball
- batter out -- 3 strikes, or ball is hit and caught, or the batter is tagged or out at base

- out -- another runner is tagged or out at base (there may be more than one out for a given pitch)
- run -- a runner crosses home plate (there may be more than one run for a given pitch)

- There are nine innings, each divided in two halves (top and bottom).
- There are three outs in each half.
- The home team is at bat in the bottom of each inning.
- Whenever the batter gets a hit, walks, or is out, the next batter comes up, and the count of balls and strikes is reset to zero.

- current half inning
- current score (number of runs, home and away)
- current count (balls, strikes, and outs)

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() { resetBallsAndStrikes(); } public void ball() { balls++; if (balls == 4) walk(); } public void strike() { strikes++; if (strikes == 3) batterOut(); } public void foul() { if (strikes < 2) strike(); } public void walk() { resetBallsAndStrikes(); } public void batterOut() { resetBallsAndStrikes(); out(); } public void out() { outs++; if (outs == 3) newHalf(); } public void run() { if (topOfInning) visitors++; else { home++; gameOver = ((inning >= 9) && (home > visitors)); } } void newHalf() { resetBallsAndStrikes(); outs = 0; if ((inning > 8) && (topOfInning == false) && (home != visitors)) gameOver = true; else { if (!topOfInning) inning++; topOfInning == !topOfInning; } } public String toString() { if gameOver return ("Final Score after " + inning + " innings: " + score()); else { String topBot; if topOfInning topBot = "top" else 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 + "."); else return (visitingTeam + " and " + homeTeam + " tied " + home + " to " + visitors + "."); } }Notice that some methods are not public (for internal use only). Also notice several examples of

`hit`

and `walk`

both use
`resetCount`

.Notice several cases where we use other methods conditionally:

- After 3 strikes,
`batterOut`

is called. - After 4 balls,
`walk`

is called.

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.

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:

**Addition:**- n1/d1 + n2/d2 = (n1*d2+n2*d1) / (d1*d2)
**Multiplication:**- n1/d1 * n2/d2 = (n1*n2) / (d1*d2)
**Negation:**- -(n/d) = (-n)/d
**Inverse:**- 1 / (n/d) = d/n

**Subtraction:**- r1 - r2 = r1 + -r2
**Division:**- r1 / r2 = r1 * (1/r2)

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 " + oneHalf.plus(threeFourths)); Terminal.println("Now, subtraction:"); Terminal.println(oneHalf.minus(threeFourths).toString()); Terminal.println("Multiplication:"); Terminal.println(oneHalf.times(threeFourths)); Terminal.println("Division:"); Terminal.println(oneHalf.over(threeFourths));The output is:

Adding 1/2 and 3/4: The result is 10/8 Now subtraction: -2/8 Multiplication: 3/8 Division: 4/6Notice 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...