menu
  index  ==>  papers  ==>  design_patterns  ==>  the_lexi_editor   

Lexi, or the Quest for the Mythical Editor - Felix John COLIBRI.




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 abstract element ancestor (partial):

    c_glyphclass(c_basic_object)
                m_xm_ym_widthm_heightInteger;

                Constructor create_glyph(p_nameString);

                procedure draw(p_c_client_region_drawingc_client_region_drawing); VirtualAbstract;
                function f_bounding_rectangletRectVirtualAbstract;
              end// c_glyph

    where c_client_region_drawing is a tCanvas encapsulation

  • the structure:

    c_composite_glyphclass(c_glyph)
                         _m_c_glyph_listtList;

                         Constructor create_composite_glyph(p_nameString);

                         function f_glyph_countInteger;
                         function f_c_glyph(p_glyph_indexInteger): c_glyph;
                         procedure append_glyph(p_c_glyphc_glyph); Virtual;

                         procedure draw(p_c_client_region_drawingc_client_region_drawing); Override;
                         function f_bounding_rectangletRectOverride;
                       end// c_composite_glyph

  • the elements (here the character glyph):

    c_character_glyphclass(c_glyph)
                         m_font_heightInteger;

                         Constructor create_character_glyph(p_nameString;
                             p_font_heightInteger);

                         procedure draw(p_c_client_region_drawingc_client_region_drawing); Override;
                       end// c_character_glyph

  • pages and rows (here the row):

    c_row_glyphclass(c_composite_glyph)
                   Constructor create_row_glyph(p_nameString);
                 end// c_row_glyph



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_drawingc_client_region_drawing);
      begin
        with p_c_client_region_drawing do
          draw_text(m_xm_ym_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_drawingc_client_region_drawing);
      var l_glyph_indexInteger;
      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_glyphc_page_glyph;
        g_c_client_region_drawingc_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_cellRECORD
               m_pt_lowert_pt_cell;
               m_nameString;
               m_pt_greatert_pt_cell;
             END;
VAR g_pt_roott_pt_cell;

PROCEDURE add_cell(p_nameString);
PROCEDURE list_names_recursive(p_pt_cellt_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_cellCLASS
               m_c_lowerc_cell;
               m_nameString;
               m_c_greaterc_cell;
               PROCEDURE display_cell;
             END;

      c_treeCLASS
                m_c_rootc_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_decoratorclass(c_page_glyph)
                                   _m_c_enclosed_glyphc_page_glyph;

                                   Constructor create_abstract_border_decorator(p_nameString;
                                       p_c_parent_glyphc_glyph;
                                       p_c_enclosed_glyphc_page_glyph);

                                   procedure draw(p_c_client_region_drawingc_client_region_drawing); Override;

                                   // -- replace ALL the functions called for m_c_root_page
                                   procedure append_glyph(p_c_glyphc_glyph); Override;
                                   procedure select_in_rectangle(p_absolute_rectangletRect); Override;
                                   // -- ... ALL the other
                                 end// c_abstract_border_decorator

  • with the following implementation code:

    Constructor c_abstract_border_decorator.create_abstract_border_decorator(p_nameString;
        p_c_parent_glyphc_glyph;
        p_c_enclosed_glyphc_page_glyph);
      begin
        // -- initialize with the enclosing rectangle of the previous enclosed
        with p_c_enclosed_glyph do
          Inherited create_page_glyph(p_namep_c_parent_glyph,
              f_absolute_xf_absolute_ym_width_maxm_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_drawingc_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_glyphc_glyph);
      begin
        _m_c_enclosed_glyph.append_glyph(p_c_glyph);
      end// append_glyph

  • and the "frame" class:

    c_frame_decoratorclass(c_abstract_border_decorator)
                         Constructor create_frame_decorator(p_nameString;
                             p_c_parent_glyphc_glyph;
                             p_c_enclosed_glyphc_page_glyph);
                         procedure draw(p_c_client_region_drawingc_client_region_drawing); Override;
                       end// c_frame_decorator

  • with the corresponding code:

    procedure c_frame_decorator.draw(p_c_client_region_drawingc_client_region_drawing);
      begin
        // -- draw the border
        with p_c_client_region_drawing do
          draw_rectangle(m_xm_ym_width_maxm_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:

  • 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

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

  procedure check_recursive(p_c_glyphc_glyph);
    var l_glyph_indexInteger;
    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_glyphdo
            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_2Boolean;
    // -- an iterator exercise
  var l_c_leaf_iteratorc_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_iteratorclass(c_basic_object)
                       _m_c_glyph_refc_glyph;

                       Constructor create_abstract_iterator(p_nameString;
                           p_c_glyph_refc_glyph);

                       procedure goto_first_glyphVirtualAbstract;
                       procedure goto_next_glyphVirtualAbstract;
                       function f_c_current_glyphVirtualAbstract;
                       function f_is_doneBooleanVirtualAbstract;
                     end// c_abstract_iterator



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

c_composite_iteratorclass(c_abstract_iterator)
                        _m_c_composite_glyph_refc_composite_glyph;
                        m_glyph_indexInteger;

                        Constructor create_composite_iterator(p_nameString;
                            p_c_glyph_refc_glyph);
                        procedure goto_first_glyphOverride;
                        procedure goto_next_glyphOverride;
                        function f_c_current_glyphc_glyphOverride;
                        function f_is_doneBooleanOverride;
                      end// c_composite_iterator

with the following implementation:

Constructor c_composite_iterator.create_composite_iterator(p_nameString;
    p_c_glyph_refc_glyph);
  begin
    Inherited create_abstract_iterator(p_namep_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_iteratorString;
  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_doneBoolean;
  begin
    Result:= m_glyph_index>= _m_c_composite_glyph_ref.f_glyph_count;
  end// f_is_done

function c_composite_iterator.f_c_current_glyphc_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_iteratorc_composite_iterator;
      l_c_current_glyphc_glyph;
      l_c_child_iteratorc_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_glyphc_glyph;
      l_c_child_iteratorc_composite_iterator;
      l_c_composite_iteratorc_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_visitorclass(c_basic_object)
                      procedure visit_character(p_c_character_glyphc_character_glyph); VirtualAbstract;
                      procedure visit_row(p_c_row_glyphc_row_glyph); VirtualAbstract;
                    end// c_abstract_visitor



The spell checker is defined as:

c_simple_spelling_checker_visitorclass(c_abstract_visitor)
                                     m_word_to_checkString;

                                     Constructor create_simle_spelling_checker_visitor(p_nameString);

                                     procedure visit_character(p_c_character_glyphc_character_glyph); Override;
                                   end// c_spelling_checker_visitor

and:

procedure c_spelling_checker_visitor.visit_character(p_c_character_glyphc_character_glyph);
  var l_characterChar;
  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_checkl_character;
  end// visit_character

with the following client code:

procedure c_page_glyph.check_spelling;
  var l_c_leaf_iteratorc_leaf_iterator;
      l_c_spelling_checker_visitorc_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_visitorclass(c_abstract_visitor)
                              m_word_to_checkString;

                              Constructor create_spelling_checker_visitor(p_nameString);

                                procedure _check_the_word;
                              procedure visit_character(p_c_character_glyphc_character_glyph); Override;
                              procedure visit_row(p_c_row_glyphc_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_glyphc_character_glyph);
  var l_characterChar;
  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_checkl_character;
  end// visit_character

procedure c_spelling_checker_visitor.visit_row(p_c_row_glyphc_row_glyph);
  begin
    _check_the_word;
  end// visit_row

and is used like this:

procedure c_page_glyph.check_spelling;
  var l_c_leaf_iteratorc_leaf_iterator;
      l_c_current_glyphc_glyph;
      l_c_spelling_checker_visitorc_spelling_checker_visitor;
      l_c_current_rowl_c_previous_rowc_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<> Niland (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_refc_row_glyph_ref;

            procedure set_row(p_c_row_glyph_reftObject);
            procedure justify_row(p_widthInteger); VirtualAbstract;
          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_nameString);
            procedure justify_row(p_widthInteger); Override;
          end// c_right_row_justification_strategy

    with the following implementation:

    procedure c_right_row_justification_strategy.justify_row(p_widthInteger);
        // -- push everything to the right

      function f_compute_row_minimum_widthInteger;
        var l_c_character_iteratorc_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(Resultm_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_widthInteger);
        var l_c_character_iteratorc_composite_iterator;
            l_c_glyphc_glyph;
            l_running_xInteger;
        begin
          if p_row_minimum_widthp_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_widthp_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_xm_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_widthInteger;

      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_widthInteger;
        p_c_row_justification_strategyc_abstract_row_justification_strategy);
      var l_c_row_iteratorc_composite_iterator;
          l_c_row_glyphc_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_widthInteger);
      var l_c_row_justification_strategyc_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_widthl_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_widthInteger);
      var l_c_row_justification_strategyc_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_widthl_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_widthInteger);
      var l_c_both_justification_strategyc_both_row_justification_strategy;
      begin
        l_c_both_justification_strategy:= c_both_row_justification_strategy.create_both_row_justification_strategy('both');
        _format_row(p_widthl_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(gi);
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_commandclass(c_basic_object)
                          procedure execu