1 Abstract Data Types
2 Sets
2.1 Implementing Sets with Lists
3 A Java Interface for Sets
4 Summary

Representing and Implementing Sets

Now that you’re able to implement basic, concrete data structures in Java, we turn to more advanced data structures and data types. We’ll be focusing both on these data types in their own right, and on various implications of building them in Java (which in turn will lead us deeper into OO programming in the coming classes).

1 Abstract Data Types

Up until now, we have maintained a close connection between data types and their underlying implementations. For example, when we wanted lists, we used Racket lists; when we wanted trees, we implemented trees (either through Racket structs or Java classes). Today, we start looking at Abstract Data Types, which admit multiple implementations through concrete data structures.

Roughly speaking, an abstract data type (henceforth abbreviated ADT) has three components:

We will work with a specific example to illustrate ADTs.

2 Sets

Sets (collections of items) are a common data type in computing. We might use them to capture the courses someone has registered for, the destinations served by an airline, or someone’s friends in a social network. As a data type, sets have two key characteristics (a.k.a., properties):

Four operations are common on sets: adding elements, removing elements, determining how many elements are in the set, and asking whether a specific item is in the set.

We summarize this information in an ADT as follows:

-------------------------------------------

ADT Name: Set

ADT operations:

  addElt : Set element -> Set

  remElt : Set element -> Set

  size : Set -> integer

  hasElt : Set element -> boolean

ADT properties (vague):

  1. The set has no duplicates

  2. The items within the set are unordered

ADT axioms

  <will fill in later>

-------------------------------------------

An ADT is like an interface, in that it specifies what to provide but not how to provide it. (There are differences between interfaces and ADTs, which we return to later.) In order to run a program that uses an ADT, we also need to provide an implementation that satisfies the specification. Let’s look at that for Sets via Lists.

2.1 Implementing Sets with Lists

Even though we haven’t yet done lists in Java (we will next week), we can sketch this implementation out in a combination of Racket and pseudocode. To implement an ADT, we provide a concrete data structure to represent the list and implementations of each operation in the ADT that satisfy the signature and the properties.

Here, for example, is an implementation of Sets basd on Lists:

A set is a list

 

addElt(Set, element) =

  (cons element Set)

 

remElt(Set, element) =

  (remove element Set)  \* assume remove built-in on lists *\

 

size(Set) =

  (length Set)

 

hasElt(Set, element) =

  (member element Set)

Not quite done though. Before we can claim to implement the Set ADT, we have to show that this implementation respects the properties of Sets. How does this implementation stack up against the two properties?

The duplicates problem reflected through add and size illustrates a key point about ADT properties: they in turn suggest good test cases for implementations of ADTs. In fact, one could view such test cases as concrete instances of the properties we have already stated for ADTs. Such instances are called axioms. We can write these down explicitly in our ADT as follows:

-------------------------------------------

ADT Name: Set

ADT operations:

  addElt : Set element -> Set

  remElt : Set element -> Set

  size : Set -> integer

  hasElt : Set element -> boolean

ADT properties (vague):

  1. The set has no duplicates

  2. The items within the set are unordered

ADT axioms (concrete)

  if (not hasElt(S, n)) then size(addElt(S,n)) = size(S) + 1

  if hasElt(S, n) then size(addElt(S,n)) = size(S)

 

-------------------------------------------

Moral of all of this: when you implement an ADT, make sure that your implementations satisfy the properties. As you discover useful axioms that embody those properties, include them with your ADT definition. They will help you develop good tests later on. We will begin to check that your test cases for ADT implementations check the required properties and axioms.

3 A Java Interface for Sets

To tie this back to Java, let’s formally write tje Sets ADT as a Java interface:

  interface Iset {

    Iset addElt (int elt);

    Iset remElt (int elt);

    int size ();

    Boolean hasElt (int elt);

  }

What about the properties and axioms? The best Java can do here is include them in comments. Java interfaces do NOT fully support ADTs, precisely because Java lacks support for stating axioms outside of comments. The interface is still useful, but just weaker than ADTs.

4 Summary

Key take-aways from these notes: