Assignment 1 Code Review

11 February 2003 - CS 509

Assignment 1 Code Review

Programming practice.
The Test Cases
Design
Statistics
Follow Directions
Procedure Size
Strings vs. Character Arrays
Use Named Constants
Understand Your Tools
Other Irritants

You Must Program Well

This is a programming course - submit code that compiles.
- Two people didn't.
- Just submitting int main() { } gets more points than submitting code that doesn't work.
- And don't submit late.
Learn proper stream termination.
You are responsible for every vector access you make.
- SaferSTL caught many many invalid vector accesses.

Understand The End-of-Stream Condition

The EOS condition is not set until the EOS position is read.
- Knock on the door, then assume nobody's home.
- Read the assignment before you take the test, not after.

This code does not work properly.

while (!(std::cin.eof())) {
  std::getline(std::cin, ln);
  // whatever.
  }

.eof() doesn't produce a useful value.
- It's always one behind the most recent read.
- The first value is completely useless because there was no previous read.
getline() could fail.
- .eof() is telling you about the previous read, not the one that's about to be made.

Correct End-of-Stream Testing

The correct approach is to read before you test.

while (true) {
  std::getline(std::cin, ln);
  if (std::cin.eof()) break;
  // whatever
  }

Or, even simpler,

while (std::getline(std::cin, ln)) {
  // whatever
  }

And don't freak out either.
```
if (std::cin.eof()) return;

while (std::getline(std::cin, ln)) {
  if (std::cin.eof()) break;
  // whatever
  }
```
- This code is not the mark of a competent programmer.
- The record is five eof tests in one loop.

Make Valid Vector Accesses

SaferSTL explodes on an invalid vector access.


$ gdb tidytree

(gdb) run < /dev/null

Starting program:  tidytree < /dev/null
Accessing element 0 in an empty vector.
Program received signal SIGABRT, Aborted.

(gdb) up 4

#4 findRoot() at main.cc:27
27       int y = clist[0].vpoint[0].y;

(gdb) print clist.size()

0

(gdb)

How did this happen?

int main () {
  while (getline(cin, buf)) {
   stroke s1(buff);
   if ( s1.fig == CIRCLE )
      clist.push_back(s1);
   }
  }

Don't Kill Yourself

What's wrong with this?

for (unsigned i = 0; i < stk.size(); i++)
   tvec.push_back(slope(stk[i], stk[i + 1]));

How do you fix it?
```
for (unsigned i = 0; i < stk.size() - 1; i++)
   tvec.push_back(slope(stk[i], stk[i + 1]));
```
What's wrong with this?
- .size() is unsigned.
- ((unsigned) 0) - 1 = 4294967295 (on a sparc).

This can get subtle.

for (unsigned x = 0; x < pts.size(); x += 2)
  point.first = pts[x];
  point.second = pts[x + 1];

What's wrong with this?

What's the missing assumption (and assertion)?

The Test Cases

The empty test tidytree < /dev/null.
The garbage test tidytree < tidytree.
A single node.
A vertical dumbell.
- Precise, positive precise, and stroke input.
A horizontal dumbell.
- Precise and stroke input.
A parent and two children.
- Positive precise and stroke input.

The Test Results

Each test gets one of five marks: y, +, -, n, f.
There were ten tests, and ten programs tested.

f n - + y

1 2 1 0 0 7

2 3 1 0 0 6

3 3 6 0 0 1

4 4 6 0 0 0

5 7 3 0 0 0

6 5 5 0 0 0

7 4 6 0 0 0

8 7 3 0 0 0

9 7 2 0 0 1

10 5 3 0 0 2

Test Your Code

Test your code - it's important.
- Only three people got any tree test right.
- Nobody got the single-node test right.
The tests don't have to be complicated.
- Simple tests applied consistently do the trick.
- Good coding habits keep you out of obscure danger.
Testing your own code is hard.
- Your own child never needs a spanking.
- Get someone else to do it.
Code a little, test a little.

Design

Algorithm design, not program design.
- Think before you type.
- Everything follows from a thought-out plan.
Understand the problem before attempting a solution.
- Read and understand the problem.
  - You'll always have the problem.
- Understand the problem's background too.
  - But don't get carried away; solve the problem in front of you.
Good programmers solve problems, they don't write code.
- No amount of typing can replace a good idea.

The Problem

What's the problem?
- I need to be able to
  1. Read the strokes.
  2. Classify the strokes.
  3. Organize the strokes into a tree.
  4. Tidy up the tree.
  5. Output the tree.
How do you solve this problem?
- How about
```
int main() {
  strokes = read_strokes(std::cin)
  classify_strokes(strokes)
  root = organize_strokes(strokes)
  tidy_tree(root)
  output_tree(std::cout, root)
  }
```
Read The Strokes
- Don't re-invent the wheel.
  - Stream extraction already skips spaces, parses ints.
- A line of text contains a stroke.
  - Reading a line's easy: getline(cin, line).
- A stroke contains a bunch of points.
  - Reading points are easy:
```
while (iss >> pt) 
  pts.push_back(pt)
```
- A point contains a pair of ints.
  - Reading a point's pretty easy:
```
istream& operator>>(istream& is, point& pt)
  return is >> pt.x >> pt.y
```
- But wait - what's iss?
  - Oh, that - it's an string input stream:
```
std::istringstream iss(line);
```

Classify The Strokes

How do you tell a node stroke an edge stroke?
- A node stroke is curvy, an edge stroke less so.
- But what is "curvy"?
How else are they different?
- Node endpoints are close, edge endpoints aren't.
- "Close" means what?
Aha! Their distance relative to the stroke.
- Draw the bounding box and consider the diagonal.
- Node endpoints are a small fraction of the diagonal.
- Edge endpoints are a large fraction of the diagonal.
It's not perfect, but it gets the job done.

Organize The Strokes

With bounding boxes, this was easy.
- Find the node boxes that intersected with edge boxes.
- Do sanity checks on the edges.
- Order the boxes by y value to simplify the search.
  - But it's simple and fast enough to intersect every box with every box.
This well works, but only for small and neatly drawn trees.
- The edge bounding box is too big.
A colleague compared node-center slopes with egde slopes.
- Cleaver, but required too much work for me.
Shrink the bounding boxes to be around the edge endpoints.
- As simple as the earlier solution and much more robust.
- Make ordering the children easier too.

Tidying the Tree

You can fix the root and work down, or fix a leaf and work up (and down).
- I find fixing the root too hard.

Trees have nice recursive algorithms for everything.

int tidy_tree(root, left_x, y)

  if (root.is_leaf())
    root->set_center(left_x + node_radius, y)
    return left_x + 2*node_radius

  right_x = 
    tidy_tree(root.left, left_x, y + gap)
  right_x = 
    tidy_tree(root.right, right_x, y + gap)
  root->set_center((left_x + right_x)/2, y)

  return right_x

A similar algorithm prints the tree.
- One pass for nodes, another for edges.

Line Statistics - Newlines

	100	200	300	400	500	600	700	1500
0			1
10
20			1	1				1
30			2
40				1
50							1
60						1
70		1
80		1		1
90	1
Totals	1	2	4	3	0	1	1	1

Line Statistics - Semicolons

	100	200	300
0
10	1
20
30		1	1
40	1	1
50	2
60	2
70	1	2
80			1
90
Totals	7	4	2

Procedure Statistics

total	pages per procedure
procs	1	2	3	4
2	2
7	5	2
9	8	1
11	2	5	3	1
11	7	4
22	16	6

Follow Directions

No tree is o.k.

$ parsess < /dev/null
Invalid Input

$

One node is o.k.

$ tidytree < one-node
Error Not enough edges.

$

What's Wrong With This Code?

void calcAngleDiff()

  bool found = false
  int i=0, psize = pv.size()
  int idx1 = 0

  for (i = 1;  i < psize; i++)
    if (pv[0].x !=  pv[1].x)
      idx1 = i;
      break;

  adjdiff = 0.0;

  for (i = idx1 + 1;  i < psize; i++)
    if ((pv[0].x > pv[idx1].x  && pv[i].x >  pv[0].x ) ||
        (pv[0].x < pv[idx1].x  && pv[i].x <   pv[0].x ))
      found = true;
      adjdiff =  dv[idx1] - dv[i];
      break;

  for (i = 1; i < psize; i++)
    if (pv[0].y !=  pv[1].y) 
      idx1 = i;
      break;

  enddiff = dv[psize] - dv[idx1];

Let me make it easy for you.

void calcAngleDiff( ) 
  int psize = pv.size()
  enddiff = dv[psize] - dv[idx1]

Procedure Size Matters

Small procedures are easy to design, write, and understand.
- "Small code" means at most 20 to 30 lines.
- If you can't write a simple, complete sentence describing function, it's probably too big.
There may be a lot of small procedures, but
- You don't have to understand them all at once.
- You can corral them in files, classes, and name spaces.

Use Named Constants

An unnamed constant is a magic number.
- It just appears; no reason, no explanation.
```
if (r_bstr[i] < 48 || r_bstr[i] > 57)
```
  48? 57? What are these? Are you sure?
Explanations don't really help.
```
if (str1[loc] == 32) // 32 is ASCII char sp
```
Oh? Is everything ASCII?
They are hard to change.
```
char ch[200]
while cin.getline(ch, 200, '\n')
  ...
  f(200)
  ...
```
Have you changed all proper values?
Have you left alone all other values?

Points to Remember

Understand the problem
- You can't solve it if you can't understand it.
Think before you program.
- A little thinking replaces a lot of typing.
Test your code.
- Find your errors before others do.
Use good programming practice.
- Small procedures, named constants.
Know your tools.
- They are there to help you.

This page last modified on 11 February 2003.

	f	n	-	+	y

1	2	1	0	0	7
2	3	1	0	0	6
3	3	6	0	0	1
4	4	6	0	0	0
5	7	3	0	0	0
6	5	5	0	0	0
7	4	6	0	0	0
8	7	3	0	0	0
9	7	2	0	0	1
10	5	3	0	0	2

	f	n	-	+	y

1	2	1	0	0	7
2	3	1	0	0	6
3	3	6	0	0	1
4	4	6	0	0	0
5	7	3	0	0	0
6	5	5	0	0	0
7	4	6	0	0	0
8	7	3	0	0	0
9	7	2	0	0	1
10	5	3	0	0	2

	f	n	-	+	y

1	2	1	0	0	7
2	3	1	0	0	6
3	3	6	0	0	1
4	4	6	0	0	0
5	7	3	0	0	0
6	5	5	0	0	0
7	4	6	0	0	0
8	7	3	0	0	0
9	7	2	0	0	1
10	5	3	0	0	2