Assignment 2 Code Review

10 October 2002 - CS 509

Assignment 2 Code Review

Big Ideas
Design
- Top-Down design and stepwise refinement
Analysis
- What's the Problem?
- What's the Solution?
Design
- Animating scripts
- Animation steps
- Time steps
- Drawing boxes
Test Cases
Statistics
Coding problems

Big Ideas

A big idea is an apparently important part of a problem or its solution.
- "Apparently" because it might not be important.
- I though merging levels was a big idea; it wasn't.
A problem's big ideas tend to lead to a solution's big ideas.
- But not always, particularly for hard problems.
A big idea is a guess about what's important.
- Guesses can be wrong.
- Knowledge and experience make you a better guesser.
- A skilled professional is a good guesser.
Big ideas are important, not trivialities.
- Letter case, white space, input format are not big ideas.
- Changing big ideas significantly changes the solution.
- If it can be easily changed, it's not a big idea.
- Thus do big ideas become trivialities.

The Big Ideas

What are this problem's big ideas?
- Concurrent movement.
- Overlapping boxes.
- Animation steps.
These are in order of importance to the solution.
- Concurrent movement establishes the solution's structure.
- Overlapping boxes wasn't a big idea after all.
- Animation steps aren't a big idea either.
Knowledge determines big ideas.
- Big ideas become little ones through experience.
- For many of you, escape sequences are a big idea.

Design

Two main design problems: how to start, how to keep going.
How to start - top-down design.
- Start from the problem, work towards a solution.
- You'll always have a problem to work on.
- Why bother if you're not going to pay attention to the problem?
How to keep going - stepwise refinement.
- Each step adds detail to the problem.
- Solve the problem at each step.
- The step-to-step solution changes should be small.
There are other approaches.
- Bottom-up design.
- Object-oriented analysis.

Top-Down Design and Stepwise Refinement

Top-down design starts with the problem.
- You'll always have a problem.
- The problem can provide a lot of guidance.
Start small, step small.
- Abstract away almost all problem details.
- Re-introduce abstracted details one at a time.
- The solution changes in small, manageable steps.
You always have a working system.
- The initial solution works, but isn't useful.
- Each step keeps a working solution, improves usefulness.
- Test each step, add tests between steps.

Top-Down Design Problems

Abstraction is hard; some people don't get it.
- Usually your bosses, their bosses, and so on.
You have to make a lot of decisions all the time.
- And you have to remember them. And you have to fix them.
Sometimes it seems like it never ends.
- But, suddenly, it does.
All of these things are skills you have to learn

What's the Problem?

Input an animation script,
output the animation.
That's it; that's the problem.
- What's an animation script?
  - Who cares? Worry about it later.
- What happens if the box color is puce?
  - Who cares? Worry about it later.
Abstracting away almost all details leaves a simple problem.
- "Abstracting" means "delaying", not "forgetting".
- The abstracted details are reintroduced one at a time.

What's the Solution?

Writing down the problem practically describes the solution.

int main(int argc, char * argv[])

  if (argc != 1)
    std::cerr << "Command format is \"" << argv[0] << "\".\n"
    return EXIT_FAILURE

  animate_boxes(std::cout, read_script(std::cin))

This is not the only solution.

int main(int argc, char **argv)
  vector<string> vsStdInput = getInputRows()
  vector<Box> vBoxes
  MO_Vector vMoveOrders

  getBoxesMoves(vsStdInput, vBoxes, vMoveOrders)
  calcMoves(vMoveOrders)
  processMoves(vBoxes, vMoveOrders)

Which is better?
- Which is simpler?
- Which reflects the problem more accurately?

Now what?

Now what are the problems?
What's an animation script?
- I dunno. A data structure. An object. Whatever.
- It depends on what you want to do with it.
How do I read an animation script?
- This is not - should not be - a big problem.
How do I animate a script?
- This is a big problem; it has great influence on everything else.

Animating Scripts

How do I animate a script?

How do you animate anything?

Draw a scene; show it.
Change the scene according to the script.
Wait for the next scene.
Repeat until done.

void
animate_boxes(
  std::ostream & os, animation_script boxes)

  unsigned time = 0, next_step_time

  while true
    draw_boxes(os, boxes)

    if (!boxes.nearest_step_time(next_step_time)) break
    usleep((next_step_time - time)*1000)
    time = next_step_time

    boxes.step()

Animation Steps

When does a scene change?
- When boxes move.
When does that happen?
- It depends on the boxes' velocity: time/character.
- Time is measured in msec; distance in characters.
For example
What is d?
- r? c? r + c? max(r, c)? min(r, c)? sqrt(r*r, c*c)?
- It doesn't matter; pick one.

Time Steps

Computing the time steps isn't important; representing them is.
Absolute time steps allows a total ordering among all steps.
- Relative time steps don't.
With absolute time steps, the animation script becomes obvious.
- It's a priority queue of boxes, ordered by next step time.
- Concurrency now appears as two boxes with the same move time.
Animation script operations.
- nearest_step_time() returns the time at the queue head.
- step() moves the queue head boxes to the next step.
- When the queue is empty, everything stops.

Drawing Boxes

Drawing overlapping and merging boxes.
Overlapping boxes is easy: draw boxes by increasing level.
Draw the outline, then blank the insides.
- This is known as z-buffer hidden surface elimination.
Unfortunately this trick doesn't work for merging boxes.

Drawing Overlapping Boxes

The z-buffer trick doesn't work for overlapping boxes.
Fortunately, a slight modification does:
- Draw the outlines of all boxes at the same level.
- Blank the interiors of all boxes at the same level.
Order the boxes in the animation script by level.
- Start at the lowest level.
- Print the outlines of all boxes at a level.
- Erase the interiors of each box at a level.
- Repeat for the next highest level.
- Stop at the highest level.

Test Cases

There were five test cases:
1. The empty test.
  - Assignments are still failing this test.
2. The garbage test.
  - Assignments are still failing this test.
  - Make sure you print error messages.
3. An overlapping boxes test.
  - One assignment got this right; a couple came close.
4. An line accuracy test.
  - A few right; a few more close.
5. A moving boxes test.
  - A few right; a few more close.
These test cases are not complex.
- Although, admittedly, testing this program was hard.

Line Statistics - Newlines

	100	200	300	400	500	600	700	800	900	1000	1100	1200	1300	1400	1500	1600	1700	1800
0			1
10							1
20					1				1
30		1			1					1
40				1		1	2
50
60					2	1												1
70	1			1		1						1
80
90							2
Totals	1	1	1	2	4	3	5	0	1	1	0	1	0	0	0	0	0	1

Line Statistics - Semicolons

	000	100	200	300	400	500	600
0				1	1	1
10				3
20			2
30		1
40				1
50
60	1		1		1
70			1	1
80	1		1				1
90			2		1
Totals	2	1	7	6	3	1	1

Procedure Statistics

total	pages per procedure
procs	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
11	11
11	6	4			1
11	8	1	1	1
12	7	1	4
13	10	1						1										1
16	9	5	1	1
19	14	3	1	1
19	18		1
20	16	3				1
24	20	3	1
30	28	2
33	26	5	1	1
38	26	6	5	1
39	33	4	1		1
49	48			1
77	70	6	1

Know Your Tools

What's this?

bool checkForColor(string str)

  if ((strcmp(str.c_str(), "black") == 0) | 
      (strcmp(str.c_str(), "red") == 0) |
      (strcmp(str.c_str(), "green") == 0) | 
      (strcmp(str.c_str(), "yellow") == 0) |
      (strcmp(str.c_str(), "blue") == 0) | 
      (strcmp(str.c_str(), "magenta")== 0) |
      (strcmp(str.c_str(), "cyan" )== 0) | 
      (strcmp(str.c_str(), "white") == 0))
    return true
  else
    return false

How about this.

bool checkForColor(string str)
  return str == "black" || str == "red" ||
	 str == "green" || str == "yellow" ||
	 str == "blue"  || str == "magenta" ||
	 str == "cyan"  || str == "white";

Names Are Important

My implementation of the assignment was wrong.
- I flipped the coordinate system.
I started off with x and y, but switched to r and c.
- Unfortunately, x is c and y is r.
Consistent naming made this easy to change.
Also, none of my self tests caught this error.
- In fact, my test cases were wrong too.

Points to Remember

Figure out the big ideas.
- Learn to appreciate the important details.
Design from the top down with stepwise refinement.
- Little by little, bit by bit.
Understand the problem and its background.
- Animation and graphics.

This page last modified on 22 November 2002.