Quiz 2 Sample solutions: 3 questions, 60 minutes

Question 1: array-based queues
For an array-based queue, emented using arrays, one index is used to track the current front position (for removes) and another to track the current back position (for inserts). After we remove we increment the front position, after we insert we increment the back position. However, when the queue is empty we should set front to -1 (so we realize there is no valid item in the queue) and we need to make front and back 'wrap around' to the start of the array when they run off the end. For the queue class shown below, implement the constructor and the insert method. 
// default size of queue array
const int DefaultSize = 100;

// a queue of ints
class queue {
   protected:
      int *q;      // array of queue elements
      int size;    // number of elements queue can hold
      int front;   // current position of front element
      int back;    // current position of back element
   public:
      // dynamically allocate the array 
      //    and initialize front, back, size
      Queue(int sz = DefaultSize);
     ~Queue();             // deallocate the array
      bool insert(int i);  // insert item i at back        
      bool remove(int &i); // remove front item into i
      bool isfull();       // returns true iff the queue is full
      bool isempty();      // returns true iff the queue is empty
};   
Sample solution
Queue::Queue(int sz)
{
   q = new int[sz];
   if (q == NULL) {
      size = 0;
   } else {
      size = sz;
   }  
   front = -1;
   back = -1;
}

bool Queue::insert(int i)
{
   // make sure it is ok to insert
   if ((q == NULL) || isfull()) {
      return false;
   } 

   // handle inserts into an empty queue
   else if (back == -1) {
      front = 0;
      back = 0;
   } 

   // handle inserts into a non-empty queue
   else {
      back++;
      if (back == size) {
         back = 0;
      }
      q[back] = i;
   }
   return true;
}

Question 2: file I/O and command line arguments
Write a complete program that expects to receive two command line arguments (aside from the name of the executable of course).

If the correct number of arguments are supplied, it takes the first as a filename and the second as a block of text to search for, opens the file, and counts the number of times the text appears in the file. For example, in the line below the text "foo" appears three times:
blah blah foo blahfoo blah blahfooblah 
Sample solution
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

// count the number of times the pattern appears in
//    the text contents
int countMatches(string pattern, string contents);

int main(int argc, char *argv[])
{
   // check for the right number of command line arguments
   if (argc != 3) {
      cout << "Expected use is\n";
      cout << argv[0] << " filename pattern" << endl;
      return 0;
   }

   // attempt to open the input file
   ifstream fpin;
   fpin.open(argv[1]);
   if (fpin.fail()) {
      cout << "Unable to open file " << argv[1] << endl;
      return 0;
   }

   // read the input file into a string
   string contents = "";
   while (!fpin.eof()) {
      char c;
      fpin.get(c);
      if (!fpin.eof()) {
         contents += c;
      }
   }

   // count and display the number of pattern matches in the contents
   int count = countMatches(argv[2], contents);
   cout << "Found pattern " << argv[2] << " " << count;
   cout << " times in file " << argv[1] << endl;
   return 0;
}

// count the number of times the pattern appears in
//    the text contents
int countMatches(string pattern, string contents)
{
   int count = 0;
   int pattlen = pattern.length();
   int textlen = contents.length();
   // for each possible starting position in the text,
   // check if the pattern matches starting from that spot
   for (int spos = 0; spos < (textlen - pattlen); spos++) {
       bool currMatch = true;
       for (int tpos = 0; tpos < pattlen; tpos++) {
           if (contents[spos+tpos] != pattern[tpos]) {
              currMatch = false;
           }
       }
       if (currMatch) {
          count++;
       }
   }
   return count;
}

Question 3: exceptions
In your own words, describe how exceptions (try, throw, and catch) work in C++, and provide a short code example.