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

Note: Handout updated Oct. 26 11:00 AM

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.

Setup

Save the following stencil files to a hw4 directory:

docs.py 





  

    
      
        
        
      
      linkedlist.py
    
    
      
        
        
      
    
    
      
        
        
      
      
        
        
      
    
  

  





In addition, create the following files for tests:



  

    
      
        
        
      
      test_linkedlist.py
    
    
      
        
        
      
    
    
      
        
        
      
      
        
        
      
    
  

  





  

    
      
        
        
      
      test_docs.py
    
    
      
        
        
      
    
    
      
        
        
      
      
        
        
      
    
  

  





Staff Assistance


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



The Assignment



Tim is working on his speech for his next talk. After all, the grind never stops. 
He doesn’t trust Google Docs and needs your help to create his very own, simplified 
document editing and sharing system to prevent his speech from falling into the wrong hands.



Linked lists



We have provided the Linked List implementation from class, along with some
tests. We’d like you to 1) add a method to remove nodes, then 2) 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.



The image below helps illustrate what the remove method should achieve. 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.



LinkedListExample



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:




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.



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 in 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 and do not forget to write documentation–you know how to do this!



Include tests for exceptional cases and edge cases – come to hours if you’re struggling to come up with edge cases to test!



README



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





Handin


Handin the following files to gradescope when submitting the assignment:




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