8.9. Composite-based Expression Tree¶
8.9.1. Composite-based Expression Tree¶
There is another approach that we can take to represent separate leaf
and internal nodes, also using a virtual base class and separate node
classes for the two types.
This is to implement nodes using the Composite design pattern.
This approach is noticeably different from the
procedural approach in that the
node classes themselves implement the functionality of traverse
.
Here is the implementation.
Base class VarBinNode
declares a member function
traverse
that each subclass must implement.
Each subclass then implements its own appropriate behavior for its
role in a traversal.
The whole traversal process is called by invoking traverse
on the root node, which in turn invokes traverse
on its
children.
/** Base class: Composite */
public interface VarBinNode {
public boolean isLeaf();
public void traverse();
}
/** Leaf node: Composite */
public class VarLeafNode implements VarBinNode {
private String operand; // Operand value
VarLeafNode(String val) { operand = val; }
public boolean isLeaf() { return true; }
public String value() { return operand; }
public void traverse() {
Visit.VisitLeafNode(operand);
}
}
/** Internal node: Composite */
public class VarIntlNode implements VarBinNode { // Internal node
private VarBinNode left; // Left child
private VarBinNode right; // Right child
private Character operator; // Operator value
VarIntlNode(Character op,
VarBinNode l, VarBinNode r)
{ operator = op; left = l; right = r; }
public boolean isLeaf() { return false; }
public VarBinNode leftchild() { return left; }
public VarBinNode rightchild() { return right; }
public Character value() { return operator; }
public void traverse() {
Visit.VisitInternalNode(operator);
if (left != null) { left.traverse(); }
if (right != null) { right.traverse(); }
}
}
/** Preorder traversal */
public static void traverse(VarBinNode rt) {
if (rt != null) { rt.traverse(); }
}
When comparing the composite implementation to
the procedural approach,
each has advantages and disadvantages.
The non-composite approach does not require that the node classes know
about the traverse
function.
With this approach, it is easy to add new methods to the tree class
that do other traversals or other operations on nodes of the tree.
However, we see that traverse
in
the non-composite approach does
need to be familiar with each node subclass.
Adding a new node subclass would therefore require modifications to
the traverse
function.
In contrast, the composite approach requires that any new operation on
the tree that requires a traversal also be implemented in the node
subclasses.
On the other hand, the composite approach
avoids the need for the traverse
function to know
anything about the distinct abilities of the node subclasses.
Those subclasses handle the responsibility of performing a traversal
on themselves.
A secondary benefit is that there is no need for traverse
to
explicitly enumerate all of the different node subclasses,
directing appropriate action for each.
With only two node classes this is a minor point.
But if there were many such subclasses, this could become a bigger
problem.
A disadvantage is that the traversal operation must not be called on a
NULL pointer, because there is no object to catch the call.
This problem could be avoided by using a
Flyweight
to implement empty nodes.
If the composite implementation is for a full tree, then it is
unnecesary to explicitly check if the children are null.
Typically, the non-composite version would be
preferred in this example if traverse
is a member function of
the tree class, and if the node subclasses are hidden from users of
that tree class.
On the other hand, if the nodes are objects that have meaning
to users of the tree separate from their existence as nodes in the
tree, then the composite version might be preferred because hiding the
internal behavior of the nodes becomes more important.
Another advantage of the composite design is that implementing each node type’s functionality might be easier. This is because you can focus solely on the information passing and other behavior needed by this node type to do its job. This breaks down the complexity that many programmers feel overwhelmed by when dealing with complex information flows related to recursive processing.