CSCI 161 Lab 2: sections S26N01/2

See the main lab page for submission deadlines and late penalties.

It is assumed you are keeping up to date with the lectures and labs.
Some additional git information is available through the git quick notes, git project/lab submission, and lecture resources pages.

This lab builds on the ideas from lab1, but now lets the user run multiple head-to-head matchups, adds dynamic array allocation (including an array-resizing approach), and uses quicksort to sort the rankings before writing them back to a file.

The mechanics of git and make are essentially unchanged since lab1 (though of course now the git repository is named lab2 and the file names are lab2.h, lab2.cpp, test2.h, test2.cpp, ranking.h, and ranking.cpp.
(Refer back to lab1 for the git/make syntax if needed.)

The marking for this lab will be stricter in terms of the code standards, so be sure you have reviewed them carefully. Marks will be deducted for failing to follow standards.

lab2 product requirements/specification/design

As mentioned at the top of this page, the desired functionality for lab2 is much the same as lab1, but with three key differences:

  1. Rather than having a fixed size array (and limit on how many items can be read from the file), dynamic allocation should be used to allocate the array (with 10 used as the starting size in the main routine) and the routine that reads the file should resize the array: doubling its size every time the array fills.

  2. After loading the rankings file, your program must ask the user how many matches they wish to run and run that many matches (with rank updates applied for each match). The user can specify any positive integer value, and your program should error check and repeat the question until a valid response is provided. (Remember to check for non-numeric input and for values that are less than 1.)

  3. After all the matches have been run, your program must sort the items from lowest rank to highest before writing them back to the file, and must use quicksort as the sorting algorithm to do the sorting.

Design ideas

As with lab1, you are encouraged to come up with your own design, but are free to use the sample design below. 

// sample main from lab2.cpp
int main(int argc, char* argv[])
{
   // quit if the user didn't pass valid arguments
   if (!checkUsage(argc, argv)) {
      cerr << "Program terminated early, unable to proceed\n";
      return 0;
   }

   string filename = argv[1]; // filename is more intuitive later
   welcome(); // program intro for user

   // load the rankings from the named file
   ItemRank *rankings = new ItemRank[DefaultSize];
   int rankSize = DefaultSize;
   int numItems = readRankings(filename, rankings, rankSize);

   // run head-to-head matchups
   int matches = getNumMatches();
   for (int m = 1; m <= matches; m++) {
      if (!runMatchup(rankings, numItems)) {
         cerr << "Error: match " << m << " unsuccessful, rankings not updated\n";
      }
   }

   // sort the rankings (lowest to highest)
   qsortRanks(rankings, 0, numItems-1);

   // write the updated rankings back to the file
   if (!writeRankings(filename, rankings, numItems)) {
      cerr << "Unable to updated rankings file " << filename << endl;
   }

   return 0;
}


//sample ranking.h
#pragma once
#include <iostream>
#include <string>
using std::cout;
using std::cin;
using std::cerr;
using std::endl;
using std::string;

const bool DEBUGMODE = false; // used to turn debugging output on/off

// representation of a single item
struct ItemRank {
   int rank;            // positive integer rank
   string description;  // text description of item
};

// load item rankings from the named file, store in rankings,
//    resizing the array as needed (whenever it fills up)
// arrSize gives the current size of the array
int readRankings(string filename, ItemRank* &rankings, int &arrSize);

// return true iff descript is a valid item description
// (i.e. contains at least one non-whitespace character)
bool validDescription(string descript);

// run a head-to-head matchup
//     - pick distinct pair of items
//     - present user with choice, get valid response
//     - update rankings based on response
// return true iff the matchup is successful
bool runMatchup(ItemRank rankings[], int items);

// write rankings to a file
// return true iff successful
bool writeRankings(string filename, ItemRank rankings[], int numItems);

// calculate and return new rank for X based on current ranks for X and Y
//    and score from X's perspective: 1=X win, 0.5=draw, 0=Y win
// return unchanged RankX in the event of an invalid parameter
int calcNewRank(int RankX, int RankY, float score);

// present the user with a choice between items X and Y
// return 1 if they choose X
//        0 if they choose Y
//        0.5 if it's a draw
// (repeat until they make a valid choice)
float getChoice(ItemRank X, ItemRank Y);

// partition the rankings items based on the provided pivot value,
//    working within array positions low through high (inclusive),
// return the position the pivot wound up in
int partition(ItemRank rankings[], int low, int high);

// sort the rankings from lowest rank to highest
//      in array positions low to high (inclusive)
void qsortRanks(ItemRank rankings[], int low, int high);

// create a new array, twice as big as the current one,
//   copy the contents across,
//   switch the rankings and size parameters to the new version,
// and delete the old (now obsolete) array
// return true iff successful
void resizeRanks(ItemRank* &rankings, int &size);

// exchange the values of two items
void swap(ItemRank &item1, ItemRank &item2);

Sample run

A sample run of the program is shown below (with user input highlighted in bold italis for extra clarity), followed by the updated file contents. 

./lab2x tests/posted 

Welcome to the lab2 item ranking program 
This program reads a collection of item rankings from a file 
   (whose name is provided as a command line argument, e.g. ./lab2x foods) 
Lets you pick how many head-to-head item comparisons to run,
then for each head-to-head comparison it presents you with a choice between two items, 
and uses your preference to update their rankings.
It then sorts the updated rankings and writes them back to the file.
 
Please enter the number of head-to-head matches you would like run (e.g. 10) 
3 
 
Given the choice between the following two items: 
   First:       brussel sprouts 
   Second:      salmon sashimi 
please enter F for first, S for second, or D for draw (tied) 
f 
 
Given the choice between the following two items: 
   First:       hawaiian pizza 
   Second:      salmon sashimi 
please enter F for first, S for second, or D for draw (tied) 
d 
 
Given the choice between the following two items: 
   First:       capsicum 
   Second:      those dutch olie bols things 
please enter F for first, S for second, or D for draw (tied) 
s 
 
Updated rankings written back to file tests/posted 


28      brussel sprouts 
900      capsicum 
1750      those dutch olie bols things 
1831      hawaiian pizza 
1883      salmon sashimi