3.

3 Designing Data Types

In this sec2on we discuss encapsula)on, immutability, and inheritance, with par2cular a:en2on to the use of
these mechanisms in data-type design to enable modular programming, facilitate debugging, and write clear
and correct code.
Encapsula)on. The process of separa2ng clients from implementa2ons by hiding informa2on is known as
encapsula2on. We use encapsula2on to enable modular programming, facilitate debugging, and clarify program
code.
• Complex numbers revisited. Complex.java has the same API as Complex.java,
except that it represents a complex number using polar coordinates
r(cosθ+ isinθ) instead of Cartesian coordinates as x+ iy. The idea of
encapsula2on is that we can subs2tute one of these programs for the other
without changing client code.
• Private. When you declare an instance variable (or method) to be private,
you are making it impossible for any client (code in another class) to directly access that instance
variable (or method). This helps enforce encapsula2on.
• Limi)ng the poten)al for error. Encapsula2on also helps programmers ensure that their code
operates as intended. To understand the problem, consider Counter.java, which encapsulates a single
integer and ensures that the only opera2on that can be performed on the integer is increment by 1.

Without the private modifier, a client could write code like the following:
Counter counter = new Counter("Volusia");
counter.count = -16022;
With the private modifier, code like this will not compile.
Immutability.
An object from a data type is immutable if its data-type value cannot change once created. An immutable data
type is one in which all objects of that type are immutable.
• Advantages of immutability. We can use immutable objects in assignment
statements (or as arguments and return values from methods) without having to
worry about their values changing. This makes immutable type easier to reason
about and debug.
• Cost of immutability. The main drawback of immutability is that a new object
must be created for every value.
• Final. When you declare an instance variable as final, you are promising to assign it
a value only once. This helps enforce immutability.
• Reference types. The final access modifier does not guarantee immutability for instance variables of
mutable types. In such cases, you must make a defensive copy.
Spa)al vectors.
A spa)al vector is an abstract en2ty that has a magnitude and a direc)on. A sequence
of n real numbers suffices to specify a vector in n-dimensional space. We use a
boldface le:er like x to denote the vector (x0,x1,…,xn−1).
• API. The basic opera2ons on vectors are to add two vectors, mul2ply a
vector by a scalar, compute the dot product of two vectors, and to compute
the magnitude and direc2on, as follows:

1
3.3 Designing Data Types

!
These basic mathema2cal defini2ons lead immediately to an API:

!
• Implementa)on. Vector.java is an immutable data type that implements this API. Internally, it uses an
array of length n to store the Cartesian coordinates.
• The this reference. Within an instance method (or constructor), the this keyword gives us a way to
refer to the object whose instance method (or constructor) is being called. For example, the
magnitude() method in Vector uses the this keyword in two ways: to invoke the dot() method and
as the argument to the dot() method.
// return the magnitude of this Vector
public double magnitude() {
return Math.sqrt(this.dot(this));
}
Interface inheritance (subtyping). Java provides the interface construct for declaring a rela2onship between
otherwise unrelated classes, by specifying a common set of methods that each implemen2ng class must
include. Interfaces enable us to write client programs that can manipulate objects of varying types, by invoking
common methods from the interface.
• Defining an interface. Func2on.java defines an interface for real-valued func2ons of a single variable.
public interface Function {
public abstract double evaluate (double x);
}
The body of the interface contains a list of abstract methods. An abstract method is a method that is
declared but does not include any implementa2on code; it contains only the method signature. You must
save a Java interface in a file whose name matches the name of the interface, with a .java extension.
• Implemen)ng an interface. To write a class that implements an interface, you must do two things.
◦ Include an implements clause in the class declara2on with the name of the interface.
◦ Implement each of the abstract methods in the interface.
For example, Square.java and GaussianPDF.java implements the Function interface.
• Using an interface. An interface is a reference type. So, you can declare the type of a variable to be the
name of an interface. When you do so, any object you assign to that variable must be an instance of a
class that implements the interface. For example, a variable of type Function may store an object of
type Square or GaussianPDF.

2
3.3 Designing Data Types
Function f1 = new Square();
Function f2 = new GaussianPDF();
Function f3 = new Complex(1.0, 2.0); // compile-time error
When a variable of an interface type invokes a method declared in the interface, Java knows which method to
call because it knows the type of the invoking object. This powerful programming mechanism is known as
polymorphism or dynamic dispatch.
• PloEng func)ons. Func2onGraph.java plots the graph of a real-valued func2on f in the interval [a, b] by
sampling the func2on at n + 1 evenly spaced points. It works for any sufficiently smooth func2on f that
implements the Function interface.

• Numerical integra)on. RectangleRule.java es2mates the integral of a posi2ve real-valued func2on f in
an interval (a, b) using the rectangle rule. It works for any sufficiently smooth func2on f that
implements the Function interface.

• Lambda expressions. To simplify syntax, Java provides a powerful func2onal programming feature
known as lambda expressions. You should think of a lambda expression as a block of code that you can
pass around and execute later. In its simplest form, a lambda expression consists of the three elements:
◦ A list of parameters variables, separated by commas, and enclosed in parentheses
◦ The lambda operator ->
◦ A single expression, which is the value returned by the lambda expression
For example, the following lambda expression implements the hypotenuse func2on:

!
Our primary use of lambda expressions is as a concise way to implement a func)onal interface (an
interface with a single abstract method). Specifically, you can use a lambda expression wherever an object
from a func2onal interface is expected. For example, all of the following expressions implement the
Func2on.java interface:

3
3.3 Designing Data Types

Consequently, you can can integrate the square func2on with the call integrate(x -> x*x, 0, 10,
1000), bypassing the need to define a separate Square class.
• Built-in interfaces. Java includes three built-in interfaces that we will consider later this book.
• The interface java.u2l.Comparable defines an order in which to compare objects of the same
type, such as alphabe2cal order for strings or ascending order for integers.
• The interfaces java.u2l.Iterator and java.lang.Iterable enable clients to iterate over the items
in a collec2on, without relying on the underlying representa2on.

Implementa)on inheritance (subclassing). Java also supports another inheritance mechanism known as
subclassing. The idea is to define a new class (subclass, or derived class) that inherits instance variables (state)
and instance methods (behavior) from another class (superclass, or base class), enabling code reuse. Typically,
the subclass redefines or overrides some of the methods in the superclass. For example, Java provides an
elaborate inheritance hierarchy for GUI components:

!
In this book, we avoid subclassing because it works against encapsula2on and immutability (e.g., the fragile
base class problem and the circle–ellipse problem).
• Java's Object superclass. Certain ves2ges of subclassing are built into Java and therefore unavoidable.
Specifically, every class is a subclass of java.lang.Object. When programming in Java, you will ocen
override one or more of these inherited methods:

!
• String conversion. Every Java class inherits the toString() method, so any client can invoke
toString() for any object. This conven2on is the basis for Java’s automa2c conversion of one
operand of the string concatena2on operator + to a string whenever the other operand is a string.
• Reference equality. If we test equality with (x == y), where x and y are object references, we are
tes2ng whether they have the same iden2ty: whether the object references are equal.
• Object equality. The purpose of the equals() method is to test whether two objects are equal
(correspond to the same data-type value). It must implement an equivalence rela)on:
◦ Reflexive: x.equals(x) is true.

4
3.3 Designing Data Types

◦ Symmetric: x.equals(y) is true if and only if y.equals(x) is

true.
◦ Transi2ve: if x.equals(y) is true and y.equals(z) is true,
then x.equals(z) is true.
In addi2on, the following two proper2es must hold:
◦ Mul2ple calls to x.equals(y) return the same truth value,
provided neither object is modified between calls.
◦ x.equals(null) returns false.
Overriding the equals() method is unexpectedly intricate because its
argument can be a reference to an object of any type (or null).
• Hashing. The purpose of the hashCode(), method is to support hashing, which
is a fundamental opera2on that maps an object to an integer, known as a hash code. It must sa2sfy the following
two proper2es:
◦ If x.equals(y) is true, then x.hashCode() is equal to y.hashCode().
◦ Mul2ple calls of x.hashCode() return the same integer, provided the object is not modified
between calls.
Typically, we use the hash code to map an object x to an integer in a small range, say between 0 and
m-1, using this hash func)on:
private int hash(Object x) {
return Math.abs(x.hashCode() % m);
}
Objects whose values are not equal can have the same hash func2on value but we expect the hash func2on to
divide n typical objects from the class into m groups of roughly equal size.
• Wrapper types.
The toString(), hashCode(), and equals() methods apply only to reference types,
not primi2ve types. For example, the expression x.hashCode() works if x is a variable
of type Integer but not if it is of type int. For situa2ons where we wish want to
represent a value from a primi2ve type as an object, Java supplies built-in reference
types known as wrapper types, one for each of the eight primi2ve types.
• Autoboxing and unboxing. Java automa2cally converts between values from a
wrapper type and the corresponding primi2ve type, so that you can write code like the following:
Integer x = 17; // Autoboxing (int -> Integer)
int a = x; // Unboxing (Integer -> int)
Applica)on: data mining. We consider a data mining applica2on in which the goal is to associate with each
document a vector known as a sketch so that so that documents that are different have sketches that are
different and documents that are similar have sketches that are similar. Our API abstracts away this no2on into
the method similarTo(), which is a real number between 0 (not similar) and 1 (similar). The parameters k
and d control the quality of the sketch.

!
• Compu)ng sketches. Sketch.java uses a simple frequency count approach to compute the sketch of a
text document. In its simplest form, it counts the number of )me each k-gram (substring of length k)
appears in the text. The sketch that we use is the direc)on of the vector defined by these frequencies.
• Hashing. For ASCII text strings there are 128 different possible values for each character, so there are
128k possible k-grams. For efficiency, Sketch.java uses hashing. That is, instead of coun2ng the number

5
3.3 Designing Data Types

of 2mes each k-gram appears, we hash each k-gram to an integer between 0 and d−1
and count the number of 2mes each hash value appears.
• Comparing sketches. Sketch.java uses the cosine similarity measure to compare two
sketches:
!
• Comparing all pairs. CompareDocuments.java prints the cosine similarity measure for
all pairs of documents on an input list.

!
Design by contract. We briefly discuss two Java language mechanisms that enable you to verify assump2ons
about your program while it is running—excep2ons and asser2ons.
• Excep)ons. An excep)on is a disrup2ve event that occurs while a program is running, ocen to signal an
error. The ac2on taken is known as throwing an excep)on. Java includes an elaborate inheritance
hierarchy of predefined excep2ons, several of which we have encountered previously.

!
It is good prac2ce to use excep2ons when they can be helpful to the user. For example, in Vector.java, we
should throw an excep2on in plus() if the two vectors to be added have different dimensions:
if (this.length() != that.length())
throw new IllegalArgumentException("Dimensions disagree.");
• Asser)ons. An asser)on is a boolean expression that you are affirming is true at some point during the
execu2on of a program. If the expression is false, the program will throw an AssertionError, which
typically terminates the program and reports an error message. For example, in Counter.java, we might
check that the counter is never nega2ve by adding the following asser2on as the last statement in
increment():
assert count >= 0 : "Negative count detected in increment()";
By default, asser2ons are disabled, but you can enable them from the command line by using the -
enableassertions flag (-ea for short). Asser2ons are for debugging only; your program should not rely
on asser2ons for normal opera2on since they may be disabled.
In the design-by-contract model of programming, the designer expresses condi2ons about the behavior of
the program using asser2ons.
• Precondi)on. A condi2on that the client promises to sa2sfy when calling a method.
• Postcondi)on. A condi2on that the implementa2on promises to achieve when returning from a method.
• Invariant. A condi2on that the implementa2on promises to sa2sfy while the method is execu2ng.