Assignment 3: Linked List Leaderboard

Due date: March 25 (Monday!), 2024 11:59pm

Objectives

• To build problem solving skills.
• To build C++ programming skills.
• To learn about singly linked lists, including building and traversing them.
• To develop linked list algorithms for node insertion and removal.
• To apply the insertion sort algorithm to linked lists.
• To gain experience with pointers.
• To gain experience with dynamic memory allocation.
• To gain experience testing and debugging more difficult algorithms.

Note: Linked lists are often more challenging than they first appear! Start early and take advantage of lab time. To focus on the linked list aspect of this problem, you may use the std::string class.

The Problem

You are working on a pretend web app that will display a leaderboard for a programming competition. The leaderboard will display the competitors (university teams) in order of their rank, along with their scores. While the real ICPC Scoring uses a more complex scoring system, we will assume that the score for each team has already been calculated.

You have been asked to implement the leaderboard using a singly linked list. The list will be sorted by score, with the highest score at the head of the list. The list will be updated frequently, so you will need to implement functions to add and remove nodes from the list.

The Program

Your program should process one to two files: the current leaderboard, and an optional file containing updates to the leaderboard.

For example, when the program is run with just the provided current leaderboard file, it should display the following:

$ ./a3 data/current_leaderboard.csv 
Current Leaderboard: 
Rank    Score    Team Name
1       382      Mount Royal University
2       243      University of Calgary
3       234      University of Alberta
4       123      University of Lethbridge
5       111      MacEwan University
6       101      University of Saskatchewan

Note that the field widths and spacing for the output are as follows:

March 20 addendum: I messed up the tests and instructions on this one; the score is clearly left aligned. I apologize for the confusion and have updated the test code to accept both the previous and this updated formatting, so you can git pull to get the new version (there should be no merge conflict if you have not edited the test code). In addition, output formatting is a very minor part of this assignment, and failing this particular test due to white space is not a big deal.

There’s also been some confusion as to why leaderboard and team both have write functions - this is a division of responsibility thing. You may want to print out a team even if it’s not part of a leaderboard, and in your next and final assignment, you will be implementing an overloaded << operator for the Team struct such that leaderboard can just call out << team.

When the program is run with both the provided current leaderboard and update file, it should display the following:

$ ./a3 data/current_leaderboard.csv data/updated_teams.csv 
Current Leaderboard: 
Rank    Score    Team Name
1       408      Mount Royal University
2       307      University of Saskatchewan
3       243      University of Calgary
4       234      University of Alberta
5       123      University of Lethbridge

If no arguments are provided, the program should display an error message and exit. Bash commands typically use [square brackets] to indicate optional arguments, e.g.:

$ ./a3
Usage: ./a3 current_leaderboard [updates]

Input Files

The input files are formatted as CSV files, with the current leaderboard and updates having the same format. For example, the current_leaderboard.csv file looks like this:

Team name, Score, Eligible
MacEwan University, 111, true
Mount Royal University, 382, true
University of Alberta, 234, true
University of Calgary, 243, true
University of Lethbridge, 123, true
University of Saskatchewan, 101, true

Don’t forget to deal with the header before reading each Team!

The output should be formatted as shown in The Program section. You do not need to write to an output file this time, just print to the console (a real program would probably re-write a new CSV with the updated list, but I figured there was enough going on in this assignment anyway).

The Starter Code

As usual, clone the starter code to begin. The repo is located at:

/library/students/comp1633/a3.git

Note: I am not providing you the exact git command to clone the repo! There has been some confusion about what a file path is and how to use it, so I want you to look at previous assignment instructions and figure out which parts need to be changed rather than just providing something you can copy and paste.

After cloning the repo, configure your “submit” repo by running:

$ git-asg-config

and selecting the a3 option from the menu.

Inside this directory you will find the following:

$ tree
.
├── data
│   ├── current_leaderboard.csv
│   └── updated_teams.csv
├── leaderboard.h
├── main.cpp
├── makefile
├── team.h
└── testing
    ├── makefile
    └── test_a3.cpp

Note that there are no files named leaderboard.cpp or team.cpp. You will need to create these files yourself.

main.cpp

The main program logic should do the following:

• Check for the correct number of command line arguments (2 or 3), print an error message and return if the number is incorrect
• Initialize an empty leaderboard (linked list) by declaring the head Node *.
• Read the current leaderboard from the first file and add each team to the list using the update function (in leaderboard.cpp) to ensure the list is sorted
• If a second file is provided, read the updates from that file and process them as follows:
  • If a team is eligible to continue, call the update to add a new team or update the score of an existing team. update should ensure the list remains sorted.
  • If a team is not eligible to continue, call the remove function to remove the team from the list.
• Print the leaderboard to the console
• Clean up any memory that was allocated, and close the input file(s)

For both files, make sure that the file can be opened; if not, display an error message and return.

You may find it useful to define a helper function to read the input file, create the list, and return the head pointer. This requires maintaining two lists (one for the current leaderboard and one for the updates), but reduces repetition in reading the input files.

team.h and team.cpp

The Team structure is provided in team.h, while you will need to implement read/write functions in team.cpp. The Team struct is defined as follows:

struct Team {
    std::string name;
    int score;
    bool eligible;
};

The read function should read a single row from the CSV into a Team object, while the write function should display the team info formatted for human readability as shown in The Program . Do not print the rank from this function - your Team object should have no idea what position it occupies in the list.

Notice also that read returns an istream& instead of void. This is so that you can chain multiple reads together, and use the read function in a while loop, e.g.:

Team t;
while (read(in, t)) {...

Tests for the read and write functions are provided in testing/test_a3.cpp.

Side note on std::string

std::string objects behave much like Python lists - they can be reassigned, concatenated, and you don’t need to worry about the buffer size. To read a line from an input stream to a string, you can use the std::getline function. For example:

string line;
getline(cin, line);

This is different from the cin.getline function used with C-strings!

leaderboard.h and leaderboard.cpp

This is where most of the magic happens: your linked list. leaderboard.h defines a Node struct as well as a set of public functions:

• update: modifies the list to either add a new team or update an existing team’s score. The list should remain sorted in descending order by score.
• remove: removes a team (by name) from the list, if it exists. Frees the memory for the removed node.
• clear: empties the list and frees all the memory
• write: writes the list to an output stream, formatted as per the examples in The Program section. You’ll need to write out the header, then iterate through the list and keep track of the rank (position in the list), printing out the rank and calling the write function for each Team.

For each of these functions, don’t forget to consider edge cases, such as:

• Is the list empty (head == NULL)?
• Does the head need to be updated (either removing the head, or inserting before the head)?
• Is the list a singleton (head is the only node)?
• Are you adding or removing at the end of the list?

Feel free to implement private helper functions as desired to keep the logic straight.

Testing

Tests are provided for the functionality defined in leaderboard.h and team.h in the testing directory. You can run these tests using the provided makefile:

$ cd testing
$ make

For your convenience, the makefile also runs the test for you.

Note: The provided tests are not exhaustive, and do not test main or check for memory leaks! Make sure to do your own testing in addition to running the provided tests.

valgrind

To make sure you don’t have memory leaks, check your program using valgrind periodically. You can run valgrind on your program using the following command:

$ valgrind ./a3 data/current_leaderboard.csv data/updated_teams.csv

Don’t forget to also try running valgrind with just the current leaderboard file, and with no arguments at all!

I will be running valgrind on your program as part of grading (memory leaks will impact your grade by up to 10%).

Testing and development tips

Test early, test often! Do not try to write the entire program at once - start with each piece and test as you go. Consider writing function stubs for each function such that the program compiles, then focus on implementing one at a time.

It’s really easy to get bogged down in the weeds of linked lists. Think carefully about each edge case, and write helper functions as necessary to simplify the logic. Also be careful with ChatGPT or Copilot etc - linked lists are a very common programming assignment, but LLMs don’t always get it right and it can be harder to try to debug someone else’ code than writing it yourself from scratch.

Marking scheme

This assignment is worth 8% of your final grade and roughly divided as:

• 40% for program functionality (does it behave as specified?)
• 40% for program implementation (is it written as specified?)
• 10% for style and documentation (is it readable and appropriately commented/cited?)
• 10% for incremental development (did you commit your changes regularly with descriptive commit messages?)

Refer to the style guide for a reference on style and documentation. If you use external resources such as Stack Overflow, ChatGPT, or a friend in the class, make sure to cite them in your comments. Failure to cite external resources will be considered plagiarism. An example of a citation is as follows:

// ChatGPT helped me with this function
void foo(int bar) {
    // ...
}

If your solution uses vectors or other data structures or techniques not covered in class, you will receive a reduced grade, possibly as low as 0. If you have previous experience, try to challenge yourself to solve this problem using only the basics. However, std::string is allowed this time and is part of the Team structure definition!

In addition, there will be an automatic 20% deduction if your code fails to compile or run. If the problem is extreme and I cannot fix it with a small change, a grade of 0 may be assigned. Make sure your code compiles and runs on INS with the given makefile before submitting.

Finally, make sure to check your code periodically for memory leaks with valgrind. Memory leaks will incur a penalty of up to 10%, even if the code appears to function perfectly.