Advanced Programming I Lecture Notes

30 March 2006 • Assignment 4 Code Review

Outline

• Assignment 3 review.

• The problem.

• Some solutions.

• Testing

• Results

• Coding observations.

Assignment 3 Review.

• A concordance ADT.

  class concordance
  
    concordance(text-file)
  
    void add-page(page)
  
    page-list on-pages(string word)
  
    word-list has-words(unsigned page-no)
  

Assignment 3 Review..

• A query ADT.

  class query
  
    query({ string, string, ... })
    query({ unsigned, unsigned, ... })
  
    unsigned count()
  
    string get-word(unsigned)
    unsigned get-pno(unsigned)
  

Assignment 3 Review...

• A page ADT.

  class page
    page(string)
    unsigned page-no()
    unsigned size()
    string get-word(unsigned)
  

• Word- and page-lists.

  typedef lst<string> word-list
  typedef vctr<unsigned> page-list
  

Assignment 3 Review....

• General solution.

  
  concordance conc(argv[1])
  query q
  
  while cin >> q
    // for pno pno ... queries
  
    common = conc.has-words(q[0])
    for i = 1 to q.size()
      common ∩= conc.has-words(q[i])
    cout << common
  
    // similar for word word ... queries
  
  

The Problem

• Build an n-neighbor tree.

  • An n-way tree for indeterminate n.

  • Each child is an n-neighbor of its parent.

  • Each node (word) is unique in the tree.

• Trees are specified as

  root-word n
  

N-Neighbors

• From the assignment:

  The n-neighbors of w are all the words that also appear on each of the pages i - n/2 through i + (n - n/2).

• This seemed to cause two difficulties:

  • The value of i.

  • The page range [ i - n/2, i + (n - n/2) ].

N-Neighbor Problems

• From the assignment:

  Let w be a word appearing on each of the pages i - n/2 through i + (n - n/2) of a text for non-negative n.

  • i is a page number.

• i is any page number; just add n/2 to it.

  [ (i + n/2) - n/2, (i + n/2) + (n - n/2) ]
  [ i, i + n ]

Computing N-Neighbors.

• How do you find n-neighbors?

  • We've already solved that problem:

    ? i i + 1 ... i + n

    that is

    word-list 
    n-neighbor(unsigned i, unsigned n)
      query q({ i, i + 1, ..., i + n } )
      return conc.has-words(q)
    

Computing N-Neighbors..

• How do you find n-neighbors for word w?

  word-list 
  n-neighbors(string w, unsigned n)
    word-list nn
    page-list pages = 
      conc.on-pages(query({ w }))
    if pages.count() > 0
      nn = n-neighbors(pages[0], n)
      for i = 1 to pages.count()
        nn ∪= n-neighbors(pages[i], n)
    return nn
  

Unique N-Neighbors

• The n-neighbors of w are unique in the tree.

  word-list all-words
  
  word-list nn = 
    wn-neighbors(w, n) - all-words
  
  // add words in nn to the tree
  
  all-words = all-words ∪ nn
  

• all-words is a global, or passed around as a parameter.

Building The Tree

• The tree should be built breadth-first.

  build-tree(word, n, all-words)
    queue q(new tree-node(word)
    do tnode = q.deq()
       nn = wn-neighbors(tnode.w, n) - 
         all-words
       all-words = all-words ∪ nn
       for w in nn
         c = new tree-node(w)
         tnode.add-child(c)
         q.enq(c)
    while not q.empty()
  

Unbounded N-Way Trees

• The n-neighbor tree should support an unbounded number of children.

  • And the operations child_count(), add_child() and get_child().

• There are three ways to go:

  1. Use a vector.

  2. Use a linked list.

  3. Use a binary tree.

Vector N-Way Trees

• With a simple implementation of vectors, the tree node is

  class tree-node
  
    vtr<tree-node *> children
  
    size-t child-count()
      return children.size()
  
    tree-node * get_child(i)
      return children.get(i)
  
    void add_child(tree-node * c)
      return children.push_back(c)

List N-Way Trees

• The children are kept in a linked-list.

• child_count() is implemented using the list size().

• add_child() inserts the new child at the end of the list.

• get_child() walks the list, returning the ith element.

Binary N-Way Trees

The two pointers in a binary tree node are usually interpreted as pointers to the left and right children.	class node T data node * left, * right
However, they can also be interpreted as pointers to the children and siblings.	class node T data node * children, * siblings

Child-Sibling Tree Examples

Child-Sibling Trees

• The sibling link is essentially a part of a singly-linked list.

  • This allows arbitrarily long chains of siblings.

    • That is, an unbounded n-way tree.

  • It avoids declaring different tree-node classes.

• The cost is more complicated linked-list-like manipulations on the children.

And Finally

• With all the pieces in place, the solution is

  int main(argc, argv)
  
    concordance conc(argv[1])
    query q
  
    while cin >> q
      show-tree(
        build-tree(
          q.word, q.n, word-list(q.word))
  

Bottom-Up Design

• The foregoing was an example of bottom-up design.

  It's easy to get pointed the wrong way with bottom-up design.

• However, the presence of well-designed high-level libraries can make bottom-up design the simpler approach.

Test Cases

• The empty and garbage tests.

• The quiz test.

• Grandchild test.

• Single-appearance test.

Test Results

• Two assignments didn't compile.

  	Tests
  	1	2	3	4	5
  1
  2
  3
  4