Skip to the content of the web site.

Design Patterns

The reference for this topic is Design Patterns by Gamma, Helm, Johnson, and Vlissides, published by Addison-Wesley in 1995. I am only taking the most elementary examples from this text.

This topic will give an introduction to design patterns. This is not required reading for ECE 250.

Two common and simple-to-understand design patterns we will look at include:

In software engineering, as in any other profession, a programmer will come across similar problems time and time again. There may be slight variations, however, there are only so many ways you can build a skyscraper. There are also only so many ways in which you can write a program. Because software engineering is younger than civil engineering, the recognition of the similarity of these problems has been more recent.

Over the years of programming, as these problems have been faced, various programmers have come across good solutions, while others have chosen, out of haste or inexperience, poor designs. We will look at a number of the patterns which have been recognized in software engineering and give what are generally recognized to be a good, if not best, solutions to these problems.

Singletons

Suppose you require only one instance of a class and any further attempts to create an instance should be avoided. The most obvious solution is to keep a static counter in the constructor which, if set to 1, returns an exception.

This solution is hardly acceptable, however. First, because the constructor may be called, it is almost certain that if there is an instance of this class, it must be stored assigned to some global name. Also, wrapping each call to a constructor inside a try-catch would be frustrating at best.

Instead, consider the following simple idea:

  • Write the class with a private constructor — this cannot be called from outside the class.
  • Keep a static class variable which stores a pointer to the class.
  • Have a public accessor which returns a pointer to the one instance of the class, and if it that instance does not yet exists, call the private constructor.

For example, the following would define such a class:

class Singleton {
	private:
		static Singleton * instance;
		Singleton();

	public:
		static Singleton * get_instance();
};

// static variables must be defined outside the class declaration
Singleton * Singleton::instance = 0;

Singleton * Singleton::get_instance() {
	if ( instance == 0 ) {
		instance = new Singleton;
	}

	return instance;
}

The UML Class Diagram for this would be:

Singleton - instance:Singleton - create():Singleton
+ get_singleton():Singleton

Reference: Gamma, p.129.

Iterators (Enumerations)

The next problem is, given a collection, suppose you want to step through all of the elements in the collection without either:

  • Allocating additional memory to store all the objects, or
  • Having access to the internal data structures.

You cannot allow the user of a class to have access to the internal data structure. This would violate encapsulation and it would make it impossible to modify the structure in the future. Alternatively, passing back an array containing all of the entries in the structure would duplicate memory, and at the time that an object is accessed from the array, it might not even be in the collection any more (i.e., it may have been removed). Finally, the actual data may be significantly larger than physical memory, e.g., it could be a data base stored on a number of hard drives.

One possible solution may be to number the objects in the container 0 through size() - 1. You could then write a function template <typename Object> Object getN( int ). In some cases, this may be an excellent solution, however, in others, it may have serious draw backs:

  • There may be no natural ordering,
  • It may be expensive to find the nth item,
  • It may not allow us to take advantage of some of the implementation features of the storage, and
  • The position of an object in a list may change based on whether new objects are being added or deleted.

For example, there is no natural ordering of all of the files on a hard drive in a file system which does not change significantly with additions or deletions of directories. Also, finding the 10001st file does not make it any easier to find the 10002nd file. Depending on how the files are stored, this could almost be a linear search.

Consider Wowbagger The Infinitely Prolonged: His goal was to insult the Universe. That is, he would insult everybody in it. Individually, personally, one by one, and (this was the thing he really decided to grit his teeth over) in Alphabetical Order (from Douglas Adams, Hitch Hiker's Guide to the Galaxy.)

To consider a solution, think of accessing rare books at a library: you often do not have access to the books themselves, but rather, you must go through an intermediary - usually a librarian. Suppose you wanted to go through every book in the rare collection. You could ask the librarian for the first book, then the next, and then the next. At some point, you will ask for the next book and the librarian will say that there are no more books left.

This model has a number of advantages:

  • You are not aware of how the books are stored: that is the librarian's problem.
  • You are not tracking which books you've seen and which ones you have not seen.
  • Your job is simple, you simply keep asking for books until you are told there are no more.

  • The librarian can make use of the most efficient manner of tracking which books you have seen.

To translate this idea into a classes, consider the following UML Class Diagram for an iterator interface:

Iterator
<<Interface>>
+ current():Object
+ next():Object
+ is_done():Boolean

The C++ implementation of this class would be:

template 
class Iterator {
	protected:
		Iterator();

	public:
		virtual T next() = 0;
		virtual bool has_next() = 0;
};

The Java interface for this is

interface Iterator {
	blic boolean hasNext();
	E next();
	void remove();
}

The C++ Standard Template Library version of iterators focuses more on operator overloading:

ContainerType Box;   // Box is some container, e.g., vector

for ( ContainerType::const_iterator iter = Box.begin(); iter != Box.end(); ++iter ) {
    cout << *iter << endl;
}

Here:

  • ++iter increments the iterator,
  • *iter accesses the current value, and
  • Box.begin() and Box.end() reference the first and one-beyond-the-last tokens.

Examples to follow...