Discussion 8: File System Trees

Solutions

Exercise 1: Warmup: Base and Recursive Cases
(a)
How many objects are allocated on the heap to model the file system pictured above? In addition to your numerical answer, separately list the counts for each type of object that is allocated.

We’ll be aware of (i.e., be able to access) a total of 45 objects. This includes

  • 6 Folder objects
  • 9 File objects
  • 24 String objects, which include the 15 names of the Folder and File objects, and the 9 contents of the File objects.
  • 6 ArrayList objects referenced by the children fields of the Folders.

Additionally, while we can’t access these objects, we know that the ArrayLists (Java’s built-in analog of our DynamicArrayList class) are backed by FileSystemNode[]s, which would contribute an additional 6 objects to the count.

(b)
Where will the base case logic be for these method definitions? How would you implement such a base case? Explain your answers.
A lot of the base case logic will be in the File class, since Files sit at the leaves of a file system tree. Since files don’t have children, we’ll need to directly compute the answers to these queries using only the state of the file, itself.

A second kind of base case will be for empty Folders, which are also leaf nodes. The Folder methods will work by iterating over their children to compute the required result. When there are no children to iterate over, we’ll need to specify some “default” result that to serve as this base case.
(c)
Where will the recursive case logic be for these method definitions? How would you implement such a recursive case and make its recursive calls?
Since Folders can have children, a likely recursive case is calling the given function on each of the children, thereby shrinking the problem to smaller file system (sub)trees. We should implement this within the Folder class, observing that the children field allows us to iterate over subdirectories and/or child files. We can use an enhanced for loop, making a recursive call on each element of children.
Exercise 2: Implementing Recursive Methods
(a)
Implement the fileCount() method within the File and Folder classes. If we called web.fileCount(), where web is a Folder representing the node labeled "web" in the diagram from earlier, the method would return 9.

File.java

(b)
Next, implement the size() method. If we called web.size(), the method would return the sum of the amount of space each folder and file takes up.

Its base case is already written for you in the File class. Note how it automatically adjusts based on the size of the file's contents. Complete the definition of this method by writing the Folder.size() method.

File.java

(c)
Now, implement getFile(). If we call web.getFile("lectures/lec01/main.tex"), the method would return the File represented by the "main.tex" node in the diagram. If we called web.getFile("grades") or web.getFile("grades/mae226.md"), we would get null (since the first path leads to a Folder and the second file does not exist).

Think carefully about how to parse its input in each class, and what to do with that input in the recursive case. This is a more complicated recursive method than the previous two, though the code itself is still not very long.

File.java

Folder.java

Exercise 3: (Challenge) Implementing getPathFromName()
If you finish early, an additional method you can complete is getPathFromName(). Unlike getFile(), this method's input doesn't need to be specially parsed. However, it has the most complex recursive case of any of these methods. Carefully consider how you can utilize the return value to make your recursion work correctly, ignoring paths that don't lead to the correct file.

If we called web.getPathFromName("staff.md"), the method would return "about/staff.md". Similarly, if we called web.getPathFromName("lec02"), we would get "lectures/lec02". If we called web.getPathFromName("discussions"), web.getPathFromName("binary.tex"), or web.getPathFromName("web"), the method should return "".

File.java