|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Preorder, inorder, and postorder traversals are special cases of the more general depth-first traversal described in the preceding section. Rather than implement each of these traversals directly, we make use a design pattern pattern, called adapter , which allows the single method to provide all the needed functionality.
Suppose we have an instance of the PrintingVisitor class
(see Section 
).
The PrintingVisitor class extends the Visitor class.
However, we cannot pass a PrintingVisitor instance
to the DepthFirstTraversal method shown in Program
because it expects an object that extends
the PrePostVisitor class.
The problem is that the protocol implemented by the PrintingVisitor does not match the protocol expected by the DepthFirstTraversal method. The solution to this problem is to use an adapter. An adapter converts the protocol provided by one class to the protocol required by another. For example, if we want a preorder traversal, then the call to the preVisit (made by depthFirstTraversal) should be mapped to the visit method (provided by the PrintingVisitor). Similarly, a postorder traversal is obtained by mapping postVisit to visit.
Programs , and define three adapter classes--PreOrder, InOrder, and PostOrder.
All three classes are similar:
They all extend the PrePostVisitor class
defined in Program ;
all have a single instance attribute that refers to a Visitor; and
all have a __init__ method that takes a Visitor.
Each class provides a different interface mapping. For example, the preVisit method of the PreOrder class simply calls the visit method on the _visitor instance attribute. Notice that the adapter provides no functionality of its own--it simply forwards method calls to the _visitor instance as required.
The following code fragment illustrates how these adapters are used:
v = PrintingVisitor() t = SomeTree() # ... t.depthFirstTraversal(preOrder(v)) t.depthFirstTraversal(inOrder(v)) t.depthFirstTraversal(postOrder(v))
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.
