This chapter is the last one in our second lecture about inheritance. The chapter is about patterns and programming techniques related to inheritance. Similar chapters appeared in Chapter 16 and Chapter 24 for classes/objects and for operations respectively.

32.1 The Composite design pattern 32.9 The fragile base class problem 32.2 A Composite Example: Music Elements 32.10 Factory design patterns 32.3 An application of Music Elements 32.11 The design pattern Factory Method 32.4 Implementation of MusicElement classes 32.12 The Visitor design pattern 32.5 A Composite Example: A GUI 32.13 Natural object-oriented IntSequence traversals 32.6 Cloning 32.14 Towards a Visitor solution 32.7 Cloning in C# 32.15 A Visitor example: IntSequence 32.8 Cloning versus use of copy constructors 32.16 Visitors - Pros and Cons

 

32.1.  The Composite design pattern
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The Composite design pattern, which we are about to study, is probably the most frequently occurring GOF design pattern at all. Most real-life programs that we write benefit from it. Recall from Section 16.2 that the GOF design patterns are the ones described in the original design pattern book [Gamma96].

A Composite deals with hierarchical structures of objects. In more practical terms, the pattern deals with tree-tructures whose nodes are objects. The main idea behind the pattern is to provide a uniform interface to both leaves and inner nodes in the tree.

From a client point of view, it is easy to operate on the nodes of a Composite. The reason is that all participating objects share the interface provided by the abstract Component class.

Figure 32.1    A template of the class structure in the Composite design pattern.

In Figure 32.1 we show the three classes that - at the principled level - make up a Composite: The abstract class Component and its two subclasses Leaf and Composite. The important things to notice are:

• The diagram in Figure 32.1 is a class diagram, not an object diagram.
• Clients access both Leaf nodes and Composite nodes (inner nodes in the tree) via the interface provided by the abstract class Component .
• The Composite (inner) node aggregates one or more Components , either Leaf nodes or (recursively) other Composite nodes. This makes up the tree structure. It is important the you are able to grasp the idea that the aggregation in Figure 32.1 gives rise to a recursive tree structure of objects.

In the following sections we will study an example of a composite design pattern which allows us to represent songs of notes and pauses. In appendix Section 58.3 we discuss another example, involving a sequence of numbers and the type Interval.

32.2.  A Composite Example: Music Elements
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The example in this section stems from the mini project programming (MIP) exam of January 2008 [mip-jan-08]. Imagine that we are interested in a representation of music in terms of notes and pauses. Such a representation can - in a natural way - be described as a Composite, see Figure 32.2. In this composite structure, both a Note and a Pause are MusicElements. A SequentialMusicElement consists of a number of MusicElements, such as Notes, Pauses, and other MusicElements. The immediate constituents of a SequentialMusicElement are played sequentially, one after the other. A ParallelMusicElement is composed similar to SequentialMusicElement. The immediate constituents of a ParallelMusicElement are played at the same time, however.

Figure 32.2    The class diagram of Music Elements

As we will see in Program 32.3 a Note is characterized by a duration, value, volume, and instrument. A Pause is characterized by a duration. As such, it may make sense to have a common superclass of Note and Pause. In the same way, it may be considered to have a common superclass of SequentialMusicElement and ParallelMusicElement which captures their common aggregation of MusicElements.

A number of different operations can be applied uniformly on all MusicElements: Play, Transpose, TimeStretch, NewInstrument, Fade, etc. Below, in Program 32.3 we program the operations Linearize, Duration, and Transpose. The Linearize operations transforms a music element to a sequence of lower-level objects which represent MIDI events. A sequence of MIDI events can be played on most computers. In this way, Linearize becomes the indirect Play operation.

32.3.  An application of Music Elements
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

As we already realized in Section 32.1 the objects in a Composite are organized in a tree structure. In Figure 32.3 we show an example of a SequentialMusicElement. When we play the SequentialMusicElement in Figure 32.3 we will first hear note N1. After N1 comes a pause P followed by the notes N2 and N3. Following N3 we will hear N4, N5 and N6 which are all played simultaneously. As such, N4-N6 may form a musical chord. A playable MIDI file similar to Figure 32.3 illustrates these observations [midi-sample].

Figure 32.3    A possible tree of objects which represent various music elements. Nodes named Ni are Note instances, and the node named P is a Pause instance

Below, in Program 32.1 we show a program that creates a SequentialMusicElement similar to the tree-structure drawn in Figure 32.3 The program relies on the auxiliary class Song. The class Song and another supporting class TimedNote are available to interested readers [song-and-timednote-classes]. Using these two classes it is easy to generate MIDI files from MusicElement objects.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class Application{

  public static void Main(){

    MusicElement someMusic =
     SequentialMusicElement.MakeSequentialMusicElement(
       SequentialMusicElement.MakeSequentialMusicElement(
         new Note(60, 480),      
         new Pause(480),     
         new Note(64, 480), 
         new Note(60, 480)),
       ParallelMusicElement.MakeParallelMusicElement(
         new Note(60, 960),
         new Note(64, 960),
         new Note(67, 960)
       ));

    Song aSong = new Song(someMusic.Linearize(0));
    aSong.WriteStandardMidiFile("song.mid");
  }
}

32.4.  Implementation of MusicElement classes
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In this section we show an implementation of the MusicElement classes of Figure 32.2. The classes give rise to non-mutable objects, along the lines of the discussion in Section 12.5.

We start by showing the abstract class MusicElement, see Program 32.2. It announces the property Duration, the method Transpose, and the method Linearize. Other of the mentioned music-related operations are not included here. As you probably expect, Duration returns the total length of a MusicElement. Transpose changes the value (the pitch) of a MusicElement. Linearize transforms a MusicElement to an array of (lower-level) TimeNote objects [song-and-timednote-classes].

1
2
3
4
5
6
7
8
9
10

public abstract class MusicElement{

  public abstract int Duration{
    get;
  }

  public abstract MusicElement Transpose(int levels);

  public abstract TimedNote[] Linearize(int startTime);
}

The class Note is shown next, see Program 32.3. Note encapsulates the note value, duration, volume, and instrument (see line 5-8). Following two constructors, we see the property Duration which simply returns the value of the instance variable duration. The method Linearize carries out the transformation of the Note to a singular array of TimedNote. The Transpose method adds to the value of the Note. The shown activation of ByteBetween enforces that the value is between 0 and 127.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

using System;

public class Note: MusicElement{
  
  private byte value;
  private int duration;
  private byte volume;
  private Instrument instrument;

  public Note(byte value, int duration, byte volume, 
              Instrument instrument){
    this.value = value;
    this.duration = duration;
    this.volume = volume;
    this.instrument = instrument;
  }

  public Note(byte value, int duration):
   this(value, duration, 64, Instrument.Piano){
  }

  public override int Duration{
    get{
      return duration;
    }
  }

  public override TimedNote[] Linearize(int startTime){
    TimedNote[] result = new TimedNote[1];
    result[0] = new TimedNote(startTime, value, duration, volume, 
                              instrument);
    return result;
  }

  public override MusicElement Transpose(int levels){
     return new Note(Util.ByteBetween(value + levels, 0, 127),
                     duration, volume, instrument);
  }
}

The class Pause shown in Program 32.4 is almost trivial.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

using System;

public class Pause: MusicElement{
  
  private int duration;

  public Pause(int duration){
    this.duration = duration;
  }

  public override int Duration{
    get{
      return duration;
    }
  }

  public override TimedNote[] Linearize(int startTime){
    return new TimedNote[0];
  }

  public override MusicElement Transpose(int levels){
     return new Pause(this.Duration);
  }
}

The class SequentialMusicElement represents the sequence of MusicElements as a list of type List<T>. Besides the constructor, SequentialMusicElement offers a factory method for convenient creation of an instance. Factory methods have been discussed in Section 16.4. Program 32.1 shows how the factory method can be applied. Duration adds the duration of the MusicElement parts together. Notice that this may cause recursive addition. Likewise, Transpose carries out recursive transpositions of the MusicElement parts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

using System;
using System.Collections.Generic;

public class SequentialMusicElement: MusicElement{
  private List<MusicElement> elements;
  
  public SequentialMusicElement(MusicElement[] elements){
    this.elements = new List<MusicElement>(elements);
  }

  // Factory method:
  public static MusicElement 
    MakeSequentialMusicElement(params MusicElement[] elements){
      return new SequentialMusicElement(elements);
  }

  public override TimedNote[] Linearize(int startTime){
    int time = startTime;
    List<TimedNote> result = new List<TimedNote>();
    
    foreach(MusicElement me in elements){
      result.AddRange(me.Linearize(time));
      time = time + me.Duration;
    }

    return result.ToArray();
  }

  public override int Duration{
    get{
      int result = 0;
   
      foreach(MusicElement me in elements){
        result += me.Duration;
      }
 
      return result;
    }
  }

  public override MusicElement Transpose(int levels){
    List<MusicElement> transposedElements = new List<MusicElement>();

    foreach(MusicElement me in elements)
      transposedElements.Add(me.Transpose(levels));
    
    return new SequentialMusicElement(transposedElements.ToArray());
  }
}

The class ParallelMusicElement resembles SequentialMusicElement a lot. Notice, however, the different implementation of Duration in line 29-39.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

using System;
using System.Collections.Generic;

public class ParallelMusicElement: MusicElement{
  private List<MusicElement> elements;
  
  public ParallelMusicElement(MusicElement[] elements){
    this.elements = new List<MusicElement>(elements);
  }

  // Factory method:
  public static MusicElement 
    MakeParallelMusicElement(params MusicElement[] elements){
      return new ParallelMusicElement(elements);
  }  

  public override TimedNote[] Linearize(int startTime){
    int time = startTime;
    List<TimedNote> result = new List<TimedNote>();
    
    foreach(MusicElement me in elements){
      result.AddRange(me.Linearize(time));
      time = startTime;
    }

    return result.ToArray();
  }

  public override int Duration{
    get{
      int result = 0;
   
      foreach(MusicElement me in elements){
        result = Math.Max(result, me.Duration);
      }
 
      return result;
    }
  }

  public override MusicElement Transpose(int levels){
    List<MusicElement> transposedElements = new List<MusicElement>();

    foreach(MusicElement me in elements)
      transposedElements.Add(me.Transpose(levels));
    
    return new ParallelMusicElement(transposedElements.ToArray());
  }
}

This completes our discussion of the MusicElement composite. The important things to pick up from the example are:

1. The tree structure of objects defined by the subclasses of MusicElement .
2. The uniform interface of music-related operations provided to clients of MusicElement .

As stressed in Section 32.1 these are the primary merits of Composite.

In Section 58.3 of the appendix we present an additional and similar example of a composite which involves an Interval. Interval is the type we encountered in Section 21.3 when we discussed operator overloading.

32.5.  A Composite Example: A GUI
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We will study yet another example of a Composite design pattern. A graphical user interface (GUI) is composed of a number of forms, such as buttons and textboxes. The classes behind these forms make up a Composite design pattern.

Figure 32.4    A Form (Window) with two buttons, a textbox, and a panel.

We construct the simple GUI depicted in Figure 32.4. The actual hierarchy of objects involved are shown in Figure 32.5. Thus, the GUI is composed of three buttons (yellow, green, and blue) and two textboxes (white and grey). The blue button and the grey textbox are aggregated into a so-called panel (which has red background in Figure 32.4).

Figure 32.5    The tree of objects behind the graphical user interface. These objects represents a composite design pattern in an executing program.

The Form class hierarchy of .NET and C# is very large. A small extract is shown in Figure 32.6. Apart from class Component, all classes are from the namespace System.Windows.Forms.

There are two Composites in Figure 32.6. The first one is (object) rooted by class Form, which may aggregate an arbitrary number of Windows form objects. The class Form represents a window. The class Control is the superclass of GUI elements that displays information on the screen. There are approximate 25 immediate and direct subclasses of class Control. In reality the classes TextBox, Button, and Panel are all indirect subclasses of Control.

The other Composite is, symmetrically, (object) rooted by Panel, which like Form may aggregate an arbitrary number of Form objects. Class Pane is intended for grouping of a collection of controls.

Figure 32.6    An extract of the Windows Form classes for GUI building. We see two Composites among these classes.

Below, in Figure 32.6 we show how to construct the form object tree shown in Figure 32.5, which gives rise to the GUI of Figure 32.4. We program a class which we name Window. Our Window class inherits from class Form. Thus, our Window is a Form. Shown in blue we highlight instantiation of GUI elements. Shown in purple we highlight the actual construction of the tree structure of Figure 32.5. The Controls property of a Form, referred in line 60 - 67, give access to a collection of controls, of type ControlCollection.

As it appears in line 23 and 31, we also add a couple of event handlers, programmed as private methods from line 70 - 83. We have discussed event handlers in Chapter 23. The associated event handlers just acknowledge when we click on of the three buttons of the GUI.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

using System;
using System.Windows.Forms;
using System.Drawing;

// In System:
// public delegate void EventHandler (Object sender, EventArgs e)

public class Window: Form{

  Button b1, b2, paBt;
  Panel pa;
  TextBox tb, paTb;

  // Constructor
  public Window (){
    this.Size=new Size(150,300);

    b1 = new Button();
    b1.Text="Click Me";
    b1.Size=new Size(100,25);
    b1.Location = new Point(25,25);
    b1.BackColor = Color.Yellow;
    b1.Click += ClickHandler; 
                              // Alternatively:
                              // b1.Click+=new EventHandler(ClickHandler);
    b2 = new Button();
    b2.Text="Erase";
    b2.Size=new Size(100,25);
    b2.Location = new Point(25,55);
    b2.BackColor=Color.Green; 
    b2.Click += EraseHandler; 
                              // Alternatively:
                              // b2.Click+=new EventHandler(EraseHandler);
    tb = new TextBox();
    tb.Location = new Point(25,100);
    tb.Size=new Size(100,25);
    tb.BackColor=Color.White;
    tb.ReadOnly=true;
    tb.RightToLeft=RightToLeft.Yes;

    pa = new Panel();
    pa.Location = new Point(25,150);
    pa.Size=new Size(100, 75);
    pa.BackColor=Color.Red;

    paBt = new Button();
    paBt.Text="A";
    paBt.Location = new Point(10,10);
    paBt.Size=new Size(25,25);
    paBt.BackColor=Color.Blue; 
    paBt.Click += PanelButtonClickHandler;

    paTb = new TextBox();
    paTb.Location = new Point(10,40);
    paTb.Size=new Size(50,25);
    paTb.BackColor=Color.Gray;
    paTb.ReadOnly=true;
    paTb.RightToLeft=RightToLeft.Yes;

    this.Controls.Add(b1);
    this.Controls.Add(b2);
    this.Controls.Add(tb);

    pa.Controls.Add(paBt);
    pa.Controls.Add(paTb);

    this.Controls.Add(pa);
  }

  // Eventhandler:
  private void ClickHandler(object obj, EventArgs ea) {
    tb.Text = "You clicked me";
  }

  // Eventhandler:
  private void PanelButtonClickHandler(object obj, EventArgs ea) {
    paTb.Text += "A";
  }

  // Eventhandler:
  private void EraseHandler(object obj, EventArgs ea) {
    tb.Text = "";
  }

}

class ButtonTest{

  public static void Main(){
    Window win = new Window();
    Application.Run(win);
  }

}

32.6.  Cloning
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We briefly discussed copying of objects in Section 13.4 of the lecture about classes and objects. In this section we will continue this discussion. First we will distinguish between different types of object copying. Later, in Section 32.7, we will see how to enable the pre-existing MemberwiseClone operation to client classes.

Instead of the word "copy" we often use the word "clone":

There are different kinds of cloning, distinguished by the copying depth:

Shallow cloning: Instance variables of value type: Copied bit-by-bit Instance variables of reference types: The reference is copied The object pointed at by the reference is not copied Deep cloning: Like shallow cloning But objects referred by references are copied recursively

Shallow cloning is the variant supported by the MemberwiseClone operation in Section 32.7. Only a single object is copied.

Deep cloning copies a network of objects, and it may, in general, involve many objects.

Recall that cloning is only relevant for instances of classes, for which reference semantics apply (see Chapter 13). Values of structs obey value semantics, and as such struct values are (shallow) copied by assignments and by parameter passing. See Chapter 14 for additional details.

32.7.  Cloning in C#
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Shallow cloning is supported "internally" by any object in a C# program execution. The reason is that any object inherit from class Object in which the protected method MemberwiseClone implements shallow cloning. (See Section 28.3 for an overview of the methods in class Object ). Recall from Section 27.3 that a protected method of a class C is visible in C and in the subclasses of c, but not in clients of C.

In this section we will see how we can unleash the protected MemberwiseClone operation as a public operation of an arbitrary class.

Below, in Program 32.8 we show how to implement a cloneable Point class. First, notice that Point implements the interface ICloneable, which prescribes a single method called Clone. We have already in Section 31.4 seen ICloneable in the context of other flavoring interfaces from the C# libraries. The public method Clone of class Point, shown in purple, delegates its work to the protected method MemberwiseClone. In other words, our Clone methods send a MemberwiseClone message to the current Point object. MemberWiseClone makes the bitwise, shallow copy of the point, and it returns it. Notice that from a static point of view, the returned object is of type Object. As we will see below, this will typically imply a need to cast the returned object to a Point.

Although a Clone method typically delegates its work to MemberwiseClone, it is not necessary to do so. Clone may, alternatively, use a constructor and appropriate object mutations in order to produce the copy, which makes sense for the class in question (which is class Point in the example shown below).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

using System;

public class Point: ICloneable {
  private double x, y;

  public Point(double x, double y){
   this.x = x; this.y = y;
  }

  public double X {
    get {return x;}
    set {x = value;}
  }

  public double Y {
    get {return y;}
    set {y = value;}
  }

  public Point move(double dx, double dy){
    Point result = (Point)MemberwiseClone();  // cloning from within Point is OK.
    result.x = x + dx;
    result.y = y + dy;   
    return result;
  }

  // public Clone method that delegates the work of
  // the protected method MemberwiseClone();       
  public Object Clone(){
    return MemberwiseClone();
  }

  public override string ToString(){
    return "Point: " + "(" + x + "," + y + ")" + ".";
  }
}

In Program 32.9 we show how a client of class Point uses the implemented Clone operation. Notice the casting, and notice that the subexpression p1.Clone() is evaluated before the casting. (A possible misconception would be that (Point)p1 is evaluated first). The evaluation order is due to the precedence of the cast operator in relation to the precedence of the dot operator, see Table 6.1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

using System;

public class Application{

  public static void Main(){
    Point p1 = new Point(1.1, 2.2),
          p2, p3;

    p2 = (Point)p1.Clone();  // First p1.Clone(), then cast to Point.
    p3 = p1.move(3.3, 4.4);
    Console.WriteLine("{0} {1} {2}", p1, p2, p3);
  }

}

It may be tempting to circumvent the ICloneable interface, the implementation of our own clone operation, and delegation to MemberwiseClone. This temptation is illustrated in Program 32.10. The compiler will find out, and it tells that we cannot just call MemberwiseClone, because it is not a public operation.

Why make life so difficult? Why not support shallow copying of all objects in an easy way, by making MemberwiseClone public in class Object? The reason is that the designers of the programming language (C#, and Java as well) have decided that the programmer of a class should make an explicit decision about which objects should be cloneable.

There are almost certainly some classes for which we do not want copying of instances, singletons (see Section 16.3 ) for instance. There are also some classes in which we do not want the standard bitwise copying provided by MemberwiseClone. Such classes should behave like Program 32.8 shown above, but instead of delegating the cloning to MemberwiseClone, the copy operation should be programmed in the Clone method to suit the desired copying semantics.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

using System;

public class Application{

  public static void Main(){
    Point p1 = new Point(1.1, 2.2),
          p2, p3;

    p2 = (Point)p1.MemberwiseClone();  
    // Compile-time error.
    // Cannot access protected member 'object.MemberwiseClone()'
    // via a qualifier of type 'Point'

    p3 = p1.move(3.3, 4.4);
    Console.WriteLine("{0} {1} {2}", p1, p2, p3);
  }

}

32.8.  Cloning versus use of copy constructors
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

In Section 32.7 we found out that cloning of class instances - on purpose - is rather cumbersome in C#. Therefore we have earlier recommended the use of copy constructors as an alternative means. See Section 12.5 for details and for an example.

In this section we will evaluate and exemplify the power of copying by cloning (as in Section 32.7) relative to copying by use of copy constructors.

In a nutshell, the insight can be summarized in this way:

In order to illustrate the differences between cloning (by use of the clone method) and copying (by use of a copy constructor) we will again use the class Point. Below, in Section 32.7 we show a version similar to Program 32.8 but now with an additional copy constructor (line 12 - 14).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

using System;
using System.Drawing;

public class Point: ICloneable {
  protected double x, y;

  public Point(double x, double y){
   this.x = x; this.y = y;
  }

  // Copy constructor
  public Point(Point p){
   this.x = p.x; this.y = p.y;
  }

  public virtual double X {
    get {return x;}
    set {x = value;}
  }

  public virtual double Y {
    get {return y;}
    set {y = value;}
  }

  public virtual Point move(double dx, double dy){
    Point result = (Point)MemberwiseClone();  // cloning from within Point is OK.
    result.x = x + dx;
    result.y = y + dy;   
    return result;
  }

  // public Clone method that delegates the work of
  // the protected method MemberwiseClone();       
  public virtual Object Clone(){
    return MemberwiseClone();
  }

  public override string ToString(){
    return "Point: " + "(" + x + "," + y + ")" + ".";
  }
}

We also show a subclass of Point called ColorPoint, see Program 32.12. It adds a color instance variable to the instance variables inherited from class Point, and it has its own copy constructor in line 10 - 13.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class ColorPoint: Point{
  protected Color color;

  public ColorPoint(double x, double y, Color c):
      base(x,y){
    this.color = c;
  }

  // Copy constructor
  public ColorPoint(ColorPoint cp):
      base(cp.x,cp.y){
    this.color = cp.color;
  }

  // Clone method is inherited

  public override string ToString(){
    return "ColorPoint: " + "(" + x + "," + y + ")" + ":" + color;
  }
}

In the Color and ColorPoint client program, shown below in Program 32.13, you should focus on the list pointList, as declared in line 14. We add two Point objects and two ColorPoint objects to pointList in line 17 - 20. Next, in the foreach loop starting at line 23 we clone each of the four points in the list, and we add the cloned points to the initially empty list clonedPointList. The elements in clonedPointList are printed at the end of the program. The output - see Listing 32.14 - reveals that the cloning is successful. We end up having two Point instances and two ColorPoint instances in clonedPointList.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

using System;
using System.Drawing;
using System.Collections.Generic;

public class Application{

  public static void Main(){
    Point p1 =       new Point(1.1, 2.2),
          p2 =       new Point(3.3, 4.4);

    ColorPoint cp1 = new ColorPoint(5.5, 6.6, Color.Red),
               cp2 = new ColorPoint(7.7, 8.8, Color.Blue);

    List<Point> pointList = new List<Point>(),
                clonedPointList = new List<Point>();

    pointList.Add(p1);
    pointList.Add(cp1);
    pointList.Add(p2);
    pointList.Add(cp2);

    // Clone the points in pointList and add them to clonedPointList: 
    foreach(Point p in pointList){
      clonedPointList.Add((Point)(p.Clone()));
    }

    foreach(Point p in clonedPointList)
      Console.WriteLine("{0}", p);

  }
}

1
2
3
4

Point: (1,1,2,2).
ColorPoint: (5,5,6,6):Color [Red]
Point: (3,3,4,4).
ColorPoint: (7,7,8,8):Color [Blue]

Let us now attempt to replicate the functionality of Program 32.13 with use of copy constructors, see Program 32.15. The attempt, shown in Program 32.15 in line 24 - 26 fails, because the activation of the copy constructors deliver Point objects, even if a ColorPoint object is passed as input. Instead we must perform explicit type dispatch, as shown in line 29-34. Clearly, constructors cannot exhibit virtual behavior.

The solution in Program 32.13 based on the Point and ColorPoint classes in Program 32.11 and Program 32.12 works because the Clone method in Program 32.11 (line 35 - 37) is inherited by ColorPoint. As already explained, the inherited method delegates its work to MemberwiseClone, which always copies its receiver. Thus, if MemberwiseClone is activated on a ColorPoint object it copies a ColorPoint object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

using System;
using System.Drawing;
using System.Collections.Generic;

public class Application{

  public static void Main(){
    Point p1 =       new Point(1.1, 2.2),
          p2 =       new Point(3.3, 4.4);

    ColorPoint cp1 = new ColorPoint(5.5, 6.6, Color.Red),
               cp2 = new ColorPoint(7.7, 8.8, Color.Blue);

    List<Point> pointList = new List<Point>(),
                clonedPointList = new List<Point>();

    pointList.Add(p1);
    pointList.Add(cp1);
    pointList.Add(p2);
    pointList.Add(cp2);

//  Cannot copy ColorPoint objects with copy constructor of Point.
//  Compiles and runs, but gives wrong result.
//  foreach(Point p in pointList){
//    clonedPointList.Add(new Point(p));
//  }

    // Explicit type dispatch:
    foreach(Point p in pointList){
      if (p is ColorPoint)
        clonedPointList.Add(new ColorPoint((ColorPoint)p));  
      else if (p is Point)
        clonedPointList.Add(new Point(p));
    }

    foreach(Point p in clonedPointList)
      Console.WriteLine("{0}", p);

  }
}

32.9.  The fragile base class problem
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

As the next part of this Pattern and Techniques chapter we will study the so-called fragile base class problem.

The problem can be summarized in this way:

The program in Program 32.16 is a principled ABC example. B is a subclass of A, and B has a dangerous method M2. As a dangerous method, clients of class B must be fully aware that M2 is called, because it can have serious consequences. (A possible serious consequence may be to erase the entire harddisk). As illustrated in the Client class, M2 can only be activated on a B object.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Original program. No problems.

using System;

class A {

  public void M1(){
    Console.WriteLine("Method 1");
  }
}

class B: A {
  
  public void M2(){
    Console.WriteLine("Dangerous Method 2");
  }
}

class Client{
  
  public static void Main(){
    A a = new B();
    B b = new B();

    a.M1();  // Nothing dangerous expected
//  a.M2();  // Compile-time error
             // 'A' does not contain a definition for 'M2'
    b.M2();  // Expects dangerous operation
  }
}

Let us now assume that we replace class A with a new version with the following changes:

1. A new virtual method M2 is added to A.
2. The existing method M1 in A now calls M2

This is shown in Program 32.17.

We will, in addition, assume that all involved methods (M1 and M2) are virtual, and that M2 in B overrides M2 in A. In C# this is not a natural assumption, but in Java this is the default semantics (and the only possible semantics).

It is purely accidental that the new method in class A has the same name as the dangerous method M2 in class B.

In the Client class in Program 32.17 a.M1() will - unexpectedly - call the dangerous method M2 in class B, because the variable a has dynamic type B. Similarly, a.M2() calls M2 in B. The programmer, who wrote class A, expected that the expression a.M1() would call the sibling method M2 in class A! This could come as an unpleasant surprise.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

// Dangerous program.
// M2 is virtual in A and overridden in B.
// Compiles and runs
// Default Java semantics.

using System;

// New version of A
class A {

  public void M1(){
    Console.WriteLine("Method 1");
    this.M2();
  }

  // New method in this version.
  // Same name as the dangerous operation in subclass B
  public  virtual  void M2(){
    Console.WriteLine("M2 in new version of A");
  }

}

class B: A {

  public override void M2(){
    Console.WriteLine("Dangerous Method 2");
  }
}

class Client{
  
  public static void Main(){
    A a = new B();
    B b = new B();

    a.M1();  // Nothing dangerous expected
             // Will, however, call the dangerous operation
             // because M2 is virtual.

    a.M2();  // Makes sense when M2 exists in class A.
             // Calls the dangerous method

    b.M2();  // Calls the dangerous method.
             // This is expected, however.
  }
}

1
2
3
4

Method 1
Dangerous Method 2
Dangerous Method 2
Dangerous Method 2

If we, in C#, just add the M2 method to class A, and change M1 such that it calls M2, as shown in Program 32.19 (only on web) it is not possible to compile class B. The problem is that we have a method, named M2 in both class A and B. This is the problem that we have discussed in Section 28.9. The programmer should decide if M2 in B should be declared as new, or if it should override M2 from class A. In the latter case, M2 in A must be declared as virtual.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// We have added M2 to class A.
// In addtion, M1 now calls M2.
// Does not compile.

using System;

// New version of A
class A {

  public void M1(){
    Console.WriteLine("Method 1");
    this.M2();
  }

  // New method in this version.
  // Same name as the dangerous operation in subclass B
  public void M2(){
    Console.WriteLine("M2 in new version of A");
  }

}

class B: A {
  
  // Compile-time error in C#:
  // 'B.M2()' hides inherited member 'A.M2()'.
  //     Use the new keyword if hiding was intended.
  public void M2(){
    Console.WriteLine("Dangerous Method 2");
  }
}

class Client{
  
  public static void Main(){
    A a = new B();
    B b = new B();

    a.M1();  // Nothing dangerous expected.
             // Will, however, call the dangerous operation
             // if M2 is regarded as virtual.

    a.M2();  // Makes sense when M2 exists in class A.
             // Dangerous

    b.M2();  // Expects dangerous operation
  }
}

Below, in Program 32.20 we show the situation where M2 in class B hides (is new) relative to M2 in class A. Notice, from the program output shown in Listing 32.21 that a1.M1() in this case activates M2 in class A. In other words, this setup does not lead to the trap discussed above.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// Non-Dangerous program.
// Compiles and runs.
// M2 is declared new in B.
// A.M2 is not virtual.

using System;

// New version of A
class A {

  public void M1(){
    Console.WriteLine("Method 1");
    this.M2();
  }

  // New method in this version.
  // Same name as the dangerous operation in subclass B
  // M2 is not virtual.
  public void M2(){
    Console.WriteLine("M2 in new version of A");
  }

}

class B: A {

  public  new  void M2(){
    Console.WriteLine("Dangerous Method 2");
  }
}

class Client{
  
  public static void Main(){
    A a = new B();
    B b = new B();

    a.M1();  // Nothing dangerous expected
             // Will call a.M2 - the non-dangerous version

    a.M2();  // Makes sense when M2 exists in class A
             // Will call a.M2 - the non-dangerous version

    b.M2();  // Expects dangerous operation
  }
}

1
2
3
4

Method 1
M2 in new version of A
M2 in new version of A
Dangerous Method 2

The fragile base class problem illustrates a danger of using virtual methods (dynamic binding) all over the place. In rare situations, as the one constructed in Program 32.17, it may lead to dangerous results. To summarize, the problem arises if a method in a subclass is unintentionally called instead of a method in a superclass. In C#, both the superclass and the subclass must specify if dynamic binding should take place. In the superclass the involved method must be virtual, and in the subclass the method must use the override modifier. Alternatively, we may opt for static binding, as in Program 32.20. As illustrated by Program 32.19 the C# programmer is likely to get a warning in case he or she approaches the fragile base class problem.

32.10.  Factory design patterns
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Instantiation of classes is done by the new operator (see Section 6.7) in cooperation with a constructor (see Section 12.4). Imagine that we need numerous instances of class C in a large program. This would lead to a situation where there appears may expressions of the form new C(...) in the program. Why can this be considered as a problem?

One problem with many occurrences of new C(...) is if we - eventually - would like to instantiate another class, say a subclass of C. In this situation we would prefer to make one change at a single place in the program, instead of a spread of changes throughout the program.

Another problem may occur if we need two or more constructors which we cannot easily distinguish by the formal parameters of the constructors. We have seen examples of such situations in Section 16.4.

As yet another problem, we may wish to introduce good names for object instantiations, beyond the possibilities of constructors.

Various uses of factory methods can be seen as solutions to the problems pointed out above. We will distinguish between the following variations of factory methods:

Factory methods implemented with class methods (static methods) in C, or in another class The design pattern Factory Method which handles instantiation in instance methods of client subclasses Relies on instance methods in class hierarchies with virtual methods The design pattern Abstract Factory which is good for instantiation of product families Relies on instance methods in class hierarchies with virtual methods

As already pointed out, we have seen examples of static factory methods in Section 16.4. We will discuss the design pattern Factory Method below, in Section 32.11. In the current version of the material we do not discuss Abstract Factory.

32.11.  The design pattern Factory Method
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The Factory Method design pattern relies on virtual instance methods in a class hierarchy that take care of class instantiation. The Factory Method scene is shown diagrammatically in Figure 32.7 and programmatically in Program 32.22.

The problem is how to facilitate instantiation of different types of Products (line 3-13 in Program 32.22) in SomeOperation (line 20) of class Creator.

The Factory Method solution is to carry out the instantiation in overridden virtual methods in subclasses of class Creator. The actual instantiations take place in line 26 and 32 of Program 32.22. In SomeOperation, the highlighted call this.FactoryMethod() will either cause instantiation of ConcreteProduct_1 or ConcreteProduct_2, depending on the dynamic type of the creator.

Figure 32.7    A template of the class structure in the Factory Method design pattern.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

using System;

public abstract class Product{
  public Product(){}
}

public class ConcreteProduct_1: Product{
  public ConcreteProduct_1(){}
}

public class ConcreteProduct_2: Product{
  public ConcreteProduct_2(){}
}


public abstract class Creator{
  public abstract Product FactoryMethod();

  public void SomeOperation(){
    Product product =  FactoryMethod();
  }
}

public class ConcreteCreator_1: Creator{
  public override Product FactoryMethod(){
    return new ConcreteProduct_1();
  }
}

public class ConcreteCreator_2: Creator{
  public override Product FactoryMethod(){
    return new ConcreteProduct_2();
  }
}

Factory Method calls for a quite complicated scene of parallel class hierarchies. The key mechanism behind the pattern is the activation of a virtual method from a fully defined, non-abstract method in the (abstract) class Creator. In many contexts, Factory Method will be too complicated to set up. If, however, the major parts of the class hierarchies already have been established, the use of Factory Method allows for flexible variations of Product instantiations.

32.12.  The Visitor design pattern
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

The Visitor design pattern is typically connected to the Composite design pattern, which we have discussed in Section 32.1. Recall that a Composite gives rise to a tree of objects, all of which expose a uniform client interface. The Visitor design pattern is about a particular organization of the operations that visit each node in such a tree.

Relative to the Composite class diagram, shown in Figure 32.1, we will discuss two different organizations of the tree visiting operations:

The natural object-oriented solution: One method per operation per Component class The Visitor solution All methods that pertain to a given operation are refactored and encapsulated in its own class

The natural object-oriented solution, mentioned first, is the solution that falls out of the Composite design pattern. We will illustrate it in the context of the IntSequence Composite in Section 32.13.

The Visitor solution is an alternative - and more complicated - organization which keeps all operations of a given traversal together. This is the solution of the Visitor design pattern. It will be exemplified in Section 32.15.

32.13.  Natural object-oriented IntSequence traversals
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

We have studied the integer sequence composite in appendix Section 58.3. The class diagram of this particular Composite is shown in Figure 58.1. Please recapitulate the essence of the integer sequence idea from there.

We will now discuss three different operations which need to visit each object in a integer sequence tree, such as the seven nodes of the tree shown in Figure 58.2. The operations are Max, Min, and Sum. Min and Max find the smallest/largest number in the tree respectively. Sum adds all numbers in the tree together.

Below we show the Min, Max, and Sum operations in four classes IntSequence, IntSingular, IntInterval, and IntComposite. All of the operation need to traverse the tree structure. Inner nodes in the composite tree are represented as instances of the class IntCompSeq, as shown in Program 32.26. The operations Min, Max, and Sum are implemented recursively in this class. A Composite is a recursive data structure which in a natural way calls for recursive processing. All this is archetypical for a composite structure.

1
2
3
4
5

public abstract class IntSequence {
  public abstract int Min {get;}
  public abstract int Max {get;}
  public abstract int Sum();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public class IntInterval: IntSequence{

  private int from, to;

  public IntInterval(int from, int to){
    this.from = from;
    this.to = to;
  }

  public int From{
    get{return from;}
  }

  public int To{
    get{return to;}
  }

  public override int Min{
    get {return Math.Min(from,to);}
  }

  public override int Max{
    get {return Math.Max(from,to);}
  }
    
  public override int Sum(){
    int res = 0;
    int lower = Math.Min(from,to),
        upper = Math.Max(from,to);

    for (int i = lower; i <= upper; i++) 
       res += i;
    return res;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class IntSingular: IntSequence{

  private int it;

  public IntSingular(int it){
    this.it = it;
  }

  public int TheInt{
     get{return it;}
  }

  public override int Min{
    get {return it;}
  }

  public override int Max{
    get {return it;}
  }

  public override int Sum(){
    return it;
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class IntCompSeq: IntSequence{

  private IntSequence s1, s2;  // Binary sequence: Exactly two subsequences.

  public IntCompSeq(IntSequence s1, IntSequence s2) {
    this.s1 = s1;
    this.s2 = s2;
  }

  public IntSequence First{
    get{return s1;}
  }

  public IntSequence Second{
    get{return s2;}
  }

  public override int Min{
    get {return Math.Min(s1.Min, s2.Min);}
  }

  public override int Max{
    get {return Math.Max(s1.Max, s2.Max);}
  }

  public override int Sum(){
    return s1.Sum() + s2.Sum();
  }
}

In the web version of the material we show an integer sequence client which traverses a composite tree structure of integer sequences with use of the operations Min, Max, and Sum, see Program 32.27 (only on web). In Listing 32.28 (only on web) we also show the program output.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

using System;

class SeqApp {

  public static void Main(){

    IntSequence isq = 
      new IntCompSeq(
            new IntCompSeq(
              new IntInterval(3,5), new IntSingular(-7) ),
            new IntCompSeq(
              new IntInterval(12,7), new IntCompSeq(
                                           new IntInterval(18,-18),
                                           new IntInterval(3,5)
                                           )));

    Console.WriteLine("Min: {0} Max: {1}", isq.Min, isq.Max);
    Console.WriteLine("Sum: {0}", isq.Sum());
  }

}

1
2

Min: -18 Max: 18
Sum: 74

The programming of Min, Max, and Sum in the integer sequence classes, as shown above, is natural object-oriented programming of the traversals. Each of the four involved classes has a Min, Max, and a Sum operation. The operations are located in the immediate neighborhood of the data on which they rely. Everything is fine.

But the solution shown in this section is not a Visitor. In the next section we will discuss and motivate the transition from the natural object-oriented solution to a visitor. After that we will reorganize Min, Max and Sum as visitors.

32.14.  Towards a Visitor solution
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Before we study Visitors for integer sequence traversals we will discuss the transition from the natural object-oriented traversal to the Visitor design pattern.

The main idea of Visitor is to organize all methods that take part in a particular traversal, in a single Visitor class. In our example from Section 32.13 it means that we will have MinVisitor, MaxVisitor, and SumVisitor class. All of these classes share a common Visitor interface.

The following steps are involved the transition from natural object-oriented visiting to the Visitor design pattern:

A Visitor interface and three concrete Visitor classes are defined The Intsequence classes are refactored - the traversal methods are moved to the visitor classes Accept methods are defined in the IntSequence classes. Accept takes a Visitor as parameter Accept passes this to the visitor, which in turn may activate Accept on components

We provide an SVG-animation that illustrates the transition.

In the following section we will study an example. In the slipstream of the example we will explain and discuss additional details. The pros and cons of the Visitor solution are summarized in Section 32.16.

32.15.  A Visitor example: IntSequence
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

Let us now reorganize the integer sequence traversals from Section 32.13 to a Visitor.

We provide three different traversals: find minimum, find maximum, and calculate sum. This will give rise to three different visitor objects: a minimum visitor, a maximum visitor, and a sum visitor of types MinVisitor, MaxVisitor, and SumVisitor respectively. The three classes implement a common Visitor interface. Each of the visitors will have VisitIntInterval, VisitSingular, and VisitCompSeq methods. As a naming issue, we chose to use the name Visit for all of them. This choice relies on static method overloading. With these considerations we are able to understand the Visitor interface shown in Program 32.29.

1
2
3
4
5

public interface Visitor{
  int Visit (IntInterval iv);
  int Visit (IntSingular iv);
  int Visit (IntCompSeq iv);
}

The abstract superclass in the integer sequence Composite design pattern, which we presented in Program 32.23, can now be reduced to a single method, which takes a Visitor object as parameter. The method is usually called Accept.

1
2
3

public abstract class IntSequence {
  public abstract int Accept(Visitor v);
}

The idea behind the Accept method is to delegate the responsibility of a particular traversal to a given Visitor object. In the class IntInterval, shown below in Program 32.31, we see that Accept passes the current object (the IntInterval object) to the visitor. This is done in line 19. The same happens in Accept of IntSingular (line 14 of Program 32.32) and in Accept of IntCompSeq (line 19 of Program 32.33).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class IntInterval: IntSequence{

  private int from, to;

  public IntInterval(int from, int to){
    this.from = from;
    this.to = to;
  }

  public int From{
    get{return from;}
  }

  public int To{
    get{return to;}
  }

  public override int Accept(Visitor v){
    return v.Visit(this);
  } 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class IntSingular: IntSequence{

  private int it;

  public IntSingular(int it){
    this.it = it;
  }

  public int TheInt{
     get{return it;}
  }

  public override int Accept(Visitor v){
    return v.Visit(this);
  } 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public class IntCompSeq: IntSequence{

  private IntSequence s1, s2;  // Binary sequence: Exactly two subsequences.

  public IntCompSeq(IntSequence s1, IntSequence s2) {
    this.s1 = s1;
    this.s2 = s2;
  }

  public IntSequence First{
    get{return s1;}
  }

  public IntSequence Second{
    get{return s2;}
  }

  public override int Accept(Visitor v){
    return v.Visit(this);
  } 
}

It is worth noticing that the Accept methods are identical in all three classes shown above. It may, therefore, be tempting to move the Accept method to the common superclass. This will not work, however. The reason is that it is important for the parameter, this, to have the correct static type for the sake of overload resolution in the visitor, and for forthcoming dynamic dispatch (using dynamic binding) of IntSequence objects.

It is now time to program the visitor classes (the classes that implement the Visitor interface of Program 32.29).

The Visit methods on intervals and singulars (the leafs in the composite tree) just extract information from the passed tree node. Thus, the Visit methods extract information from the objects that hold the essential information (this is the objects that provide the Accept methods). The Visit methods on the inner tree nodes (of type IntCompSeq) are more interesting. They call Accept methods on subtrees of the inner tree node. This is highlighted with blue color in Program 32.34, Program 32.35, and Program 32.36.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class MinVisitor: Visitor{
  public int Visit (IntInterval iv){
    return Math.Min(iv.From, iv.To);
  }

  public int Visit (IntSingular iv){
    return iv.TheInt;
  }

  public int Visit (IntCompSeq iv){
    return Math.Min(iv.First.Accept(this), 
                    iv.Second.Accept(this));
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public class MaxVisitor: Visitor{
  public int Visit (IntInterval iv){
    return Math.Max(iv.From, iv.To);
  }

  public int Visit (IntSingular iv){
    return iv.TheInt;
  }

  public int Visit (IntCompSeq iv){
    return Math.Max(iv.First.Accept(this), 
                    iv.Second.Accept(this));
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class SumVisitor: Visitor{
  public int Visit (IntInterval iv){
    int res = 0;
    int lower = Math.Min(iv.From,iv.To),
        upper = Math.Max(iv.From,iv.To);

    for (int i = lower; i <= upper; i++) 
       res += i;
    return res;
  }

  public int Visit (IntSingular iv){
    return iv.TheInt;
  }

  public int Visit (IntCompSeq iv){
    return (iv.First.Accept(this) + 
            iv.Second.Accept(this));
  }
}

As it appears, each Accept method in the Composite calls a Visit method in a Visitor class, which in turn may call one or more Accept methods on a composite constituents. This leads to indirect recursion in between Accept methods and Visit methods. Compared with the natural object-oriented solution, which uses direct recursion, this is slightly more complicated to understand.

The indirect recursion, pointed out above, may also be understood as a simulation of double dispatching. First, we dispatch on the Visitor object and next we dispatch on an object from the composite tree structure. Most object-oriented programming language only allows single dispatching - corresponding to message passing via a virtual method. This can be generalized to multiple dispatching, where the dynamic type of several objects determine which method to activate. The object-oriented part of Common Lisp - CLOS [Keene89] - supports multiple dispatching.

In Program 32.37 we show a client program with an integer sequence composite structure (line 7-15), three visitors (line 16-18), and sample activations of tree traversals (highlighted in line 21, 22, and 28). The output of the program is shown in Listing 32.38 (only on web)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

using System;

class SeqApp {

  public static void Main(){

    IntSequence isq = 
      new IntCompSeq(
            new IntCompSeq(
              new IntInterval(3,5), new IntSingular(-7) ),
            new IntCompSeq(
              new IntInterval(12,7), new IntCompSeq(
                                           new IntInterval(18,-18),
                                           new IntInterval(3,5)
                                           )));
    Visitor min = new MinVisitor();
    Visitor max = new MaxVisitor();
    Visitor sum = new SumVisitor();


    Console.WriteLine("Min: {0} Max: {1}", isq.Accept(min),
                                           isq.Accept(max));

//  Alternative activation of Visit methods:
//  Console.WriteLine("Min: {0} Max: {1}", min.Visit((IntCompSeq)isq), 
//                                         max.Visit((IntCompSeq)isq));

    Console.WriteLine("Sum: {0}", isq.Accept(sum));
  }
}

1
2

Min: -18 Max: 18
Sum: 74

32.16.  Visitors - Pros and Cons
Contents   Up Previous Next   Slide Annotated slide Aggregated slides    Subject index Program index Exercise index 

As it is already clear from our explanation of Visitor in Section 32.15 there are both advantages and disadvantages of this design pattern.

We summarize the consequences of Visitor in the following items:

A new kind of traversal can be added without affecting the classes of the Composite A Visitor encapsulates all methods related to a particular traversal State related to a traversal can - in a natural way - be represented in the Visitor If a new class is added to the Composite all Visitor classes are affected The indirect recursion that involves Accept and the Visit methods is more complex than the direct recursion in the natural object-oriented solution

In case you are going to study compilers implemented the object-oriented way, you will most likely encounter Visitors for such tasks as type checking and code generation.