9.4 Designing Complex Logic
Complex logic is often needed to control programs with numerous actions and states, especially when current state determines whether, which, or how actions are performed. User-interface systems, communication protocols, interactive systems, and embedded systems typically exhibit complex logic. As an example of a state-dependent action, consider a user-interface system with cut-and-paste commands. The paste command should only be possible after a cut operation has been performed; the state of the system reflects whether this has happened. The logic of such systems is complicated to program due to the state dependence of actions and the usually large number of states.
Complex logic is difficult to design. In realistically sized systems, the explosion of combined state and/or action pairs creates such a large space that attempts at easy solutions are usually defeated. In addition, the design difficulty is compounded if the system specification is stated in an informal manner (e.g., in natural language). It is difficult to analyze informal specification for crucial properties consistency, clarity, and completeness.
Accordingly, complex logic is tough to capture in an object-oriented style. It may not be clear how the if-then-else, or case-statement form, of the logic can be transformed into an object structure. Also, it may not be apparent how the other objects in the application relate to the states and actions of the system. If the actions are made methods of some objects, how does the object know the state of the system so that the object can decide on the proper way to deal with the action? On the other hand, turning the states into objects may not seem natural or in keeping with the object-oriented philosophy.
The processing of mouse events in a simple graphical editor will be used in this section as an example of how to design and implement complex logic in an object-oriented form. The key ideas developed by this example are how to present the processing logic in a graphical, semiformal representation, and transliterate this graphical representation into code. The real design work is accomplished in the first of these steps, for the transliteration step is straightforward. Two different transliterations are given; one is much more object-oriented than the other.
This section's example is small so that it can be presented completely. However, it should be clear that the same technique used here can be used for larger, more complex problems as well.
Representing Complex Logic
Given below is a natural-language statement describing how mouse
events should be handled in a simple graphical editor system.
Only two mouse events are used: depressing the left mouse button
and dragging (moving the mouse while the left mouse button remains
in the depressed state). The specification details how the user
creates and manipulates shapes. Clearly, this specification could
be complicated further by introducing more actions (e.g., grouping
shapes together, ungrouping shapes, rotating shapes, saving to
a file), and employing alternative user-interface mechanisms (e.g.,
using a pulldown menu in addition to the popup menu to select
the shape to be drawn). The technique for handling the simpler
case described below can also be applied to these more complicated
A state-transition diagram will be used to represent the specifications in a graphical, semiformal manner. The state-transition diagram is graphical because it is drawn using circles, arrowed lines, and textual annotations, and is semiformal because it lies between the informality of a natural-language expression, where no direct analyis can be done, and the full formality of a mathematical expression that can be subject to rigorous analysis. The state-transition diagram has a prescribed form (a syntax) and there are heuristic rules that can detect certain weaknesses in the specification.
As implied by its name, a state-transition diagram depicts states of the system, drawn as circles or ovals, and transitions between states, drawn as arrowed lines. Each state has a name suggestive of the system condition to which it corresponds. Possible states in the graphical editor system might be these:
Transitions are indicted by arrowed lines that connect states. The direction of the arrow shows which of the two states is the starting state and which is the ending state. The transition usually contains an annotation of a condition and a set of actions. A given transition may only be taken if the condition specified for that transition holds. The condition may use actual program variable names or operations that could clearly be computed from the information available in the starting state. The set of actions for a given transition is executed when the transition is taken.
The operation of a state transition diagram is captured in the following steps:
If none of the conditions for a state hold, then the system remains in the current state and no action is taken. In a properly formed diagram at most one of the conditions can be true at any one time. These steps are applied in a state until a transition is taken to another state, where the steps are applied again until another transition is taken, and so on. In a properly constructed state transition diagram, every execution of the real system corresponds to a sequence of transitions in the diagram and every sequence of transitions in the diagram corresponds to a legal execution of the real system.
The state-transition diagram denotes a single initial state; the initial state for the graphical editor system is the state in which it is awaiting a user action. The initial state has a single transition directed into it to denote that it is the initial state. The action on this transition expresses initializing operations that are performed when the system begins.
A part of the graphical editor system is illustrated in the following state-transition diagram. This diagram focuses on two states, the initial state Awaiting and the state Moving. The initial transition into the Awaiting state shown below specifies that the drawing area is cleared when the system begins. Two other transitions and their associated annotations are also shown. The first transition, from Awaiting to Moving, is taken when a left-click occurs within a shape. This shape is referred to in the condition part of the annotation by the name "s," which is also used in the action part of the condition where s is assigned to the program variable current. When the condition is true, the action is taken and the Moving state is entered. The second transition shows a case where the starting and ending state of the transitions are the same; a moving shape causes the system to remain in a state where that shape can be moved again. Notice that the annotation on a transition is written with a horizontal line separating the condition on the top from the action on the bottom.
The state-transition diagram easily reveals that the written specification is incomplete. An inspection of the state transition diagram shows that the only transition from the Moving state leads back to the Moving state. This means that once the Moving state is entered, the system stays in that state forever. Clearly this is an oversight. While it would be difficult to recognize this oversight in the written specification, the graphic form directly exposes this weakness. Lacking this insight, the question of how to terminate the moving of a shape might not otherwise arise until the coding phase at which point it is more expensive and more difficult to resolve the oversight.
The written specification is ammended and the resulting state-transition diagram, including the Resizing state, is shown below. The amendment includes the statement: "The dragging operation is terminated when the user releases the left-mouse button." This same issue arises for the Resizing state and a similiar statement is added to the specification: "The resizing operation is terminated when the user releases the left- mouse button."
However, examination of the transition actions for the corrected specifications for the Moving and Resizing states reveals that the wording and structure of the written specification are ambiguous. The specification states that "the user may select an existing shape to manipulate" and that a selected shape highlights its border. Ambiguity arises because the word may is open to several interpretations. In its stronger sense may could be interpreted as must, and in its weaker sense may could be interpreted as describing a permisible but not required act. A second source of ambiguity lies in the structure of the specification. That statement of how to "select" a shape for manipulation immediately precedes the description of the moving operation. Is the specification of selection to apply only to the moving operation? Or to the resizing operation that follows later as well? Furthermore, the term select is used in two places in the specification, once in reference to how to choose an item from the popup menu ("The user selects one of the shapes") and again in the context of identifying a shape for manipulation. Are these the same or different operations? Does the highlight apply to both cases in some way, or only to the latter case?
When ambiguities in the written specification are corrected, the state- transition diagram may be revised as shown below. The diagram indicates that the stronger sense of may is meant and that highlighting applies to both moving and resizing operations. The written specification will use different terms to describe choosing from a menu item and selecting a shape. Notice that the transitions into the Moving and Resizing states include as their actions the highlighting of the selected shape and that transitions out of these two states include the actions to unhighlight the selected shape.
The final step in the development of the state-transitions diagram deals with that part of the specifiction for drawing a new shape. Drawing a new shape is defined in two steps: (1) choosing a new shape from a menu, and (2) placing the new shape within the drawing area. These two steps are modelled by two states named Choosing and Placing. In defining the conditions and the actions related to these two states, the written specification is found to be incomplete in these two ways:
The written specification will be revised yet again to indicate that the user selects a menu item by a left click and that the menu should be automatically dismissed after the selections. With these changes in the specification, the Choosing and Placing states are added to the state-transition diagram as depicted below. The annotations for the previous transitions are not repeated again in this figure.
The written specification, incorporating all changes thus far, is repeated below with the changes in bold. Clearly, the original specification was incomlete and ambiguous in several important areas. The development of the state-transition diagram served as a useful device to discover these problems and to represent the specification in more precise way. In addition, the state-transition diagram, as a graphical representation, more clearly shows the structure of the system's behavior: the major conditions in which the system exists are modeled as states and the actions that drive the system among its states are modeled as transitions.
Implementing the Design
A state-transition diagram can be transformed into an object-oriented structure by designating a class to each state . The implementation of the class representing a given state is derived from the annotations of all transitions that exit from that state in the state-transition diagram. The implementation includes code for:
A state is represented by a class because each state has a distinct set of transitions with distinct conditions to evaluate and distinct actions to take. Note that the use of classes to represent states is counter intuitive. Usually, it is expected that there will be multiple objects of a given class in use at one time. However, in this case, only one object of a class will exist at any one time.
Each class must have access to those parts of the system that it needs to test its conditions and perform its actions. For example, in the graphical editor system, the conditions and actions make reference to the system components current, shape, and mouse coordinates. Testing the condition "outside of any shape" implies that the class has access to a list of all of the current shapes and a means of determining whether the mouse coordinates lie outside of a shape. Finally, the action "draw shape at mouse coordinates" implies that the class has access to the drawing area. Of course, the specific components that are accessed by the states are system dependent. Thus, the structure of this system data can only be defined in the most general terms. The SystemData class shown below introduces a name to refer to this collection of system-dependent information.
All classes that represent states have the same interface - which is captured in an abstract base class. The figure below shows this shared interface. Each class has a single method, Next, which has as its parameter the collection of system data needed by any state to properly interrogate the system's condition and modify the system as required by the state's actions. Because the Next method may modify the system's condition, the SystemData is passed by reference. The value returned by the Next method is a State object representing the new state of the system.
An example of a class for a specific state is coded below. Here, the Moving state is defined as a derived subclass of the abstract-base class State. This derived class implements the Next() method as required by the base class. The Moving class also provides a codeless constructor as the Moving state maintains no state dependent information. Classes for other states may have state-dependent information and may in addition provide methods other than the Next method.
The implementation of the Moving class's Next method is the critical part of this class. This method tests the SystemData to determine whether a relevant event has occurred. As shown in the state-transition diagrams, the two relevant events in the Moving state are a drag event that leaves the system in the Moving state and a left-mouse-button-up event that returns the system to the Awaiting state. The Next method achieves this change of states by returning a state object for the correct state of the system. If the system remains in the Moving state, the Next method simply returns the current object (itself an object representing the Moving state). If the system should return to the Awaiting state, then a new object representing that state is constructed and returned.
Read the description below of the control logic for the Circle-Placement System and answer the questions that follow.