Introduction to Object Oriented Programming, 3rd Ed

Timothy A. Budd

Chapter 19 Container Classes

Outline

Other Material

A printer friendly version of all slides

Intro OOP, Chapter 19, Outline

Roadmap

In this chapter we will examine how object-oriented programming techniques can be applied to the problem of creating container, or collection classes.

Containers in Dynamically Typed Languages
The Tension between Reuse and Strong Typing
Object Oriented Solutions
- Substitution and Downcasting
- Substitution and Overriding
- Templates
Collection Traversals
- Iterators
- Visitors

Intro OOP, Chapter 19, Slide 01

Containers in Dynamically Typed Languages

Collection classes are simple to write in dynamically typed languages, Since all variables are polymorphic.

Contains simply hold values in variables (which can hold anything), and when they are removed from the container they can be assigned to any variable.

Dynamically typed languages have historically come with a rich set of container classes in their standard library.

Intro OOP, Chapter 19, Slide 02

Tension between Strong Typing and Reuse

The situation is very different when we move to statically typed languages. There, the strong typing can get in the way of software reuse.

type
	Link = Record
		value : integer
		nextelement : ^ Link
	end;

What happens when we need a linked list of doubles? or of a user defined type?

The strong typing is getting in the way of software reuse.

Intro OOP, Chapter 19, Slide 03

Can OO Techniques Solve This

Can we bring any of the OO techniques (subsitution, polymorphism) into the solution of this problem? We examine three techniques:

Using Substitution and Downcasting
Using Substitution and Overriding
Using Templates (or Generics)

Intro OOP, Chapter 19, Slide 04

Using Substitution and Downcasting

In Java and other languages, (almost) all values can be stored in a variable of type Object.

Therefore, we write containers that store Object values.

Problem. Requires a cast when a value is removed from the container.

Vector aVector = new Vector();
Cat Felice = new Cat();
aVector.addElement(Felice);
	...
	// cast used to convert Object value to Cat
Cat animal = (Cat) aVector.elementAt(0);

Worse problem, typing errors are detected when a value is removed from the collection, not when it is inserted.

Intro OOP, Chapter 19, Slide 05

Heterogeneous Collections

Because any value can be stored in an Object, this allows heterogeneous collections; although the actual type must be checked when a value is removed:

Stack stk = new Stack();
stk.addElement(new Cat());
stk.addElement(new Dog()); 
	// ... adding more values
	// now do something with Cat values
if (stk.peek() instanceof Cat) {
		// do conversion to Cat
	Cat aCat = (Cat) stk.pop(); 
	// .. also do something with cat values
	// now do something with Dog values
} else if (stk.peek() instanceof Dog) {
		// do conversion to Dog
	Dog aDog = (Dog) stk.pop(); 
	// .. do something with Dog value
}

Intro OOP, Chapter 19, Slide 06

Using Classes as Objects to do Type Checking

In languages in which classes are objects, and have the ability to tell if an object is an instance, the container can hold the class object that represents its type:

var
	stack : TStack;
	aCat : TCat;
	aDog : TDog;

begin
		// create a stack that can hold only TCat values
	stack := TStack.Create (TCat);
	stack.push (aCat); // ok
	stack.push (aDog); // will raise exception
	...
end

Allows typing errors to be caught on insertion, but uses more space and time.

Intro OOP, Chapter 19, Slide 07

Storing Primitive Values

In some languages (Java, Delphi) primitive types are not objects.

These values cannot be stored using this scheme.

Thus, languages introduce wrapper classes that do nothing but hold a primitive value.

Vector aVector = new Vector();
aVector.add(new Integer(17)); // wrap up primitive int as Integer
...
Integer a = aVector.elementAt(1);
int x = a.intValue(); // must subsequently be unwrapped

Intro OOP, Chapter 19, Slide 08

Using Substitution and Overriding

In certain situations we can eliminate the downcast, replacing it with overriding.

This only works, however, if you can predict ahead of time what operations you want to do on a collection.

Intro OOP, Chapter 19, Slide 09

An Example, Java Window Events

A good example is the way that window events are handled in Java. Each window maintains a list of listeners, each listener must implement a fixed interface (WindowListener).

public class CloseQuit extends WindowAdapter {
		// execute when the user clicks in the close box
	public void windowClosing (WindowEvent e) {
		System.exit(0); // halt the program
	}
}

When an event occurs the window simply runs down the list of listener, invoking the appropriate method in each. No downcasting required.

Intro OOP, Chapter 19, Slide 10

A Third Alternative, Generics

Generics, as we described in the last chapter, are a third approach.

template <class T> class List {
public:
	void	addElement (T newValue);
	T	firstElement ();

private:
	Link * firstLink;

	private class Link { // nested class
	public:
		T	value;
		Link *	nextLink;

		Link (T v, Link * n) : value(v), nextLink(n) { }
	};
};

Allow for both strong typing and reuse.

Intro OOP, Chapter 19, Slide 11

Collection Traversal

Here is another difficult problem. How to you allow access to elements of a collection without exposing the internal structure?

Consider the conventional solution:

var
	aList : List;	(* the list being manipulated *)
	p : Link;	(* a pointer for the loop *)

begin
	...
	p := aList.firstLink;
	while (p <> nil) do begin
		writeln (p.value);
		p := p^.nextElement;
	end;

Needed to expose the link type, and the field nextElement.
Can we avoid this problem?

Intro OOP, Chapter 19, Slide 12

Two Solutions

There are two common solutions:

Create an iterator; an object that facilitates access to elements and enumeration over the collection.
The vistor. Bundle the action to be performed as an object, and pass it to the collection.

Intro OOP, Chapter 19, Slide 13

Iterator

An iterator is an object that has two major responsibilities:

Provide access to the current element
Provide a way to move to the next element

Different languages use different interfaces, but the basic idea is the same.

Intro OOP, Chapter 19, Slide 14

An Enumeration Loop in Java

		// create the iterator object
	Enumeration e = aList.elements();
		// then do the loop
	while (e.hasMoreElements()) {
		Object obj = e.nextElement();
		// ... do something with obj
	}

Interface consists of two methods, hasMoreElements and nextElement.

Intro OOP, Chapter 19, Slide 15

An Iterator Loop in C++

		// create starting and stopping iterators
	list::iterator start = aList.begin();
	list::iterator stop  = aList.end();
		// then do the loop
	for ( ; start != stop; start++ ) {
		string value = *start; // get the value
		// ... do something with the value
	}

Interface consists of three operations; comparison, increment, and dereference.

Intro OOP, Chapter 19, Slide 16

Iterators and Encapsulation

Note that the iterator must almost always have detailed knowledge of the internal data structure. Wasn't our goal to hide these details?

Not exactly. The iterator is usually developed by the same programmer creating the data structure. It can share detailed knowledge with the data structure. And using the iterator does not require any knowledge of how the iterator is implemented.

Often friends (in C++) or nested classes (in Java) can be used to help the iterator share information with the container.

Intro OOP, Chapter 19, Slide 17

Alternative, the Visitor

An alternative to iterators is the idea of a visitor. Requires the ability to bundle the action to be performed into an object, and hand it to the collection.

This is most common technique used in Smalltalk

aList do: [:x | ('element is' + x) print ].

The block is passed as argument to the list, which turns around and executes the block on each element.

Intro OOP, Chapter 19, Slide 18

The Visitor in C++ in the STL

class printingObject {
public:
	void operator () (int x) 
	{
		cout << "value is " << x << endl;
	}
};

printingObject printer;  // create an instance of the function object

for_each (aList.begin(), aList.end(), printer);

The function for_each passes the object to element element in the collection.

Intro OOP, Chapter 19, Slide 19

Chapter Summary

Collection Classes are easy to write in dynamically typed languages
In statically typed languages, there is a conflict between reuse and strong typing
Three approaches to overcoming this include
- Using substitution and downcasting
- Using substitution and overriding
- Using generics
A related problem, looping over elements
- The iterator solution
- The visitor solution