What would be a good approach to generate a tree of folders?

Question

Say I have an array of strings, like this:

var folders = new[]
{
    "Foo",
    "Bar",
    "Foo\Bar"
    "Foo\Bar\Baz"
};

And that I have an object that represents a folder - something like this:

class Folder
{
    private readonly string _name;
    private readonly IEnumerable<Folder> _folders;

    public Folder(string name, IEnumerable<Folder> folders)
    {
        _name = name; 
        _folders = folders;
    }

    public string Name { get { return _name; } }
    public IEnumerable<Folder> Folders { get { return _folders; } }
}

What would be a good way to end up with an object structure like this?

- Folder {Name:Foo}
  - Folder {Name:Bar}
    - Folder {Name:Baz}
- Folder {Name:Bar}

I'm thinking this in terms of splitting the strings on the delimiter and then grouping... and I'm thinking this wrong, I simply don't have an approach to get there, it's not going anywhere. I get the gut-feeling that I need to involve recursion somehow, but I don't see where to fit that in, I'm stuck.

The example code above is C#, but I don't need actual code, just some pseudo-code, or a line of thought, a little clue.

_{...I hope it's in-scope?}

Answer 1

The following algorithm should do almost what you've asked for.

paths : List<String>    ;; your list of paths
tree : Folder = NEW Folder("")
FOREACH path IN paths DO
    node : Folder = tree
    FOREACH component IN split(path, "/") DO
        next : Folder = node.getChild(component)
        IF next IS NULL THEN
            next := NEW Folder(component)
            node.addChild(next)
        FI
        node := next
    DONE
DONE

I'm saying almost because it will create a directory tree under a common root node labeled with the empty string (like / in POSIX file systems). If you don't want this but rather have a forest of directory trees, you'd have to write a small data structure to hold the forest's trees. Or you go ahead and use the common root and after you've built the tree, extract its child nodes (the trees) into a list.

The code example assumes a method Folder::getChild that will either return a reference to a child with that name if it exists or else the NULL pointer. Folder::addChild is of course supposed to add another child Folder.

Answer 2

Let's assume you have an additional method GetOrCreate(name) that returns a folder for a given name, or creates it if no such folder exist, and that you have a root folder that contains your whole hierarchy. Then given a list of strings path, we can easily implement an iterative solution:

Folder current = root;
for (name in path)
  current = current.GetOrCreate(name);

Alternatively you could define a recursive method MakePath(path):

public void MakePath(names) {
  return if path is empty;
  GetOrCreate(path.First).MakePath(path.Rest);
}

The interesting question is how GetOrCreate might work. Your problem is that you are using an IEnumerable<Folder>, where you really want an associative data structure (map, dictionary, hash table, whatever that's called in your language). This allows easy membership test, and enforces uniqueness – no two folders with the same parent can share the same name.

The root folder would be another problem in your current design, since it doesn't have any obvious name (well, in Windows land that would be kind of like the drive letters, but that might be useless in your application). Instead, the name of childs might be a property of the parent folder, not of the child folders. The name is implicit as the key in the hash table rather than an explicit object property. This avoids data duplication, but makes it hard to answer questions like “given this folder, what is its name?”. Of course, it's already difficult to answer “given this folder, what is its full path?”, unless each folder has easy access to its name and its parent.

Answer 3

If you look at how the file system handles folder within their structure, there is one vital difference making stuff easier for traversing and that is keeping track of the parent as well as the folders (and files).

In your case this means that you should keep track of the parent of any given Folder, and make a decision regarding the top level to either have an empty top folder, or let the folder at the top level have null as parent folder, thusly allowing the folder to be at the same level.

This means you need a constructor taking up to three parameters:

• name – The name of current folder, should require a value always
• parent – Link to the parent folder, preferably a weak reference to avoid strong circular reference which can throw of the garbage collectors. Can default to null
• folders – List of sub-folders, or null to indicate no sub-folders, yet. Do however ensure that the constructor creates a suitable instantation of the list of folders. It can be empty, but it should be ready for adding new folders.

Regarding methods for this class, I would suggest at least the following:

• GetOrCreate(folderName) – Searches through folder list, and if not found it creates a new folder with self/this as parent. Return this newly created Folder
• Optionally AddPath(path) – Accepts a full path, which it splits into the folder components. Starting at the current level, do a GetOrCreate(), and change current level and repeat for next folder component.
• GetFullPath() – Starting at current level prepend current level with all parent levels to give you the full path.

If not implementing the AddPath() as a separate method, you still need to do the following for the list of paths, and this could be a static method of your Folder() class:

• define your top level, i.e. tree = new Folder("")
• foreach path in paths:
  • current = tree
  • foreach component in split path
    • current = current.GetOrCreate(component, current.parent)

Hope this helps to get you started.