lab05 : Ordered Linked Lists

num ready? description assigned due
lab05 true Ordered Linked Lists Tue 05/07 11:59PM Tue 05/14 11:59PM

In this lab, you’ll have the opportunity to practice:

Note: It is important that you start this lab early so you can utilize our office hours to seek assistance / ask clarifying questions during the week before the deadline if needed!

You will write a program that will organize Book objects into a Book Collection. The Book Collection will be implemented as an Ordered Linked List with a head reference. The implementation in this lab will be different than an Unordered Linked List since you will need to organize the nodes by the Book’s author (in lexicographical / alphabetical order). In the event of a tie (several books are written by the same author), the published year will be used to determine the Book object’s place in the Ordered Linked List. If the author and year published are the same, then the Book’s title (lexicographical / alphabetical order) will be used to determine the Book object’s place in the Ordered Linked List.

This lab will require you to define classes for a Book, BookCollection, and a BookCollectionNode, as well as writing your own unit tests to verify the correctness of your implementation.

Instructions

You will need to create four files:

There will be no starter code for this assignment, but rather the class descriptions and required methods are defined in the specification below.

You should organize your lab work in its own directory. This way all files for a lab are located in a single folder. Also, this will be easy to import various files into your code using the import / from technique shown in lecture.

Book.py class

The Book.py file will contain the definition of a Book. We will define the Book attributes as follows:

You should write a constructor that allows the user to construct a book object by passing in values for all of the fields. Your constructor should set the title and author attribues to empty strings (""), and the year attribute to None by default.

In addition to your constructor, your class definition should also support “getter” methods that can receive the state of the Book object:

You will implement the method

that returns a str with all of the Book attributes. The string should contain all attributes in the following EXACT format (Note: There is no \n character at the end of this string):

b = Book("Ready Player One", "Cline, Ernest", 2011)
print(b.get_book_details())

Output

Title: Ready Player One, Author: Cline, Ernest, Year: 2011

We reviewed operator overloading in class and the textbook does discuss overloading Python operators. You can also refer to this reference on overloading various operators as well:

https://www.geeksforgeeks.org/operator-overloading-in-python/

BookCollectionNode.py

The BookCollectionNode.py file will define the BookCollectionNode class. This will be similar to the Linked List Node implementation done in lecture. You will need to write the following methods:

BookCollection.py

The BookCollection.py file will contain the definition of a collection of Book objects stored in an Ordered Linked List. The BookCollection will manage an Ordered Linked List containing BookCollectionNodes.The BookCollection class will be responsible for maintaining the overall structure of the Ordered Linked List. Your BookCollection class will need to support the following methods:

b0 = Book("Cujo", "King, Stephen", 1981)
b1 = Book("The Shining", "King, Stephen", 1977)
b2 = Book("Ready Player One", "Cline, Ernest", 2011)
b3 = Book("Rage", "King, Stephen", 1977)

bc = BookCollection()
bc.insert_book(b0)
bc.insert_book(b1)
bc.insert_book(b2)
bc.insert_book(b3)
print(bc.get_books_by_author("KING, Stephen"))

Output:

Title: Rage, Author: King, Stephen, Year: 1977
Title: The Shining, Author: King, Stephen, Year: 1977
Title: Cujo, Author: King, Stephen, Year: 1981

b0 = Book("Cujo", "King, Stephen", 1981)
b1 = Book("The Shining", "King, Stephen", 1977)
b2 = Book("Ready Player One", "Cline, Ernest", 2011)
b3 = Book("Rage", "King, Stephen", 1977)

bc = BookCollection()
bc.insert_book(b0)
bc.insert_book(b1)
bc.insert_book(b2)
bc.insert_book(b3)
print(bc.get_all_books_in_collection())

Output:

Title: Ready Player One, Author: Cline, Ernest, Year: 2011
Title: Rage, Author: King, Stephen, Year: 1977
Title: The Shining, Author: King, Stephen, Year: 1977
Title: Cujo, Author: King, Stephen, Year: 1981

testFile.py pytest

This file should import your Book, BookCollection, and BookCollectionNode classes so you can write unit tests using pytest to test your functionality is correct. Think of various scenarios and edge cases when testing your code. Write your tests first in order to check the correctness of the Book, BookCollection and BookCollectionNode methods. Gradescope requires testfile.py to be submitted before running any autograded tests. You should write at least one test for each method in each of these classes and ensure your test cases are covering all branches of the code effectively (but more tests can help you debug various cases!).

Submission

Once you’re done with writing your class definitions and tests, submit your Book.py and BookCollection.py BookCollectionNode.py, and testFile.py files to the Lab05 assignment on Gradescope. Remember to remove any print statements in your code since this may confuse the autograder. There will be various unit tests Gradescope will run to ensure your code is working correctly based on the specifications given in this lab.

If the tests don’t pass, you may get some error message that may or may not be obvious. Don’t worry - if the tests didn’t pass, take a minute to think about what may have caused the error, and try writing more comprehensive tests for various cases. If your tests didn’t pass and you’re still not sure why you’re getting the error, feel free to ask your TAs or Learning Assistants.

Troubleshooting