Homework 4: C'mon Let's Link-ed List

The goal of this assignment is to get some more practice writing recursive methods, as well as to get some practice with object-oriented programming concepts like inheritance.

Due Date

Due: 3rd November 2021, 9:00pm EDT

Setup and Handin

Setup

In order to setup homework4, download or copy and paste the stencils: linkedlist.py, docs.py, test_linkedlist.py, test_docs.py. Move the files into your hw4 directory in VSCode, and create the testing files as well (the specific file names you have to create are outlined below).

Handin

Handin the following files to gradescope when submitting the assignment:

  • linkedlist.py
  • test_linkedlist.py
  • docs.py
  • test_docs.py
  • README.txt

Remember to include a README.txt when submitting your assignment!

Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our hours schedule here.

The Assignment

Linked Lists

We have provided the Linked List implementation from class, along with some tests. We'd like you to add a method to remove nodes, then change the class to have a more efficient length implementation.

Adding remove

You should add a method called remove, which removes a node by its index, as seen in the figure below.

We have the linked-list [a,b,c,d] and we want to remove the item at the 2nd index. The result would be linked list [a,b,d] pictured below with the pre-removal list.

You should implement remove using a recursive helper method called remove_from. Think about what the base case and recursive case should look like!

If the specified index isn't in the list (i.e., if it is less than 0 or greater than or equal to the list's length), you should raise an exception (see the implementation of nth for an example of what this might look like).

You should write good tests for remove. Make sure to test error cases (see the tests for nth).

Making length more efficient

Right now, the length() method runs in linear time in the length of the list, since it has to look at every node. We can do this more efficiently by adding a field called count to the LinkedList class. count represents the number of nodes in the list. It should be initialized to 0 in __init__, and be updated in both append and remove. You can then modify length to return count instead of looking at the nodes in the list.

Modify the linked list implementation (__init__, append, and your remove method) to track the count field.

You don't need to write or modify any tests for this part of the assignment. Once you've fixed all of the methods, our test suite (as well as the tests you wrote for remove) should pass.

Cloud documents

We'd like you to implement a (very) simplified version of the logic for a cloud-based document editing and sharing system (like Google Docs). You'll implement two classes that handle document creation and permissions.

Take a look at the Document class in docs.py. This class represents individual documents, which have:

  • a name
  • contents (i.e., text)
  • a list of user IDs who can access the document

You'll implement two classes: User and AdminUser. A User has a collection of documents, some of which may be shared with other users. An AdminUser is a user who can access any document. Your AdminUser class should inherit from your User class.

We have provided some commented-out tests in test_docs.py. Once you have implemented your User and AdminUser classes, you can uncomment these tests. Note that you should write your own tests for all of your methods in addition to the included tests.

User methods

__init__

The init method should take in a user id (an integer). It should initialize two fields: a user_id field that records the user's ID and a documents field that holds an (initially empty) list of the documents the user has created.

create_document

The create_document method should take in the name and contents of a document. It should create a new document (i.e., a new instance of the Document class) and add it to the user's list of documents. The constructor for the Document class takes a user ID; you should pass in the user's ID for that argument.

can_access

The can_access method takes in a Document and returns a boolean. It should check whether the user's ID is in the set of users who can access the document (which you can get with doc.user_ids_with_access()).

get_document

The get_document method takes in the index of a document and returns that document (i.e., looks up that index in the user's documents list). If there is no such document in the list, your method should raise a NoDocumentError.

AdminUser methods

The AdminUser class should be a subclass of the User class. You will need to implement one method on this class. Note that AdminUser should not implement __init__.

can_access

Admin users should be able to access any document, so this method should always return True. It should have the same signature as the can_access method on the User class.

Testing

Write good tests for all of your methods--you know how to do this!

Include tests for exceptional cases--especially for your docs.py implementation.

README

In your README.txt, please include answers to the following questions:

  • Did you discuss this assignment with any other students? Please list their cs logins.
  • How many late days are you using on this assignment?