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:
  
  • Introduction
    
  • The description of Lexi
    
  • The Composite Pattern
    
  • The Decorator Pattern
    
  • The Iterator Pattern
    
  • The Visitor Pattern
    
  • The Strategy Pattern
    
  • The Command Pattern
    
  • The Abstract Factory Pattern and the Bridge
    
  • The Source code
    
  • Lessons Learned
    
  • Download the Source Code
    

1 - Introduction

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
  

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

2.2 - Our specification

• 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
  

The user interface will have the following look:

2.3 - The Classes

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
  

3 - The Composite Pattern

3.1 - The 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
  

• the abstract element ancestor (partial):

  c_glyph= class(c_basic_object)             m_x, m_y, m_width, m_height: Integer;             Constructor create_glyph(p_name: String);             procedure draw(p_c_client_region_drawing: c_client_region_drawing); Virtual; Abstract;             function f_bounding_rectangle: tRect; Virtual; Abstract;           end; // c_glyph

  where c_client_region_drawing is a tCanvas encapsulation

• the structure:

  c_composite_glyph= class(c_glyph)                      _m_c_glyph_list: tList;                      Constructor create_composite_glyph(p_name: String);                      function f_glyph_count: Integer;                      function f_c_glyph(p_glyph_index: Integer): c_glyph;                      procedure append_glyph(p_c_glyph: c_glyph); Virtual;                      procedure draw(p_c_client_region_drawing: c_client_region_drawing); Override;                      function f_bounding_rectangle: tRect; Override;                    end; // c_composite_glyph

• the elements (here the character glyph):

  c_character_glyph= class(c_glyph)                      m_font_height: Integer;                      Constructor create_character_glyph(p_name: String;                          p_font_height: Integer);                      procedure draw(p_c_client_region_drawing: c_client_region_drawing); Override;                    end; // c_character_glyph

• pages and rows (here the row):

  c_row_glyph= class(c_composite_glyph)                Constructor create_row_glyph(p_name: String);              end; // c_row_glyph

  
  

• 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

with the corresponding Pascal definitions and declarations:

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)
  

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
  

with the following code:

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

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

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
  

• 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

• 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

  
  

4.3 - CLASSes vs COMPONENTS

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.
  

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:

• the objective of the Delphi delegation was to avoid the proliferation of CLASS definitions:

      tButton1= CLASS(tButton) ...

  like in Object Window Library (OWL was the first Windows Object Library from BORLAND)
  

• in Delphi the tForm is not a "wrapper" around a tButton
  

5 - The Iterator Pattern

5.1 - Iterating over the elements

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:

5.2 - The Iterator Pattern

• goto_first_glyph
  
• f_c_current_glyph
  
• goto_next_glyph
  
• f_is_done
  

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

We used the following composite iterator class (to iterate over ANY composite):

with the following implementation:

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 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

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
    

• 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
    

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

The spell checker is defined as:

and:

with the following client code:

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).
  

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:

which is implemented as:

and is used like this:

6.4 - Visitors

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
  

6.5 - Main Lesson From the Gof

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
  

7 - The Strategy Pattern

7.1 - Formating Text

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

7.3 - Delphi implementation

• 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.
  

7.4 - Strategy and Composite

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
  

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.
  

For the "first time" structure building, this would be all right with me.

However the UML diagram presents the following code snippet:

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
  

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

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
  

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

• Here is the abstract command CLASS:

  c_abstract_command= class(c_basic_object)                       procedure execute_command; Virtual; Abstract;                       function f_is_reversible: Boolean; Virtual; Abstract;                       procedure undo_command; Virtual; Abstract;                      end; // c_abstract_command

• and the command stack:

  c_command_stack= Class(c_basic_object)                    m_c_command_stack: tStringList;                    Constructor create_command_stack(p_name: String);                    function f_command_count: Integer;                    function f_c_command(p_command_index: Integer): c_abstract_command;                    function f_is_empty: Boolean;                    function f_c_push_command(p_c_command: c_abstract_command): c_abstract_command;                    function f_c_peek_command: c_abstract_command;                    function f_c_pop_command: c_abstract_command;                    procedure undo_command;                    Destructor Destroy; Override;                  end; // c_command_stack

• and we show the undo part:

  procedure c_command_stack.undo_command;   var l_c_command: c_abstract_command;   begin     if not f_is_empty       then begin           l_c_command:= f_c_pop_command;           l_c_command.undo_command;           l_c_command.Free;         end;   end; // undo_command

• the concrete insert command is defined by:

  c_insert_command= Class(c_abstract_command)                     m_c_document_ref: c_document;                     // -- m_name contains the name of the character (debug)                     // -- this is the insertion point                     m_row_index, m_column_index: Integer;                     Constructor create_insert_command(p_name: String;                         p_c_document_ref: c_document);                     procedure execute_command; Override;                     procedure undo_command; Override;                   end; // c_command

• and the insertion / undo methods

  procedure c_insert_command.execute_command;   var l_row_index, lcolumn_index: Integer;   begin     with m_c_document_ref do     begin       f_c_insert_leaf_glyph(Self.m_name[1]);       // -- column_index-1 since by now the caret has been moved ahead       m_row_index:= m_c_caret.m_caret_row_index;       m_column_index:= m_c_caret.m_caret_element_index- 1;     end; // with m_c_document_ref   end; // execute_command procedure c_insert_command.undo_command;   var l_c_row_glyph: c_row_glyph;   begin     with m_c_document_ref do     begin       l_c_row_glyph:= m_c_root_page_glyph.f_c_glyph(m_row_index) as c_row_glyph;       l_c_row_glyph.remove_glyph_by_index(m_column_index);       m_c_root_page_glyph.compute_placement;       clear_page;       draw_page_and_caret;     end; // with m_c_document_ref   end; // undo_command

• the client triggers the insertion:

  procedure c_document.do_insert_command(p_character: Char);   var l_c_insert_command: c_insert_command;   begin     l_c_insert_command:= c_insert_command.create_insert_command(p_character, Self);     l_c_insert_command.execute_command;     // -- add the command     m_c_command_stack.f_c_push_command(l_c_insert_command);   end; // do_insert_command

• to undo the insertion (or any other command), the client calls:

  procedure c_document.undo_command_click;   begin     m_c_command_stack.undo_command;   end; // undo_command_click

  
  

9 - The Abstract Factory Pattern and the Bridge Pattern

The main idea, once again, is to build a generic abstract layer, with the specific implementations derived from this abstract layer.

We have implemented those patterns, and they are present in the .ZIP project. But the full presentation of those patterns would burden this paper too much, so this has been presented in a companion paper.

10 - The Source code

10.1 - The file organization

ROOT
      - p_lexi.dpr, u_lexi.pas, u_lexi.dfm: the project, the form
  UNITS
    COMPOSITE
        - u_c_glyph: c_glyph plus c_composite_glyph
        - u_c_glyph_kinds.pas
        - u_c_page_glyph
        - u_c_row_glyph
    DECORATOR
        - u_c_glyph_border_decorator_2.pas
        - u_c_glyph_border_decorator_kinds_2.pas
    ITERATOR
        - u_c_iterator.pas
        - u_c_iterator_kinds.pas
    VISITOR
        - u_c_glyph_count_visitor.pas
        - u_c_spelling_checker_visitor.pas
        - u_c_visitor.pas
    STRATEGY
        - u_c_row_justification.pas
        - u_c_justification_strategy_2.pas
    BRIDGE
        - u_c_bridge_canvas.pas
        - u_c_bridge_drawings.pas
    COMMAND
        - u_c_command.pas
        - u_c_command_kinds.pas
    U_C_DOCUMENT
        - u_c_document.pas
      U_C_CARET
          - u_c_caret.pas
      U_C_SELECTION
          - u_c_selection.pas
    FACTORY
        - u_c_widget_factory.pas
    U_C_CONTROLS
        - u_c_control.pas
        - u_c_pen_brush_stack.pas
        - u_c_round_controls.pas
        - u_c_square_controls.pas

10.2 - Mini Guided Tour

	select the "window implementation" by clicking "square_window_" or "round_window_"
	create the Lexi application by clicking "create_"
	the Lexi widget and the drawing surface will be displayed
	create some text by hitting either "generate_" or "random_"
	the text will be displayed
	try the justification by clicking on the "< justify", "justify >" etc widgets (the page width can be changed in the edit above the Lexi area)
	select an area containing characters with the mouse, then change the font height by clicking the "+" or "-" widgets
	position the caret, and type some text
	click the "rectangle_" or "bitmap_" widget, and type some text
	click the "Esc" widget to undo the insertions

10.3 - Todo

• selection of the bitmap file name
  
• add "controls" for editing values (tEdit)
  
• implement the scrolling in the scroller Decorator
  
• change the font NAME (we only change the size)
  
• add the delete command (we have UNDO, but not DELETE)
  

10.4 - Known bugs

• unimplemented features
  
  • Paint is not considered at all.
    
  • the mouse click assumes that you do not release the mouse outside of the widget where you started the click
    
• bugs. Among those I noticed while writing this paper:
  
  • the layout of glyphs is not totally coherent (in some place we add spade between characters, in other they are glued together)
    
  • justification does not always reset the layout, and currently only works on the "random" text
    
  • the decorator pattern does not delegate enough of the enclosed glyph methods. This will have to be fixed in the next .ZIP release
    

11 - Lessons Learned

11.1 - Performance

• In my first trials, I had spontaneously placed the container structure (the tList) in a c_composite_glyph, instead of placing it at the c_glyph level.

  The Gof Lexi presentation assumes that the composition takes place at the c_glyph level. But in the Composite chapter, they agree that the composition overhead (16 byte for a tList in our case) could be a deterrent, and indicate that this load might be shifted to the c_composite_glyph, which is exactly what I did.

  They also tell us that doing so would complicate the code, since we would have to make the distinction in attributes, ancestors and parameters between c_glyph and c_composite_glyph.

• the Strategy pattern showed that using a single structuring concept (the tree) for Lexi is not necessarily optimal.

  In my opinion, whenever we have to reorganize the lines (hyphenation, cut and paste, duplication etc) the intimate knowledge of the structure would actually simplify the code. If this kind of processing becomes important, the best structure could be an explicit page / column / row structure (page, column and row have their own container data and routines). We could then write:

  FOR l_page_index:= 0 TO f_page_count- 1 DO   FOR l_column_index:= 0 TO f_column_count- 1 DO     FOR l_row_index:= 0 TO f_row_count- 1 DO

  
  

11.2 - The Delphi way

• Casting
  We chose to split the code in units, to isolate each pattern in its own text. Some patterns are even separated in several parts:
  • the abstract ancestor in one unit
    
  • the descendents in one or many other
    
  This is the case for Composite, Iterator, Decorator, Visitor and Command

  Now if there are some cross references between the units, we have a circularity problem on our hands: two Delphi UNITs cannot reference each other in the INTERFACE USES clause. This was the case for

  • Visitor: each visitor contains visit_xxx_glyph(c_xxx_glyph) calls, and the c_glyph contain visit(c_visitor)
    
  • Strategy: the Strategy must know the structure it operates on, and the structure must be able to call the Strategy
    
  There are 2 possible solutions:
  • put the CLASSes in the same unit, and using a forward definition of one of the CLASS
    
  • defining the attribute or parameter as tObject, and casting it into the correct CLASS in the implementation
    
  We chose the second solution. It is not a politically correct as the first one, but preserves the modularity, which in my view is more important than some casting.
  

11.3 - Ambiguities

This explains why in some places, there are some ambiguities concerning Lexi. For instance

• it is not clear whether Lexi should be a "presentation" editor (some kind of Page Maker) or a writing tool (the user inserts text by using a keyboard). This mainly showed up in the Strategy pattern, where handling the first-time formating is much easier than formating a line when a single character at the end of the line could trigger massive reformatting
  

11.4 - The order of development

In any case

• the development took about 2 weeks
  
• I stared to generate some random character and display them in a tPaintBox
  
  • the definition of the Composite tree came first
    
  • the positioning of the random characters in rows came next
    
  • the selection rectangle, with font change showed that the classes had the correct attributes and that the layout methods worked as expected
    
• then I added all the patterns, using the Gof order:
  
  • Decorator, Strategy, Iterator, Visitor
    
  Iterator, which by the way is required by Strategy, was the most difficult of those
  
• at the end I tried the Bridge. This forced a complete rewrite, since the display part had to be reorganized. It took about half of the development time. Not because Bridge is that complex, but because we tried to make it look natural. Pretending you are using X-Windows and Presentation Manager while you are sitting on top of Windows took some effort.
  
• the easy part was Command, and I knew it. The c_caret and c_selection classes were then written
  

11.5 - The natural order

• bypass the Abstract Factory and Bridge, they are a pain in the neck, and how many people really develop for Windows, X Windows and Presentation Manager all the time anyway ?
  But decide at this early stage how you are going to draw your glyphs (pass a tPaintBox to the drawing routines, or only a tCanvas, put a tCanvas reference in each c_glyph or pass it as a parameter etc)
  
• Composite is the mandatory first step
  
• Decorator would be a nice test for the understanding of the Composite
  
• Iterator is the first roadblock. And a tough one on a tree like structure. Iterator will then be used by Visitor and Strategy
  
• from then on, it will be rock, rattle and roll.
  

11.6 - How to learn pattern

Many will argue that by definition, patterns are concepts, and showing code that used those concepts will kill the abstraction. Quite so.

I you want to get familiar with the Design Patterns, my advice would be to put your hands on any of the classical design example (Point of Sale, NextGen from Larman, the Video Sales Shop, Automatic Teller Machine, the Steam Boiler, the Pet Shop from SUN and revised by Microsoft, etc), and do write the code implementing the example, paying special attention to the organization of classes. Using Lexi simplified the pattern part, since the Gof told me where the pattern could be used.

If you do not find any suitable example, why not use the Gof Lexi case study: it worked for me. But be prepared to buy a second Gof book: by the time you are done, your current version will be completely worn out. That is the goal of the exercise, after all.

12 - Download the Source Code

• lexi.zip: the Lexi source code (64 K)
  

• the main program (.DPR, .DOF, .RES), the main form (.PAS, .DFM), and any other auxiliary form
  
• any .TXT for parameters
  
• all units (.PAS) for units
  

• is self-contained: you will not need any other product.
  
• can be used from any folder (the pathes are RELATIVE)
  
• will not modify your PC in any way beyond the path where you placed the .ZIP (no registry changes, no path creation etc).
  

• create or select any folder of your choice
  
• unzip the downloaded file
  
• using Delphi, compile and execute
  

As usual:

• please tell us at fcolibri@felix-colibri.com if you found some errors, mistakes, bugs, broken links or had some problem downloading the file. Resulting corrections will be helpful for other readers
  
• we welcome any comment, criticism, enhancement, other sources or reference suggestion. Just send an e-mail to fcolibri@felix-colibri.com.
  
• or more simply, enter your (anonymous or with your e-mail if you want an answer) comments below and clic the "send" button

  Name :
  E-mail :
  Comments * :

• and if you liked this article, talk about this site to your fellow developpers, add a link to your links page ou mention our articles in your blog or newsgroup posts when relevant. That's the way we operate: the more traffic and Google references we get, the more articles we will write.
  

13 - Conclusion

By the way, the figures presented here have been drawn using Lexi's grand daddy (Fig, a figure editor) which was first written in UCSD Pascal. And the text is written using Lexi's grand grand daddy (Ed, the text editor), which started way back in 1980 as a 6502 assembler program. So, keeping in touch with the evolution of programming concepts was vital to maintain both projects.

And maintenance, as testified by the longevity of both tools, is really the name of the game.

14 - References

• Erich GAMMA, Richard HELM, Ralph JOHNSON, John VLISSIDES
  Design Patterns - Elements of Reusable Object-Oriented Software
      Addison Wesley - 1994 - ISBN 0-201-63361-2
  
• Paul CALDER, Mark LINTON
  The Object Oriented Implementation of a Document Editor
      OOPSLA 1992 - Proceedings pages 154-165 Vancouver - ACM Press
  
• Niklaus Wirth
  Algorithms+ Data Structure= Programming
      Prentice Hall - 1976 - ISBN 0-13-022418-9
  
• Bertrand MEYER
  Object Oriented Software Construction
      Prentice Hall - 1997 (2nd Edition) - ISBN 0-13-629155-4
  
• Bertrand MEYER
  UML, the Positive Spin
      Published in Software Development, Vol. 5 No. 9, September 1997, as "The View from the Eiffel Tower"
      A paper criticising UML
  
• Martin BUCHI, Wolfgang WECK
  Generic Wrapping
      Turku Center for Computer Science, April 2000 Report 317
  

15 - Other Papers with Source and Links

16 - The Author