Homework #5¶

Due Date: Monday, May 9th at 9pm.

The following homework exercises are intended to help you practice some of the programming concepts introduced in weeks 5 and 6 including heap allocation, structs, and linked lists.

Getting Started¶

You will be using a new repository for each homework in this course. Please follow the instructions in the Ed post “Homework #5 now available” to set up your Homework #5 repo.

Compiling and testing your code¶

We will continue to use the testing infrastructure that you are now accustomed to. For a refresher, please read through the “Compiling and testing your code” section of Homework #1. To run the Homework #5 tests, you will need to replace homework1 with homework5 as needed.

You also might want to run your code with LLDB and Valgrind to aid in debugging. Please see the “Debugging with LLDB and Valgrind” section of Homework #3 for instructions on how to run your code with these tools.

Representing books in a library¶

In this assignment, you will work with structs that implement a circular, doubly linked list. In particular, each element of the list will represent a book. We will store the list of books in a structure called a library. We will use the following types to represent a book and a library:

typedef struct book book_t;
typedef struct library library_t;

struct book {
   char *title;
   char *author;
   int year;
   int ISBN;
   book_t *prev;
   book_t *next;
};

struct library {
   int num_books;
   book_t *books;
};

A book_t stores information about one book in a list. It stores the book’s title, author, the year it was published, and its ISBN number (ISBN is short for International Standard Book Number, a unique identifier given to every published book). It also stores a pointers to the previous and next books in the list. A library_t stores the number of books in the list and a pointer to the first book in the list. Note that the library can be empty.

Here is a depiction of a library with three books:

The book field of a library points to the first book in the list. Within the list, each book stores a pointer the next book in the list as well as the previous book in the list. Keep in mind that in a regular (non-circular) linked list, the end of the list is marked with NULL in the next field. In a circular list, the end of the list is marked by a next field that points back to the beginning of the list.

Here is a depiction of an empty library:

In the empty library (a library with no books), the books field of the library is NULL.

And here is a depiction of a library with one book:

Notice that both the next field and the prev field of the book point back to itself.

Exercises¶

Throughout this assignment, you may assume that pointer parameters point to valid data and are not NULL. You can also assume that the value of the length of an array passed as parameter to a function is indeed the length of that array. You can use the stdlib.h functions malloc or calloc as needed throughout this assignment. You should not use other functions or functions from other libraries unless it is explicitly stated that you can do so in a task.

We have provided interfaces for book_t and library_t that contains constructors and destructors for each type, as well the function book_cmp, which can be used to order the books in the library. These interfaces are described in homework5.h and implemented in homework5.c. Make sure you read the documentation carefully, as you will be expected to utilize some of these functions in your code.

As a running example, consider the library with the books (written below as title, author, year, ISBN number):

“The Prince and the Pauper”, “Twain”, 1881, 100001
“The Merry Adventures of Robin Hood”, “Pyle”, 1883, 100220
“Treasure Island”, “Stevenson”, 1883, 808800
“Dr. Jekyll and Mr. Hyde”, “Stevenson”, 1886, 200400

Note that the books are stored in order by year, then by author within a year, then by title, if necessary.

Complete the function add_book, which takes a pointer to a library_t and information about a book and adds that book to the library. Again, books in the library are arranged by year, then author, then title. You must use the book_t functions make_book and book_cmp in your implementation.

For example, adding the book:

“Adventures of Huckleberry Finn”, “Twain”, 1884, 550099

to the library above should insert a new book_t between “Treasure Island” and “Dr. Jekyll and Mr. Hyde”. It should also update the num_books field of the library.
Complete the function empty_library, which takes a pointer to a library_t and returns true if the library is empty, and false otherwise.
Complete the function verify_num_books, which takes a pointer to a library_t and verifies that the number in its num_books field matches the number of books stored in the list of book_t.

Using the example above, the num_books field in the library should be the value 4, since there are four books stored in the library.
Complete the function remove_book, which takes a pointer to a library_t and an ISBN number and attempts to remove the book with that ISBN number from the library. This function should return true if the book was successfully removed from the library, and false otherwise (that is, if the book was not found in the library).

For example, calling remove_book with the library above and ISBN number 100220 should remove the “The Merry Adventures of Robin Hood” from the list of books in the library and return true. When a book is successfully removed from the library, the space for that book should be deallocated using the book_t destructor, and the num_books field of the library should be updated.

Calling remove_book with the ISBN number 770909 should return false, since there is no book with that ISBN number in the library.
Complete the function books_by_year, which takes a pointer to a library_t and creates an array of integers that contains the number of books from each year in the library. This function also returns the length of the array as an out parameter.

Calling books_by_year with the original four book library above should return the array {1, 0, 2, 0, 0, 1}. The first element in the array represents the number of books from the first year in the library (in this case, 1881). Then the array contains the number of books from each year up to the last year in the library (1886). In other words, the library contains 1 book from 1881, 0 books from 1882, 2 books from 1883, 0 books from 1884, 0 books from 1885, and 1 book from 1886. After this call, the out parameter num_years should point to the value 6 (the length of the output array).

If the library is empty, this function should return NULL and num_years should point to 0.
This exercise makes use of the enum:

enum flip {FORWARDS, BACKWARDS};

Complete the function flip_through_books, which takes a pointer to a library_t, an array of enum flip and the length of the array, and “flips” through the books in the library. Starting at the beginning of the list of books, navigate forward in the list on the enum flip FORWARDS and move backwards in the list on the enum flip BACKWARDS. This function should return a pointer to the book the flip ends on and should return NULL if the library is empty (there are no books to flip through).

Here are some examples with the original four book library above and a given array of enum flip:
- {} (the empty array) should return a pointer to “The Price and the Pauper” since flipping starts at the beginning of the list an no flips occurred
- {FORWARDS} should return a pointer to “The Merry Adventures of Robin Hood”
- {BACKWARDS} should return a pointer to “Dr. Jekyll and Mr. Hyde”
- {FORWARDS, BACKWARDS} should return a pointer to “The Prince and the Pauper”
- {BACKWARDS, FORWARDS} should also return a pointer to “The Prince and the Pauper”
- {BACKWARDS, BACKWARDS, BACKWARDS, FORWARDS} should return a pointer to “Treasure Island”
- {FORWARDS, FORWARDS, BACKWARDS, FORWARDS, BACKWARDS} should return a pointer to “The Merry Adventures of Robin Hood”
Restriction In this task, you should not count the number of FORWARDS and BACKWARDS in the array of enum flip, then attempt to move through the list accordingly. Instead, navigate through the list of books as you iterate through the array.

Please note that our automated tests first test your add_book function, then use your implementation of add_book to test your other functions (empty_library, verify_num_books, etc.).

Grading¶

For this assignment, the weights will be:

Completeness: 60%
Code Quality: 40%

The code quality score will be determined by code clarity, style, and whether your implementation stays within the allowed constructs for each exercise.

Preparing your submission¶

There are three things you should do before you submit your work.

First, make sure you have added the required information to the header comment in homework5.c:

your name,
the names of anyone beyond the course staff you discussed the assignment with, and
links to any resources that you used other than course materials and the course textbook.

Please remove the explanation for what is required. Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

Second, remove directives, such as:

// YOUR CODE HERE

from your code. Make sure to recompile and rerun the tests after you make these changes. It is easy to introduce a syntax error at this stage.

Third, add, commit, and push your work to GitHub.

And finally, get your directory into a clean state. Run make clean to remove any executables that are laying around.

Submission¶

To submit your work, you will need to add, commit, and push your code to GitHub. Before you upload your code to GitHub, run git status . to make sure you did not forget to add/commit any of the required files. Then upload your submission to Gradescope under the “Homework #5” assignment. Make sure to choose the right assignment on Gradescope!

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.