848 Patterns and UML
Self-Test Exercises
The Divide-and-Conquer Sorting pattern must divide the interval being sorted into two smaller
intervals. If there were cases in which the
split function divided the interval into an empty
interval and the rest, then one subinterval would be the same as the original interval being
divided, and infinite recursion would result. In the quick-sort realization we avoided this infinite
recursion with the following lines from the definition of
split:
if (up > 0)
return (begin + up);
else
return (begin + 1); //Ensures that both pieces are nonempty.
Without this extra adjustment, the function split could compute 0 as the value of up and so
divide the interval into two intervals with one of the two being empty. That would produce infi-
nite recursion. The way this is usually avoided with a quick-sort realization (and the way that pro-
duces the nicest code) is to separate out the split point and divide only the remaining element, so
that the array interval is divided into three pieces: the split point, the subinterval before the split
point, and the subinterval after the split point. This guarantees that even if one subinterval is
empty, the other is shorter than the interval being divided. Thus, infinite recursion is avoided.
When these points are taken into consideration, you are likely to change the Sorting pattern to the
following when you are designing the quick-sort realization:
if ((end - begin) > 1)
{
int splitPt = split(a, begin, end);
sort(a, begin, splitPt - 1);
sort(a, splitPt + 1, end);
}//else sorting one (or fewer) elements, so do nothing.
Patterns are there to help you, not to provide an obstacle. Feel free to adjust them if need be.
■
PATTERN FORMALISM

be wanting. Terms such as flowchart, structure diagram, and many other names of
graphical program representations are today only recognized by those of the older gen-
eration. Today’s candidate for a graphical representation formalism is the Unified
Modeling Language (UML). The UML was designed to reflect and be used with the
object-oriented programming philosophy. It is too early to say whether or not the
UML will stand the test of time, but it is off to a good start. A number of companies
have adopted the UML formalism for use in their software design projects.
■
HISTORY OF UML
UML developed along with object-oriented programming. As the OOP philosophy
became more and more commonly used, different groups developed their own graphi-
cal or other representations for OOP design. In 1996 Grady Booch, Ivar Jacobson, and
James Rumbaugh released an early version of UML. The UML was intended to bring
together the various different graphical representation methods to produce a standard-
ized graphical representation language for object-oriented design and documentation.
Since that time the UML has been developed and revised in response to feedback from
the OOP community. Today the UML standard is maintained and certified by the
Object Management Group (OMG), a nonprofit organization that promotes the use of
object-oriented techniques.
20.2
Unified
Modeling
Language
(UML)
20_CH20.fm Page 849 Monday, August 18, 2003 2:08 PM
850 Patterns and UML
■
UML CLASS DIAGRAMS
Classes are central to OOP, and the class diagram is the easiest of the UML graphical
representations to understand and use. Display 20.6 shows the class diagram for a class

+resize(double newSide): void
+move(Pair<double, double> point): void
#erase( ): void

-side: double
-topRtCorner: Pair<double, double>
Square
20_CH20.fm Page 850 Monday, August 18, 2003 2:08 PM
Answers to Self-Test Exercises 851
Self-Test Exercises
can add it to the UML. Of course, this all takes place inside a prescribed framework so
that different software developers can understand each other’s UML.
This is just a hint of what the UML is all about. If you are interested in learning
more, consult the references listed at the end of this book.
4. Draw a class diagram for a class whose objects represent circles. Use Display 20.6 as a
model.
5. Draw a class diagram for the
IntNode class presented in Display 17.4.
■ Patterns are design principles that apply across a variety of software applications.
■ The patterns discussed in this chapter are the Container-Iterator, Adapter, Model-
View-Controller, and Divide-and-Conquer Sorting patterns.
■ A pattern can give you a framework for comparing related algorithms for efficiency.
■ The Unified Modeling Language (UML) is a graphical representation language for
object-oriented software design.
■ UML is one formalism that can and is used to express patterns.
ANSWERS TO SELF-TEST EXERCISES
1. Yes, a template function definition is a pattern, but the term pattern is much more general and
encompasses more. Moreover, a useful pattern expressed as a template function would leave
some details unimplemented. If the only variation possible is a type parameter, it is still a pat-
tern but not likely to be usefully viewed as a pattern. (It can still be useful as a template func-

return (begin + 1);
}
template <class T>
void join(T a[], int begin, int splitPt, int end)
{
//Nothing to do.
}
3. An array of random values would have the fastest running time, since it would divide the
array segments into approximately equal subarrays most of the time. The other two cases
would give approximately the same running time, which would be the worst-case O(N
2
)
running time because the algorithm would always divide an array segment into very
unequal pieces, one piece with only one element and one piece with the rest of the ele-
ments. It is ironic but true that our version of the quick-sort algorithm has its worst behav-
ior on an already sorted array. There are variations on the quick-sort algorithm that
perform well on a sorted array. For example, choosing the middle element as the splitting
value will give good performance on an already sorted array. But whatever splitting value
you choose, there will always be a few cases with this worst-case running time.
4. There is no unique answer, but below is one suitable answer:
+resize(double newRadius): void
+move(Pair<double, double> point): void
#erase( ): void

-radius: double
-center: Pair<double, double>
Circle
20_CH20.fm Page 852 Monday, August 18, 2003 2:08 PM
Programming Projects 853
5.

close, and an alarm button. You will have to decide what outputs are needed from the sim-
ulator so that a user can see and understand what is happening in the simulation.
+constructors
+getLink( ): IntNode*
+getData( ): int
+setData(int theData): void
+setLink(IntNode* pointer); void
-data: int
-link: IntNode*
IntNode
20_CH20.fm Page 853 Monday, August 18, 2003 2:08 PM
854 Patterns and UML
Identify the main objects in this situation. Identify the behavior of each object. Decide how
the several objects interact. Then identify the classes and the member functions. Then iden-
tify the state that the class(es) must remember to be able to control the elevator.
We suggest a clock-driven simulation where everything happens on a clock tick (of say one
second, but your program will not have any timing. A click will just be one execution of a
loop.) You call a random-number generator to decide how many people arrive on each
floor at each tick.
Design and code a simulation of the building’s elevator.
This is not a hard exercise, but it requires clear thinking. It also requires that you supply
some of the details we have left out such as the bell ringing on arrival at a floor, and the
door opening, just to mention two things.
5. (Harder version of 4.) Generalize Programming Project 4 to simulate an elevator system
where the number of elevators is greater than one and the number of floors is greater than
two. In this version each floor will have two call buttons: one to call the elevator to go up
and one to call the elevator to go down. For definiteness, use 2 elevators and 10 floors, but
the principles will be the same regardless of the number. You have to decide on which of
the elevators is called when the call button is pressed under several situations. For example
suppose the elevator is called while one elevator is moving toward the caller’s floor while