CSCI 161 Spring 2026: lab 4, S26N01/2

CSCI 161 Lab 4: 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.

In this lab we start working with C++ classes, using them to build our own linked list class and then use that class in a small application.

Be sure to follow the course code standards. Marks will be deducted for failing to follow standards.

lab4 product requirements/specification/design

For lab4 we'll leave the rankings system behind and start on a new application, as well as begin creating our own C++ class to hold data in a linked list structure.

Product overview

The lab4x program allows the user to manipulate a stored list of bug reports, each having a name for the bug, a short description of it, and a name of the file suspected to contain the bug.

As the program runs, the user is able to insert new bug reports into either of two lists, remove reports from the lists, lookup reports in a list, make one list a duplicate of the other, print the contents of the lists, and print just the reports related to a specific file.

The buglist class (in buglist.h/cpp) will provide the implementation of a linked list of bug reports, while the lab4.h/cpp functions actually utilize the buglists.

As you can see in the sample run at the bottom of the page, the user is repeatedly presented with the following command options:

   H (this menu) 
   Q (end program) 
   P (print all bugs in current list) 
   F (print all current-list bugs relating to specific file) 
   I (insert new bug into current list) 
   L (lookup bug in current list) 
   R (remove bug from current list) 
   D (create second bugs list as duplicate of first) 
   S (switch between working on first/second lists)

Most of the user interaction for this program is already handled in the lab4.cpp file (e.g. getting and checking user commands and calling the appropriate buglist methods), so your task is getting the actual buglist class methods implemented correctly.

The general linked-list concepts and logic we've worked with previously all still apply, but now we're using a class instead of plain structs to carry out the implementation.

The big behavioural differences with past labs are how inserting, removing, and sorting are handled.

In this lab, bug reports are stored in sorted order (by the bug name), and as each new item is inserted we find it's correct spot to insert. This makes insertion a bit more complex, but means we never need to sort the list (the items are always sorted because of the way we inserted them).

In this lab we are also searching for and removing bugs by their name, rather than simply from the front of the list, so the remove method will also need particular care.

Implementation details

As with past labs, the core code is spread across a set of four C++ files (buglist.h, buglist.cpp, lab4.h, lab4.cpp) along with a pair of test files (test4.h, test4.cpp) and a makefile to compile the various .o's, lab4x, and test4x.

For this lab one of the goals is to implement the methods of a class, but following a fairly strict set of implementation rules. As such, you're provided with the full final versions of lab4.h, lab4.cpp, buglist.h, and you are not permitted to alter any of those three files.
The only files you're allowed to modify for this lab are the buglist.cpp, test.h, and test.cpp.

Furthermore, you must follow the method specifications in buglist.h as closely as possible: ensuring both the methods and the internal data structure follow the comments provided in the buglist.h.

The application that uses the buglist, i.e. the lab4.h/cpp code, is already complete: you should not need to alter it in any way. (If you want to do other forms of testing on your buglist.cpp code then use the test4.h/cpp files for that.)

When you compile/run lab4x, it provides the user with the ability to repeatedly select from the various commands, manipulating the contents of two buglists. I recommend completing at least basic versions of insert and prtAll first (don't worry about sorted insertion at first), so you can ensure your basic buglist structure is intact before trying to implement and debug other features.

A copy of the buglist class definition (from buglist.h) is provided below, along with sample implementations for several of the methods in buglist.cpp.

Note that for this lab the buglist.cpp file is incomplete to begin with, so buglist.o and lab4x cannot compile until you add at least skeletal methods for the remaining public and protected buglist methods.

(Copies of the lab4.h and lab4.cpp files can also be viewed here if desired: there is nothing particularly fancy going on in the code, just getting the user's command choice and applying it to the list in question.)

file buglist.h

#pragma once
#include <iostream>
#include <string>
using std::string;
using std::cin;
using std::cout;
using std::cerr;
using std::endl;

// biglist maintains a list of suspected programming bugs found across a variety of files.
// The list is maintained in (pseudo)alphabetically-increasing sorted order (< on strings),
//     with each insert finding the correct position for the new bug
//     and embedding it at that spot in the list.
class buglist {
   protected:
      struct bug {
         string name; // one word (no spaces) identifier for bug
         string desc; // short text description of nature of bug
         string file; // name of file believed to contain source of bug

         // going from front to back,
         //   next points to the one closer to back, nullptr if none
         //   prev points to the one closer to the front, nullptr if none
         bug* next;
         bug* prev;
      };

      // front and back point to alphabetically first/last bugs in the list
      bug* front;
      bug* back;

      int numBugs; // used to track current number of bugs in the list

      // protected methods are used by some of the public methods
      bug* create(string name, string desc, string file); // allocate, initialize, return bug
      bug* getByName(string name); // find and return pointer to named bug, null if not found
      void prtBug(bug* bptr); // if not null, display using prtBug(n,d,f)
                              // otherwise does nothing
      void insertBack(string name, string desc, string file); // create/insert at back

   public:
      buglist(); // generates an empty buglist
      buglist(const buglist &b); // initializes this list as a duplicate of the provided buglist
     ~buglist(); // delete each bug in the list

      // both prt methods must use prtBug to display the individual bugs' contents
      void prtAll(); // display all bugs in the list, front to back
      void prtFile(string file); // display all bugs (front to back) related to the named file
      void prtBug(string name, string desc, string file);
              // display in format name(file): desc (all one line, no newline/endl at the end)

      // insert, lookup, and remove each return true if successful, false otherwise
      // (insert doesn't allow two bugs with the same name for the same file)
      bool insert(string name, string desc, string file); // create/insert bug (sorted position)
      bool lookup(string name, string &desc, string &file); // find bug, fill in the parameters
      bool remove(string name); // find bug, remove from list, and deallocate
};

file buglist.cpp

#include "buglist.h"

// display the string fields for the passed bug in the format
// name(file): desc (all one line, no newline/endl at the end)
void buglist::prtBug(string name, string desc, string file)
{
   cout << name << "(" << file << "): " << desc;
}


// generates an empty buglist
buglist::buglist()
{
   front = nullptr;
   back = nullptr;
   numBugs = 0;
}


// display all bugs in the list, front to back, use prtBug
void buglist::prtAll()
{
   bug* b = front;
   while (b) {
      cout << "   ";
      prtBug(b);
      cout << endl;
      b = b->next;
   }
}

// all the remaining buglist methods still need to be added ...

Sample run

A sample test run of the program is shown below, highlighting some of the key behaviour. (As usual, with bold italics used to highlight the parts that are user input).

Available commands are: 
   H (this menu) 
   Q (end program) 
   P (print all bugs in current list) 
   F (print all current-list bugs relating to specific file) 
   I (insert new bug into current list) 
   L (lookup bug in current list) 
   R (remove bug from current list) 
   D (create second bugs list as duplicate of first) 
   S (switch between working on first/second lists) 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
 
 
Enter your next command (from HQPFILRDS) 
s 
Switching to list 2 
 
Enter your next command (from HQPFILRDS) 
p 
Error: no list currently allocated for list 2 
 
Enter your next command (from HQPFILRDS) 
s 
Switching to list 1 
 
Enter your next command (from HQPFILRDS) 
i 
Enter the name of the new bug (no spaces) 
middle 
Enter the bug description (one line) 
eventually will be in mddle of list 
Enter the name of the file containing the bug (no spaces) 
lab1 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   middle(lab1): eventually will be in mddle of list 
 
 
Enter your next command (from HQPFILRDS) 
i 
Enter the name of the new bug (no spaces) 
first 
Enter the bug description (one line) 
gets to front of list 
Enter the name of the file containing the bug (no spaces) 
lab2 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
 
 
Enter your next command (from HQPFILRDS) 
i 
Enter the name of the new bug (no spaces) 
very 
Enter the bug description (one line) 
ends up very last in list 
Enter the name of the file containing the bug (no spaces) 
lab1 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
i 
Enter the name of the new bug (no spaces) 
second 
Enter the bug description (one line) 
will be second to last 
Enter the name of the file containing the bug (no spaces) 
lab2 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
d 
Making list2 a duplicate of list1 
 
Enter your next command (from HQPFILRDS) 
i 
Enter the name of the new bug (no spaces) 
fine 
Enter the bug description (one line) 
new front of list 
Enter the name of the file containing the bug (no spaces) 
lab1 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   fine(lab1): new front of list 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
s 
Switching to list 2 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 2: 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
l 
Enter the name of the bug of interest (no spaces) 
second 
Found: second(lab2): will be second to last 
 
Enter your next command (from HQPFILRDS) 
r 
Enter the name of the bug of interest (no spaces) 
middle 
Removed bug middle 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 2: 
   first(lab2): gets to front of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
s 
Switching to list 1 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 1: 
   fine(lab1): new front of list 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
f 
Enter the name of the file of interest (no spaces) 
lab1 
List 1 bugs related to lab1: 
   fine(lab1): new front of list 
   middle(lab1): eventually will be in mddle of list 
   very(lab1): ends up very last in list 
 
Enter your next command (from HQPFILRDS) 
d 
Making list2 a duplicate of list1 
(deleting old list 2 before duplicating) 
 
Enter your next command (from HQPFILRDS) 
s 
Switching to list 2 
 
Enter your next command (from HQPFILRDS) 
p 
Contents of list 2: 
   fine(lab1): new front of list 
   first(lab2): gets to front of list 
   middle(lab1): eventually will be in mddle of list 
   second(lab2): will be second to last 
   very(lab1): ends up very last in list 
 
 
Enter your next command (from HQPFILRDS) 
q 
 
Bye!

Algorithms/approaches for the methods

If you're struggling with the implementation of any of the methods, here's what I would view as a design for each:

buglist(b) (the copy constructor)

say curr is a bug*
start it at b's front
while it isn't null
   call insertBack using its name/desc/file
        (which creates/adds a new node to the buglist we're in now, see below)
   move curr along to curr's next

~buglist()

say current is a bug*
while front isn't null
   set current to front
   move front along to front's next
   delete current

prtFile(f)

just like prtAll, except
   we only call prtBug and print the endl if the filenames match

create(n, d, f)

allocate a new bug
set its next/prev to null
set its other data fields to the parameters
return it

getByName(n)

start current at front
while current isn't null
   if current's name matches n then return current
   otherwise move current along to its next
return null if you get to the end (never found the name)

insertBack(n, d, f)

like previous insert at backs:
   use create to create a new node
   set the new node's prev to back
       and back's next to the new node
   update back to refer to the new node
   update numBugs

lookup(n,d,f)

call getByName
if it returns null then return false
otherwise set d and f from the ptr returned by getByName
   and return true

insert(n,d,f)

use a technique like getByName to search for any existing bug with the
    same name and file, return false if you find one
(since it's not supposed to allow multiple bugs where the name and file are both the same)

otherwise, call create to allocate a new node then insert as follows:

      if the list is currently empty then just make
         the new node the only thing in the list, i.e.
         front and back refer to the new node, size is 1, return true

      otherwise if the new node's name < front's name then
         insert the new node at the front, i.e.  the new node's next is front,
         front's prev is the new node, front is the new node

      otherwise if the new node's name >= back's name then
         insert the new node at the back, i.e.  the new node's prev is back,
         back's next is the new node, back is the new node

      otherwise have an 'after' pointer search from front towards back,
         continuing as long as n > after's name
         before = after's prev
         embed the new node between before and after
            (before's next is the new node, the new node's prev is back,
             similar logic the other way around for after)

increment the size and return true

remove(n,d,f)

left as a design exercise for the student, but I'd recommend using the insert logic
   as a template/starting point

Inheritance and your test4.h/cpp

The buglist class uses protected as the designator for the bug struct, the front/back/numBugs fields, and the various helper methods.

Now that we know about inheritance, and that buglist's 'hidden' content is just protected (not private), we could build extra debugging functionality into a new specialized buglist class in our test4.h/test4.cpp.

In the example below, we create a debuglist that inherits from buglist, and adds several extra methods for examining the content of the bug list:

showFront(): simply displays whatever front points to, giving our main a chance to check front is actually valid after we make a change to the list
showBack(): same idea, but for back
countNodes(): walks through the list and counts the nodes encountered, so we can compare that against numBugs
checkStructure(): runs a set of structural validity tests on the buglist:
- check that if one of front/back are null then the other one is too
- check that numBugs and countNodes match
- check that front->prev and back->next are both null
- for every pair of connected nodes, if A->next points to B then B->prev also points back to A (and vice versa)

The main routine then tries modifying the a list (e.g. doing inserts/removes), and calls showFront, showBack, and checkStructure after each modification.

#pragma once
#include "buglist.h"

class debuglist: public buglist {
   public:
      void showFront(); // shows the front node content
      void showBack(); // shows the back node content
      int countNodes(); // manually counts the nodes (instead of trusting numBugs)
      bool checkStructure(); // verifies the validity of the pointers/connections
};

Now our test4.cpp's main can use the debuglist to examine/test our buglist code a little deeper:

#include "test4.h"

int main()
{
   debuglist b;

   // do some checking after one insert
   cout << "\nTesting round 1" << endl;
   b.insert("bug1", "the first bug inserted", "somefile");
   b.showFront();
   b.showBack();
   if (!b.checkStructure()) cerr << "Error detected, structure not valid!" << endl;
   else cout << "Looks ok so far" << endl;

   // check again after another insert
   cout << "\nTesting round 2" << endl;
   b.insert("bug2", "the second bug inserted", "anotherfile");
   b.showFront();
   b.showBack();
   if (!b.checkStructure()) cerr << "Error detected, structure not valid!" << endl;
   else cout << "Looks ok so far" << endl;

   // check again after a third insert
   cout << "\nTesting round 3" << endl;
   b.insert("anotherbug", "the third bug inserted", "somefile");
   b.showFront();
   b.showBack();
   if (!b.checkStructure()) cerr << "Error detected, structure not valid!" << endl;
   else cout << "Looks ok so far" << endl;

   // print the list, just to see
   b.prtAll();
}

void debuglist::showFront()
{
   cout << "Front node  is: ";
   prtBug(front);
   cout << endl;
}

void debuglist::showBack()
{
   cout << "Back node  is: ";
   prtBug(back);
   cout << endl;
}

int debuglist::countNodes()
{
   int count = 0;
   bug* curr = front;
   while (curr != nullptr) {
      curr = curr->next;
      count++;
   }
   return count;
}

// checks links are logically consistent, size is correct, etc
bool debuglist::checkStructure()
{
   // check 1: either front and back are both null or neither of them are null
   cout << "Running check 1" << endl;
   if ((front == nullptr) && (back != front)) {
      cerr << "Error: front is null but back is not" << endl;
      return false;
   }

   // check 2: front->prev and back->next should both be null
   cout << "Running check 2" << endl;
   if (front != nullptr) {
      if (front->prev != nullptr) {
         cerr << "Error: front->prev is not null" << endl;
         return false;
      }
      if (back->next != nullptr) {
         cerr << "Error: back->next is not null" << endl;
         return false;
      }
   }

   // check 3: sizes match
   cout << "Running check 3" << endl;
   int count = countNodes();
   if (count != numBugs) {
      cerr << "Error: number of nodes counted (" << count << ") ";
      cerr << "does not match numBugs (" << numBugs << ")" << endl;
      return false;
   }

   // check 4: for each node, curr, if its neighbours aren't null then
   //      curr->next->prev should point back to curr
   //      curr->prev->next should point back to curr
   cout << "Running check 4" << endl;
   bug* curr = front;
   while (curr != nullptr) {
      bug* after = curr->next;
      bug* before = curr->prev;
      if ((after != nullptr) && (after->prev != curr)) {
         cerr << "Error: disconnect between two nodes" << endl;
         prtBug(curr);
         prtBug(after);
      }
      if ((before != nullptr) && (before->next != curr)) {
         cerr << "Error: disconnect between two nodes" << endl;
         prtBug(curr);
         prtBug(after);
      }
      curr = curr->next;
   }

   // everything looks ok
   cout << "Everything passed!" << endl;
   return true;
}

A sample run of our tester (./test4x) hopefully gives:

Testing round 1
Front node  is: bug1(somefile): the first bug inserted
Back node  is: bug1(somefile): the first bug inserted
Running check 1
Running check 2
Running check 3
Running check 4
Everything passed!
Looks ok so far

Testing round 2
Front node  is: bug1(somefile): the first bug inserted
Back node  is: bug2(anotherfile): the second bug inserted
Running check 1
Running check 2
Running check 3
Running check 4
Everything passed!
Looks ok so far

Testing round 3
Front node  is: anotherbug(somefile): the third bug inserted
Back node  is: bug2(anotherfile): the second bug inserted
Running check 1
Running check 2
Running check 3
Running check 4
Everything passed!
Looks ok so far
   anotherbug(somefile): the third bug inserted
   bug1(somefile): the first bug inserted
   bug2(anotherfile): the second bug inserted

You could then extrapolate on the testing to try them after removes as well.

(Checking things like the destructor externally is more problematic, as the object has already ceased to exist by the time the destructor finishes. For examining things like that, one is more-or-less restricted to either trying debugging statements within the destructor itself or viewing the code through a debugger as it actually executes.)