Object-oriented Programming in Python — Lesson 2. The “Composite” Pattern

This is the second in a series of five lessons, summarizing the practical need for object-oriented programming, and the common facilities provided by object-oriented languages, with examples in Python, stressing the Python implementation and approach. In the first lesson, we considered the object-oriented paradigm as response to the need for functional substitutability, in a certain (and very frequent) applicative context. Then, we saw why inheritance is often employed to construct infrastructure for it (and why it is indeed useful — but not essential — in Python). This furnishes the basis. But then, experience has been showing that the benefits of object-oriented programming are closely tied to disciplined application: complying with common design idioms, patterns, and architectures. Thus, the rest of this course is dedicated to demonstrating some of the more significant practices in this common wisdom, starting, in this lesson, with some heavy-weight design patterns that demonstrate the power of object-oriented programming in all its glory.

Sections in this lesson:

1. About Design Patterns
2. The Recursive Object Model — One Node Type.
3. The “Decorator” Pattern — Two Node Types
4. The “Composite Pattern” — Three (or more) Node Types + Traversal
5. Exercise Step 1 / 3. Partial “Outline” Composite
6. Exercise Step 2 / 3. Partial “Outline” Composite (self-rendering)
7. Exercise Step 3 / 3. Full “Outline” Composite (Rendered from Outside)

1. About Design Patterns

A common mistake among newcomers to object-oriented programming is that all there is to it is concentrating functionality in classes. What you get in the end are so many classes, where each class encapsulates all the functionality that requires access to an object’s information hiding (associations with other objects, data that represents the current state of processing the object, cached data, and internal logic). Unfortunately, this — alone — never worked and there is no reason why it ever will. Commercial-strength object-oriented design is about teamwork between objects, where each is (indeed) characterized by its class. But teamwork — in object-oriented design as well as anywhere in our world —requires that team members give up some of their privacy for the benefit of the common objective. Thus, the genuine challenge of object-oriented design is to distribute the common functionality among so many (objects of) classes, finding the best compromise, causing the least harm to the information hiding of each. But in a real-world design, some object-structure is going to be duplicated and some internal object logic is going to be exposed. This is the bad news!

The good news is that through the many years of intensive commercial application of the object-oriented paradigm of programming (since, at least, 1980 — Smalltalk), much collective understanding has been accumulating as to its useful application — i.e. patterns of teamwork among object classes. The recommended strategy to obtain this knowledge is through one (or all) of the following:

1. To integrate your code in a widely used application framework and follow the practices it dictates.
2. To write code in a language that is profoundly object-oriented, stick to the language constructs and standard library and follow the common language practice.
3. To study design patterns and idioms carefully and try to follow their example (which will be included in the first two items, anyway). Especially, Design Patterns, introduced to the object-oriented community in the early 1990’s, have been responsible for the current widespread structured practice of object-orientation.

A design pattern is both a recurring structuring of code (“pattern”) and the problem that invited it in the first place. (It would be a mistake to consider only the first, as some would-be object-oriented programmers do)! But first, some history. (I am using the term “Design Idioms” for practices that resemble the canonized patterns but have not been fortunate enough to be officially recognized as such).

Originally, there were Design Patterns of architecture, introduced by Christopher Alexander in1978 (in the context of building architecture). Alexander both introduced the concept and provided an intensive catalog of what he termed “Design Patterns”, complete with names, descriptions, and examples, with which buildings may be assembled, to satisfy required functionality of their Human inhabitants or visitors. (For example: Barn, Balcony, Lobby, Living Room, etc.). While a design pattern of (building) architecture is eventually remembered by visual shape, it is selected (and integrated into the building) due to the functionality that it satisfies. In summary, a design pattern is a way of ordering objects in space that suggests functionality. Well-built buildings, according to Alexander, have their underlying patterns constitute a “living pattern language”, guiding the visitor to useful areas in the obvious way. (As opposed to a building posing a “dead pattern language” — i.e. is useless).

In addition, the specifications that Alexander gives in his catalogs follow a literary form, consisting of passages that normally describe (1) a common context, (2) a recurring problem in this context (that the pattern comes to solve), and (3) the core of the solution, often terminated by (4) a concrete example. Indeed, authors of design patterns (of software) that followed Alexander kept the idea of a design pattern form, though following their own private forms. Finally, it is important to stress that a design pattern is neither formula nor template. Repeated a million times — the solutions will never be identical!

Then came Design Pattern of Software, culminating some attempts, in the early 1990’s, to establish common practices in object-oriented programming, regardless of language (mainly Smalltalk and C++), and borrowing Alexander’s terminology. The most famous of these is summarized in the so called “Gang of Four” book (signed by four authors: Gamma, Vlissides, Helm and Johnson), but there are also the works by Coplien, Schmidt, Buchman and others. Once introduced, these Design Patterns of Software (as well as the structured example they set) fast became the recognized way of automating the gap between top-level design and (object-oriented) programming (beyond the language-assimilated assets of generic containers and algorithms, etc.).

In my humble opinion (acknowledging the existence of other opinions), the position of design patterns is between design and implementation. There are no design Patterns of Software Analysis (that I am aware of); expertise in design patterns will not help you understand the functional requirements of a software product or model its problem domain. But once the requirements are known, the novice object-oriented designer may be disappointed to realize that just arranging them into an object model and using the message paradigm to implement the procedural part leaves many gaps, yet to solved. The reason for this is that object-oriented design is not (and never was) about just securing each individual object’s single class’s responsibility by encapsulation and information hiding. This is futile! Object-oriented design is about distributing the general responsibility among peer object classes, finding the compromise that inflicts the minimal possible damage to the information hiding of each. (But some “damage” there will always be — look at collaboration and interaction in the real world around you!). And here, established design idioms, patterns, and architectures are handy, demonstrating valid and productive use cases of distribution of responsibility, to copy or to learn from.

Experience has been showing that filling the gaps (left by straightforward object-oriented design) “creatively” by arbitrary solution-domain entities and functions often ends in maintenance disaster, and especially when more than one developer is involved. (Reasoning follows). On the contrary, when versed in design patterns, the object-oriented designer proceeds to solve technical problems in a fairly standard way, that other developers may understand and maintain.

Because the object-oriented way of doing business stresses encapsulation of functionality (in classes, rather than functions), finishing the solution model with design patterns normally results in the addition of solution-domain entities — in the form of classes, base classes, and interfaces — that solve familiar technical problems in a recognizable way, creating visible patterns in the code. Since classes (data structures aggregating functions) have a much stronger impact on code structure than individual functions, it follows that a good object-oriented design carries the potential to deliver a better software product (because its effect is more profound and structured) than a procedural design (which is more less at the fancy of the designer). But based on the same premises, a bad object-oriented design will destroy the software product beyond repair. (Both benefits and damage are proportional to the strength of the technology). Hence, the importance of adhering to established procedures (patterns, idioms, and architectures) for applying it!

As demonstration to my observation that design patterns belong in the gap between design and implementation, consider that some design patterns of software (most notably, the “Visitor”, discussed in length in the next lesson), may — on the contrary — require changing our understanding of the problem domain. This twist may be either a blessing (an illumination leading us “back to the drawing board”) or a curse (the problem “kidnapped” by the solution). Anyway — to demonstrate my point — this comes as a surprise to many object-oriented designers, because, in this case, the pattern seems to escape from its natural position (which is indeed between design and implementation, or at most, between top-level design and detailed design).

Summary: (Assuming that (1) the program must reflect (in its control and data constructs) the problem domain (and as close as possible), and (2), all the other programmatic constructs thrown on top of that must avoid distorting the bulk that models the problem), being versed in design patterns and idioms allows the object-oriented designer to secure the following:

1. To match familiar problems with familiar solutions (rather than waste time on — working but — fancy solutions that will complicate maintenance and inhibit third-party API usage with no justification).
2. To use familiar naming conventions.
3. To water-mark recognizable “patterns” into the fabric of the code (recurring control constructs, data structures and names), suggesting (to the versed reader) commonly needed functionality.

Here are some interesting (and useful) design patterns that we are going to study in detail on this course:

1. The “Decorator” pattern. Recursive object structure (1: 1), emulating “metamorphism”.
2. The “Composite” pattern. Recursive object structure (1: N), allowing traversal from outside.
3. The “Visitor” pattern. Object-oriented response to “asymmetric multiple polymorphism”.
4. The “Hierarchical Visitor” variant. Combined with the “Composite” pattern.

We shall also discuss some design patterns made redundant by (among other things) Python’s weak typing and easy access to object metadata:

1. The “Singleton” pattern.
2. The “Dynamic-Pluggable Factory” pattern
3. Variant using “Factory Methods”
4. Variant using “Prototypes”
5. Strong-typed implementations of polymorphic design patterns, such as Visitor and Decorator.

So far, the introduction. And now to work…

2. The Recursive Object Model — One Node Type

Recursive object models (“trees”) feature an association between an object of a class and (same or another) object of the class (either directly or through an interim association). Some complicated tree structures (such as the Decorator and Composite design patterns that we are going to discuss next) need specialized node types and a transitional association. But, for a start, let us consider the simplest tree form that can do with a single node type with a single association. E.g., a binary tree.

Read: “Node contains zero or two Nodes (where each contained Node, as we already know, contains zero or two Nodes, which…). A Node is contained by either one parent Node or none (in case of the root of the tree)”.

In this simple architecture, there is only one node type and “to contain” indicates its state (rather than a specialized class). At any moment of its existence, a Node may contain either two child nodes or none (subject to change). The containment is optional — “0, 2” (implemented by, e.g., the null value) — with the zero-quantity stopping the recursion!

For example:

“A” contains “B” and “C”. “B” contains “D” and “E”. “C”, “D” and “E” contain nothing (are the “leaves” of the tree). “A” is the root of the tree.

Sample code:

Output:

A
 B
  D
  E
 C

3. The Decorator” Pattern — Two Node Types

The “decorator” pattern uses the recursive structure idiom to implement a poor-man’s metamorphism (the capability of an object to “transcend its type”). Suppose there is a family of My String types, all storing a string, but with various adornments: Quoted, Bracketed, etc. And suppose, furthermore, that we want this string classification to be dynamic. For example, given a simple My String, we may wish it to become Quoted (and remain that way). And suppose, still furthermore, that we need this capability to be accumulative (and substitutable). Given the quote augmented My String (which is still, for all purposes, a My String), we may wish it to further become Bracketed (and remain that way). Etc.

Since an object cannot change its class during runtime (actually, no one is stopping you from redirecting a Python object’s internal type-pointer to another class, but, due to much preparatory work done during object construction, this will not work for you), we wrap it with a proxy that augments its behavior and may take its place, being substitutable with it (because of its class also being derived from its). The combination of the “proxy” pattern (referencing with forwarding) and substitutability (derivation from the same base class) allows for the illusion of…

1. “Dynamic” classification. An object appears (for its clients) to “change its type” during its lifetime.
2. “Multiple” classification. An object features the accumulated behavior of several types.

None of these pyrotechnics may be achieved with normal inheritance since that involves duplication of the internal string and defies the permanent association of object to type.

The following example uses the “Decorator” pattern to elevate a string from simple unadorned to various string adornments, accumulative, while remaining substitutable with string.

Output:

[“TEST”]

Footnotes:

1. “My String” is a wrapper for the built-in string for the purpose of decoration. (It is not a clever idea to inherit directly from built-in types).
2. Silent conversion to the built-in string. Note that this is inherited (and not overridden) by the decorators, due to the way inheritance is implemented in Python. (More on this below).
3. The abstract class “String Decorator” inherits both ABC (making it an abstract class) and “My String”.
4. The “trick” of both inheriting and wrapping My String is in the heart of the “Decorator” pattern.
5. “Data override” — this trick is peculiar to Python. Since the object has a single attribute dictionary, its string member replaces the string inherited from My String (keyed by the same name)! Whether this is proper or improper use of inheritance may be debated, but it certainly saves redundant code! (On the contrary, in languages where data members are part of the class — rather than its object initialization — like C++, C#, Java etc., the Decorator turns out to contain two strings, one of which is redundant. And further requires proliferating the getters!)
6. The default built-in string conversion is a template method (another design pattern), requiring an abstract method, which is to be implemented by the concrete String Decorator (on which the method is really invoked).
7. The concrete String Decorators do not need an explicit initializer. (They inherit the base initializer that already does the job. The string received is passed to it).
8. “Quoted String” is a String Decorator that adds double quotes.
9. “Bracketed String” is a String Decorator that adds square brackets.
10. “Upper String” is a String Decorator that converts to upper-case.
11. Bracketing of quoting of upper-casing of a string.
12. The built-in print silently converts the decorator to the built-in string, which silently unrolls the layers of decoration.

4. The “Composite Pattern” — Three (or more) Node Types, made for Traversal

A 1: 1 two-node architecture is insufficient as a general recursive data-structure solution. The “Composite” pattern generalizes the (1: N) recursive object model into a three-node topology, which is — for most purposes — the complete solution.

Read: A Component may be either Leaf or Composite (but not abstract Component). A Composite contains zero or more Components (and, as we already know, each of which may be either Leaf or Composite. And if it is a Composite…).

An interesting lesson from this object model is that an inheritance hierarchy may also be regarded as the Selection control construct. (Precisely: directing the traversal algorithm to make a selection). This is a “xor” construct: “a Component is either Leaf or Composite (but not really Component)”. (“Xor”, rather than “or”, because a Component cannot be both Leaf and Composite). The latter objection — “but not really Component “— refers to Component’s abstract base status. You cannot create an abstract Component (but you can reference an object responding to its interface). Note that where the base of the inheritance hierarchy is not abstract, the selection becomes three-fold: “A Component may be either Leaf or Composite or plain Component” (which is not the case here).

Some object-oriented programmers have been making the naive mistake of taking any implementation of the above three-node topology for “The Composite Pattern”. Recall that a “Design Pattern” is not only a pattern for arranging objects in space but also — and first — response to a functional requirement. On the contrary, “to arrange some objects in a tree” is not a functional requirement addressing a problem, but a data structure, facilitating a solution. (And to what?)

The purpose of the three-node data topology in the “Composite” pattern is to support functionality: to facilitate traversal (and manipulation) of the composite structure from outside. And which problem does this feature address? Why traverse from outside, rather than inside?

Recursive object structures and their traversal, paramount in functional programming, pose a fundamental challenge to object-oriented design. (Soon to be resolved!) Information hiding is hard to observe inside a recursive algorithm (that is needed to traverse the recursive structure). We cannot implement an encapsulation-and-information-hiding observing method over the entire tree! (Because it is not a discrete object, to which we may pass a discrete message and be done with it. Instead, we must somehow disperse many discrete messages to many discrete objects that we cannot yet see). The methods in each Component will not do, because, in the case of Composite, as in the tree root, there may still be many additional components hidden inside them. In a procedural design, we only have direct control over the function that is explicitly invoked to process the root node. But once it proceeds to recurse inside, we must sit patiently and wait for the whole sequence to unwind, having no control over what happens in the meantime. (Allowing so many innocent and defenseless objects to be plundered inside, which is not the object-oriented way!)

While the procedural design challenge seems to be how to concentrate so much functionality in a single function (taking the objects of manipulation as arguments), the object-oriented design challenge is how to distribute responsibility among the participant objects. And in the Composite context: what should each Node do and not do? Is there a different functional responsibility according to Component type?

Yes, there is! This is the reason for the three-fold node structure in the first place. Obviously, Composites must be responsible for traversal inside, while Leaves must be responsible for doing work! Still, it would be a bad design decision to delegate the responsibility for (1) traversing the Composite and (2) deciding to either do work or traverse inside (as applies) to the Composite at hand, because (1) the latter (doing work) is not the Composite’s business, and (2) that would require explicit type query(which is not a good idea, if it can be avoided, and as we shall see, it can), and (3) which Composite are we talking about? There are many more of them waiting inside, and we had rather respect their information hiding, in turn.

And that is only about traversal and triggering discrete work. What practical work should the Composite, as a structure (counting its Composites and Leaves), do and what should it not do? The object-oriented answer is decisive: just traversal and as little work as needed to define the Composite’s business. Other work (that can be based on that) should be left to specialized helpers and manipulators (be them functions or objects). For example: rendering the tree, computations involving the whole tree, etc. The Composite elements must feature the bare protocol to enable manipulation and scrutiny from outside, using getters and setters, and without resorting to explicit type query (because there are better ways, as we shall see)!

Consider this rich Shape Composite topology that features several Leaf types and a Composite sub-hierarchy. (Which is common in object modelling. On the contrary, the simple single-Leaf/single-Composite topology seems to be the exception). The descriptors within double angular brackets (“guillemets”) — also called “stereotypes” — are used here to specify the node’s role in the pattern.

Line, Circle and Square are Leaves. Multi-line and Multi-shape are Composites (with Multi-line specializing in Lines), inheriting the Composite behavior from the abstract Compo-shape. The odd restrictive inheritance of association (“Multi-line agrees to accommodate only Lines, although it is built to contain any Shape. The slash preceding the name of the association indicates that it is not implemented physically) is frequent in object-modelling and — despite being restrictive, does not compromise the principle of substitutability (to be discussed)! Correct substitutability does not mean that the list must contain instances of all available Shape sub-classes. It only means that all objects in the list must respond to the Shape interface, and indeed they do!

This design features true Composites: Compo-shapes carry little added value besides containing Shapes, thus facilitating type-less rendering. In a clean design, rendering a Compo-shape is reduced to just rendering each Shape inside, and in the correct covering order, no more and no less! In addition, some Compo-shapes may add some preparatory work before that, as well as some cleanup work afterwards, still, requiring no functionality to be interleaved in the middle (other than what is already encapsulated in the contained objects)!

And this is the reason for the interim abstract Compo-shape. Since the iteration protocol is Composite-generic, then it may be factored to a base class and inherited. (“For each Shape inside…”). Unless there is some special effect to draw where lines or shapes collide, it is possible to draw the entire tree without knowing what it is that we draw, as long as composites are concerned! (And even if such line-bonding special effects are specified, including augmentation, and I’ve had such designs, I would rather define these as “Fixture” kind of Shapes, to be rendered, in the correct covering order, like any other Shape, and prepare them in advance. Indeed, in the world of civil engineering, “Fixture” is a problem-domain entity — rather than rendering effect: Fixtures occupy expensive space, must endure stress, cost money to produce, bear catalog ids, etc.). And the knowledge that Fixtures are needed to support other Shapes is impervious to the object model. The object model takes stock of the kind of objects we are going to need, and the machinery needed to hold them together. Why all these objects are there in the first place is the secret of initialization procedures.

But what about iterating inside Leaves? What? Wait a moment, this must be a misunderstanding! We iterate inside Composites. We do work with Leaves. That is true, but while iterating inside a Composite, we are likely to meet both Leaves and Composites, and the last thing we want to do is to ask each of them for its type (and iterate into it only if it identifies as Composite). Either there is a smart replacement for iteration from outside (which we will consider later), or we match Leaf and Composite behavior, in respect to iteration! In a clean Composite design, a Leaf should be identical to an empty Composite, in respect to “iteration inside”. This is in the spirit of Python-style “Duck typing”. In both cases — empty Composite or Leaf — we have nothing to look for inside, so whether the empty Component happens to be a Composite or something else does not matter! And as to doing Leaf work — that, as already said, is Leaf work; Composites may pass over it silently!

But then, the genericity ends when it comes to rendering Leaf Shapes (Line, Circle or Square). Here, because rendering is type-dependent, type query is imminent; rendering straight Lines, Circles and Squares is powered by different formulae. Requesting the Leaf Shape to render itself may work in script scope but is not a practical solution for commercial-strength software: there are many rendering technolgies, media and styles, which are likely to be runtime configurable. And anyway, rendering (let alone dump for debug or persistence) is categorically not in the responsibility of Shape, to begin with!

There are several ways to solve this design problem (and ensure an open design). We will discuss a (non-trivial) object-oriented solution in the next lesson. For the sake of simplicity, and to just demonstrate the point, in this lesson we will restrict ourselves to a simple (but practical) Composite that — in contrast to Shape — features a single “strongly typed” Leaf. In this composite, there is only one Leaf type — string — which defines the Composite content, is officially known and is not going to change.

Follow the three steps to this exercise.

5. Exercise Step 1 / 3. Partial “Outline” Composite Structure (self-manipulating)

The exercise program reads an “Outline” file (see example below) and parses its contents giving object model. This “Outline” format is a straightforward hierarchical structure of text lines, Python and Pseudocode style, which lends itself trivially to the “Composite” pattern.

Here is sample outline file for the exercise:

to develop software 
    to analyze the requirements 
        to understand the needs 
        to model the problem domain 
    to design the solution 
        to select architecture
            to make design decisions
        to model the solution domain
            to apply design patterns
        to confirm fidelity
    to implement the solution
        to code the solution
        to test the solution
        to package the solution

Each line is a (Leaf) node in the Outline tree, where indentation indicates a nested block structure — the Composite of the Outline tree. (In the drawing below, the Blocks are highlighted by yellow rectangles). Blocks contain no further information, besides lines. Each indent opens a new block (in the current block, as well as providing the first line in it). The outermost line (the root of the tree — there is only one root) sits in a block of its own (not indicated in the drawing).

Here is the object model:

An Outline Document contains a Block (the root of the recursive document structure). Block is a kind of Outline Element that contains one or more Outline Elements. Each Outline Element (playing the role of the “Component” of this “Composite” pattern) may be either a Line (the “Leaf”) or a Block (the “Composite”).

The assignment: For the first prototype, implement this “Outline Document” design, for the time being, just parsing the file. (We will add traversing functionality — rendering — in the next prototype).

Return here after solving the assignment and compare your solution with this “schoolbook solution”:

Footnotes:

1. Outline Block (the Composite) contains Outline Lines (the Leaves).
2. Each Block points back to its parent (for the temporary purpose of parsing. Not used afterwards).
3. The outermost Block is opened by default.
4. Empty lines are ignored.
5. An indented line also opens a Block.
6. A de-dented line attempts to unwind the Block stack, consulting the original indent saved in the unwound blocks. (Same-indent line does nothing).
7. The current Line, its content stripped, is appended to the current Block.
8. The demo program creates the disk file and fills it with the right content, if not found.

6. Exercise Step 2 / 3. Partial “Outline” Composite (self-rendering)

Next, we are going to add the rendering logic. For the sake of this prototype, we will allow the Outline to render itself. (We will refactor this functionality out, in the next — and final — version). Add the appropriate render functions to the Outline Document and to the respective Component types.

A to rendering: For this prototype, we will do with a simple textual style called “military numbering”. Each line is preceded by a dot-separated list of numbers, specifying its “rank” — enumerated hierarchical position (starting with rank 1).

Sample “military numbering” listing for this input:

1. to develop software 
    1.1. to analyze the requirements 
        1.1.1. to understand the needs 
        1.1.2. to model the problem domain 
    1.2. to design the solution 
        1.2.1. to select architecture
            1.2.1.1. to make design decisions
        1.2.2. to model the solution domain
            1.2.2.1. to apply design patterns
        1.2.3. to confirm fidelity
    1.3. to implement the solution
        1.3.1. to code the solution
        1.3.2. to test the solution
        1.3.3. to package the solution

Return here after solving the assignment and compare your solution with this “schoolbook solution”:

Footnotes:

1. “Render” is an abstract method of the Component, to be implemented by the concrete Components. All renderers get the rank (list of numbers).
2. Line rendering advances the current rank (in its parent— the rank was passed “by reference”)!
3. Line rendering displays the line, complete with military numbering prefix, using the rank received, after advance.
4. Block rendering opens a sub-rank (numbered zero, for now — to be advanced by the Line).
5. The Block, in its role of Composite, does not actively display anything. Instead, it delegates the actual rendering to the Components inside, one by one.
6. Outline Document rendering delegates the actual rendering to the root Block.
7. In this interim prototype, the Outline Document renders itself, and to the standard output.

Output:

1. build software
 1.1. analyze requirements
  1.1.1. understand needs
  1.1.2. model problem domain
 1.2. design solution
  1.2.1. select architecture
   1.2.1.1. make design decisions
  1.2.2. model solution domain
   1.2.2.1. apply design patterns
  1.2.3. confirm fidelity
 1.3. implement solution
  1.3.1. code solution
  1.3.2. test solution
  1.3.3. package solution

7. Exercise Step 3/3. Full Composite Outline (Rendered from Outside)

With all low-level logic (including textual rendering) resolved, let us, finally, conclude the proper “Composite” pattern, by refactoring the capability for rendering to a third party, of course, providing it with the appropriate infrastructure inside the Composite. For the time being, we maintain the simple “military numbering” rendering style. (We will tackle the problem of facilitating any rendering style in the next lesson).

The assignment: using the current prototype, refactor the rendering functionality out of the Outline Document Composite, and into a render function using the Outline document. Design a smart Composite interface that will allow the renderer to traverse the Outline Document Composite and extract the information to render without explicit type query (i.e. without explicit selection based on the current node type: Leaf or Composite)!

For the “schoolbook solution”, press this link.

What next?

In the first lesson, we acquired the bare vocabulary of object-oriented programming: functional substitutability, using the message paradigm, to objects whose behavior and data are encapsulated in classes. In this lesson, I argued that applying an object-oriented design in practice must be disciplined, following established idioms, patterns, and architectures, and proceeded to dedicate the rest of the lesson to the object-oriented approach to recursive data structures — the “Decorator” and “Composite” patterns. In the next lesson we will proceed to explore the limits of the message paradigm and how to overcome them, using other polymorphic design patterns and idioms, concentrating on the “Visitor” pattern, and combining the latter with the “Composite” pattern, giving the “Hierarchical Visitor” variant.

References

1. Christopher Alexander: “The Timeless Way of Building”, Oxford University Press, 1979.
2. Gamma, Vlissides, Helm & Johnson: “Design Patterns: Elements of Reusable Object-Oriented Software”, Addison-Wesely, 1994.

Lessons on this course:

1. Substitutability and Inheritance
2. The glory of OO Substitutability: the “Composite” Pattern ← you are here!
3. The limits of OO substitutability: the “Visitor” Pattern
4. Some boring design patterns
5. The limits of inheritance