A Case Study: Designing a Document Editor

Overview

This topic presents a case study in the design of a "What-You-See-Is-What-You-Get" (WYSIWYG) document editor called Lexi, whose design is based on Doc, a text-editing application developed by Calder. It is the book's worked demonstration of how design patterns capture solutions to recurring design problems, and it walks through eight patterns by example.

Lexi's user interface places a WYSIWYG representation of the document in a large rectangular area in the center; the document mixes text and graphics freely in a variety of formatting styles. Surrounding the document are the usual pull-down menus and scroll bars, plus a collection of page icons for jumping to a particular page.

The study examines seven problems in Lexi's design, and each problem culminates in the introduction of one or more patterns that solve it: document structure (Composite), formatting (Strategy), embellishing the user interface (Decorator), supporting multiple look-and-feel standards (Abstract Factory), supporting multiple window systems (Bridge), user operations (Command), and spelling checking and hyphenation (Iterator and Visitor). A recurring theme unifies them: encapsulate the concept that varies.

Key takeaways

Mental model

Copy sourceZoom

Design problems

The study examines seven problems in Lexi's design. The choice of internal representation for the document affects nearly every aspect of the design — all editing, formatting, displaying, and textual analysis require traversing the representation.

1. Document structure. The way the document's information is organized impacts the design of the rest of the application.
2. Formatting. How does Lexi arrange text and graphics into lines and columns? What objects carry out different formatting policies, and how do they interact with the document's internal representation?
3. Embellishing the user interface. Scroll bars, borders, and drop shadows embellish the WYSIWYG interface. These embellishments are likely to change as the interface evolves, so it must be easy to add and remove them without affecting the rest of the application.
4. Supporting multiple look-and-feel standards. Lexi should adapt easily to standards such as Motif and Presentation Manager (PM) without major modification.
5. Supporting multiple window systems. Different look-and-feel standards are usually implemented on different window systems; the design should be as independent of the window system as possible.
6. User operations. Functionality behind buttons and pull-down menus is scattered throughout the application's objects. The challenge is a uniform mechanism for both accessing this scattered functionality and undoing its effects.
7. Spelling checking and hyphenation. How does Lexi support analytical operations, and how can it minimize the number of classes that must be modified to add a new analytical operation?

Each problem has an associated set of goals plus constraints on how to achieve them. The discussion for each culminates in a brief introduction to the relevant patterns.

Document structure — Composite

A document is ultimately just an arrangement of basic graphical elements such as characters, lines, polygons, and other shapes, which capture the total information content of the document. Yet an author often views these elements in terms of the document's physical structure — lines, columns, figures, tables, and other substructures. These substructures have substructures of their own, and so on.

The internal representation should support: maintaining the document's physical structure (the arrangement of text and graphics into lines, columns, tables, etc.); generating and presenting the document visually; and mapping positions on the display to elements in the internal representation, so Lexi can determine what the user is pointing to.

Constraints

Two constraints shape the design. First, text and graphics should be treated uniformly — the interface lets the user embed text within graphics and vice versa, so treating graphics as a special case of text (or the reverse) would yield redundant formatting and manipulation mechanisms. Second, the implementation shouldn't have to distinguish between single elements and groups of elements: the tenth element in line five of column two could be a single character or an intricate diagram with many subelements, and as long as an element can draw itself and specify its dimensions, its complexity has no bearing on how and where it appears. Opposing the second constraint is the need to analyze text — it makes little sense to check the spelling of a polygon or to hyphenate it — so the representation must accommodate potentially conflicting constraints.

Recursive composition

A common way to represent hierarchically structured information is recursive composition, building increasingly complex elements out of simpler ones. A set of characters and graphics is tiled left to right to form a line; multiple lines form a column; multiple columns form a page, and so on. Each important element gets its own object — not just visible elements like characters and graphics, but the invisible structural elements (lines, columns) as well. The object structure mimics the document's physical structure.

This approach has two implications: the objects need corresponding classes, and those classes must have compatible interfaces, because the objects are treated uniformly. In a language like C++, the way to make interfaces compatible is to relate the classes through inheritance.

Glyphs

A Glyph abstract class is defined for all objects that can appear in a document structure. Its subclasses define both primitive graphical elements (like characters and images) and structural elements (like rows and columns). Glyphs have three basic responsibilities — they know (1) how to draw themselves, (2) what space they occupy, and (3) their children and parent:

• Draw(Window*) — Glyph subclasses redefine Draw to render themselves onto a window, passed a reference to a Window object that defines graphics operations for rendering text and basic shapes. A Rectangle subclass redefines Draw to call DrawRect on the window, using its corner data members.
• Bounds() — returns the rectangular area the glyph occupies (the opposite corners of the smallest rectangle that contains it). A parent glyph needs this to arrange children in a line without overlap.
• Intersects(Point) — returns whether a specified point intersects the glyph. When the user clicks in the document, Lexi calls this to determine which glyph is under the mouse.
• Insert(Glyph*, int) / Remove(Glyph*) — a common interface to add and remove children. Insert adds a glyph at a position specified by an integer index; Remove removes a specified child.
• Child(int) / Parent() — Child returns the child at a given index; glyphs that can have children should use Child internally rather than accessing the child data structure directly, so that operations like Draw need not change when the structure changes from an array to a linked list. Parent returns the glyph's stored parent reference.

The pattern

Recursive composition is good for more than documents: it can represent any potentially complex, hierarchical structure. The Composite pattern captures the essence of recursive composition in object-oriented terms.

Formatting — Strategy

Representation and formatting are distinct: the ability to capture the document's physical structure doesn't tell us how to arrive at a particular structure. That responsibility rests mostly on Lexi, which must break text into lines, lines into columns, and so on, taking into account higher-level desires such as margin widths, indentation, tabulation, and line spacing. (Here "formatting" is restricted to mean breaking a collection of glyphs into lines — "formatting" and "linebreaking" are used interchangeably — but the techniques apply equally to breaking lines into columns and columns into pages.)

Encapsulating the formatting algorithm

Formatting isn't easy to automate, and many algorithms exist with different strengths. Because Lexi is a WYSIWYG editor, an important trade-off is the balance between formatting quality and formatting speed; another balances formatting speed against storage (caching more information can reduce formatting time). These trade-offs are subject to factors not all knowable at compile time.

Formatting algorithms should be kept well-contained, or better yet completely independent of the document structure: it should be possible to add a new Glyph subclass without regard to the formatting algorithm, and to add a new formatting algorithm without modifying existing glyphs. The design should make it easy to change the algorithm at compile time, if not at run time. The solution is to isolate the algorithm and make it replaceable by encapsulating it in an object — a separate class hierarchy whose root defines an interface supporting a range of formatting algorithms, with each subclass implementing a particular one.

Compositor and Composition

A Compositor class encapsulates a formatting algorithm; its interface lets a compositor know what glyphs to format and when. The glyphs it formats are the children of a special Glyph subclass called Composition. A composition receives an instance of a Compositor subclass when created, and tells the compositor to Compose its glyphs when necessary (for example, when the user changes the document).

An unformatted Composition contains only the visible glyphs of the document's basic content — not structural glyphs like Row and Column. When it needs formatting, it calls its compositor's Compose operation; the compositor iterates through the composition's children and inserts new Row and Column glyphs according to its linebreaking algorithm. Each Compositor subclass implements a different algorithm: a SimpleCompositor does a quick pass without regard to the document's "color" (an even distribution of text and whitespace), whereas a TeXCompositor implements the full TeX algorithm, which takes color into account in exchange for longer formatting times.

The Compositor–Composition split ensures a strong separation between code supporting the physical structure and code for different formatting algorithms. New Compositor subclasses can be added without touching the glyph classes, and vice versa; the algorithm can even be changed at run time by adding a single SetCompositor operation to Composition's interface.

The pattern

Encapsulating an algorithm in an object is the intent of the Strategy pattern. The key participants are Strategy objects (which encapsulate different algorithms) and the context in which they operate. Compositors are strategies; a composition is the context. The key to applying Strategy is designing interfaces — for both the strategy and its context — general enough to support a range of algorithms without changing those interfaces to support a new one.

Embellishing the user interface — Decorator

Two embellishments are considered: a border around the text-editing area to demarcate the page, and scroll bars that let the user view different parts of the page. To make these easy to add and remove (especially at run time), inheritance should not be used to add them — the most flexibility comes when other user-interface objects don't even know the embellishments are there.

Transparent enclosure

Using inheritance for this extension precludes rearranging embellishments at run time and, more seriously, causes an explosion of classes: a BorderedComposition, a ScrollableComposition, a BorderedScrollableComposition, and so on — a class for every possible combination.

Object composition is more workable. Since an existing glyph is being embellished, the embellishment itself becomes an object (say, an instance of Border), giving two candidates for composition. The border should contain the glyph (it surrounds the glyph on screen), which keeps the border-drawing code entirely in Border and leaves other classes alone. Because borders have an appearance, Border should itself be a subclass of Glyph — but there is a more compelling reason: clients shouldn't care whether glyphs have borders. They treat glyphs uniformly, telling a bordered glyph to draw itself just as they told a plain one. This implies the Border interface matches the Glyph interface, so Border is subclassed from Glyph to guarantee it.

This leads to transparent enclosure, which combines (1) single-child (single-component) composition and (2) compatible interfaces. Clients generally can't tell whether they're dealing with the component or its enclosure, especially if the enclosure simply delegates its operations to its component. But the enclosure can also augment the component's behavior by doing work before and/or after delegating, and it can effectively add state to the component.

MonoGlyph

A subclass of Glyph called MonoGlyph serves as the abstract class for "embellishment glyphs" like Border. MonoGlyph stores a reference to a component and forwards all requests to it, making it totally transparent to clients by default. Subclasses reimplement at least one forwarding operation. Border::Draw, for instance, first invokes MonoGlyph::Draw on the component (letting the component draw everything but the border), then draws the border via a private DrawBorder operation — extending the parent operation rather than merely replacing it.

Another MonoGlyph subclass, Scroller, draws its component in different locations based on two scroll bars it adds as embellishments, and clips to its bounds so parts scrolled out of view don't appear. A border and scrolling interface are added to Lexi's text-editing area by composing the existing Composition in a Scroller, then composing that in a Border. The order of composition can be reversed (putting the bordered composition into the Scroller), in which case the border scrolls along with the text — transparent enclosure makes such alternatives easy to experiment with while keeping clients free of embellishment code.

A border composes one glyph, not several — putting a border around something implies that something is singular. Keeping embellishment independent of other kinds of composition (row, column) both simplifies the embellishment classes and reduces their number, and avoids replicating existing composition functionality.

The pattern

The Decorator pattern captures the class and object relationships that support embellishment by transparent enclosure. In the pattern, "embellishment" has a broader meaning than scroll bars and borders: it refers to anything that adds responsibilities to an object — for example, embellishing an abstract syntax tree with semantic actions, a finite-state automaton with new transitions, or a network of persistent objects with attribute tags.

Supporting multiple look-and-feel standards — Abstract Factory

Portability across hardware and software platforms is a major problem in system design. One obstacle is the diversity of look-and-feel standards (such as Motif and Presentation Manager), which enforce uniformity between applications by defining how they appear and react to the user. The goals are to make Lexi conform to multiple existing standards, to make it easy to add support for new standards, and to support changing the look and feel at run time.

Abstracting object creation

Everything in Lexi's interface is a glyph composed in invisible glyphs like Row and Column. Style guides have much to say about "widgets" — visible glyphs like buttons, scroll bars, and menus. Two sets of widget glyph classes are assumed: (1) a set of abstract Glyph subclasses for each category of widget (e.g., an abstract ScrollBar, an abstract Button), and (2) a set of concrete subclasses for each abstract subclass implementing different standards (e.g., MotifScrollBar and PMScrollBar).

Lexi must instantiate the right concrete subclass for the targeted style. It can't do this directly with a constructor call — that would hard-code the style, making run-time selection impossible and requiring every such call to be tracked down and changed when porting. Littering the code with constructor calls to specific look-and-feel classes yields a maintenance nightmare: miss one, and you could end up with a Motif menu in a Mac application. The solution is to abstract the process of object creation.

Factories and product classes

Rather than:

ScrollBar* sb = new MotifScrollBar;

write:

ScrollBar* sb = guiFactory->CreateScrollBar();

where guiFactory is an instance of a MotifFactory class. CreateScrollBar returns the proper ScrollBar subclass for the desired look and feel — but nothing in the code mentions Motif by name. The guiFactory object abstracts the creation of widgets for any standard, and it isn't limited to scroll bars: it can manufacture a full range of widget glyphs (buttons, entry fields, menus, and so forth).

This works because MotifFactory is a subclass of GUIFactory, an abstract class defining a general interface for creating widget glyphs (operations like CreateScrollBar and CreateButton). We say factories create product objects, and the products a factory produces are related to one another — here, all widgets for the same look and feel.

The GUIFactory instance can come from anywhere convenient — a global, a static member of a well-known class, or a local variable (the Singleton pattern is mentioned for managing such one-of-a-kind objects). The important thing is to initialize it before it's used but after the desired look and feel is clear. If known at compile time:

GUIFactory* guiFactory = new MotifFactory;

If the user specifies it by string name at startup, the factory is created accordingly; a more sophisticated approach maintains a registry mapping strings to factory objects, which lets new factory subclasses be registered without modifying existing code and avoids linking every platform-specific factory into the application. Once configured with the right factory, the application creates the appropriate look and feel without modification; reinitializing guiFactory and reconstructing the interface changes it.

The pattern

Factories and products are the key participants in the Abstract Factory pattern, which captures how to create families of related product objects without instantiating classes directly. It's most appropriate when the number and general kinds of products stay constant but there are differences in specific product families. A family is chosen by instantiating a particular concrete factory and using it consistently; entire families can be swapped by replacing the concrete factory. The emphasis on families of products distinguishes Abstract Factory from other creational patterns, which involve only one kind of product object.

Supporting multiple window systems — Bridge

Look and feel is just one portability issue; another is the windowing environment. A window system creates the illusion of multiple overlapping windows on a bitmapped display, manages screen space, and routes input. Several important and largely incompatible window systems exist (Macintosh, Presentation Manager, Windows, X), and Lexi should run on as many as possible.

Can an Abstract Factory be reused?

At first glance this looks like another opportunity for Abstract Factory, but the constraints differ significantly. For look-and-feel independence, we defined the concrete widget glyph classes, so each concrete product (e.g., MotifScrollBar) could derive from an abstract product class (e.g., ScrollBar). For window systems, we already have several class hierarchies from different vendors, and they are highly unlikely to be compatible — so there is no common abstract product class for each kind of widget, and Abstract Factory won't work without those crucial classes. We can't afford to implement our own nonstandard window system either. The saving grace: window-system interfaces aren't radically different, because all window systems do generally the same thing. What's needed is a uniform set of windowing abstractions that lets any window-system implementation slide under a common interface.

Encapsulating implementation dependencies

A Window class is used for displaying a glyph or glyph structure. It encapsulates what windows tend to do across window systems: providing operations for drawing basic geometric shapes; iconifying and de-iconifying themselves; resizing themselves; and (re)drawing their contents on demand.

The Window class must span the functionality of windows from different systems. Two extreme philosophies are rejected:

1. Intersection of functionality — provide only what's common to all window systems. The interface ends up only as powerful as the least capable system.
2. Union of functionality — incorporate the capabilities of all systems. The interface becomes huge and incoherent, and must change whenever any vendor revises its interface.

The design falls between the two: a convenient interface supporting the most popular windowing features, plus a basic set of graphics operations that lets glyphs draw themselves. Window is an abstract class; concrete subclasses such as ApplicationWindow, IconWindow, and DialogWindow capture the differing behaviors of application windows, icons, and warning dialogs, giving Lexi a uniform, vendor-independent windowing abstraction.

The real platform-specific window must come in somewhere. Implementing multiple versions of Window per platform invites maintenance headaches (many classes all named "Window"); creating implementation-specific subclasses of each Window class causes another subclass explosion; and neither allows changing the window system after compilation. The answer is the same as for formatting and embellishment — encapsulate the concept that varies, here the window-system implementation. If a window system's functionality is encapsulated in an object, Window and its subclasses can be implemented in terms of that object's interface, configured (even at run time) by passing the right window-system-encapsulating object.

Window and WindowImp

A separate WindowImp class hierarchy hides different window-system implementations. WindowImp is an abstract class for objects that encapsulate window-system-dependent code; to make Lexi work on a particular system, each window object is configured with an instance of a WindowImp subclass for that system. Hiding the implementations in WindowImp keeps the Window hierarchy comparatively small and stable while the implementation hierarchy can be extended to support new window systems.

Subclasses of WindowImp convert requests into window-system-specific operations. Rectangle::Draw is defined in terms of DrawRect on the Window instance; the default DrawRect uses the abstract DeviceRect operation declared by WindowImp, where _imp is a Window member storing the configured WindowImp. An XWindowImp (for the X Window System) implements DeviceRect using XDrawRectangle, which defines a rectangle by its lower-left corner, width, and height — so DeviceRect first finds the lower-left corner (since the supplied corners might be any of the four) and then computes width and height. A PMWindowImp (for Presentation Manager) defines DeviceRect quite differently, because PM has no explicit rectangle-drawing operation — it offers a more general interface for specifying the vertices of multisegment shapes (a path) and outlining or filling them. The two implementations differ, but that doesn't matter: WindowImp hides variations behind a potentially large but stable interface.

Configuring windows with WindowImps

How does a window get the proper WindowImp — when does _imp get initialized, and who knows which window system is in use? One approach uses the Abstract Factory pattern: an abstract WindowSystemFactory provides an interface for creating window-system-dependent implementation objects, with a concrete factory for each window system. The Window base-class constructor uses the WindowSystemFactory interface to initialize _imp with the right WindowImp. The well-known windowSystemFactory variable is initialized the same way as the guiFactory variable for look and feel.

The pattern

The relationship between Window and WindowImp is an example of the Bridge pattern. Window's interface caters to the application programmer; WindowImp caters to window systems, and its interface can more closely reflect what window systems actually provide, warts and all. The intent behind Bridge is to allow separate class hierarchies — one for the logical notion of windows, another for capturing different implementations — to work together even as they evolve independently, so the windowing abstraction can be maintained and enhanced without touching window-system-dependent code, and vice versa.

User operations — Command

Some functionality is available through the WYSIWYG representation directly (entering and deleting text, moving the insertion point, selecting ranges). Other functionality is accessed indirectly through pull-down menus, buttons, and keyboard accelerators — creating a new document; opening, saving, and printing; cutting and pasting; changing font and style; changing alignment and justification; quitting; and on and on.

A particular operation shouldn't be tied to a particular user interface, because the same operation may be reachable through multiple interfaces (you can turn the page with a page button or a menu operation), and the interface may change later. These operations are also implemented in many different classes, and accessing their functionality shouldn't create a lot of dependencies between implementation and interface classes. Finally, Lexi should support undo and redo of most — but not all — of its functionality: document-modifying operations like delete should be undoable, but operations like saving or quitting should have no effect on the undo process, and there should be no arbitrary limit on the number of undo/redo levels.

Encapsulating a request

A pull-down menu is just a glyph that contains other glyphs; what distinguishes its items is that most do some work in response to an up-click. These work-performing glyphs are instances of a Glyph subclass called MenuItem, which do their work in response to a request from a client (conceptually the user, but in reality an event dispatcher).

Defining a MenuItem subclass for every operation is wrong — it couples the request to a particular interface, making the same request hard to fulfill through a different interface, and gives rise to a number of classes approaching the product of the number of widget types and the number of requests. What's missing is a way to parameterize menu items by the request they fulfill. Parameterizing MenuItem with a function is incomplete for three reasons:

1. It doesn't address the undo/redo problem.
2. It's hard to associate state with a function (a font-changing function needs to know which font).
3. Functions are hard to extend, and hard to reuse parts of.

So menu items are parameterized with an object, not a function: inheritance can then extend and reuse the request's implementation, and the object provides a place to store state and implement undo/redo. Each request is encapsulated in a command object — another instance of encapsulating the concept that varies.

Command class and subclasses

A Command abstract class provides an interface for issuing a request; its basic interface is a single abstract operation, Execute. Subclasses implement Execute differently to fulfill different requests — some delegate part or all of the work to other objects, others fulfill the request entirely on their own — but to the requester, a Command object is a Command object, treated uniformly. A MenuItem stores a Command object that encapsulates a request; when a user chooses a menu item, the MenuItem calls Execute on its Command. Buttons and other widgets can use commands the same way.

Undoability

To undo and redo commands, an Unexecute operation is added to Command's interface. Unexecute reverses the effects of a preceding Execute using whatever undo information Execute stored — a FontCommand's Execute, for instance, stores the affected text range and the original font(s), and its Unexecute restores them.

Sometimes undoability must be determined at run time: a request to change the font of a selection does nothing if the text is already in that font, and a spurious change repeated several times shouldn't require exactly that many undo operations to reverse. If the net effect of executing a command was nothing, there's no need for a corresponding undo. So an abstract Reversible operation returning a Boolean is added to the Command interface, which subclasses can redefine based on run-time criteria.

Command history

Arbitrary-level undo and redo is supported by a command history — a list of commands that have been executed (or unexecuted). Each entry is a Command object; a "present" line tracks the most recently executed (and unexecuted) command.

• To undo the last command, call Unexecute on the most recent command, then move the "present" line one command to the left. Repeating this yields multiple levels of undo, limited only by the length of the history.
• To redo a just-undone command, call Execute on the command to the right of the present line, then advance the present line. Commands to the right of present are candidates for future redo.

If the next operation is an undo rather than a redo, the command to the left of present is undone — so the user can go back and forth in time to recover from errors.

The pattern

Lexi's commands are an application of the Command pattern, which describes how to encapsulate a request. It prescribes a uniform interface for issuing requests that lets clients be configured to handle different requests and shields them from the request's implementation; a command may delegate all, part, or none of its implementation to other objects. This is perfect for applications that must provide centralized access to scattered functionality, and the pattern also discusses undo and redo mechanisms built on the basic interface.

Spelling checking and hyphenation — Iterator and Visitor

The last design problem involves textual analysis — checking for misspellings and introducing hyphenation points for good formatting. As with formatting, there's more than one way to check spelling and compute hyphenation, so multiple algorithms must be supported, with a choice of space/time/quality trade-offs, and it should be easy to add new ones. Wiring this functionality into the document structure must be avoided — even more so than for formatting, because spelling and hyphenation are just two of potentially many analyses (searching, word counting, tabular calculation, grammar checking), and the Glyph class and all its subclasses shouldn't change every time a new one is added.

There are two pieces to the puzzle, examined separately: (1) accessing the information to be analyzed, scattered over the glyphs, and (2) doing the analysis.

Accessing scattered information

Many analyses examine text character by character, but the text is scattered throughout a hierarchical structure whose glyphs may store children in linked lists, arrays, or more esoteric structures — so the access mechanism must handle all these possibilities. Different analyses also access information differently: most traverse from beginning to end, but a reverse search progresses backward, and evaluating algebraic expressions could require an inorder traversal. The mechanism must therefore accommodate differing data structures and support different kinds of traversals (preorder, postorder, inorder).

Encapsulating access and traversal

The current glyph interface uses an integer index to refer to children — reasonable for arrays, inefficient for linked lists. An important role of the glyph abstraction is to hide the data structure children are stored in, so the interface shouldn't be biased toward arrays over linked lists, as it currently is. Only the glyph should know its data structure.

One approach puts multiple access and traversal capabilities directly in the glyph classes, choosing among them via an enumerated Traversal constant. The following abstract operations could be added to Glyph:

void First(Traversal kind);  // CHILDREN, PREORDER, POSTORDER, INORDER
void Next();
bool IsDone();
Glyph* GetCurrent();         // replaces Child
void Insert(Glyph*);

First initializes the traversal (taking the kind as a parameter), Next advances, IsDone reports whether it's over, GetCurrent accesses the current glyph (replacing Child), and Insert inserts at the current position. This banishes the integer index and saves clients from implementing common traversals. But it still has problems: new traversals require extending the enumeration (e.g., adding TEXTUAL_PREORDER) or adding operations; putting the mechanism entirely in Glyph makes it hard to modify or extend without changing many classes; it's hard to reuse for other object structures; and only one traversal can be in progress at a time.

The better solution, once again, is to encapsulate the concept that varies — the access and traversal mechanisms — in a separate class of objects called iterators.

Iterator class and subclasses

An abstract Iterator class defines a general interface for access and traversal. Concrete subclasses like ArrayIterator and ListIterator provide access to arrays and lists, while PreorderIterator, PostorderIterator, and the like implement different traversals. Each subclass holds a reference to the structure it traverses, set at creation. A CreateIterator abstract operation is added to Glyph to support iterators.

The Iterator interface provides First, Next, and IsDone for controlling traversal, plus CurrentItem to return the glyph it points to. CreateIterator returns a NullIterator by default — a degenerate iterator for leaf glyphs, whose IsDone always returns true. A glyph with children overrides CreateIterator to return the appropriate subclass (a Row storing children in a list _children returns a ListIterator over them).

Iterators for preorder and inorder traversals are implemented in terms of glyph-specific iterators: supplied the root glyph, they call CreateIterator on glyphs in the structure and use a stack to track the resulting iterators. A PreorderIterator gets the iterator from the root, initializes it to its first element, and pushes it on the stack; CurrentItem calls CurrentItem on the top iterator; Next asks the current item to create an iterator (descending as far as possible), sets it to its first item and pushes it, then, if its IsDone returns true, pops and repeats until it finds the next incomplete traversal — or finishes the structure.

This lets new traversals be added without modifying glyph classes (just subclass Iterator); glyphs give clients access to children without revealing the underlying data structure; multiple traversals can run simultaneously, even on the same structure, because each iterator stores its own state; and a class like PreorderIterator can be parameterized (via C++ templates) by the object type to reuse its machinery on other structures.

The Iterator pattern

The Iterator pattern captures these techniques for supporting access and traversal over object structures. It's applicable not only to composite structures but to collections as well, abstracts the traversal algorithm, and shields clients from the internal structure of the objects they traverse — another illustration that encapsulating the concept that varies gains flexibility and reusability.

Traversal versus traversal actions

With traversal in hand, spelling checking and hyphenation remain — both accumulate information during the traversal. Analysis should be kept separate from traversal: the same kind of traversal (preorder, say) is common to many analyses (spelling checking, hyphenation, forward search, word count), so the same iterators can be reused.

Where, then, should the analysis responsibility live? Different analyses do different things at different points and care about different glyphs (spelling and hyphenation consider character glyphs, not graphical ones; color separation considers visible glyphs, not invisible ones). Putting analytical capability into the glyph classes — adding abstract operations to Glyph for each analysis — means changing every glyph class whenever a new analysis is added. A default implementation in Glyph can limit changes to deviating subclasses, but an insidious problem remains: Glyph's interface expands with every new analytical capability, until the analytical operations obscure the basic glyph interface.

Encapsulating the analysis

So the analysis is encapsulated in a separate object, used with an appropriate iterator that "carries" it to each glyph; the analysis object performs a piece of the analysis at each point and accumulates information of interest. The fundamental question is how the analysis object distinguishes different kinds of glyphs without type tests or downcasts — the brute-force approach (a SpellingChecker full of type-safe casts) is ugly, hard to extend, and exactly what object-oriented languages were meant to eliminate.

The technique: add an abstract operation to Glyph —

void CheckMe(SpellingChecker&)

— defined in every Glyph subclass to call back the matching checker operation. When CheckMe is called, the specific subclass is known (we're in one of its operations), so it invokes the right SpellingChecker operation (CheckGlyphSubclass) for its type. The SpellingChecker interface includes one such operation per Glyph subclass:

void CheckCharacter(Character*);
void CheckRow(Row*);
void CheckImage(Image*);
// ... one per Glyph subclass

CheckCharacter accumulates alphabetic characters into a _currentWord buffer (using a GetCharCode operation defined specially on Character); when it hits a nonalphabetic character it calls IsMisspelled on the word, adds misspelled words to a list, and clears the buffer. (IsMisspelled implements the spelling algorithm, kept independent of Lexi's design — different algorithms can be supported by subclassing SpellingChecker or by applying the Strategy pattern, as for formatting.) After the traversal, GetMisspellings retrieves the list. This lets the checker handle subclass-specific operations without type tests or casts.

But this seems to require adding a CheckMe(SpellingChecker&) operation to Glyph for every new analysis — true only if each analysis insists on an independent class. Giving all analysis classes the same interface lets them be used polymorphically, replacing analysis-specific operations like CheckMe(SpellingChecker&) with an analysis-independent operation taking a more general parameter.

Visitor class and subclasses

The term visitor refers generally to classes of objects that "visit" other objects during a traversal and do something appropriate. A Visitor class defines an abstract interface for visiting glyphs; concrete subclasses perform different analyses — a SpellingCheckingVisitor (implemented as SpellingChecker was, but with operation names like VisitCharacter) and a HyphenationVisitor. Since CheckMe isn't appropriate for visitors that don't check anything, it's renamed Accept, and its argument changes to a Visitor&. Now adding a new analysis requires just defining a new Visitor subclass — no glyph class is touched; all future analyses are supported by adding this one Accept operation to Glyph and its subclasses.

HyphenationVisitor accumulates text like the spelling checker, but once VisitCharacter has assembled a whole word it applies a hyphenation algorithm to find potential hyphenation points and inserts a discretionary glyph at each. Discretionaries (instances of Discretionary, a Glyph subclass) have one of two appearances depending on whether they are the last character on a line: at line end, a discretionary looks like a hyphen; elsewhere it has no appearance at all. The discretionary checks its parent (a Row) to see whether it is the last child whenever it draws or calculates its bounds, and the formatting strategy treats discretionaries like whitespace, making them candidates for ending a line.

The Visitor pattern

This is an application of the Visitor pattern, which captures the technique of allowing an open-ended number of analyses of glyph structures without changing the glyph classes. Visitors apply not just to composites but to any object structure (sets, lists, even directed-acyclic graphs), and the classes a visitor visits needn't share a common parent — visitors can work across class hierarchies.

The important question before applying Visitor is: which class hierarchies change most often? The pattern suits doing a variety of different things to objects with a stable class structure — adding a new visitor needs no change to that structure. But adding a subclass to the structure forces updating all visitor interfaces to include a Visit... operation for it (adding a Glyph subclass Foo requires a VisitFoo on Visitor and all its subclasses). Because Lexi is far more likely to add a new analysis than a new Glyph, Visitor is well-suited here.

Summary

Eight patterns were applied to Lexi's design:

| # | Pattern | Design problem it solves | | --- | --- | --- | | 1 | Composite | Represent the document's physical structure | | 2 | Strategy | Allow different formatting algorithms | | 3 | Decorator | Embellish the user interface | | 4 | Abstract Factory | Support multiple look-and-feel standards | | 5 | Bridge | Allow multiple windowing platforms | | 6 | Command | Support undoable user operations | | 7 | Iterator | Access and traverse object structures | | 8 | Visitor | Allow an open-ended number of analytical capabilities without complicating the document structure |

None of these design issues is limited to document editors. Most nontrivial applications will use many of these patterns, though perhaps to do different things: a financial analysis application might use Composite to define investment portfolios made of subportfolios and accounts; a compiler might use Strategy for different register-allocation schemes per target machine; applications with a graphical user interface will probably apply at least Decorator and Command. A unifying lesson runs through every solution — encapsulate the concept that varies (the formatting algorithm, the request, the window-system implementation, the look-and-feel family, the traversal, the analysis) to gain flexibility and reusability.

Related lessons