CSCI 161 Lab 3: 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 lab2, but now stores the data in a linked list, rather than an array, and uses mergesort on the linked list (instead of quicksort on an array).

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.

lab3 product requirements/specification/design

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

  1. Rather than using arrays to store the data we will now use a linked list, adding a new element to the back of the existing list each time you read a new valid pair from the file.

  2. The sorting algorithm you are using must be mergesort this time (not quicksort), and it must operate on your linked list (not an array).

    Hand-built linked list development is a core part of this lab. As such, you must use the linked-list of structs approach for this lab, i.e. not C++ library lists or queues or similar data structures to store your collection of rankings.

    Similarly, the implementation, testing, and debugging of a recursive mergesort algorithm (with separate merge function) is another core part, and you are required to implement each of them yourself - i.e. do not use the various C++ algorithm/sort libraries and functions.

Design ideas

As with labs 1 and 2, you are encouraged to come up with your own design, but are free to use the sample design below.

The design shows a similar set of functions as those in lab2, but using two new structs, one for individual items and one for a list of rankings as a whole.

Underneath the sample design code you'll find discussion of the more challenging aspects of switching to work with a linked list and switching to work with mergesort. 

// sample main from lab3.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
   ItemList rankings;
   initList(rankings);
   if (!readRankings(filename, rankings)) {
      cerr << "Error: could not load file, ending program" << endl;
      deallocate(rankings);
      return 0;
   }

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

   // sort the rankings (lowest to highest)
   msortRanks(rankings);

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

   deallocate(rankings);
   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 within a linked list
struct ItemRank {
   int rank;            // positive integer rank
   string description;  // text description of item
   ItemRank* next; // pointer to the item after/behind this item (closer to the back)
   ItemRank* prev; // pointer to the item ahead/before this item (closer to the front)
};

// representation of a list of items
struct ItemList {
   ItemRank* front; // the first item in line
   ItemRank* back; // the last item in line
   int size; // number of items in the list
};

// delete all the allocated items in a list then re-initialize it
void deallocate(ItemList &rankings);

// load item rankings from the named file, store in rankings,
// return true if successful, false otherwise
bool readRankings(string filename, ItemList &rankings);

// initialize a list as empty
void initList(ItemList &rankings);

// insert the item at the back of the rankings list
// return true if successful, false otherwise
bool insertBack(ItemList &rankings, ItemRank* item);

// remove the front item from the rankings list
// return the pointer to it (null if list was empty)
ItemRank* removeFront(ItemList &rankings);

// return a pointer to the nth item in the list, null if N not valid
ItemRank* getNthItem(ItemList rankings, int N);

// 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(ItemList &rankings);

// write rankings to a file
// return true iff successful
bool writeRankings(string filename, ItemList rankings);

// 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);

// remove rankings from the two sorted source lists, merging them into the destination list
bool merge(ItemList &source1, ItemList &source2, ItemList &destination);

// sort the rankings from lowest rank to highest
void msortRanks(ItemList &rankings);

How our read routine changes

In our lab2 version of reading from a file we could simply put the next item into the next array position. Now we need to create a new item (like the allocate function from the lecture on Feb. 25) and then insert it into the list of items (like the insertAtBack function from the Feb25 lecture).

How picking two random items for a match changes

In our lab2 version for an array of N elements we could simply pick two different random numbers in the range 0..N-1 and grab those two items for our matchup.

In lab3, however, the list doesn't inherently have a size associated with it and we have no way to jump directly to the i'th item in the list.

One possible solution is to add a size field to the list struct: initialize it to 0 and increment it every time you do an insert (so the size always matches the number of elements currently in the list).

Then we can still pick two random numbers in the range 0..N-1 (or 1..N), but we need to scan the list from the front to find the i'th item. This is essentially just a for loop that counts how many items to skip across, then return a pointer to the item you land on. If you look at the example design above, you'll see a getNthItem function that does exactly that.

Mergesort on linked lists

If you're looking at the slides/sample code online, you'll see the mergesort and merge in that example ( mergesort.cpp ) is based on sorting an array, whereas here in lab3 you'll be using mergesort on a linked list (like the msortRanks and merge functions in the design above).

This does involve some extra juggling to translate an array-based solution into a linked-list style. The core steps are still the same for the recursive mergesort function itself (msortRanks above):

  1. split the original linked list into two roughly-equal halves
  2. call mergesort (msortRanks) on each half
  3. merge the two sorted half-lists back into one sorted whole

The big changes are in steps 1 and 3.

  - In step one, to split the list in half, we can't simply point at the middle and break the list in half since we only have pointers to the two ends (front and back). What we can do, is create two new empty lists and go through the 'big' list one item at a time, removing them from the big list and alternating between putting them in little list one and little list two.

  - In step three, to merge the two lists together into one big one, we just keep looking at the current front item in each of the two little lists, picking the smaller of them and moving it from the little list (e.g. removeFront) and putting it into the big list (e.g. insertBack).