Lecture: Data Definitions: Unions

5.3.5

Lecture: Data Definitions: Unions

Design of classes that represent a disjoint union of sets of data.
Extending unions to represent self-referential data.

Unions.java AncestorsData.java

Lecture outline

Representing unions of data sets
Making examples of unions of data
Self-referential unions
Information and data - understanding the connection

Unions: Traveling on the T in Boston

We wish to represent train stations for the subway and for the commuter lines. Each station has a name and the name of the line that serves it. A subway stations also has a price it costs to get on the train. For commuter trains the price depends also on the place of exit, and so we do not need that information. However, a station on the commuter line may be skipped by the express trains we need to know whether this is the case.

Examples: Harvard station on the Red line costs $1.25 to enter Kenmore station on the Green line costs $1.25 to enter Riverside station on the Green line costs $2.50 to enter

Back Bay station on the Framingham line is an express stop West Newton stop on the Framingham line is not an express stop Wellesely Hills on the Worcester line is not an express stop

So, in DrRacket the data definition would be:

;; IStation is one of

;; -- T Stop

;; -- Commuter Station

;; T Stop is (make-tstop String String Number)

(define-struct tstop (name line price))

;; Commuter Station is (make-commstation String String Boolean)

(define-struct commstation (name line express))

(define harvard (make-tstop "Harvard" "red" 1.25))

(define kenmore (make-tstop "Kenmore" "green" 1.25))

(define riverside (make-tstop "Riverside" "green" 2.50))

(define backbay (make-commstation "Back Bay" "Framingham" true))

(define wnewton (make-commstation "West Newton" "Framingham" false))

(define wellhills (make-commstation "Wellesley Hills" "Worcester" false))

This can information and data organization can also be represented by the following calss diagram:

+----------+

| IStation |

+----------+

/ \

---

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

| |

+--------------+ +-----------------+

| TStop | | CommStation |

+--------------+ +-----------------+

| String name | | String name |

| String line | | String line |

| double price | | boolean express |

+--------------+ +-----------------+

In Java, we give a common name to the data type that represents both kinds of station by defining an interface, and each class that represents a sub-type of the type defined by the interface specifies that it impplements this interface:

The data definitions then become:

// to represent a train station

interface IStation {

}

// to represent a subway station

class TStop implements IStation {

String name;

String line;

double price;

TStop(String name, String line, double price) {

this.name = name;

this.line = line;

this.price = price;

}

// to represent a stop on a commuter line

class CommStation implements IStation {

String name;

String line;

boolean express;

CommStation(String name, String line, boolean express) {

this.name = name;

this.line = line;

this.express = express;

}

Defining Examples of Data

As before, we define examples of data in a corresponding class ExamplesIStation:

class ExamplesIStation{

ExamplesIStation() {}

Harvard station on the Red line costs $1.25 to enter

Kenmore station on the Green line costs $1.25 to enter

Riverside station on the Green line costs $2.50 to enter

Back Bay station on the Framingham line is an express stop

West Newton stop on the Framingham line is not an express stop

Wellesely Hills on the Worcester line is not an express stop

IStation harvard = new TStop("Harvard", "red", 1.25);

IStation kenmore = new TStop("Kenmore", "green", 1.25);

IStation riverside = new TStop("Riverside", "green", 2.50);

IStation backbay = new CommStation("Back Bay", "Framingham", true);

IStation wnewton = new CommStation("West Newton", "Framingham", false);

IStation wellhills = new CommStation("Wellesley Hills", "Worcester", false);

}

The tester will display the data as follows:

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

Tests for the class: ExamplesIStation

Tester Prima v.1.5.2.1

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

Tests defined in the class: ExamplesIStation:

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

ExamplesIStation:

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

new ExamplesIStation:1(

this.harvard =

new TStop:2(

this.name = "Harvard"

this.line = "red"

this.price = 1.25)

this.kenmore =

new TStop:3(

this.name = "Kenmore"

this.line = "green"

this.price = 1.25)

this.riverside =

new TStop:4(

this.name = "Riverside"

this.line = "green"

this.price = 2.5)

this.backbay =

new CommStation:5(

this.name = "Back Bay"

this.line = "Framingham"

this.express = true)

this.wnewton =

new CommStation:6(

this.name = "West Newton"

this.line = "Framingham"

this.express = false)

this.wellhills =

new CommStation:7(

this.name = "Wellesley Hills"

this.line = "Worcester"

this.express = false))

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

No test methods found.

As an exercise, think of what would need to be done, if we decided that we also want to represents all stops on all bus lines, including the express bus lines.

Self-referential unions: Ancestor trees

We wanted to represent an ancestor tree for a person, naming the ancestors as far as we can remember, and using ’unknown’ for those nobody can remember or trace.

Here is the data definition in DrRacket:

;; An Ancestor tree (AT) is on of

;; -- 'unknown

;; -- Person

;; A Person is (make-person String AT AT)

(define-struct person (name mom dad))

and here are a few examples:

(define mary (make-person "Mary" 'unknown 'unknown))

(define robert (make-person "Robert" 'unknown 'unknown))

(define john (make-person "John" 'unknown 'unknown))

(define jane (make-person "Jane" mary robert))

(define dan (make-person "Dan" jane john))

Two important skills you need to practice early are:

design a representation of the given information as data
interpret the given data as the information it represents

So, here, to understand what the data shown above represents, we may want to draw the ancestor tree, so we can tell easily how the differnt people are related. The given data represents the following ancestor tree:

Dan

/ \

Jane John

/ \ / \

Mary Robert ? ?

/ \ / \

? ? ? ?

We used the ? for the unknown names. The class diagram that represents this data definition looks like this:

+------------------+

| +-------------+ |

| | | |

v v | |

+-----+ | |

| IAT | | |

+-----+ | |

/ \ | |

--- | |

| | |

----------------- | |

| | | |

+---------+ +-------------+ | |

+---------+ +-------------+ | |

+---------+ | String name | | |

| IAT mom |-+ |

| IAT dad |---+

+-------------+

We replaced AT with IAT as in Java the union type will be represented as an interface, and our convention tells us to start the names of interface types with the letter I.

The code below shows how this class diagram and our examples can be translated into a represetation as Java classes and interfaces (Java class hierarchy):

// to represent an ancestor tree

interface IAT{ }

// to represent an unknown member of an ancestor tree

class Unknown implements IAT{

Unknown() {}

}

// to represent a person with the person's ancestor tree

class Person implements IAT{

String name;

IAT mom;

IAT dad;

Person(String name, IAT mom, IAT dad){

this.name = name;

this.mom = mom;this.dad = dad;

}

Notice that we have defined a class Unknown, even though it does not contain any additional information (has no fields). In Java, the class definitions also include the definitions of the behavior of the instances of the class, (we will start learning this very soon), and the behavior of the object that represent unknown people will be different from the behavior of the people whose names we know.

Examples of Ancestor Trees

As before, we define examples of the data in the class named ExamplesAncestors:

// examples and tests for the class hierarchy that represents

// ancestor trees

class ExamplesAncestors{

ExamplesAncestors(){}

IAT unknown = new Unknown();

IAT mary = new Person("Mary", this.unknown, this.unknown);

IAT robert = new Person("Robert", this.unknown, this.unknown);

IAT john = new Person("John", this.unknown, this.unknown);

IAT jane = new Person("Jane", this.mary, this.robert);

IAT dan = new Person("Dan", this.jane, this.john);

}

At the time the program is checked for corectness by the compiler, the compiler knows that mary is of the type IAT (also known as its compile-time type; when the program runs, it will also know that after the data definition has been made, the run-time type of mary is Person.

We can see this when the tester displays our data:

ExamplesAncestors:

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

new ExamplesAncestors:1(

this.unknown =

new Unknown:2()

this.mary =

new Person:3(

this.name = "Mary"

this.mom = Unknown:2

this.dad = Unknown:2)

this.robert =

new Person:4(

this.name = "Robert"

this.mom = Unknown:2

this.dad = Unknown:2)

this.john =

new Person:5(

this.name = "John"

this.mom = Unknown:2

this.dad = Unknown:2)

this.jane =

new Person:6(

this.name = "Jane"

this.mom = Person:3

this.dad = Person:4)

this.dan =

new Person:7(

this.name = "Dan"

this.mom = Person:6

this.dad = Person:5))

When designing a program, we must make sure that the compile-time types af all data items (variables and arguments) correspond to what the compiler can expect. (More about this later.)