|
Lexi, or the Quest for the Mythical Editor - Felix John COLIBRI.
|
- abstract: An introduction to design patterns by coding the Lexi document
editor
- key words: design patterns - Lexi - document editor - gof - gang of four -
Composite - Decorator - Strategy - Iterator - Visitor - Command - Abstract
Factory - Bridge
- software used: Windows XP, Delphi 6
- hardware used: Pentium 1.400Mhz, 256 M Ram, 140 G disk
- scope: Delphi, Java, C#, C++ programmer
- level: Intermediate
- plan:
1 - Introduction
Who's Lexi ?
Lexi is the name of the sample "document editor" used by the Gang of Four,
Gof for short, as the introductory example to design patterns.
This book written in 1996 by Erich GAMMA, Richard HELM,
Ralph JOHNSON, John VLISSIDES literaly started the whole pattern
movement.
After introducing the Design Pattern idea, the Gof spent about 40 pages
presenting a case study which explains how to use 8 typical patterns in the
course of designing the "LEXI document editor". The next 300 pages then
explain each of the 23 Design Patterns, with motivation, diagrams and coding
examples.
However the book does not present the full source code of Lexi. In addition,
the other coding examples are in other domains than document editing, like game
programming for instance. I have nothing against enchanted rooms, exploding
doors or flying windows, but I missed the more realistic text editor example.
Googling on the web, you will find lots of "editors", and in source. To name a
few:
- HotDraw and jHotDraw
- Interview and UniDraw, which are editor frameworks
- MiniDraw as example for learning object oriented programming
- figure editor, mainly used as testbeds for Aspect Oriented Programming
The Gof tell us in a note that Lexi is based on "Doc, a text editing
application developed by Calder". But this paper only outlines an editor,
without any source. And I even believe today that Lexi never truly existed as a
program. Well, no longer: here comes Lexi !
In writing my own Lexi, my purpose was:
- to follow as closely as possible the Gof case study
- to offer a Delphi source code, that you can compile, execute, examine,
improve
2 - The description of Lexi
2.1 - The Original Lexi
The Gof book presents the following Lexi example:
2.2 - Our specification
The editor we wish to build will have the following features:
- characters, shapes, bitmaps
- layout in lines and columns
- toolbar for character, shape, bitmap
- mouse selection of an area for font change
- caret positioning for insert, delete
- infinite undo
- reformatting
- orthographic correction
- optional scrollbars and borders
- use of different windowing libraries
This is not a bona fide specification, but will be sufficient to give you an
idea of the ground that will be covered.
The user interface will have the following look:
2.3 - The Classes
In an analysis and design paper, we would show how to go through the user
description, build the specification, perform a full fledged analysis and
design phase, to finally find the classes and their responsibilities
(attributes and methods).
Our goal however is to stress the Design Pattern point of view. Patterns are
one level above Classes: they are concerned with Classes relations and
interactions.
We will start with the following obvious Classes, which would be defined by any
programmer having some Object Oriented programming experience:
- c_character, c_rectangle, c_bitmap to handle the elements of our editor
- c_row and c_page for the structure
- c_caret, c_selection for the mouse handling
So let us now dwelve into the Pattern part.
3 - The Composite Pattern
3.1 - The structure
The most important decision is the structure for storing the items in memory.
All processing will manipulate in one way or another this structure.
Our data consist of pages / columns / rows / items. To any programmer worth his
salt, this should be organized as a tree-like structure. It could be
constructed with binary trees, n-ary trees, lists of lists, or any other parts
/ whole structuring element of the programming language.
Many of the function on each figure element like drawing, loading, saving, will
also have their counterpart on the structure elements like rows, columns and
pages. Hence the idea to use a common abstract ancestor, with all the
commonalities, and both individual pieces AND the structural parts will descend
from this ancestor. In UML notation, we will have the following organization:
In this figure
- the c_glyph is the abstract class for all drawing (pieces and structure).
This class is ABSTRACT, as testified by the italic font of the class name
- the c_character, c_rectangle, c_bitmap are some of the possible elements
of the document
- c_page, c_column (which we did not implement) and c_row are the
structuring parts
In Delphi terms, the CLASS definitions will be the following:
The benefit of using the same ancestor for the element AND for the structure is
that we will be able to call a single function for drawing the whole structure:
- here is the individual c_character draw method:
procedure c_character_glyph.draw(p_c_client_region_drawing: c_client_region_drawing);
begin
with p_c_client_region_drawing do
draw_text(m_x, m_y, m_name[1]);
end; // draw
|
- the c_composite_glyph simply calls the drawing of each individual child
glyph:
procedure c_composite_glyph.draw(p_c_client_region_drawing: c_client_region_drawing);
var l_glyph_index: Integer;
begin
for l_glyph_index:= 0 to f_glyph_count- 1 do
f_c_glyph(l_glyph_index).draw(p_c_client_region_drawing);
end; // draw
|
- and, to draw the whole figure with all rows and characters, the main program
calls:
VAR g_c_page_glyph: c_page_glyph;
g_c_client_region_drawing: c_client_region_drawing;
...
g_c_page_glyph.draw(g_c_client_region_drawing);
|
3.2 - The evolution of Trees
Way back on the Apple ][, we used pointers to build trees.
Wirth's "Algorithms+ Data Structures" was the golden book
in those time (it still should be for starting programming), and we represented
trees in the following way:
with the corresponding Pascal definitions and declarations:
TYPE t_pt_cell= ^t_cell;
t_cell= RECORD
m_pt_lower: t_pt_cell;
m_name: String;
m_pt_greater: t_pt_cell;
END;
VAR g_pt_root: t_pt_cell;
PROCEDURE add_cell(p_name: String);
PROCEDURE list_names_recursive(p_pt_cell: t_pt_cell);
|
Notice that:
- there is no distinction between the "tree" and the "leaves".
- all processing is done using procedures, which manipulate the global
variable (the structure), usually recursing to get at the leaves (the
elements)
If we wanted to handle several trees in our programs, we used parameters to
pass the different trees to the procedures. And when the program grew in size
and complexity, we placed the tree handling in a UNIT, thereby building an
Abstract Data Type. The starting point of the Object movement.
Now comes step two: Bertrand MEYER explained in his
seminal book on Object that there are processing concerning the leaves
(displaying its shape, saving it on disk), and some processing concerning the
whole structure (counting the elements, rearranging the layout). So it was
rightly advised to separate the data and the functions in two CLASSes:
- on class representing the structure elements
- one class reprsenting the structure itself
The definition therefore looked like this:
with the following code:
TYPE c_cell= CLASS
m_c_lower: c_cell;
m_name: String;
m_c_greater: c_cell;
PROCEDURE display_cell;
END;
c_tree= CLASS
m_c_root: c_cell;
PROCEDURE display_tree;
PROCEDURE count_cells;
END;
|
Finally the Design Patterns recommend to derive the structure from an abstract
element, factoring out the functions common to both the element and the
structure:
Somehow we are back to step one, with the element as the top of the handling.
However this "element" is an ABSTRACT element, nowhere to be instantiated: it
is defined only to offer a unified syntax and allow a single call from the user
program.
But this has far reaching consequences as well. With this recursive structure,
we can build trees of trees. Let us compare the classical tree CLASSes to the
"pattern" tree CLASSes:
In the "pattern" architecture, c_tree is a child of c_cell, and thererfore
can be used in the same way as any other c_cell. Hence the trees of trees:
3.3 - UML
This also shows the power of object notation: just looking at the class
diagram, you can foresee the consequences, ponder the alternatives, evaluate
the costs and benefits of each organization.
UML comes here very handy: it unified the notation. That's the least one could
expect from a UNIFIED thing. I am not overly enthusiastic about the whole UML
business though. As criticized by many people already, the whole set is too
redundant, trying to include every little bit of notation to make sure that no
single searcher would start promoting his own drawings. Grady BOOCH's touch, I
guess. Reminds me of the early eighties, when Bill Gates was trying to propose
"standards" everywhere, his standards of course. Anyway, tools that require
such huge books to describe them cannot be that perfect. For me, three quarter
of the graphics can be thrown to the thrash can right from the start. As
explained by Bertrand MEYER, Use Cases are even a big step
backward. To me, Use Cases often take the form of "I get up in the morning, and
then I shave, and then I brush my teeth, and then I have breakfast...". Simple
flows of actions, like in the olden time of structured programming. This looks
more like talking to a 6 year old kid than Analysis and Design. Where are the
concepts, where are the abstractions ?
So, in this paper, I will only use Class Diagrams, Object Diagrams, eventually
Sequence diagrams. In my own projects, I sometimes also use State Charts, when
the application requires the representation of complex interactions. And that's
it.
4 - The Decorator Pattern
4.1 - Objective
This is an easy one. The objective is to let the user add scroll bars or
borders to his page:
In addition:
- we do not want to change any existing source line: the client program uses
the same calls to perform drawing, saving etc, whether the structure is
nested in scrolling or border containers or not
- the addition of "decorations" will take place at RUN TIME
This is achieved:
- by creating a new class with the bordering artifact
- this class includes a attributes which points to the existing page
- the new class
- directly handles all the border management
- forwards all calls to the existing page
If we use several kinds of border, we define an abstract parent, and can
instantiate any of the children at run time.
The UML representation is the following:
And since the border and the page are both descendents of c_glyph, we can nest
the addition of decoration at any depth.
4.2 - Our implementation
There is our Delphi code:
- the abstract decorator:
c_abstract_border_decorator= class(c_page_glyph)
_m_c_enclosed_glyph: c_page_glyph;
Constructor create_abstract_border_decorator(p_name: String;
p_c_parent_glyph: c_glyph;
p_c_enclosed_glyph: c_page_glyph);
procedure draw(p_c_client_region_drawing: c_client_region_drawing); Override;
// -- replace ALL the functions called for m_c_root_page
procedure append_glyph(p_c_glyph: c_glyph); Override;
procedure select_in_rectangle(p_absolute_rectangle: tRect); Override;
// -- ... ALL the other
end; // c_abstract_border_decorator
|
- with the following implementation code:
Constructor c_abstract_border_decorator.create_abstract_border_decorator(p_name: String;
p_c_parent_glyph: c_glyph;
p_c_enclosed_glyph: c_page_glyph);
begin
// -- initialize with the enclosing rectangle of the previous enclosed
with p_c_enclosed_glyph do
Inherited create_page_glyph(p_name, p_c_parent_glyph,
f_absolute_x, f_absolute_y, m_width_max, m_height_max);
_m_c_enclosed_glyph:= p_c_enclosed_glyph;
end; // create_abstract_border_decorator
// -- delegation of the methods
procedure c_abstract_border_decorator.draw(p_c_client_region_drawing: c_client_region_drawing);
begin
_m_c_enclosed_glyph.draw(p_c_client_region_drawing);
end; // draw
procedure c_abstract_border_decorator.append_glyph(p_c_glyph: c_glyph);
begin
_m_c_enclosed_glyph.append_glyph(p_c_glyph);
end; // append_glyph
|
- and the "frame" class:
c_frame_decorator= class(c_abstract_border_decorator)
Constructor create_frame_decorator(p_name: String;
p_c_parent_glyph: c_glyph;
p_c_enclosed_glyph: c_page_glyph);
procedure draw(p_c_client_region_drawing: c_client_region_drawing); Override;
end; // c_frame_decorator
|
- with the corresponding code:
procedure c_frame_decorator.draw(p_c_client_region_drawing: c_client_region_drawing);
begin
// -- draw the border
with p_c_client_region_drawing do
draw_rectangle(m_x, m_y, m_width_max, m_height_max);
// -- draw the enclosed content
Inherited;
end; // draw
|
Here is a shapshot of the addition of a couple of frames (in green) and
scrollbars (in blue):
4.3 - CLASSes vs COMPONENTS
The key to the decorator pattern is delegation. The scroller delgates all
page method calls to the enclosed page.
Delegation was already at the heart of the COM concept, where COM objects could
encapsulate other COM objets, provided that the calls to the inner object were
forwarded by the wrapper:
We can go one step further: today, many people talk about "components" as
software pieces that the USER can assemble at runtime. We have been accustomed
to talk about Delphi components, which are assembled at design time.
In both cases, to build a working application, on needs to glue the components
together so that they can work together. The gluing part is performed by so
called "connectors"
Some people then criticized the Delphi framework because
- it only assembles graphical components (which is not entirely true)
- much of the time spent by a developer is in writing glue code, instead of
using more finished components and let the user snap them together.
I was very disappointed. I truly believed that during all those years I had
been using Delphi to write wonderful code with cute algorithms, whereas I was
merely gluing things together. And they even tell me that I was using the wrong
glue !
In any case, the component / connector / composition / delegation issue is at
the heart of intense research today.
And also notice that the delegation we are talking about is not the "Delphi
delegation", where a tButton "delegates" the OnClick to the tForm CLASS:
5 - The Iterator Pattern
5.1 - Iterating over the elements
In many places we will have to enumerate the items of our structure. Our
prefered method was to recurse in the tree structure. To check whether our page
contains any rectangle, we would use:
function c_page_glyph.f_contains_rectangle_glyph: Boolean;
procedure check_recursive(p_c_glyph: c_glyph);
var l_glyph_index: Integer;
begin
if p_c_glyph is c_rectangle_glyph
then begin
Result:= True;
Exit;
end;
if p_c_glyph is c_composite_glyph
then
with c_composite_glyph(p_c_glyph) do
for l_glyph_index:= 0 to f_glyph_count- 1 do
check_recursive(f_c_glyph(l_glyph_index));
end; // check_recursive
begin // f_contains_rectangle_glyph
Result:= False;
check_recursive(Self);
end; // f_contains_rectangle_glyph
|
This code requires intimate knowledge of the structure implementation. A more
transparent way would be to simply call some "next" enumerator which would hand
over all the elements required by our computation:
function c_page_glyph.f_contains_rectangle_2: Boolean;
// -- an iterator exercise
var l_c_leaf_iterator: c_leaf_iterator;
begin
l_c_leaf_iterator:= c_leaf_iterator.create_leaf_iterator('leaf_iter', Self);
l_c_leaf_iterator.goto_first_glyph;
Result:= False;
while not l_c_leaf_iterator.f_is_done do
begin
if l_c_leaf_iterator.f_c_current_glyph IS c_rectangle
then begin
Result:= True;
Break;
end;
l_c_leaf_iterator.goto_next_glyph;
end; // while not f_is_done
l_c_leaf_iterator.Free;
end; // f_contains_rectangle_2
|
5.2 - The Iterator Pattern
Basically the iterator pattern has the following methods
- goto_first_glyph
- f_c_current_glyph
- goto_next_glyph
- f_is_done
and in addition it somehow remembers the current position to be able to fetch
the next item.
If our structure has multiple containers, implemented by different means
(trees, lists, arrays, bags, collections), we will create an abstract iterator,
and derive the tree iterator, list iterator etc from this ancestor. The client
code would declare an abstract iterator variable, and instantiate whatever
concrete iterator is desirable at run time.
The UML schema for the iterator is:
Notice that
- there is a link from the iterators to the c_glyph, since the iterator has
some member attribute to remember the current position (this is not
inheritance: it is a relation between two classes)
- the c_null_iterator is useful if the container structure is nested at the
c_glyph level: any iterator at this level should always return f_is_done
TRUE. We nested the structure in c_composite_glyph, so the c_null_iterator
is of no use.
- if we use a tree-like structure, we may build several iterators:
- iterators for pages
- iterators for rows
- iterators for characters
5.3 - The Delphi Implementation
The abstract iterator is defined as:
c_abstract_iterator= class(c_basic_object)
_m_c_glyph_ref: c_glyph;
Constructor create_abstract_iterator(p_name: String;
p_c_glyph_ref: c_glyph);
procedure goto_first_glyph; Virtual; Abstract;
procedure goto_next_glyph; Virtual; Abstract;
function f_c_current_glyph: Virtual; Abstract;
function f_is_done: Boolean; Virtual; Abstract;
end; // c_abstract_iterator
|
We used the following composite iterator class (to iterate over ANY composite):
c_composite_iterator= class(c_abstract_iterator)
_m_c_composite_glyph_ref: c_composite_glyph;
m_glyph_index: Integer;
Constructor create_composite_iterator(p_name: String;
p_c_glyph_ref: c_glyph);
procedure goto_first_glyph; Override;
procedure goto_next_glyph; Override;
function f_c_current_glyph: c_glyph; Override;
function f_is_done: Boolean; Override;
end; // c_composite_iterator
|
with the following implementation:
Constructor c_composite_iterator.create_composite_iterator(p_name: String;
p_c_glyph_ref: c_glyph);
begin
Inherited create_abstract_iterator(p_name, p_c_glyph_ref);
// -- avoid continuous casts
_m_c_composite_glyph_ref:= c_composite_glyph(_m_c_glyph_ref);
end; // create_composite_iterator
function c_composite_iterator.f_display_iterator: String;
begin
Result:= m_name;
end; // f_display_iterator
procedure c_composite_iterator.goto_first_glyph;
begin
m_glyph_index:= 0;
end; // f_c_first_glyph
procedure c_composite_iterator.goto_next_glyph;
begin
Inc(m_glyph_index);
end; // f_c_next_glyph
function c_composite_iterator.f_is_done: Boolean;
begin
Result:= m_glyph_index>= _m_c_composite_glyph_ref.f_glyph_count;
end; // f_is_done
function c_composite_iterator.f_c_current_glyph: c_glyph;
begin
Result:= _m_c_composite_glyph_ref.f_c_glyph(m_glyph_index);
end; // f_c_current_glyph
|
As an example of a simple iterator, the coloring and resizing of fonts use
iterators. Here is a snapshot:
Now the interesting part. The Gof explained that in order to iterate over the
leaves of the tree in "preorder" (the bottom leaves first), we should use a
stack to save the nodes during the descent in the branches. This is classic
tree traversal business: you can visit the nodes of a tree in depth first or
width first order (or in any other custom order you may choose):
The tree shown above are "binary sort tree": the user entered "m" "e" "a" "z"
"d", and by visiting the node in preorder, you will see "a" "d" "e" "m" "z"
(which is the alphabetical sort order).
However this is not what we have in Lexi. Let us assume that we enter the
following lines:
me
azd
If we build the tree by adding the rows at the bottom of the tree, which is the
normal way of adding items to a tree (it always grows at the leaf level), the
tree will look like this:
This can be more naturally presented by rotating the tree 45 degrees anti clock
wise:
In this case the "preorder" iterator of the Gof will visit the character in the
following order:
azd
me
So the first line entered is visited last (this is depth first). If the
insertion order if of no importance to you, this is irrelevant. But for
hyphenation, for instance, it is crucial that leaves are visited in the
insertion order.
To get insertion order traversal, we can:
- build the tree by inserting new rows "above" previous rows
- build another visiting algorithm
- change the page / row / character structure
We chose to change the visiting algorithm, since other pieces of code assuming
bottom growth of the tree were already written. Here is the code:
procedure c_leaf_iterator.goto_first_glyph;
var l_c_composite_iterator: c_composite_iterator;
l_c_current_glyph: c_glyph;
l_c_child_iterator: c_composite_iterator;
begin
l_c_composite_iterator:= c_composite_iterator.create_composite_iterator('compo', _m_c_glyph_ref);
l_c_composite_iterator.goto_first_glyph;
m_c_composite_iterator_stack.clear_stack;
m_c_composite_iterator_stack.push_composite_iterator(l_c_composite_iterator);
// -- even for the first, must drill down to get the first leaf
with m_c_composite_iterator_stack do
begin
l_c_current_glyph:= f_c_top_of_stack_composite_iterator.f_c_current_glyph;
l_c_child_iterator:= c_composite_iterator.create_composite_iterator('child_iter', l_c_current_glyph);
l_c_child_iterator.goto_first_glyph;
push_composite_iterator(l_c_child_iterator);
end;
end; // goto_first_glyph
procedure c_leaf_iterator.goto_next_glyph;
var l_c_current_glyph: c_glyph;
l_c_child_iterator: c_composite_iterator;
l_c_composite_iterator: c_composite_iterator;
begin
with m_c_composite_iterator_stack do
begin
l_c_current_glyph:= f_c_top_of_stack_composite_iterator.f_c_current_glyph;
if l_c_current_glyph is c_composite_glyph
then begin
l_c_child_iterator:= c_composite_iterator.create_composite_iterator('child_iter', l_c_current_glyph);
l_c_child_iterator.goto_first_glyph;
push_composite_iterator(l_c_child_iterator);
end
else begin
// -- this is a simple glyph
Repeat
l_c_composite_iterator:= f_c_top_of_stack_composite_iterator;
// -- get the next (to toggle done eventually)
l_c_composite_iterator.goto_next_glyph;
if l_c_composite_iterator.f_is_done
then begin
// -- pop and free
f_c_pop_composite_iterator.Free;
l_c_composite_iterator:= Nil;
if not f_is_empty
then begin
l_c_composite_iterator:= f_c_top_of_stack_composite_iterator;
if not l_c_composite_iterator.f_is_done
then begin
l_c_composite_iterator.goto_next_glyph;
if not l_c_composite_iterator.f_is_done
then // -- recurse
Self.goto_next_glyph
else l_c_composite_iterator:= Nil;
end;
end;
end;
until f_is_empty or (l_c_composite_iterator<> Nil);
end;
end; // with
end; // goto_next_glyph
|
We did not present the c_composite_iterator_stack which is a simple stack
build with a tList (see the .ZIP for the details).
You might believe that I am heavily criticizing the Gof Iterator. Quite the
contrary: this is a perfect example of the usefulness of this pattern: instead
of smearing the user code with different visiting algorithms, we encapsulate
all the iteration part in the Iterator classes.
Our Lexi code does not use the iterator everywhere, since I started the project
with standard recursion, before I reached the Iterator part. But those
recursions could now be replaced with iterators everywhere (except in the
iterators themselves).
6 - The Visitor Pattern
6.1 - Spell Checking
Many functions will require visiting the characters of the text in insertion
order. Spell checking is an example. We could add word counting (many magazine
pay authors based on word count), or text search, translation etc.
If we have many different processing tasks, Gof recomends to use the Visitor
pattern:
- we define an abstract visitor class, and separate descendent visitors, one
for each specific task
- each part of our structure (c_glyp, c_row, c_page) has an
accept_visitor(c_abstract_visitor) method
- the client code
- initializes a concrete Visitor
- uses an Iterator to reach the elements
- for each element, accept_visitor is called, and the specific visitor
handles the task
In our spell checking case:
- the main application will create a c_spell_checker visitor
- a c_character_iterator will find each character
- for each character, the c_spell_checker will be called:
- if the character is a letter, it will be concatenated to a "running word"
- if the character is a separator (space, return...), the running word will
be checked against a dictionnary
And if we wish to do word counting, the only thing that changes is the
instantiation of a c_word_count_visitor instead of a c_spell_checker_visitor.
6.2 - Visitor UML representation
Notice that there is a mutual link between c_glyph and c_visitor (since
c_glyph uses c_visitor as a parameter in accept_visitor, and each c_visitor
uses a c_glyph descendent in the visit_xxx methods)
6.3 - The Delphi implementation
Here is the c_abstract_visitor:
c_abstract_visitor= class(c_basic_object)
procedure visit_character(p_c_character_glyph: c_character_glyph); Virtual; Abstract;
procedure visit_row(p_c_row_glyph: c_row_glyph); Virtual; Abstract;
end; // c_abstract_visitor
|
The spell checker is defined as:
c_simple_spelling_checker_visitor= class(c_abstract_visitor)
m_word_to_check: String;
Constructor create_simle_spelling_checker_visitor(p_name: String);
procedure visit_character(p_c_character_glyph: c_character_glyph); Override;
end; // c_spelling_checker_visitor
|
and:
procedure c_spelling_checker_visitor.visit_character(p_c_character_glyph: c_character_glyph);
var l_character: Char;
begin
l_character:= p_c_character_glyph.m_name[1];
if l_character= ' '
then begin
// -- check the word
m_word_to_check:= '';
end;
else m_word_to_check:= m_word_to_check+ l_character;
end; // visit_character
|
with the following client code:
procedure c_page_glyph.check_spelling;
var l_c_leaf_iterator: c_leaf_iterator;
l_c_spelling_checker_visitor: c_simple_spelling_checker_visitor;
begin
l_c_leaf_iterator:= c_leaf_iterator.create_leaf_iterator('leaf_iter', Self);
l_c_spelling_checker_visitor:=
c_simple_spelling_checker_visitor.create_simple_spelling_checker_visitor('spell');,
with l_c_leaf_iterator do
begin
goto_first_glyph;
while not f_is_done do
begin
f_c_current_glyph.accept_visitor(l_c_spelling_checker_visitor);
goto_next_glyph;
end; // while not f_is_done
l_c_previous_row.accept_visitor(l_c_spelling_checker_visitor);
Free;
end; // with l_c_leaf_iterator
l_c_spelling_checker_visitor.Free;
end; // check_spelling
|
We assumed that words were separated by punctuations like spaces, commas,
returns etc. In many editors, there are 2 line breaking possibilities:
- the return entered by the user
- the end of line imposed by the line breaking algorithm. If the line is
longer then allowed by the window size, the editor can use "pseudo returns"
(some unused character replacing the last space, not shown to the user, and
marking the end of line for the line handling tasks).
If we do not use pseudo-returns (which is the unhappy choice we made in this
version of Lexi), then previous visitor will mistakenly concatenate each end
of line words with the next start of line word. The character flow does not
allow detection of the line break.
One possibility would be to use the y value of each character. Another
possibility is to use a row_visitor.
Here is the new visitor:
c_spelling_checker_visitor= class(c_abstract_visitor)
m_word_to_check: String;
Constructor create_spelling_checker_visitor(p_name: String);
procedure _check_the_word;
procedure visit_character(p_c_character_glyph: c_character_glyph); Override;
procedure visit_row(p_c_row_glyph: c_row_glyph); Override;
end; // c_spelling_checker_visitor
|
which is implemented as:
procedure c_spelling_checker_visitor._check_the_word;
begin
if m_word_to_check<> ''
then begin
// -- do the checking
m_word_to_check:= '';
end;
end; // _check_the_word
procedure c_spelling_checker_visitor.visit_character(p_c_character_glyph: c_character_glyph);
var l_character: Char;
begin
l_character:= p_c_character_glyph.m_name[1];
if l_character= ' '
then _check_the_word
else m_word_to_check:= m_word_to_check+ l_character;
end; // visit_character
procedure c_spelling_checker_visitor.visit_row(p_c_row_glyph: c_row_glyph);
begin
_check_the_word;
end; // visit_row
|
and is used like this:
procedure c_page_glyph.check_spelling;
var l_c_leaf_iterator: c_leaf_iterator;
l_c_current_glyph: c_glyph;
l_c_spelling_checker_visitor: c_spelling_checker_visitor;
l_c_current_row, l_c_previous_row: c_row_glyph;
begin
l_c_leaf_iterator:= c_leaf_iterator.create_leaf_iterator('leaf_iter', Self);
l_c_spelling_checker_visitor:=
c_spelling_checker_visitor.create_spelling_checker_visitor('spell');
l_c_previous_row:= Nil;
with l_c_leaf_iterator do
begin
goto_first_glyph;
while not f_is_done do
begin
l_c_current_glyph:= f_c_current_glyph;
if l_c_current_glyph is c_character_glyph
then begin
l_c_current_row:= l_c_current_glyph.f_c_parent_glyph as c_row_glyph;
if (l_c_previous_row<> Nil) and (l_c_current_row<> l_c_previous_row)
then l_c_previous_row.accept_visitor(l_c_spelling_checker_visitor);
l_c_previous_row:= l_c_current_row;
end;
l_c_current_glyph.accept_visitor(l_c_spelling_checker_visitor);
goto_next_glyph;
end; // while not f_is_done
l_c_previous_row.accept_visitor(l_c_spelling_checker_visitor);
Free;
end; // with l_c_leaf_iterator
l_c_spelling_checker_visitor.Free;
end; // check_spelling
|
6.4 - Visitors
Visitors are a very nice pattern, which helps us add all kinds of functionality
to our application.
In the following figure, we represented the structure, where each element has a
reference to the abstract visitor (the white ellipse):
When the client instantiates a visitor descendent (the blue visitor, for
instance), the iterator will go through the elements of the structure, and call
the "blue" visitor processing:
To add a new kind of processing, all we have to do is
- to write a new c_abstract_visitor descendent
- in the client code, instantiate THIS visitor
On the donwside however, whenever we add a new c_xxx_glyph element type, we
will have to add a new visit_xxx_glyph method in each c_visitor. For
instance, adding a new c_column_glyph forces us to add visit_column in the
c_abstract_visitor, and in all its descendents:
6.5 - Main Lesson From the Gof
I think by now you will start to get some feel of the pattern way of coding.
Essentially, whenever your application uses features with "some variability"
- you encapsulate the feature in an abstract class
- the client references the abstract class
- you define the different processing in the descendent
- the client instantiates any of the descendents at run time
We already encountered this behaviour in Decorator, Iterator and Visitor.
And it will be uses in many other patterns.
7 - The Strategy Pattern
7.1 - Formating Text
As another example of the "encapsulate variation" mechanism, let us look at the
Strategy pattern.
To display our Lexi text, we want to select one of several layout
possibilities: justify to the right, to the left or on both sides.
The traditional solution is to write c_row.justify_left,
c_row.justify_right, c_row.justify_both. If we want to define another
layout, this would involve adding another method, AND calling it from the main
structure.
The idea of the Strategy pattern is:
- to define an abstract strategy
- different line breaking algorithms are implemented in descendents of the
abstract strategy
- the client structure needing some reformatting instantiates one of the
possible concrete strategies and calls it's justify method
7.2 - UML representation of Strategy
The UML class diagram is the following:
7.3 - Delphi implementation
Let us start with a simple "per line" justification:
- the abstract strategy is defined by:
c_abstract_row_justification_strategy
= class(c_basic_object)
m_c_row_glyph_ref: c_row_glyph_ref;
procedure set_row(p_c_row_glyph_ref: tObject);
procedure justify_row(p_width: Integer); Virtual; Abstract;
end; // c_abstract_row_justification_strategy
|
- here is the right justification class (the left justification is trivial, as
the .ZIP will testify)
c_right_row_justification_strategy
= class(c_abstract_row_justification_strategy)
Constructor create_right_row_justification_strategy(p_name: String);
procedure justify_row(p_width: Integer); Override;
end; // c_right_row_justification_strategy
|
with the following implementation:
procedure c_right_row_justification_strategy.justify_row(p_width: Integer);
// -- push everything to the right
function f_compute_row_minimum_width: Integer;
var l_c_character_iterator: c_composite_iterator;
begin
l_c_character_iterator:= c_composite_iterator.create_composite_iterator('row_iter',
c_glyph(m_c_row_glyph_ref));
// -- first compute the pixels of the glyphs
Result:= 0;
while not l_c_character_iterator.f_is_done do
begin
with l_c_character_iterator.f_c_current_glyph do
Inc(Result, m_width);
l_c_character_iterator.goto_next_glyph;
end; // while not l_c_character_iterator.f_is_done
end; // f_compute_row_minimum_width
procedure push_to_the_right(p_row_minimum_width: Integer);
var l_c_character_iterator: c_composite_iterator;
l_c_glyph: c_glyph;
l_running_x: Integer;
begin
if p_row_minimum_width> p_width
then begin
display('*** not_wide_enough');
Exit;
end;
l_c_character_iterator:= c_composite_iterator.create_composite_iterator('row_iter',
c_glyph(m_c_row_glyph_ref));
l_running_x:= p_width- p_row_minimum_width;
while not l_c_character_iterator.f_is_done do
begin
l_c_glyph:= l_c_character_iterator.f_c_current_glyph;
with l_c_glyph do
begin
m_x:= l_running_x;
Inc(l_running_x, m_width);
end; // with l_c_row_glyph
l_c_character_iterator.goto_next_glyph;
end; // while not l_c_character_iterator.f_is_done
end; // push_to_the_right
var l_row_minimum_width: Integer;
begin // justify_row
l_row_minimum_width:= f_compute_row_minimum_width;
push_to_the_right(l_row_minimum_width);
end; // justify_row
|
- and here is the client code:
procedure c_page_glyph._format_row(p_width: Integer;
p_c_row_justification_strategy: c_abstract_row_justification_strategy);
var l_c_row_iterator: c_composite_iterator;
l_c_row_glyph: c_row_glyph;
begin
l_c_row_iterator:= c_composite_iterator.create_composite_iterator('row_iter', Self);
while not l_c_row_iterator.f_is_done do
begin
l_c_row_glyph:= c_row_glyph(l_c_row_iterator.f_c_current_glyph);
l_c_row_glyph.set_row_justification_strategy(p_c_row_justification_strategy);
p_c_row_justification_strategy.set_row(l_c_row_glyph);
with l_c_row_glyph do
p_c_row_justification_strategy.justify_row(p_width);
l_c_row_iterator.goto_next_glyph;
end; // while not l_c_row_iterator
end; // _format_row
procedure c_page_glyph.format_row_to_the_left(p_width: Integer);
var l_c_row_justification_strategy: c_abstract_row_justification_strategy;
begin
l_c_row_justification_strategy:= c_left_row_justification_strategy.create_left_row_justification_strategy('row_left');
_format_row(p_width, l_c_row_justification_strategy);
l_c_row_justification_strategy.Free;
end; // format_row_to_the_left
procedure c_page_glyph.format_row_to_the_right(p_width: Integer);
var l_c_row_justification_strategy: c_abstract_row_justification_strategy;
begin
l_c_row_justification_strategy:= c_right_row_justification_strategy.create_right_row_justification_strategy('row_right');
_format_row(p_width, l_c_row_justification_strategy);
l_c_row_justification_strategy.Free;
end; // format_row_to_the_right
procedure c_page_glyph.format_row_both_sides(p_width: Integer);
var l_c_both_justification_strategy: c_both_row_justification_strategy;
begin
l_c_both_justification_strategy:= c_both_row_justification_strategy.create_both_row_justification_strategy('both');
_format_row(p_width, l_c_both_justification_strategy);
l_c_both_justification_strategy.Free;
end; // format_row_both_sides
|
And by changing the row justification strategy constructor, it is easy to
apply different justifications.
And here we show the justification in action:
7.4 - Strategy and Composite
Changing justification is easy to change, would'nt you agree ?
Well, looking at the above code, it somehow smells:
- the concrete strategy needs some handle on the structure to do the
computation
- the structure needs the correct strategy reference to apply the correct
formating rule
Hence the mutual initialization:
l_c_row_glyph.set_row_justification_strategy(p_c_row_justification_strategy);
p_c_row_justification_strategy.set_row(l_c_row_glyph);
|
This is a Visitor in disguise !
That is not what the Gof tell us. Reading again and again those pages, my
understanding is as follows:
- the program receives a stream of characters
- the strategy is used to build the column / row structure with different line
breaking strategies.
And they stress the fact that the structure is not known at the client level:
the client sends over the character stream, and the strategy transparently
builds the column / line structure (there is even a graphic, with shading and
all, to hammer this point home).
For the "first time" structure building, this would be all right with me.
However the UML diagram presents the following code snippet:
Glyph.Insert(g, i);
Compositor.Compose();
|
I understand this as
- whenever the user insert a character at the caret position in a text
- insert the character in the tree structure and apply whatever formating
strategy was chosen before the insertion
I fail to see how you can perform any decent formating without intimate
knowledge of the structure. If you add a single character to the end of the
line, this would trigger the flushing of the complete word to the next line,
with possible cascading adjustments up to the end of the paragraph. So you must
have a simple grip on the line structure. The same is true for deleting a
character from the word at the start of a line: in some cases the word should
be appended to the previous line, and the current line reformatted, with a
possible cascade reformatting.
In any case, I tried to implement this "no structure" formating. Whenever we
call the formating, the complete text is formated according to a left / right
or "both side" strategy, and with reorganization of the line structure. The
source of this "no structure" strategy is in the .ZIP. Nothing to be proud of:
each time the formating method is called, a new page is rebuilt from scratch
using a glyph iterator, and, at the end of the procedure, this new page
replaces the old page, which is then somehow destroyed.
Is this another insidious attack against the Gof ? Not at all. What I am
criticizing it the use of a "no structure strategy" pattern for reformatting
text on the run. The Strategy pattern in itself is very useful, and the
concept simple: encapsulate different computations in an abstract class, whose
descendents can be instantiated at run time. Should the Strategy have intimate
knowledge of the structure it operates on: this would depend on the operation.
8 - The Command Pattern
8.1 - The Command CLASS
This is yet another bright idea from Bertrand MEYER.
When in a project you wish to have "undo" capability, you have to remember the
changes, to be able to revert to the previous states. Thats obvious. So you
define:
- a RECORD storing the "before" parameters
- a stack where the RECORDs are pushed, and eventually popped to undo the
changes
Now if the changes come from different processings, you have to create a
different RECORDs for each kind of change.
If you are in the Object Oriented Programming part since a couple of years,
this "multiple record kind stack" is easily transformed in a list of OBJECTs,
using the polymorphic capability of the object oriented structures (tList,
ARRAY or whatever).
But back in 1985, when I first read about placing "Insert", "Append" and
"Delete" in CLASSes, it certainly looked very strange.
Back to Lexi: to be able to have unlimited UNDO:
- we create an abstract c_command CLASS
- each command that must have the UNDO possibility is specified by a derived
class, where the attributes save "enough information" to allow the undoing.
For the insertion of a character, we saved the ASCII code, and the row /
column indices.
- the action is performed
- by pushing the command object on a stack
- by doing the effective work (insert, delete etc)
8.2 - The Delphi Implementation
We implemented the command pattern in the following way:
- Here is the abstract command CLASS:
c_abstract_command= class(c_basic_object)
procedure execu | |