CSC148-Winter-2023-A2

Assignment 2 of CSC148 (Intro to Computer Science) University of Toronto 2023 A2 - Treemaps

Learning goals After completing this assignment, you will be able to:

model different kinds of real-world hierarchical data using trees
implement recursive operations on trees (both non-mutating and mutating)
implement an algorithm to generate a geometric tree visualisation called a treemap
use the os library to write a program that interacts with your computer’s file system
use inheritance to design classes according to a common interface

Introduction

As we’ve discussed in class, trees are a fundamental data structure used to model hierarchical data. Often, a tree represents a hierarchical categorization of a base set of data, where the leaves represent the data values themselves, and internal nodes represent groupings of this data. Files on a computer can be viewed this way: regular files (e.g., PDF documents, video files, Python source code) are grouped into directories, which are then grouped into larger directories, etc.

Sometimes the data in a tree has some useful notion of size. For example, in a tree representing the departments of a company, the size of a node could be the dollar amount of all sales for that department, or the number of employees in that department. Or in a tree representing a computer’s file system, the size of a node could be the size of the file.

A treemap is a visualisation technique to show a tree’s structure according to the weights (or sizes) of its data values. It uses rectangles to show subtrees, scaled to reflect the proportional sizes of each piece of data.

Treemaps are used in many contexts. Among the more popular uses are news headlines, various kinds of financial information, and computer disk usage.

For this assignment, you will write an interactive treemap visualisation tool that you can use to visualize hierarchical data.

It will have a general API (implemented with inheritance, naturally!) and you will define specific subclasses that will allow you to visualize different kinds of data.

Task 1: TMTree basics In this task, you will implement:

TMTree.init
TMTree.is_displayed_tree_leaf
TMTree.get_path_string In order to use a treemap to visualize data, we first need to define our tree structure and be able to initialize it. For this program, you will develop a TMTree class to define the basic functionality required by the provided treemap visualizer. To visualize any specific hierarchical dataset, we simply need to define a subclass of TMTree, which we will do later.

The TMTree class is similar to the basic Tree class that you have already worked with, but with some differences. A few of the most conceptually important ones are discussed here.

First, the class has a data_size instance attribute that is used by the treemap algorithm to determine the size of the rectangle that represents this tree. data_size is defined recursively as follows:

If the tree is a single leaf, its data_size is some measure of the size of the data being modelled. For example, it could be the size of a file.
If the tree has one or more subtrees, its data_size is equal to the sum of the data_sizes of its subtrees, plus some additional size of its own.

Second, the class not only stores its subtrees, but it also stores its parent as an attribute. This allows us to traverse both up and down the tree, which you will see is necessary when we want to mutate the tree.

Third, we’ll also track some information inside our tree related to how to display it. More on this shortly.

Fourth, we don’t bother with a representation for an empty TMTree, as we’ll always be visualizing non-empty trees in this assignment.

To get started, you should do the following:

Complete the initializer of TMTree according to its docstring. This will get you familiar with the attributes in this class.
Implement the is_displayed_tree_leaf method according to its docstring and the definition of the displayed-tree (see below).
Implement the get_path_string method according to its docstring.

In the subsequent parts of this assignment, your program will allow the user to interact with the visualizer to change the way the data is displayed to them. At any one time, parts of the tree will be displayed and others not, depending on what nodes are expanded.

We’ll use the terminology displayed-tree to refer to the part of the data tree that is displayed in the visualizer. It is defined as follows:

The root of the entire tree is in the displayed-tree. For each “expanded” tree in the displayed-tree, its children are in the displayed-tree.
The trees whose rectangles are displayed in the visualization will be the leaves of the displayed-tree. A tree is a leaf of the displayed-tree if it is not expanded, but its parent is expanded. Note that the root node is a leaf of the displayed-tree if it is not expanded.

We will require that (1) if a tree is expanded, then its parent is expanded, and (2) if a tree is not expanded, then its children are not expanded. Note that this requirement is naturally encoded as a representation invariant in the TMTree class.

Note: the displayed-tree is not a separate tree! It is just the part of the data tree that is displayed.

Task 2: The Treemap algorithm

In this task, you will implement:

TMTree.update_rectangles
TMTree.get_rectangles

The next component of our program is the treemap algorithm itself. It operates on the data tree and a 2-D window to fill with the visualization, and generates a list of rectangles to display, based on the tree structure and data_size attribute for each node.

For all rectangles in this program, we’ll use the pygame representation of a rectangle, which is a tuple of four integers (x, y, width, height), where (x, y) represents the upper-left corner of the rectangle. Note that in pygame, the origin is in the upper-left corner and the y-axis points down. So, the lower-right corner of a rectangle has coordinates (x + width, y + height). Each unit on both axes is a pixel on the screen.

We are now ready to see the treemap algorithm.

Note: We’ll use “size” to refer to the data_size attribute in the algorithm below.

Input: An instance of TMTree, which is part of the displayed-tree, and a pygame rectangle (the display area to fill).

Output: A list of pygame rectangles and each rectangle’s colour, where each rectangle corresponds to a leaf in the displayed-tree for this data tree, and has area proportional to the leaf’s data_size.

Treemap Algorithm:

Note I: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer to a data tree.

Note II: (Very Important) The overall algorithm, as described, actually corresponds to the combination of first calling TMTree.update_rectangles to set the rect attribute of all nodes in the tree and then later calling TMTree.get_rectangles to actually obtain the rectangles and colours corresponding to only the displayed-tree’s leaves.

If the tree is a leaf in the displayed-tree, return a list containing just a single rectangle that covers the whole display area, as well as the colour of that leaf.
Otherwise, if the display area’s width is greater than its height: divide the display area into vertical rectangles (by this, we mean the x-coordinates vary but the y-coordinates are fixed), one smaller rectangle per subtree of the displayed-tree, in proportion to the sizes of the subtrees (don’t use this tree’s data_size attribute, as it may actually be larger than the sizes of the subtrees because of how we defined it!)

Example: suppose the input rectangle is (0, 0, 200, 100), and the displayed-tree for the input tree has three subtrees, with sizes 10, 25, and 15.

The first subtree has 20% of the total size, so its smaller rectangle has width 40 (20% of 200): (0, 0, 40, 100). The second subtree should have width 100 (50% of 200), and starts immediately after the first one: (40, 0, 100, 100). The third subtree has width 60, and takes up the remaining space: (140, 0, 60, 100). Note that the three rectangles’ edges overlap, which is expected.

If the height is greater than or equal to the width, then make horizontal rectangles (by this, we mean the y-coordinates vary, but the x-coordinates are fixed) instead of vertical ones, and do the analogous operations as in step 2.
Recurse on each of the subtrees in the displayed-tree, passing in the corresponding smaller rectangle from step 2 or 3.

Note about rounding: because you’re calculating proportions here, the exact values will often be floats instead of integers. For all but the last rectangle, always truncate the value (round down to the nearest integer). In other words, if you calculate that a rectangle should be (0, 0, 10.9, 100), “round” (or truncate) the width down to (0, 0, 10, 100). Then a rectangle below it would start at (0, 100), and a rectangle beside it would start at (10, 0).

However, the final (rightmost or bottommost) edge of the last smaller rectangle must always be equal to the outer edge of the input rectangle. This means that the last subtree might end up a bit bigger than its true proportion of the total size, but that’s okay for this assignment.

Important followup to Note II above: You will implement this algorithm in the update_rectangles method in TMTree. Note that rather than returning the rectangles for only the leaves of the displayed-tree, the code will instead set the rect attribute of each node in the entire tree to correspond to what its rectangle would be if it were a leaf in the displayed-tree. Later, we can retrieve the rectangles for only the leaf nodes of the displayed-tree by using the get_rectangles method.

Note: Sometimes a TMTree will be sufficiently small that its rectangle has very little area (it has a width or height very close to zero). That is to be expected, and you don’t need to do anything special to deal with such cases. Just be aware that sometimes you won’t be able to actually see all the displayed rectangles when running the visualizer, especially if the window is small.

Tips: For the recursive step, a good stepping stone is to think about when the tree has height 2, and each leaf has the same data_size value. In this case, the original rectangle should be partitioned into equal-sized rectangles.

Warning: make sure to follow the exact rounding procedure in the algorithm description above. If you deviate from this, you might get slightly incorrect rectangle bounds.

Important: The docstring of the get_rectangles method refers to the displayed-tree. For now, the whole tree is the displayed-tree, as all trees start expanded. Make sure that you come back later and further test this method on trees where the displayed-tree is a subset of the full data tree to ensure that your code is fully correct.

Task 3: Selecting a tree In this task, you will implement:

TMTree.get_tree_at_position

The first step to making our treemap interactive is to allow the user to select a node in the tree. To do this, complete the body of the get_tree_at_position method. This method takes a position on the display and returns the displayed-tree leaf corresponding to that position in the treemap.

IMPORTANT: Ties should be broken by choosing the rectangle on the left for a vertical boundary, or the rectangle above for a horizontal boundary. That is, you should return the first leaf of the displayed-tree that contains the position, when traversing the tree in the natural order.

In the visualizer, the user can click on a rectangle to select it. The text display updates to show two things:

the selected leaf’s path string returned by the get_path_string method.
the selected leaf’s data_size

Clicking on the same rectangle again unselects it. Clicking on a different rectangle selects that one instead.

Reminder: Each rectangle corresponds to a leaf of the displayed-tree, so we can only select leaves of the displayed-tree.

Task 4: Making the display interactive

In this task, you will implement:

TMTree.expand
TMTree.expand_all
TMTree.collapse
TMTree.collapse_all
TMTree.move
TMTree.change_size Note: Unless explicitly written as “displayed-tree”, all occurrences of the word “tree” below refer to a data tree.

Now that we can select nodes, we can move on to making the treemap more interactive.

In addition to displaying the treemap, the pygame graphical display responds to a few different events (by event, we mean the user presses a key, hovers, or clicks on the window). The first such event was actually clicking on a rectangle to select it, which we implemented in the previous task. We will now implement the rest of the actions associated with events, by implementing methods in the TMTree class which the visualizer calls:

The user can close the window and quit the program by clicking the X icon (like any other window). No additional code required.
The user can resize the window by clicking and dragging a corner or side of the window (like any other resizable window). No additional code required.

The next four events change which rectangles are included in the displayed-tree.

If the user selects a rectangle, and then presses e, the tree corresponding to that rectangle is expanded in the displayed-tree. If the tree is a leaf in the data tree, nothing happens, since we can’t expand a leaf. When a tree is expanded, the visualization will make the first subtree of the newly expanded tree the new selected tree. implement TMTree.expand
If the user selects a rectangle, and then presses c, the parent of that tree is unexpanded (or “collapsed”) in the displayed-tree. (Note that since rectangles correspond to leaves in the displayed-tree, it is the parent that needs to be unexpanded.) If the parent is None because this is the root of the whole tree, nothing happens. When a tree is collapsed, the visualization will make its parent tree the new selected tree, as it is now a leaf of the displayed-tree. implement TMTree.collapse
If the user selects a rectangle, and then presses a, the tree corresponding to that rectangle, as well as all of its subtrees, are expanded in the displayed-tree. If the tree is a leaf, nothing happens. When a tree is expanded in this way, the visualization will make the “last” subtree of the newly expanded trees the new selected tree. Note: The docstring for the relevant method clarifies what we mean by “last”. implement TMTree.expand_all
If the user selects any rectangle, and then presses x, the entire displayed-tree is collapsed down to just a single tree node. If the displayed-tree is already a single node, nothing happens. When a tree is collapsed in this way, the visualization will make this single tree node the new selected tree, as it is now the only leaf of the displayed-tree. implement TMTree.collapse_all

The following two events allow the user to actually mutate the data tree, and see the changes reflected in the display.

If the user presses the Up Arrow or Down Arrow key when a rectangle is selected, the selected node’s data_size increases or decreases by 1% of its current value, respectively. Note: This affects the data_size of its ancestors as well, given our definition of data_size! implement TMTree.change_size

Details:

A node’s data_size cannot decrease below 1. There is no upper limit on the value of data_size. Just keep in mind that if a node is too large, then other nodes will appear relatively small in the visualization!
If a node has children, its data_size cannot decrease below the sum of its child data sizes.
The 1% amount is always “rounded up” before applying the change. For example, if a leaf’s data_size value is 140, then 1% of this is 1.4, which is “rounded up” to 2. So its value could increase up to 152 142, or decrease down to 148 138. (Note: the docstring for the relevant method provides similar clarification.)
If the user selects a rectangle, then hovers the cursor over another rectangle and presses m, the selected node should be moved to be the last subtree of the node being hovered over. Remember: we can only select and hover over leaves of the displayed-tree. implement TMTree.move

Very Important: Whenever you modify a tree’s data_size, the data_size attributes of all its ancestors need to be updated too! You must make use of the parent_tree attribute to do this: it’s a widely-used technique for traversing up a tree (this should feel a lot like traversing a linked list!).

Task 5: File System Data In this task, you will implement:

path_to_nested_tuple
dir_tree_from_nested_tuple

You will also:

override any methods necessary for your subclasses of TMTree to behave as specified below.
decide on an appropriate inheritance hierarchy for the FileTree and DirectoryTree classes.

Consider a directory on your computer (e.g., the assignments directory you have in your csc148 directory). It contains a mixture of other directories (“subdirectories”) and some files; these subdirectories themselves contain other directories, and even more files! This is a natural hierarchical structure, and can be represented by a tree.

The _name attribute will always store the name of the directory or file (e.g. preps or prep8.py), not its path; e.g., /Users/courses/csc148/preps/prep8/prep8.py.

The data_size attribute of a file is simply how much space (in bytes) the file takes up on the computer. Note: to prevent empty files from being represented by a rectangle with zero area, we will always add a +1 to file sizes. The data_size of a directory corresponds to the size of all files contained in the directory, including its subdirectories. As with files, we’ll also add a +1 to directory sizes for this assignment.

In our code, we will represent this filesystem data using the FileTree and DirectoryTree classes.

Complete the path_to_nested_tuple function according to its docstring.
Complete the dir_tree_from_nested_tuple function. This function is the public interface for how we will create DirectoryTree objects to test your code for correctness.
Override or extend methods from TMTree, as appropriate, in the FileTree and DirectoryTree classes. You will need to decide if you can just use the inherited methods as they are or not (see additional requirements below).

To complete step 1, you will need to read the Python os module documentationLinks to an external site. to learn how to get data about your computer’s files in a Python program. You may also find the provided print_dirs.py to be a useful example to base your implementation on.

We recommend using the following functions:

os.path.isdir
os.path.join
os.path.getsize
os.path.basename
os.listdir (see note below)

Note: Since the order that os.listdir returns file names is dependent on your operating system, we have provided a helper, ordered_listdir which you MUST use in your implementation. You MUST add the subtrees in the order they are produced from ordered_listdir.

You may NOT use the os.path.walk function — it does a lot of the recursive work for you, which defeats the purpose of this part!

Warning: Make sure to either use os.path.join (recommended) or make use of string concatenation and the os.sep string to build larger paths from smaller ones, because different operating systems use different separators for file paths.

Requirements for step 3:

FileTree objects can be resized in exactly the same way as TMTree objects, while DirectoryTree objects can NOT be resized. Attempting to change the size of a directory should raise an OperationNotSupportedError.
We can only move files and directories into a directory. Attempting to move a file or directory into a file should raise an OperationNotSupportedError, as demonstrated in the doctests for the DirectoryTree class. Also note that, since every event is designed for use with the visualizer, you can only perform moves between leaves of the displayed-tree.
Ensure your code is consistent with any other behaviour demonstrated in the provided doctests for the DirectoryTree class.
If you decide you would like an additional class in your hierarchy, you are free to define a new class.

Task 6: Chess! In this task, you will implement:

moves_to_nested_dict
ChessTree.init

You will also:

override or extend any methods necessary for ChessTree to behave as specified below.

Our last dataset consists of games extracted from a database of chess games played by WGMs. While you don’t have to know the exact rules of chess for this part, there are a few important things to note:

a game consists of a sequence of moves
“white” goes first and “black” goes second, with the two players continuing to take alternating turns until the game ends.
Each move can be represented by a code indicating which piece was moved and where it moved to.
the games can potentially end at any time, with some games taking less than 10 moves and others taking 100 or more.

Similar to the filesystem data initialization process, we will again have you do this in two steps:

Implement the moves_to_nested_dict function according to its docstring.
Implement the initializer for ChessTree according to its docstring.

A few important notes about the structure:

The root node should be the string '-'
The children of the root node should be all moves that occur as the first move of at least one game.
The children of all deeper moves should be the moves that follow the move represented by the parent move in at least one game.

We also need to update the functionality of our ChessTree class to reflect what events should be ignored for this new kind of data. In particular, given the interpretation of the nodes, we don’t want to support either changing the sizes of nodes or moving nodes. As you did with the file system related subclasses, appropriately override the relevant methods in a way consistent with the provided code.

This project was completed on Pycharm. This project was given a 78.52% grading (class avg: 77.19%)