Assignment 1 Code Review

25 September 2001 - Stream I-O

Design

• A sequence of max words.

  

• Keep track of each max-sequence.

  input, max = 3:

  A B C D E F
  

  stored as:

  A B C
  B C D
  C D E
  D E F
  E F
  F
  

• The first column are 1-tuples.

  The first and second column are the 2-tuples.

  The first three columns are the 3-tuples, and so on.

Refining the Design

• Counting's a pain, and it uses a lot of space.

  • Combine common words.

    

  • This is a recursive trick.

    

  • Keep track of counts.

    

• This is a tree.

  • Nodes at level i are i-tuples.

The Last Trick - Inserting New Words

• Build the max sequence in the tree itself.

• Each word contributes to max sequences.

• Keep a pointer to the end of each sequence in the tree.

• The pointer at level max goes back to the root.

Estimates

• Worst case space is still expensive.

• Worst case time is bad, average case is better.

• Code

  • Input - word read, tree insert, manipulate pointers.

  • Processing - none, really.

  • Output - tree walk, output at each node.

• Code sizes.

  • Input - 5 + 20 + 10 = 35 lines.

  • Processing - 10 lines.

  • Output - 20 + 5 = 25 lines.

  • Miscellaneous - 20 + 20 = 40 lines.

  • Total - 35 + 10 + 25 + 40 = 110 lines.

Line Statistics - Newlines

Line Statistics - Semicolons

Procedure Statistics

File Statistics

How People Lost Points

• EOF abuse - 2

• Char array abuse - 1

• Empty input abuse - 3

• Incorrect tuple counts - 4

• No comments - 2

• Too much code - 1

Don't Use Char Array Strings - I

• They're dangerous.

  #define MAX_WORD_SIZE 80
  
  char word[MAX_WORD_SIZE];
  
  while(true >> word;
    if(cin.eof()) break;
    // blah blah blah
    }
  

• This is a buffer-overflow error.

  Half-Life vulnerability announcement
  www.securityfocus.com, 20 September 2001

  A problem in the software package could allow
  a malicious server to execute arbitrary code.
  This could allow unauthorized local access.

  The problem is in the /Connect command. This
  command is used by a client to negotiate a
  connection with a server on a specific IP address
  and port. A buffer overflow in this command occurs
  when 128 bytes or more of data have been received.

Don't Use Char Array Strings - II

• They're hard to use correctly.

  while (cin.getline(word, MAX_WORD_SIZE))
    // blah blah blah
  

• But, that chops off long words.

  while (true)
    cin.getline(word, MAX_WORD_SIZE)
    if (cin.fail())
      // partial long word.
    if (cin.eof())
      // eof.
    // blah blah blah
  

• But, that ignores short words.

  while (true)
    cin.getline(word, MAX_WORD_SIZE)
    if (cin.fail())
      // partial long word.
    if (cin.gcount() > 0)
      // non-long word
    if (cin.eof())
      // eof.
    // blah blah blah
  

• But, the interactions are still wrong.

Dynamic Memory Is Not Your Friend - I

• What is this?

  string lowerCase(string s) {
    char* buf = new char[s.length()];
    s.copy(buf, s.length());
    for(int i = 0; i < s.length(); i++)
      buf[i] = tolower(buf[i]);
    string r(buf, s.length());
    delete buf;
    return r;
    }
  

  It's this:

  string lowerCase(string s) {
    for(int i = 0; i < s.length(); i++)
      s[i] = tolower(s[i]);
    return s;
    }
  

Dynamic Memory Is Not Your Friend - II

• If you need to use it, use it correctly.

  LList::~LList() {
    ListNode * curr = firstPtr, *temp;
    while(curr != 0){
      temp = curr;
      curr = firstPtr->nextPtr;
      delete temp;
      }
    }
  

Understand the EOF Condition

• This is wrong:

  while (cin.eof()) {
    cin >> word;
    WordList.push_back(word);
    }
  

• This is why:

  $ echo x | count-tuples
  2       x
  
  $ 
  

• This is right:

  while (true) {
    cin >> word;
    if (cin.eof()) break;
    WordList.push_back(word);
    }
  

  or just

  while (cin >> word)
    WordList.push_back(word);
  

Other Points to Keep In Mind

• Avoid globals.

  • Globals complicate program understanding and change.

• No unnecessary output.

  • It's annoying.

    $ count-tuples < /dev/null
    FILE IS EMPTY PLEASE TRY AGAIN !
    
    $
    

  • It breaks the Unix style.

• Keep it simple - what's the loop invariant?

This page last modified on 25 September 2001.