Advanced Programming I Lecture Notes

30 March 2007 • Assignment 4 Code Review

Outline

• Background

• The problem.

• A solution.

• Testing

• Results

• Coding observations.

Background: XML

• XML documents are trees.

  <class>
    <name> ... </name>
    <room> ... </room>
    <days> ... </days>
  </class>
  

• XPath expressions match XML documents parts.

  /class/name/following-sibling::*
  

Background: LDAP

• LDAP directories are attributed trees.

  

• LDAP search expressions match directory parts.

  (& (objectClass = person)
     (| (givenName = John) (mail = john*)))
  

The Problem

1. Read in a tree T.

2. Read in a sequence of path patterns.

3. For each path pattern p read

   1. Find all matches to p in T.

   2. Print out the matches.

A Solution

int main()
  std::string emsg
  nary_tree t = input_tree(std::cin, emsg)
  if not emsg.empty()
    std::cerr << "! " << emsg << ".\n"
    exit(EXIT_FAILURE)

  path_pattern pp
  while input_path_pattern(std::cin, pp)
    output_matches(
      std::cout, match_paths(t, pp))

• Any questions?

Wish List

Tree Input

• Consider the cases: having read in green, what's next?

      green
        red
      blue
    white
  

  • Red has greater indentation than green.

  • Blue has the same indentation as green.

  • White has smaller indentation than green.

Indentation Illustrated

green red blue white

Indentation Cases

• Greater indentation indicates a child.

  • Add it to the current node.

• Equal indentation indicates a sibling, a child of the current node's parent.

  • Let the parent deal with it.

• Lesser indentation indicates a distant relation, a child of an ancestor of the current node.

  • Let the proper ancestor deal with it.

Inputting A Tree

nary-tree 
tree-input(istream & is, string & emsg)

  node-data nd
  read-node-data(is, nd, emsg)

  const unsigned indent = nd.indent
  nary-tree t = nary-tree(nd.label)

  while peek-node-data(is, nd, emsg) and 
        nd.indent > indent
    t.add-child(tree-input(is, emsg))

  return t

Indentation Errors

• The root should not have siblings or ancestors.

nary-tree input-tree(istream & is)

  if ¬peek-node-data(is, nd)
    return nary-tree()

  const nary-tree t = tree-input(is)

  if peek-node-data(is, nd)
    emsg = "Root with a sibling or parent"

  return t

Path Matching

What does the problem say? The path pattern p1 p2 ... pi matches the path N1 N2 ... Ni if pj = nj.label for 1 ≤ j ≤ i.

Matching Paths

• The code follows immediately:

  match(t, p, i)
  
    if p.size == i
      found a match
  
    else if t.label = p[i]
      for c in t.children
        match(c, p, i + 1)
    

• But what about wildcard matching?

Wildcard Matching

• The wildcard * matches any label.

  match(t, p, i)
  
    if p.size == i
      // found a match.
  
    else if t.label = p[i] ∨ "*" == p[i]
      for c in t.children
        match(c, p, i + 1)
    

• But what is the match with wildcards?

Partial Matching

• Pass the partial match along:

  match(t, p, i, mtch)
  
    if p.size == i
      // mtch is the complete match.
  
    else if t.label == p[i] ∨ "*" = p[i]
      mtch = mtch + " " + t.label
      for c in t.children
        match(c, p, i + 1, mtch)
    

• Does this find all the matches?

Complete Matching

• Don't forget to match against the children too.

  match(t, p, i, mtch)
  
    if p.size == i
      // mtch is the complete match.
  
    else if t.label == p[i] ∨ "*" == p[i]
      mtch = mtch + t.label
      for c in t.children
        match(c, p, i + 1, mtch)
  
    for c in t.children
      match(c, p, 0, "")
    

Data Structures

• A path pattern is an array of strings.

• Path matches are a set (or an array) of strings.

• An n-ary tree is a string label and a bunch of children.

  class nary-tree {
    string label
    sequence children
    }
  

  • A sequence is a variable-length array of nary-tree pointers.

Testing

• Garbage and empty tests.

• One-node trees with some or no matches.

• Two-node trees with some or no matches.

• Three-node trees with some or no matches.

• Corner cases:

  trees and no patterns
  patterns and no trees
  trees with root parents or siblings

Results

	Tests
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
1
2
3

Empty Input

• Handle unexpected input gracefully.

  • Gracefully: don't die, and don't freak out.

• The problem defines unexpected input.

  • If it doesn't, find out.

  • If it does, pay attention.

• The assignments rarely consider empty input invalid.

Empty Input Don'ts

*** Empty tree with path patterns

Input (between the --- lines):
---

red
*
---

Expected output (between the --- lines):
---
---

Actual output (between the --- lines):
---
! Error! No input!
---

Don't Prompt.

• Excessive, unrequested prompting is confusing.

  • Both for humans and machines.

• Don't prompt on input;
  don't excessively decorate output.

  • But there are human factors to consider.

  • Notice the “human” in the last point.

Prompting Don'ts

*** Two-node tree with no two-node match

Input (between the --- lines):
---
red
  blue

blue red
---

Expected output (between the --- lines):
---
---

Actual output (between the --- lines):
---
[none]
---

Write Useful Comments

• Comments should describe what the function does and how to use it.

  
  // Finds the appropriate place to put a
  // node in a tree that already has a root.
  
  void findSpace(
    nodePtr& root, nodePtr& newNode, 
    int& numberOfNodes, int& treeDepth)
  

• This isn't a game of Twenty Questions.

Obey the Rule of Three

• If a class has a pointer instance variables, it must have

  1. a destructor,

  2. a copy constructor,

  3. and an assignment operator.

• Classes that don't obey the Rule of Three are wrong.

The Miscreants

struct node { string label node* parent int indent int nodeDepth int noOfChildren node** children }

template<class T> struct clist{ public: clist() void addnode(T* achild) void delnode() void setfirst(cnode<T>*) cnode<T>* getfirst() int getsize() void pprint() void printloop(cnode<T>*&) private: cnode<T>* first int size }

• These classes are wrong.

References

• The XPath reference, description and tutorial.

• The Lightweight Directory Access Protocol.