Abstract data types (ADT) and encapsulation

The way to cope with the complexity of a program is abstraction: seeing only the properties of an entity that matter at the moment and hiding the rest. Subprograms are process abstraction (you call sort without knowing the sorting algorithm). This week the second kind: data abstraction, that is the abstract data type (ADT). On exams conceptual questions are asked (the two conditions of an ADT, the benefit of information hiding, language comparisons) and the output of code that uses an ADT.

Golden rules:

1. ADT = hidden representation + a type and operations defined in a single unit.
2. The user sees only the interface. Changing the inside does not break user code.
3. A stack is LIFO, a queue is FIFO. In output questions write the contents at each step.
4. A parameterized ADT catches type errors at compile time.

Abstract data type

A user-defined type is an ADT if it satisfies two conditions:

1. Hidden representation: the internal structure of the type’s objects is hidden from the units that use the type. The user accesses the objects only through the operations the type defines.
2. A single unit: the declaration of the type and the protocols of the operations on it are in a single syntactic unit. Other units can create variables of this type.

In fact float is also like an ADT: you use + and * without knowing how the bits are arranged. User-defined ADTs bring the same comfort to the programmer’s own types.

Benefits of information hiding:

• Reliability: the user cannot corrupt the internal state of the object (cannot set the stack’s top field to a random value).
• Changeability: if the representation changes (a linked list instead of an array), the user code doesn’t change, because it depends only on the interface.
• Fewer name clashes and smaller, manageable units.

ADTs in Java: the class

static class IntStack {
    private int[] items = new int[10];
    private int top = -1;
    public void push(int x) { items[++top] = x; }
    public int pop() { return items[top--]; }
    public int peek() { return items[top]; }
    public boolean isEmpty() { return top == -1; }
}

IntStack s = new IntStack();
s.push(3); s.push(7); s.pop(); s.push(2); s.push(9);
System.out.println(s.pop() + s.peek());

11

operation  stack (bottom → top)
push 3     [3]
push 7     [3, 7]
pop        [3]          (7 returned)
push 2     [3, 2]
push 9     [3, 2, 9]
pop        [3, 2]       (9 returned)
peek                    (2, not removed)  → 9 + 2 = 11

Writing s.top = 5; or a.balance = 5000; from outside gives a compile error:

error: balance has private access in Account

Access levels in Java: private (only the class), package access (if not specified: the same package), protected (package + subclasses), public. Access is at the class level: a Money object can read the private field of another Money object.

Immutable ADT

static final class Money {
    private final int cents;
    Money(int c) { cents = c; }
    Money add(Money o) { return new Money(cents + o.cents); }
    int cents() { return cents; }
}
Money m1 = new Money(150);
Money m2 = m1.add(new Money(75));
System.out.println(m1.cents() + " " + m2.cents());

150 225

Objects that don’t change can be shared; aliasing problems (being changed from one place and surprised from another) disappear. Java’s String is like this too.

Interface separate from representation

List<Integer> nums = new ArrayList<>(List.of(4, 1, 3));
List<Integer> view = Collections.unmodifiableList(nums);
try { view.add(5); } catch (UnsupportedOperationException e) { System.out.println("UnsupportedOperationException"); }
nums.add(5);
System.out.println(view.size());

UnsupportedOperationException
4

ADTs in other languages

In Ada the private part of the specification package is there for the compiler to see (it needs to know the size of the object), but the user cannot access the fields there. To hide the representation completely, the type is declared as a pointer and the structure it points to is defined in the body.

In C++ the destructor is called automatically when the object’s lifetime ends and gives back the memory allocated on the heap. They run in the reverse order of creation. In Java a similar order is seen in try-with-resources:

try (Res r1 = new Res("A"); Res r2 = new Res("B")) {
    System.out.print("body ");
}

open A open B body close B close A

Parameterized ADTs

You want to write a stack that does the same job whatever the element type is. A parameterized ADT (generic class) takes a type parameter:

List<Integer> xs = new ArrayList<>();
xs.add("five");

error: no suitable method found for add(String)

C++ templates generate separate code for each different type (instantiation at compile time). Java generics use a single piece of code and the type information is erased after compilation (type erasure); that is why you cannot write new T().

Encapsulation for large programs

An ADT encapsulates a single type. In a system with thousands of classes, you need to group related types and subprograms, compile them separately and prevent name clashes.

• C: a header file (.h, interface) + an implementation file (.c). The compiler does not guarantee that the two files are consistent.
• C++, C#: namespace. Qualified names like std::cout or using.
• Java: package. A package is both a namespace and a unit of access: members without a modifier are visible inside the package.
• Ada: packages can be nested and compiled separately.
• Ruby: module.

Common mistakes

IntStack s = new IntStack();   // push, pop, peek on an int array
s.push(3); s.push(7); s.pop(); s.push(2); s.push(9);
System.out.println(s.pop() + s.peek());

IntStack t = new IntStack();
for (int i = 1; i <= 4; i++) t.push(i * i);
int sum = 0;
while (!t.isEmpty()) { int v = t.pop(); if (v % 2 == 0) sum += v; }
System.out.println(sum);

Queue2<String> q = new Queue2<>();
q.enqueue("a"); q.enqueue("b"); q.dequeue(); q.enqueue("c");
System.out.println(q.dequeue() + q.size());

class Account {
    private int balance = 100;
    public int getBalance() { return balance; }
}
// in another class:
Account a = new Account();
a.balance = 5000;

// Res(String n) prints "open n", close() prints "close n"
try (Res r1 = new Res("A"); Res r2 = new Res("B")) {
    System.out.print("body ");
}

List<Integer> xs = new ArrayList<>();
xs.add("five");

static final class Money {
    private final int cents;
    Money(int c) { cents = c; }
    Money add(Money o) { return new Money(cents + o.cents); }
    int cents() { return cents; }
}
// in main:
Money m1 = new Money(150);
Money m2 = m1.add(new Money(75));
System.out.println(m1.cents() + " " + m2.cents());

List<Integer> nums = new ArrayList<>(List.of(4, 1, 3));
List<Integer> view = Collections.unmodifiableList(nums);
try { view.add(5); }
catch (UnsupportedOperationException e) { System.out.println("UnsupportedOperationException"); }
nums.add(5);
System.out.println(view.size());