.. _Composite:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "Composite";ODSA.SETTINGS.MODULE_LONG_NAME = "Composite-based Expression Tree";ODSA.SETTINGS.MODULE_CHAPTER = "Binary Trees"; ODSA.SETTINGS.BUILD_DATE = "2020-08-13 17:53:17"; ODSA.SETTINGS.BUILD_CMAP = true;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://opendsa.org for more details.
.. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer
   :requires: binary tree terminology; design patterns; expression tree
   :satisfies: composite
   :topic: Binary Trees, Design Patterns

Composite-based Expression Tree
===============================

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 :term:`Composite design pattern`.
This approach is noticeably different from the
:ref:`procedural approach  <BinaryTreeImpl>` 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.

.. codeinclude:: Binary/ExpressionTreeC
   :tag: Composite

.. .. inlineav:: compositeTraversalCON ss
      :long_name: Composite Expression Tree Traversal Slideshow
..    :links: AV/Binary/BTCON.css
      :scripts: AV/Binary/compositeTraversalCON.js
      :output: show

When comparing the composite implementation to
the :ref:`procedural approach  <BinaryTreeImpl>`,
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
:ref:`Flyweight  <DesignPatterns>`
to implement empty nodes.

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.