Discussion 8: File System Trees

In lecture, we focused on binary trees defined by a single node type. However, many trees include multiple types of nodes, with differing numbers of children possible for each node type. File systems are one example of this kind of tree. In this discussion, we'll explore how to implement recursive methods over a tree structure that operates like your computer's file system.

Learning Outcomes

Given a parent class, use inheritance to develop one or more child subclasses.
Identify parent, child, root, leaf, ancestor, and descendant nodes in a tree.
Write and analyze recursive methods on general and binary trees.

Exercise 1: Modeling a File System

Our abstract FileSystemNode class serves as the base class for both Files and Folders. You'll be implementing its four abstract methods later in this discussion.

FileSystemNode.java

Files are a FileSystemNode subtype that model leaf nodes in the file system, text files that directly contain information content.

File.java

Folders are FileSystemNodes that are used to build up a hierarchical structure. Each Folder organizes (i.e., contains) any number of other child FileSystemNodes, its files and subfolders.

/** Models a folder within a hierarchical file system with a name that
 *  contains any number of child folders/files. */
public class Folder extends FileSystemNode {
  /** The amount of space, in bytes, taken up by the folder metadata,
    * excluding the data for its children. */
  public static final int BASE_METADATA_SIZE = 32;
  
  /** The amount of space, in bytes, that each child adds to this
   *  folder's metadata. */
  public static final int CHILD_METADATA_SIZE = 8;
  
  /** The directory nodes contained within this folder. Each entry 
   *  of `children` must have a distinct `name`. */
  private final Collection<FileSystemNode> children;
  
  /** Constructs a new, initially empty, folder with the given name. */
  public Folder(String name) {
    super(name);
    this.children = new ArrayList<>();
  }
  
  /** Returns an unmodifiable list of the children of this folder. */
  public Iterable<FileSystemNode> children() {
    return Collections.unmodifiableCollection(children);
  }
  
  // abstract FileSystemNode method definitions 
}

Folder.java

Throughout the discussion, we'll assume that the client has a reference to a Folder object, the file system's root, through which they can make queries of the abstract FileSystemNode methods.

As an apt example, the following diagram models the organization of some of the CS 2110 course website assets using a tree of FileSystemNodes rooted at a web folder. Each clear node represents a Folder, and each shaded node represents a File.

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

In the next exercises, you'll provide recursive definitions for each of the four abstract FileSystemNode methods within the File and Folder classes.

(b)

Where will the base case logic be for these method definitions? How would you implement such a base case? Explain your answers.

(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?

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

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

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

Folder.java