How to convert list of filepaths to a hireachial tree in Java

Question

can someone give me some pointers for this. I want take a list of file paths (just Strings) and convert into a hierachial tree like structure. So there are two tasks, parsing the strings to create a tree, and creating a tree or some sort of mapping structure to actually put the result into. (The third task is then to parse the tree to display as as a tree in html)

I'm using Java 7 so I assume i could use Paths to accomplish the first part, but struggling to get a clear algorithm in place.

C:\Music\Blur\Leisure
C:\Music\KateBush\WholeStory\Disc1
C:\Music\KateBush\WholeStory\Disc2
C:\Music\KateBush\The Kick Inside   
C:\Music\KateBush\The Dreaming
C:\MusicUnprocessed\Blue\ParkLife

So it gives

C:\
   Music
      Blur 
          Leisure
      Kate Bush
          Whole Story
               Disc 1
               Disc 2
          The Kick Inside
          The Dreaming
    MusicProcessing
      Blur
         ParkLife

Answer 1

Here's a very simple implementation, which will give you an idea of where to start. :-)

import java.io.PrintStream;
import java.util.Collections;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.regex.Pattern;

public class PathWalker {
    public static class Node {
        private final Map<String, Node> children = new TreeMap<>();

        public Node getChild(String name) {
            if (children.containsKey(name))
                return children.get(name);
            Node result = new Node();
            children.put(name, result);
            return result;
        }

        public Map<String, Node> getChildren() {
            return Collections.unmodifiableMap(children);
        }
    }

    private final Node root = new Node();

    private static final Pattern PATH_SEPARATOR = Pattern.compile("\\\\");
    public void addPath(String path) {
        String[] names = PATH_SEPARATOR.split(path);
        Node node = root;
        for (String name : names)
            node = node.getChild(name);
    }

    private static void printHtml(Node node, PrintStream out) {
        Map<String, Node> children = node.getChildren();
        if (children.isEmpty())
            return;
        out.println("<ul>");
        for (Map.Entry<String, Node> child : children.entrySet()) {
            out.print("<li>");
            out.print(child.getKey());
            printHtml(child.getValue(), out);
            out.println("</li>");
        }
        out.println("</ul>");
    }

    public void printHtml(PrintStream out) {
        printHtml(root, out);
    }

    public static void main(String[] args) {
        PathWalker self = new PathWalker();
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine())
            self.addPath(scanner.nextLine());
        self.printHtml(System.out);
    }
}

Originally, I thought about making separate classes for directories and regular files, but I felt in this case that, since all you wanted to do is to print the names, that using a unified node class makes the code simpler to work with, not least because you can avoid having to implement the visitor pattern.

The output isn't formatted in any particular nice way. So that's something you can tweak the code on, if you want; alternatively, you can run the output through HTML Tidy if you want something nicer-looking.

I chose to use TreeMap, so the directory entries are lexicographically ordered. If you want to use insertion order instead, just change to use LinkedHashMap.

Answer 2

Could you be a bit more specific about what you're struggling with? It seems to me that you've already managed to split up the tasks into nice chunks (parsing, creating a tree, and displaying it).

If you want to know more about trees, then I'd recommend Stanford's excellent CS library (http://cslibrary.stanford.edu/), which is how I learned about linked lists and binary trees. I think coming up with my own lisp implementation of a binary tree and functions to insert new elements, and parse it, has really helped me get my head around these kinds of problems.

Do note that in your example a binary tree would suffice to represent the data, as every parent has at most two children, but I would have thought that you might encounter situations where this is not the case.

But once you've got your head around binary trees, it shouldn't be too difficult to understand trees with an arbitrary number of children.

As for the parsing, I'm not sure you really need Paths. As you're already given a file in which every line is a file with its fully qualified pathname, it shouldn't be too difficult to write a simple parse function yourself.

I mean, basically you want to split on slashes "\", so everytime you see a slash, you create a new node, with the previous node as its parent. If the node already exists, you simply append to it. For every line you start from the very root of the tree.

Outputting the tree as html is essentially tree traversal.