Assignment 2 Code Review

Lecture Notes for Advanced Programming II

16 October 2001 - Assignment 2 Code Review

Design Principle

Match the algorithm to the data.
- Trees are recursive, tree algorithms are recursive.
Understand the problem.
- Once properly formatted, a tree remains properly formatted.
- Properly formatted trees can be rigidly shifted around.

Properly Formatting Trees

To properly format a tree:
1. Properly format the children.
2. Properly position the children.
3. Properly position parent.

The algorithm.

format(root)

  for i = 0; i < root.children.size; i++
    format(root.children[i])

  fix root.children[0]
  for i = 1; i < root.children.size; i++
    position(root.children[i - 1], root.children[i])
 
  center parent over children
  width(root)

Simple Child Positioning

Use total tree widths.

And remember, trees are recursive

position(left, right)
  compute gap between left and right
  shift the right subtree to make the gap xsep.

width(root)
  if root.children.size == 0
    root.width = root.node.width
  else
    root.width = root.children[0].width
    for i = 1 to root.children.size
      root.width += x separation + root.children[i].width

shift(root, delta_x)
  root.x += delta_x
  for c in root.children
    shift(c, delta_x)

The width() code is wrong? Why?

What's Wrong?

Tree widths push siblings too far apart.
A level-by-level comparison works better.
Define the left and right boundaries of a tree.

Boundary Child Positioning

A tree's left- and rightmost nodes at each level.

position(left, right)
  compute the minimum gap between left's right boundary
    and right's left boundary
  shift the right subtree to make the gap xsep.

find_boundary(root)
  if root.children.size == 0
    left boundary = right boundary = root
  else
    root's left boundary = child 1's left boundary
      for c in root.children
        if c's left boundary extends below root's left boundary
          copy the below part to root's left boundary
    do the same for root's right boundary

This also solves balanced smaller subtrees.
- The same sized minimum gap between subtrees.

Algorithm Estimates

Input, processing, output.
Input
- Read a node description - 30 lines.
- Form a tree - 30 + 30 lines.
- 90 total lines.
Processing - two tree walks
- Position tree walk.
  - Shifting code - 10 lines.
  - Boundary code - 30 lines.
  - Walking code - 30 lines.
- Centering tree walk.
  - Walking code - 30 lines.
  - Shifting code - 30 lines.
- 130 total lines.
Output - 5 lines.
230 total lines, say 450 total lines.

Line Statistics - Newlines

	300	400	500	600	700	800	900	1000
0	1
10		2	1
20	1	2		1
30					1		1
40	1		1
50
60	1	1						1
70		1	1
80	1
90		1	3					1
Totals	5	7	6	1	1	0	1	2

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Line Statistics - Semicolons

	100	200	300	400
0		3
10		1
20		1		1
30	1	3
40	1
50	1	1
60	1
70	3
80	2	1
90	1	1	1
Totals	10	11	1	1

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Procedure Statistics

total	30-line pages per procedure
procs	1	2	3	4	5	6	7	8	9	10	11
1								1
1										1
2					1	1
4	2	1					1
4	2	1					1
5	4										1
7	2		3		1	1
8	3	2	2			1
8	3	3		1			1
10	7	2		1
12	9	1	1		1
13	9	2	2
15	12	1	1	1
16	14	1	1
19	17	2
20	17	2		1
28	26	1	1
35	30	2	1		1	1

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

File Statistics

File Counts	Count	Average Lines/File	Avg Semicolons per File
1	11	420	191
2	4	274	111
3	5	214	81
4	2	201	59
5	0
6	0
7	0
8	0
9	0
10	1	106	42

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

How People Lost Points

Empty input - 3.
Core dump - 6.
Mal-formed output - 6.
Memory exhausted - 1.
Improperly parsed input - 1.
Compiler problems - 1.

Follow the Directions

What's the output format?
d b 2 2 (-13,42)
n1 root 2 2 1.08488e+307 -20
n2 root 2 2 X-Cordinate 20
"root root 1 1 0 0 <root <<n1> <n2>>> " "root root 1 1 0 0 <root <<n1> <n2>>> " "root root 1 1 (0,0) <root <<n1> <n2>>> " "root root 1 1 0 0 <root <<n1> <n2>>> " "root root 1 1 0.00 0.00 <root <<n1> <n2>>> " "root root 1 1 0 0 <root <<n1> <n2>>> "
0 root root 1 1 0 0 <n2>>>

Think Before You Type

What is this?

int to_int(string& s) {
char* buf = new char[s.length()];
int ret;
s.copy(buf, s.length());
ret = atoi(buf);
delete buf;
return ret;
}

It's just this

int to_int(const string & s) {
  return atoi(s.c_str());
  }

Remember:
1. Think before you type.
2. Don't use character arrays.
3. Make sure you really need to use dynamic memory.
4. Know your tools.
5. You can't be sloppy too many times.
  One or two strikes rule.

Don't use Character Arrays

What is this?

const char * ptr1 = 0;
int len = s1.length();
char * ptr2 = new char[len + 1 ];

ptr1 = s1.data();
s1.copy(ptr2, len, 0);
ptr2[len] = '\0';

tokenPtr = strtok(ptr2, " ");
while (tokenPtr != NULL) {
  storage1.push_back(tokenPtr);
  tokenPtr = strtok(NULL , " " );
  }
delete [] ptr2 ;

See pages 88 or 103 in the text for better code.

Dynamic Memory is Not Your Friend

What is this?

class Node {

  friend class ListInt2;   

  private:

    char * child_label, * parent_label;
    int    height, width;
    int    x_coordinate, y_coordinate;
    char * restofdata;
    Node * next;

   public:

     Node();
     Node(const Node & p);
     Node(char*, char*, Node *, int, int, int, int, char*);

     char * get_child_label() const;
     char * get_parent_label() const;
     int    getwidth() const;
     int    getheight() const;
     int    get_x_coordinate() const;
     int    get_y_coordinate() const;
     char * get_restofdata() const;
     Node * get_next() const;

     void display_node() const;
     void operator = (Node &);
  };

This class has no destructor - it produces garbage.
The friend class doesn't inspire confidence.
Don't use character arrays.
Don't use dynamic memory if you don't have to.
This is bad, bad code.

Don't Use Character Arrays

Consider

Node::Node(const Node & p) {
  assert(p.get_child_label() != NULL);
  child_label = new char[strlen(p.get_child_label()) + 1];
  child_label = '\0';
  strcpy(child_label, p.get_child_label());
  assert(p.get_parent_label() != NULL);
  parent_label = new char[strlen(p.get_parent_label()) + 1];
  parent_label = '\0';
  strcpy(parent_label, p.get_parent_label());
  assert(p.get_restofdata() != NULL);
  restofdata = new char[strlen(p.get_restofdata()) + 1];
  restofdata = '\0';
  height = p.getheight();
  width = p.getwidth();
  x_coordinate = p.get_x_coordinate();
  y_coordinate = p.get_y_coordinate();
  next = p.get_next();
  }

With the string class this is

Node::Node(const Node & p) {
  child_label = p.get_child_label();
  parent_label = p.get_parent_label();
  restofdata = p.get_restofdata();
  height = p.getheight();
  width = p.getwidth();
  x_coordinate = p.get_x_coordinate();
  y_coordinate = p.get_y_coordinate();
  next = p.get_next();
  }

Is code format important?
- Find the error in the first version of Node::Node().

Don't Use Dynamic Memory

Remove the next link from Node and use a list.
```
typedef std::list tree;
typedef tree::iterator  node_itr;
```
- Node is independent of tree structure.
- No more pointers in Node.
- list is tested and efficient.
- No more explicit dynamic memory.

Another Clue - Repeated Code is Bad Code

Code bloat.
Makes maintenance and repair difficult.
- Find and fix everywhere.
Requires more work to understand.
- Almost repeated code is worse.

A Repeated Code Example

Have you seen this code before?

void Node::operator=(Node & p) {
  child_label = new char[strlen(p.child_label) + 1];
  child_label = '\0';
  strcpy(child_label, p.child_label);
  parent_label = new char[strlen(p.parent_label) + 1];
  parent_label = '\0';
  strcpy(parent_label, p.parent_label);
  height = p.height;
  width = p.width;
  x_coordinate = p.x_coordinate;
  y_coordinate = p.y_coordinate;
  restofdata = new char[strlen(p.restofdata) + 1];
  restofdata = '\0';
  strcpy(restofdata, p.restofdata);
  }

Do instead

void Node::copy_data(const Node & p) {
  child_label = p.get_child_label();
  parent_label = p.get_parent_label();
  restofdata = p.get_restofdata();
  height = p.getheight();
  width = p.getwidth();
  x_coordinate = p.get_x_coordinate();
  y_coordinate = p.get_y_coordinate();
  }

void Node::operator=(Node & p) {
  copy_data(p);
  }

Node::Node(Node & p) {
  copy_data(p);
  }

Much easier to understand the code now.
- Find the errors in operator =().

This page last modified on 6 December 2001.