Here is my code:
counthits.cpp(main driver program)
#include <cstdlib> #include <iostream> #include <string> #include <fstream> #include "histogram.h" using namespace std; // Read log entries from the provided input stream, extracting the request // portion from each. If the request is a GET, extract the locator (throwing // away any part after a '?') and update a count of how many times that locator // has appeared. // // Write the resulting wlocators and counts (in alphabetic order by locator) // in CSV format to the output stream. // // - Assume that the input contains a maximum of MaxPages distinct locators. // If more distinct locators than this are actually // encountered, write nothing to the output stream but print an error // message on the standard error stream. void histogram(const int MaxPages, istream& input, ostream& output); int main (int argc, char** argv) { if (argc != 4) { cerr << "Usage: " << argv[0] << " MaxPages inFileName outFileName" << endl; return -1; } // Get MaxPages from the command line int MaxPages = atoi(argv[1]); // Take input and output file names from the command line ifstream in (argv[2]); ofstream out (argv[3]); histogram (MaxPages, in, out); in.close(); out.close(); return 0; }
histogram.cpp (The part that needs fixing is at the bottom of this function)
#include "histogram.h" //#include "arrayUtils.h" #include <string> using namespace std; struct CountedLocations { string Location; int numHits; }; // Extract the quoted request from a line containing a log entry string extractTheRequest(string logEntry) { string::size_type requestStart = logEntry.find('"'); string::size_type requestEnd = logEntry.rfind('"'); if (requestStart != requestEnd) { return logEntry.substr(requestStart+1, requestEnd-requestStart-1); } else return ""; } template <typename T> void addElement (T* array, int& size, int index, T value) { // Make room for the insertion int toBeMoved = size - 1; while (toBeMoved >= index) { array[toBeMoved+1] = array[toBeMoved]; --toBeMoved; } // Insert the new value array[index] = value; ++size; } int binarySearch(const CountedLocations list[], int listLength, string searchItem) { int first = 0; int last = listLength - 1; int mid; string midFind; bool found = false; while (first <= last && !found) { mid = (first + last) / 2; midFind = list[mid].Location; if (midFind == searchItem) found = true; else if (searchItem < midFind) last = mid - 1; else first = mid + 1; } if (found) return mid; else return -1; } // Check to see if this is a GET request bool isAGet (string request) { return request.size() > 3 && request.substr(0,4) == "GET "; } // Extract the locator part of a GET request string extractLocator (string request) { // strip off the GET string::size_type locatorStart = 3; // Skip any blanks while (request[locatorStart] == ' ') ++ locatorStart; // The locator ends at the first blank or ? after that. string::size_type locatorEnd = locatorStart; while (request[locatorEnd] != ' ' && request[locatorEnd] != '?') ++ locatorEnd; string locator = request.substr(locatorStart, locatorEnd-locatorStart); return locator; } //template <typename T> int addInOrder (CountedLocations array[], int& size, string value) { // Make room for the insertion int toBeMoved = size - 1; while (toBeMoved >= 0 && value < array[toBeMoved].Location) { array[toBeMoved+1] = array[toBeMoved]; --toBeMoved; } // Insert the new value array[toBeMoved+1].Location = value; ++size; return toBeMoved+1; } // Read log entries from the provided input stream, extracting the request // portion from each. If the request is a GET, extract the locator (throwing // away any part after a '?') and update a count of how many times that locator // has appeared. // // Write the resulting wlocators and counts (in alphabetic order by locator) // in CSV format to the output stream. // // - Assume that the input contains a maximum of MaxPages distinct locators. // If more distinct locators than this are actually // encountered, write nothing to the output stream but print an error // message on the standard error stream. void histogram(const int MaxPages, istream& input, ostream& output) { // Step 1 - set up the data // Data should be stored in two parallel arrays, locators and counts. // locators[i] will be the i_th locator string and counts[i] will be the // count of how many times that particular locator has been requested. CountedLocations C [MaxPages]; int nLocators = 0; // Step 2 - read and count the requested locators string logEntry; getline (input, logEntry); while (input) { string request = extractTheRequest(logEntry); if (isAGet(request)) { string locator = extractLocator(request); int position = binarySearch (C, nLocators, locator); if (position >= 0) { // We found this locator already in the array. // Increment its count C[position].numHits+=1; } else { if (nLocators < MaxPages) { // This is a new locator. Add it. position = addInOrder (C, nLocators, locator); // And add a count of one at the corresponding position // in the counts array //int nCounts = nLocators - 1; C[position].numHits = 1; //addElement (CountedLocations, nCounts, position, 1); } else { // Not enough room in the arrays ++nLocators; } } } getline (input, logEntry); } // Step 3 - write the output report string Location; int Hits; if (nLocators <= MaxPages) { for (int i = 0; i < nLocators; ++i) { Location = C[i].Location; Hits = C[i].numHits; } output << "\"" << Location << "\"," << Hits << endl; } else { cerr << "Input file contains more than " << MaxPages << " locators." << endl; } // Step 4 - cleanup }
This is my input:
70.161.31.80 - - [30/Mar/2008:23:31:21 -0500] "GET /cocoon/~cs330web/forum/show/_axle/private.gif HTTP/1.1" 302 -
70.161.31.80 - - [30/Mar/2008:23:31:21 -0500] "GET /cocoon/~cs330web/forum/show/_axle/feed-icon16x16.png HTTP/1.1" 302 -
70.161.31.80 - - [30/Mar/2008:23:31:21 -0500] "GET /axle/Forum/_axle/private.gif HTTP/1.1" 304 -
70.161.31.80 - - [30/Mar/2008:23:31:21 -0500] "GET /axle/Forum/fckeditor/editor/fckeditor.html?InstanceName=text&Toolbar=ForumToolbar HTTP/1.1" 304 -
70.161.31.80 - - [30/Mar/2008:23:31:21 -0500] "GET /axle/Forum/fckeditor/fckconfig.js HTTP/1.1" 304 -
127.0.0.1 - - [30/Mar/2008:23:31:28 -0500] "GET / HTTP/1.0" 200 2499
127.0.0.1 - - [30/Mar/2008:23:31:29 -0500] "GET / HTTP/1.0" 200 2499