A treemap (http://en.wikipedia.org/wiki/Treemapping) 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. Some free programs use treemaps to visualize the size of files on your computer; for example:

WinDirStat (http://portableapps.com/apps/utilities/windirstat_portable) for Windows

Disk Inventory X (http://www.derlien.com/) for MacOS

KDirStat (http://kdirstat.sourceforge.net/) for Linux

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.

And with that, let’s get started on your final CSC148 assignment!

Task 0: Getting started

1. Download and unzip the starter code (a2_starter_files.zip ()

(https://q.utoronto.ca/courses/292974/files/25399282/download?download_frd=1) ) into your directory for Assignment 2.

2. With  tm_trees.py open, take the time to read through the tasks below to get a sense of what code you’ll be writing throughout this assignment.

3. Familiarize yourself with the following coding guidelines:

You may NOT define any new public or private attributes.

You are always free to define private helpers (functions or methods).

Complete docstrings are not required for any helpers that you define or for methods that you

override or extend, but you are encouraged to take the time to write them.

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_size s 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:

1. Complete the initializer of  TMTree according to its docstring. This will get you familiar with the attributes in this class.

2. Implement the  is_displayed_tree_leaf method according to its docstring and the definition of the displayed-tree (see below).

3. 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.

Progress check!

After this step is done, you should be able to instantiate and print a  TMTree , as is done in the provided main block of  tm_trees.py .

In the next task, you will implement the code required for the treemap algorithm.

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. Below, we show a grid representing the rectangle  (0, 0, 8, 4) :

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.

(https://q.utoronto.ca/courses/292974/files/25397463/download?download_frd=1) , and ask clarifying questions as needed.

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 method in . Note that rather than returning the rectangles for only the leaves of the displayed-tree, the code will instead set the 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 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.                                                                                                                  Progress check!                                                                            Note that the basic treemap algorithm does not require pygame or the visualizer at all! You can check your work simply by instantiating a  TMTree object, calling  update_rectangles on it, then calling            get_rectangles to see the list of rectangles returned.

This is primarily how we’ll be testing your implementation of the treemap algorithm!

At this point, you can now run  treemap_visualiser.py and see your treemap. By default, it will display the example from the worksheet, which should look something like below (with random colours of      course). Note: the bar across the bottom is where the path string of the selected rectangle will appear once you complete the next task.

Next, you will implement the method necessary to enable the selection of rectangles in the visualizer.

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.

Progress check!

Try running the program and then click on a rectangle on the display. You should see the information for that displayed-tree leaf shown at the bottom of the screen, and a box appear around the selected rectangle. Click again to unselect that rectangle, and try selecting another one. Note that you will also see a thinner box appear around any rectangle that you hover over in the display.

For the worksheet example, it should look something like the below, if you have selected rectangle “d” and are not hovering over any rectangle:

Note: As you run the visualizer, you will see output in the python console in PyCharm. This output is to help you see what events are being executed. You may find this information useful when              debugging your code. Feel free to modify anything that is being printed in  treemap_visualiser.py if  you find it helpful to do so.

Task 4: Making the display interactive

In this task, you will implement:

TMTree.expand

TMTree.expand_all

TMTree.collapse

TMTree.collapse_all

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:

a. The user can close the window and quit the program by clicking the X icon (like any other window).

No additional code required.

b. 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.

c. 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

d. 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

e. 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

f. 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.

g. 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.)

h. 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!).

Progress check!

At this point, your visualizer should be fully functional!

One of the nice things about code with an interactive display is that it’s usually pretty straightforward to test basic correctness.

Try running the treemap visualizer, and see if you can resize, move rectangles, and manipulate the displayed-tree as outlined above.

Of course, you can also write pytests to check the correctness of the methods you have written too! Next, we’ll write code to allow us to visualize the files on your computer!

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.

1. Complete the  path_to_nested_tuple function according to its docstring.

2. 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.

3. 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 module documentation (https://docs.python.org/3/library/os.html) 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) <