4
\$\begingroup\$

I have implemented an in-memory filesystem - this is a design question from LeetCode. Is there a better OOP approach to represent files and directories? The current code uses a boolean flag isDirectory to distinguish between files and directories and I'm not confident that it is the best approach. See the code below. I'll also be happy to get any other comments about the code - readability, variable and method naming, etc.

class FileSystem {
    
    Inode root;

    public FileSystem() 
    {
        root = new Inode("/", true);
    }
    
    public List<String> ls(String path) 
    {
        List<String> listing = new ArrayList<>();
        
        String[] queries = path.substring(1).split("/");
        
        Inode node = root;
        
        for(String query: queries)
        {
            if(query.isEmpty()) // happens when we search root
                break;
            
            node = node.children.get(query);
            
            if(node == null)
                return listing;
        }
        
        if(node.isDirectory)
        {
            node.children.forEach((name, inode) -> { 
                listing.add(name);
            });
        }
        else
        {
            listing.add(node.Name);
        }
        
           
        Collections.sort(listing);
        
        return listing;
    }
    
    public void mkdir(String path) 
    {
        String[] subdirs = path.substring(1).split("/");
        Inode node = root;
        
        for(String dir: subdirs)
        {
            if(dir.isEmpty()) // happens when we search root
                break;
            
            if(!node.children.containsKey(dir))
                node.children.put(dir, new Inode(dir, true));
            
            node = node.children.get(dir);
        }
        
    }
    
    public void addContentToFile(String filePath, String content) 
    {
        String[] subdirs = filePath.substring(1).split("/");
        Inode node = root;
        
        for(int i=0; i<subdirs.length; i++)
        {
            if(!node.children.containsKey(subdirs[i]))
            {
                if(i < subdirs.length-1)
                    node.children.put(subdirs[i], new Inode(subdirs[i], true));
                else
                    node.children.put(subdirs[i], new Inode(subdirs[i], false));
                
            }
                
            node = node.children.get(subdirs[i]);
        }
        
        node.fileContent.append(content);
        
    }
    
    public String readContentFromFile(String filePath) 
    {
        String[] subdirs = filePath.substring(1).split("/");
        Inode node = root;
        
        for(String dir: subdirs)
        {
            node = node.children.get(dir);
        }
        
        return node.fileContent.toString();
    }
    
}

// Trie data structure for files and directories

    class Inode
    {
        public String Name;
        public boolean isDirectory=true;
        public StringBuilder fileContent=null;
        public HashMap<String, Inode> children = null;
        
        public Inode(String name, boolean is_dir)
        {
            this.Name = name;
            this.isDirectory = is_dir;
            
            if(!is_dir)
                fileContent = new StringBuilder();
            
            if(is_dir && children == null)
                children = new HashMap<>();
        }
        
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ If you want a solution that is less "leetcode" (aka no-sense training program) and more real life, look into implementing a real custom file system in java. Here's an entrypoint to the oracle docs: docs.oracle.com/javase/8/docs/technotes/guides/io/fsp/… \$\endgroup\$ – mtj Jul 28 at 5:40
  • \$\begingroup\$ Awesome this looks very interesting. Thanks @mtj \$\endgroup\$ – Kimutai Jul 28 at 18:43
1
\$\begingroup\$

The implementation is easy to understand but the model can be improved.

Input validation

As said by @Martin Frank it's very important to validate the input for a file system. For example:

public void mkdir(String path){
    if(path==null) {
        throw new IllegalArgumentException("Input cannot be null");
    }
    // ...
}

Bug

String[] queries = path.substring(1).split("/");

This line cuts the first letter of the path and then splits it. If you call mkdir("newFolder") the result is a folder called ewFolder. You can't assume that all the users will use an absolute path.

Duplicated code

Parsing the path is duplicated many times, this is an indicator that you should move the logic into its own method.

Polymorphism

Using a single class Inode to model a file and a directory has the following issues:

  • Why a directory has fileContent?
  • Why a file has children?
  • How to add another entity like a symbolic link?

The class is going to became too complex and hard to test. Create multiple classes that extend Inode.

Encapsulation

The instance variables (fileContent, children, etc.) of Inode shouldn't be public. Consider these points:

  • What if you want to change the children to a LinkedList?
  • What if you want to store an image instead of text?

You'll need to change almost every methods of FileSystem! To fix this issue make the state of Inode private and provide access only via methods (Encapsulation).

Consider this design:

abstract class Inode {
    private String name;

    public Inode(String name) {
        this.name = name;
    }

    public abstract boolean isDirectory();

    // methods to get the name, rename, etc..
}

These are the classes File and Directory.

class File extends Inode {
    public File(String name) {
        super(name);
    }

    @Override
    public boolean isDirectory() {
        return false;
    }
}

class Directory extends Inode {
    private HashMap<String, Inode> children;

    public Directory(String name) {
        super(name);
        children = new HashMap<>();
    }

    @Override
    public boolean isDirectory() {
        return true;
    }
    public boolean contains(String nodeName) {
        return children.containsKey(nodeName);
    }
    // methods to query children. Do not return the HashMap!
}

In this way you can easily change the HashMap to another data structure without impacting the FileSystem.

A file that contains text will extends from File:

class TextFile extends File{
    private StringBuilder content;
    
    public TextFile(String name) {
        super(name);
        content = new StringBuilder();
    }
    // methods to get and add content
}

Separation of Concerns

The method ls does too many things:

  1. Move the current directory to the given path -> move this logic in a method (e.g. cd)
  2. List the files -> this is the purpose of the method
  3. Sort the files -> don't assume that a user always wants a sorted output, this can be a parameter

Same for the methods addContentToFile and readContentFromFile, they are too high-level for a file system. Usually a file system provides only low-level methods to manage files like create/delete and write/read bytes.

You can move the high-level features from the file system to other classes.

Minor change

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ thanks for the feedback. So on the point you make about putting regular files and directories into separate classes, when listing them using ls Inode objects are returned and we can use the isDirectory() method to determine whether they are files are not. So suppose they are directories and I want to list the contents of the directories, is down-casting the Inode object into a Directory object a good idea in this case? \$\endgroup\$ – Kimutai Jul 28 at 10:12
  • \$\begingroup\$ Down-casting is the only option with the example I provided, but there are other approaches. For example the class java.io.File has a method list() that returns null if invoked on a non directory. My point was to show how to separate and hide the state into classes but you can adjust the Inode interface. \$\endgroup\$ – Marc Jul 28 at 10:34
  • \$\begingroup\$ Thanks. I like your answer \$\endgroup\$ – Kimutai Jul 28 at 10:55
2
\$\begingroup\$

create Subclasses / interfaces

if you think there is a difference in Behaviour then there is a need for a seperate class - if you think some classes have something in common, extract an interface!

so create a class Directory and a class File. Let both classes implement the Node Interface. (Note - in Java we don't use the hungarian notation )

inconsistency // oo-abuse

what's the purpose of Node if you don't use it? compare these two approaches

  1. public List<String> ls(String path) vs.
  2. public List<Node> ls(Node path)

in case 1 it is absolutly not clear how the String path should look like, especially since it is OS-dependant. (what would String[] subdirs = filePath.substring(1).split("/"); on other OS do?) It is also not clear what kind of output this Method delivers

in case 2 we have cleary declared what kind of input we expect, (even though i'm missing a parent attribut - that would ease up the searching) - we reduce the problem with different OSes to the single place where it belongs: at the constructor of the Node (Single responsibility). And we have a very accurate output (compared to the List<String> from case 1 - how would we know if a String is a Directory or a File? Node already provides all these information!)

File System vs. Editor

i'm not sure how addContentToFile() and readContentFromFile match for a FileSystem - in my opinion these two methods belong to an Editor/Viewer and not the the File System - create an Editor (an Editor class)! think of the possibilities: you can then provide different Editors for different file Types?

Error Handling

i would expect a file system to be a bit more chatty about IllegalArgumentException (why are none thrown? how is such case treated?)

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the feedback @Matrin Frank. +1 \$\endgroup\$ – Kimutai Jul 28 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.