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!