Homework 3: Trees and Objects

The goals of this assignment are:

• To get practice implementing methods on classes
• To get practice designing and developing programs on trees

Due date

• HW3 is due on Tuesday, October 12th at 9pm EST.

Setup and Handin

Setup

In order to setup hw3, open up VSCode and create five files outlined below. For testing, make sure you install pytest. The functions you need to complete will be outlined later. The five files you need to create are the following:

• tree.py
• tree_test.py
• messagecenter.py
• messagecenter_test.py
• htmltree.py

Make sure you add the the stencil code for tree.py, which can be copied from here. In addition, add the stencil code for messagecenter.py, which can be copied from here. Also, since you will be working with HTMLTrees in tree.py, add this code to htmltree.py. This contains the structure of the HTMLTree, which is imported into tree.py.

Handin

You may submit as many times as you want. Only your latest submission will be graded. This means that if you submit after the deadline, you will be using a late day – so do NOT submit after the deadline unless you plan on using late days.

The README template can be found here. Please follow the design and clarity guide--part of your grade will be for code style and clarity. After completing the homework, you will submit:

• README.txt
• tree.py
• tree_test.py
• messagecenter.py
• messagecenter_test.py

Because all we need are the files, you do not need to submit the whole project folder. As long as the file you create has the same name as what needs to be submitted, you’re good to go!

If you are using late days, make sure to make a note of that in your README. Remember, you may only use a maximum of 3 late days per assignment. If the assignment is late (and you do NOT have anymore late days) no credit will be given.

Please don't put your name anywhere in any of the handin files--we grade assigments anonymously!

You can follow this step-by-step guide for submitting assignments through Gradescope here.

Helpful Things

Documentation

• Python testing, design and clarity guide

Staff Assistance

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

The Assignment

Part 1: Traversing the HTML Tree

The first part of this homework is to get some practice working with trees. Suppose you have data stored inside html trees, just like we've seen in lecture. You would like to know how "deep" the tree is in order to know how long it might take for you to process the data, and then write functions to carry out specific tasks on that data.

We'd like you to write the following functions on HTMLTrees in the tree.py file.

tree_height

tree_height computes the maximum distance from the root to any leaf. This function should take an HTMLTree and return an integer. The height of a tree with no children is 1; the height of a tree with children is the maximum height of any of its children plus 1.

has_strong_grandchildren

has_strong_grandchildren should return True if any of the grandchildren of the node at the root of the tree (i.e., children of its children) have the "strong" tag. Note that it doesn't matter whether the root of the tree or any of its children are strong, we only care about the grandchildren. has_strong_grandchildren should take an HTMLTree and return a boolean.

Part 2: Getting the message

Now that we have successfully found the data, it's time to move on to another task. We would like to model a messaging app using our newfound knowledge of objects!

You should write code for this part in messagecenter.py. The Message class is defined as follows:

class Message:
    def __init__(self, from_user: str, to_user: str, contents: str):
        self.from_user = from_user
        self.to_user = to
        self.contents = contents
        self.read = False

    def mark_read(self):
        self.read = True

For this part, you'll write some code to implement a messaging application--think WhatsApp. Your application will track messages (as a list of Message objects) and groups, which are sets of users. Users can send messages either to other users or to a group; sending a message to a group results in it being sent to every user in the group. Your messaging applicaiton will be implemented as a class called MessageCenter.

Your MessageCenter class should implement the methods below. Remember that all of your methods need to take self as their first argument! We list the other arguments below.

__init__

The init method doesn't need to take any arguments besides self. It should add messages and groups fields to the object; these should be an empty list responsible for keeping track of the messages and an empty hashtable in charge of the different groups present in the message center, respectively.

add_user_to_group

add_user_to_group should take (in addition to self) the name of a group (a string) and the name of a user (also a string). It should add a group with the given name if it doesn't exist, and then add the named user to the group if it's not already in the group.

add_direct_message

add_direct_message should take (in addition to self) two users and a message body. It should create a message with the given users and body and store it in the messages list.

add_group_message

add_group_message should take (in addition to self) a user, a group, and a message body. If the given group exists, it should add messages with the given body from the given user to every member of the group.

next_message

next_message should take (in addition to self) a user and return the first unread message in the messages list addressed to that user. Before returning the message, it should mark the message as read using the mark_read method. If there are no messages in the list, next_message should return None.

message_history

message_history should take (in addition to self) two users and return all of the messages (read or unread) between those two users--messages from the first user to the second user and vice versa.