Data Structures & Algorithms Lecture Notes

6 November 2008 • Assignment 1a Code Review

Outline

• The problem.

• Testing

• Coding observations.

The Problem

• Make sure you understand the problem.

  • You can't possibly solve the problem if you don't understand it.

• Make sure you follow the directions.

  • People and code are going to rely on your ability to do so.

No Prompting

• If the problem doesn't ask for decorative input or output, don't provide it.

• People and programs not expecting decoration will get confused by it.

  ??? Unexpected output from std-out (between --):
  --
  Enter sequence for region:
  --

Testing

• Always test your code.

  • I'm going to.

• Tests don't have to be complicated.

  • Lots of simple tests run all the time.

• When you find an error, write a test for it and add it to your test suite.

Tests

• The test cases were simple:

  1 1 1 1
  -1 1 1 1
  1 -1 1 1
  1 1 -1 1
  1 1 1 -1
  1 1 1
  1 1
  1
  30x100 region
  

• Simple tests run frequently do the job.

Coding

• Program Defensively.

• No coredumping.

• Know your tools.

• Coding style.

  • Write small functions.

  • Document your functions.

Program Defensively

• Imagine the error cases, then write your program to handle them.

  • “Handle” means “not coredumping.”

• The answer to the question

  “Can input be like this...?”

  is “Yes.”

Fixed-Size Arrays

• Using Fixed size arrays is poor programming.

  • Particularly when unprotected.

  • Fixed limits are not general.

  int region[15][15]
  
  int main()
    int rows, cols
    cin >> rows >> cols
    // if rows*cols > 15*15: oops!
    for (int r = 0; r < rows; r++)
      for (int c = 0; c < cols; c++)
        cin >> region[r][c]

No Coredumping

• A coredump is an unexpected, abnormal termination.

• Coredumping looks like this:

  ../../test-code: line 165: 10192 Segmentation fault ...
  
  ../../test-code: line 133: 10060 Killed ...

• It is easy to coredump programs in C++.

  • Particularly when pointers are involved.

• It's your responsibility to make sure coredumps don't happen.

Unchecked Input

• Never use unchecked input.

  cin >> regionSizeA >> regionSizeB
  loopSize = (regionSizeA*regionSizeB)
  int * elevationArray = new int[loopSize]
  

• What's regionSizeA? What's regionSizeB? Who knows?

  terminate after throwing an instance of 'std::bad_alloc'
  what():  St9bad_alloc
  ../../test-code: line 185:  3683 Done
  3684 Aborted (core dumped)
  
    

Know Your Tools

• C++ and the standard library are powerful tools.

  • They can give you a lot of help, if you know how to work them.

  • But they're also complex to learn and use.

Easy I-O Example

static std::string
read_signed(std::istream & ins, int * value)

  // Read an int from ins and store it in *value.  
  // Return an error message or the empty string 
  // if no errors.

  ins >> *value
  if (ins.eof())
    return "Unexpected eof"
  if (ins.fail())
    return "Unexpected non-integer value"
  if (ins.bad())
    return "Unrecoverable I-O error"

  return ""

A Harder Alternative

bool isNotAnInt(string s)
  bool isNaI = false
  if (s[0] == '-') //if it's a negative number
	  //skip 1st character, goes through chars in string 
	  for (unsigned int k = 1; k < s.length(); k++)
		  //if it's not a # or if it's a decimal
		  if(!(isdigit(s[k])) || s[k] == '.')
			  isNaI = true
  else
	  //goes through chars in string
	  for (unsigned int j = 0; j < s.length(); j++)
		  //if it's not a # or if it's a decimal
		  if (!(isdigit(s[j])) || s[j] == '.')
			  isNaI = true
  return isNaI

int validateWidth(string s)
  int number = atoi(s.c_str())
  if (isNotAnInt(s))
    // error
  else if (!(withinRange(number)))
    // error
  else
    return number

int getWidth()
  string strWidth
  cin >> strWidth
  return validateWidth(strWidth)

Write Small Functions

• Each functions or procedure should be small: 20 to 30 lines.

  • Small functions are focused.

  • The less it does, the less likely it is to go wrong.

  • A small function is easier to understand than a large one.

Comment Functions

• Each function should have a comment describing what it does and how to use it.

  • Nothing about how it works, or why.

• How to use it:

  • The inputs and outputs, including globals.

  • The relation between inputs and outputs.

  • The error conditions.

Example Function Comments

• Good

  // Takes string and returns true if it is 
  // an int and false if it is not an int.
  
  bool isNotAnInt(string s) { ... }
  

• Better (answers more questions).

  // Return true iff the entire string s can
  // be interpreted as a decimal integer.
  
  bool isNotAnInt(string s) { ... }
  

An Interesting Case

*** 1 1 1 1 test.
*** -1 1 1 1 test.
*** 1 -1 1 1 test.
*** 1 1 1 -1 test.

??? Unexpected output from std-err (between --):
--
!!!Rainfall should be a non-negative integer, Not, -1
--

*** 1 1 1 test.

??? Output expected from std-err, none produced.

*** 1 1 test.
*** 1 test.
*** 30x100 test.

Copying Code

• How could single tests fail, but the other tests pass?

  cerr << "!!! Row should be non negative, not " << row
  
  cerr << "!!! Column should be non negative, not " << col
  
  cerr << "!!! Region height should be an integer" << endl
  
  cerr << "!!!Rainfall should be non-negative, Not, " << rainfall << endl

• Duplicating code increases bulk and chances for mistakes.

Code Factoring

• Factor duplicate code into procedures.

void perr(const string & emsg)
  cerr << "!!! " < emsg < ".\n"
  exit(EXIT_FAILURE)

perr(string("Row should be non negative, not ") + row)

perr(string("Column should be non negative, not " + col)

perr("Region height should be an integer")

perr(string("Rainfall should be non-negative, not ") + rainfall)