Algorithms

• There are two algorithms - generating and generated

• The generating algorithm is simple - read, eval, print

  • Read the commands.

  • Eliminate the duplicates.

  • Print the code.

• The generated algorithm is a bit harder

  • Search for prefix matches.

  • Copy each match found.

Algorithm Estimates

• 10 lines for the generated algorithm.

  • 5 lines to prefix match.

  • 5 lines to search for matches.

• 40 lines for the generating algorithm.

  • 5 lines to read commands.

  • 10 lines to find duplicates.

    • 5 lines to search.

    • 5 lines for a case-insensitive search.

  • 25 lines to print.

    • 5 lines to print commands.

    • 20 generated-code lines.

• Generating algorithm is O(n²).

• Generated algorithm is O(n).

File Counts

Code Size, Newlines

Code Size, Semicolons

Procedure Statistics

How People Lost Points

Not handling the empty prefix - 5

Not handling big commands - 4

Not handling many commands - 2

Not handling duplicates - 2

Not doing prefix matching - 3

Not doing storage management - 10

Be Straightforward

while( (input=getchar()) != EOF )
  switch (input) {
    case SPACE:
      if (last_digit == COMMAND) {
	command_list = realloc(command_list, strlen(command_list) + 2);
	if (command_list == 0) {
	  cout << "Error: Not enough memory." << endl; 
	  exit(-1);
	  }
	strcat (command_list, " ");		
	}
      last_digit = EMPTY;
      break;

    case ENTER:
      break;

    default:
      command_list = realloc(command_list, strlen(command_list) + 2);
      if (command_list == 0) {
	cout << "Error: Not enough memory." << endl; 
	exit(-1);
	}

      if (input>='A' && input <= 'Z')
	input = input+'a'-'A';
      token[0] = input;

      strcat (command_list, token);
      if (last_digit==EMPTY) cmd_number ++;
      last_digit = COMMAND;
      break;
    }

Don't Use char * Strings

int MAX_LEN_OF_CMD = 300;
char inputCmd[MAX_LEN_OF_CMD];

cin >> inputCmd;
while (!cin.eof()) {
  if (noOfCmd > 0)
    cout << "," << endl;
  cout <<  "                      \"" << inputCmd << "\"";
  noOfCmd++;
  cin >> inputCmd;
  }

• char * are unsafe and inconvenient - don't use them.

• If you must, use them safely.

  • cin.getline(inputCmd, MAX_LEN_OF_CMD)

  • But this is complicated and unnecessary.

Always Know Where Array Writes Go

string words[4000];
int counter = 0;
int l;

cin >> words[counter];
while(!cin.eof()) {
  l = words[counter].length();
  for(int m = 0; m < l; m++) {
    if (isupper(words[counter][m]))
      words[counter][m] = static_cast(tolower(words[counter][m]));
    }
  counter++;
  cin >> words[counter];
  }

• Good code doesn't have fixed limits.

• If you must fix limits, check them.

• No magic numbers.

• What's up with that cast?

Know Your Tools

string convert_to_uppercase_and_quotes(string input_command) {

  // converts string from lower to upper case
  // adds \ for quotes 

 int size = input_command.length();
 static string output_command;
 
 for(int x=0; x<=size; x++)
  if(input_command[x] >= 'a' && input_command[x] <= 'z')
     output_command += (input_command[x]-TO_UPPER);
  else {
    if (input_command[x] == '\"')
       output_command += '\\';
    output_command +=input_command[x];
    }

 return output_command;
 }

• How about
  

  if (islower(input_command[x]))
    output_command += toupper(input_command[x])
  

• Escaping quotes is excellent, but . . .

• Is static necessary?

Know Your I-O

• I-O in C++ is hard and obscure.

  string s;
  
  while(cin && (cin.peek()!=EOF)) {
    void eat_white();
    cin >> s;
    eat_white();
    // and so on.
    }
  

• Be as plain as you can.

  while (cin >> s) {

• It probably does what you want to do.

  • Skip white space.

  • Indicate end of file.

Know Your Limits

int size = cmd_in.length();
static string cmd_out;

for (int x = 0; x <= size; x++) {
 if (cmd_in[x] >= 'a' && cmd_in[x] <= 'z')
   cmd_out += (cmd_in[x] - TO_UPPER);
 else{
   if (cmd_in[x] == '\"')
     cmd_out += '\\';
   cmd_out += cmd_in[x];
   }

cout << "for (unsigned x = 0; x <= cmd.length(); x++) {\n";

• Megyer Laszlo report on Bugtraq that the cfingerd Debian as
  distributed with Debian GNU/Linux 2.2 was not careful in its
  logging code. By combining this with an off-by-one error in
  the code that copied the username from an ident response
  cfingerd could exploited by a remote user. Since cfingerd
  does not drop its root privileges until after it has
  determined which user to finger an attacker can gain root
  privileges.

  --- Freshmeat, 18 April 2001.

Design Intelligently

• Which is better:

  cmd[0]  = "";
  cmd[0] += "r";
  cmd[0] += "e";
  cmd[0] += "d";
  cmd[1]  = "";
  

  or

  string strarray[] = { "red", . . . };
  

  Hint: The first approach generated a 6 meg file.

• Which is better:

  const string * command(const string & prefix) {
    string comm[] = { "red", . . . };
    // and so on
    }
  

  or

  static const unsigned numwords = 2;
  static const string words[numwords+1] = { "red", . . . };
  static string matches[numwords+1];
  
  const string *command(const string& s) {
    // and so on.
    }
  

  Hint: Don't do more work than you have to.

This page last modified on 27 February 2001.