SE 2811, Note 13b: Composite Revisited, Pattern Review

Composite, Revisited

• [Exercise: create a "new" example of a class hierarchy that violates LSP]
• What is LSP?
• How do we represent a binary search tree storing strings?
  • Standard model:

            class Node {
               private String _item;
               private Node _left, _right;
               public Node(String item, Node left, Node right) {
                  _item = item;
                  _left = left;
                  _right = right;
               }
               public String item() { return _item; }
               public Node left() { return _left; }
               public Node right() { return _right; }
               public boolean isLeaf() { return _left == null && _right == null; }
            }
    
            class Tree {
               private Node _root = null;
               public boolean contains(String target) {
                  return contains(_root, target);
               }
               protected boolean contains(Node n, String target) {
                  if ( n == null )
                     return false;
                  else if ( n._item.equals(target) )
                     return true;
                  else if ( n.compareTo(target) < 0 )
                     return contains(n.left(), target);
                  else
                     return contains(n.right(), target);
               }
               public void add(String target) { ... code omitted ... }
            }
    

  • Arbitrary number of children:

            class Node {
               private String _item;
               private ArrayList<Node> _children = new ArrayList<>();
               public Node(String item) {
                  _item = item;
               }
               public add(Node n) {
                  _children.add(n);
               }
               public String item() { return _item; }
               public Iterator<Node> childrenIterator() { return _children.iterator(); }
               public boolean isLeaf() { ...?... }
            }
    

  • Alternative: having different classes for leaves, non-leaves:

            abstract class Node {
               private String _item;
               public String item() { return _item; }
               public Node(String item) {
                  _item = item;
               }
               abstract boolean isLeaf();
               abstract void add(Node n);
               abstract Iterator<Node> childrenIterator();
            }
    
            class Leaf extends Node {
               public Leaf(String i) { super(i); }
               public void add(Node n) { throw new UnsupportedOperationException("children not supported"); }
               public Iterator<Node> childrenIterator { return null; }
               public boolean isLeaf() { return true; }
            }
    
            class Branch extends Node {
               public Branch(String i) { super(i); }
               private ArrayList<Node> _children = new ArrayList<>();
               public void add(Node n) { _children.add(n); }
               public Iterator<Node> childrenIterator { return _children.iterator(); }
               public boolean isLeaf() { return false; }
            }
    

  • Which pattern does this exhibit?
  • Is this violation of LSP "bad"?
  • What would be the alternative?

Pattern review

• Name the patterns we have covered
• For each, give a one-line description of what problem is being solved
• For each, give an example where you might be tempted to use the pattern, but it would not be reasonable to use it
• What would an n-way search tree look like with all patterns applied?
• Explain how the Strategy Pattern implements "program to interfaces, not implementations"
  • What does programming to an interface mean?
  • Programming to an interface: using abstract classes/interfaces when declaring variables
  • Give an example with ArrayList