Java Tree to represent filesystem (files/dir) from list of paths

Question

I've a list of paths like this

/mnt/sdcard/folder1/a/b/file1
/mnt/sdcard/folder1/a/b/file2
/mnt/sdcard/folder1/a/b/file3
/mnt/sdcard/folder1/a/b/file4
/mnt/sdcard/folder1/a/b/file5
/mnt/sdcard/folder1/e/c/file6
/mnt/sdcard/folder2/d/file7
/mnt/sdcard/folder2/d/file8
/mnt/sdcard/file9

So from this list of paths (Stings) I need to crete a Java Tree structure that has folders as nodes and files as leaf (there wont be empty folders as leaf).

What I need I think is the add method where I pass to them a String (path of the file) and it add it to the correct place in the tree creating correct nodes (Folder) if they are not already there

This tree structure will need me to get list of nodes when I'm on node and list of leafs (but I think this will be a normal features for trees)

I will always have Strings as paths and not real file or folders. Is there something ready to use or a source code to start?

Thank you very much.

Answer 1

I implemented a solution to the challenge myself. I am representing each node of a filesystem-hierarchy in a DirectoryNode. A helper-method createDirectoryTree(String... filePaths) creates a direcotry-tree.

Here is the usage example:

final String[] list = new String[]{
  "mnt/sdcard/folder1/a/b/file1.file",
  "mnt/sdcard/folder1/a/b/file2.file",
  "mnt/sdcard/folder1/a/b/file3.file",
  "mnt/sdcard/folder1/a/b/file4.file",
  "mnt/sdcard/folder1/a/b/file5.file",
  "mnt/sdcard/folder1/e/c/file6.file",
  "mnt/sdcard/folder2/d/file7.file",
  "mnt/sdcard/folder2/d/file8.file",
  "mnt/sdcard/file9.file"
};

final DirectoryNode directoryRootNode = createDirectoryTree(list);

System.out.println(directoryRootNode);

The System.out.println -output is:

  {value='mnt', children=[{value='sdcard', children=[{value='folder1', 
  children=[{value='a', children=[{value='b', children=[{value='file1.file', 
  children=[]}, {value='file2.file', children=[]}, {value='file3.file', 
  children=[]}, {value='file4.file', children=[]}, {value='file5.file', 
  children=[]}]}]}, {value='e', children=[{value='c', 
  children=[{value='file6.file', children=[]}]}]}]}, 
  {value='folder2', children=[{value='d', children=[{value='file7.file', 
  children=[]}, {value='file8.file', children=[]}]}]}, 
  {value='file9.file', children=[]}]}]}

Java source:

// DirectoriesHelper.java
import java.util.Optional;

public final class DirectoriesHelper {

  private DirectoriesHelper() {}

  public static Optional<DirectoryNode> createDirectoryTree(String... filePaths) {

    DirectoryNode treeRootNode = null;
    for (final String childPath : filePaths) {
      final String path = childPath == null ? "" : childPath;
      final String[] pathElements = path.split("/");
      DirectoryNode movingNode = null;
      for (final String pathElement : pathElements) {
        movingNode = new DirectoryNode(movingNode, pathElement);
      }

      if (treeRootNode == null) {
        treeRootNode = movingNode.getRoot();
      } else {
        treeRootNode.merge(movingNode.getRoot());
      }
    }

    return Optional.ofNullable(treeRootNode);
  }
}


// DirectoryNode.java
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;

public class DirectoryNode implements Comparable<DirectoryNode> {

  private final Set<DirectoryNode> children = new LinkedHashSet<>();

  private final String value;

  private final DirectoryNode parent;

  public DirectoryNode(final DirectoryNode parent, final String value) {
    this.parent = parent;
    if (this.parent != null) {
      this.parent.children.add(this);
    }

    this.value = value;
  }

  private static void appendDirectoryNode(
      final Set<DirectoryNode> directoryNodes, final DirectoryNode node) {
    if (node.isLeaf()) {
      return;
    }

    directoryNodes.add(node);
    node.getChildren().parallelStream()
        .forEach(childNode -> appendDirectoryNode(directoryNodes, childNode));
  }

  public Set<DirectoryNode> getChildren() {
    return children;
  }

  public String getValue() {
    return value;
  }

  public DirectoryNode getParent() {
    return parent;
  }

  public String getPath() {
    if (getParent() == null) {
      return value;
    }

    return parent.getPath() + "/" + value;
  }

  public int getLeafCount() {
    int leafCount = isLeaf() ? 1 : 0;
    for (final DirectoryNode child : children) {
      leafCount += child.getLeafCount();
    }

    return leafCount;
  }

  public boolean isLeaf() {
    return children.isEmpty();
  }

  /**
   * @return Subnodes of this node, which are directory (non-leaf / no-children) nodes
   */
  public Set<DirectoryNode> getDirectoryNodes() {
    final Set<DirectoryNode> directoryNodes = Collections.synchronizedSortedSet(new TreeSet<>());
    appendDirectoryNode(directoryNodes, this);

    return directoryNodes;
  }

  public DirectoryNode getRoot() {
    return parent == null ? this : parent.getRoot();
  }

  public boolean isRootNode() {
    return equals(getRoot());
  }

  public void merge(final DirectoryNode that) {
    if (!value.equals(that.value)) {
      return;
    } else if (children.isEmpty()) {
      children.addAll(that.children);
      return;
    }

    final DirectoryNode[] thisChildren = children.toArray(new DirectoryNode[children.size()]);
    for (final DirectoryNode thisChild : thisChildren) {
      for (final DirectoryNode thatChild : that.children) {
        if (thisChild.value.equals(thatChild.value)) {
          thisChild.merge(thatChild);
        } else {
          children.add(thatChild);
        }
      }
    }
  }

  @Override
  public boolean equals(final Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    final DirectoryNode that = (DirectoryNode) o;
    return Objects.equals(value, that.value) && Objects.equals(parent, that.parent);
  }

  @Override
  public int hashCode() {
    return Objects.hash(value, parent);
  }

  @Override
  public String toString() {
    return "{" + "value='" + value + '\'' + ", children=" + children + '}';
  }

  @Override
  public int compareTo(final DirectoryNode o) {
    return getPath().compareTo(o.getPath());
  }
}

Answer 2

Seems like you could adapt either a Trie / Radix Trie or a Binary Search Tree to work in either situation. You could augment a Trie to store "folders" as the inner nodes (instead of characters like in a regular Trie) or you could augment a Binary Search Tree to store "folders" as inner nodes (as long as they implement a comparable interface) and "files" as leaf nodes.

My implementation of those structures are linked in the text above.

Answer 3

Thank you for all your answer. I made my working implementation. I think that I will need to improve it in order to make it works better with more caching in adding element to the tree structure.

As I said what I was needing was a structure that allow me to have a "virtual" rappresentation of a FS.

MXMTree.java

public class MXMTree {

    MXMNode root;
    MXMNode commonRoot;

    public MXMTree( MXMNode root ) {
        this.root = root;
        commonRoot = null;
    }

    public void addElement( String elementValue ) { 
        String[] list = elementValue.split("/");

        // latest element of the list is the filename.extrension
        root.addElement(root.incrementalPath, list);

    }

    public void printTree() {
        //I move the tree common root to the current common root because I don't mind about initial folder
        //that has only 1 child (and no leaf)
        getCommonRoot();
        commonRoot.printNode(0);
    }

    public MXMNode getCommonRoot() {
        if ( commonRoot != null)
            return commonRoot;
        else {
            MXMNode current = root;
            while ( current.leafs.size() <= 0 ) {
                current = current.childs.get(0);
            }
            commonRoot = current;
            return commonRoot;
        }

    }


}

MXMNode.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class MXMNode {

    List<MXMNode> childs;
    List<MXMNode> leafs;
    String data;
    String incrementalPath;

    public MXMNode( String nodeValue, String incrementalPath ) {
        childs = new ArrayList<MXMNode>();
        leafs = new ArrayList<MXMNode>();
        data = nodeValue;
        this. incrementalPath = incrementalPath;
    }

    public boolean isLeaf() {
        return childs.isEmpty() && leafs.isEmpty();
    }

    public void addElement(String currentPath, String[] list) {

        //Avoid first element that can be an empty string if you split a string that has a starting slash as /sd/card/
        while( list[0] == null || list[0].equals("") )
            list = Arrays.copyOfRange(list, 1, list.length);

        MXMNode currentChild = new MXMNode(list[0], currentPath+"/"+list[0]);
        if ( list.length == 1 ) {
            leafs.add( currentChild );
            return;
        } else {
            int index = childs.indexOf( currentChild );
            if ( index == -1 ) {
                childs.add( currentChild );
                currentChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length));
            } else {
                MXMNode nextChild = childs.get(index);
                nextChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length));
            }
        }
    }

    @Override
    public boolean equals(Object obj) {
        MXMNode cmpObj = (MXMNode)obj;
        return incrementalPath.equals( cmpObj.incrementalPath ) && data.equals( cmpObj.data );
    }

    public void printNode( int increment ) {
        for (int i = 0; i < increment; i++) {
            System.out.print(" ");
        }
        System.out.println(incrementalPath + (isLeaf() ? " -> " + data : "")  );
        for( MXMNode n: childs)
            n.printNode(increment+2);
        for( MXMNode n: leafs)
            n.printNode(increment+2);
    }

    @Override
    public String toString() {
        return data;
    }


}

Test.java for test code

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {

        String slist[] = new String[] { 
                "/mnt/sdcard/folder1/a/b/file1.file", 
                "/mnt/sdcard/folder1/a/b/file2.file", 
                "/mnt/sdcard/folder1/a/b/file3.file", 
                "/mnt/sdcard/folder1/a/b/file4.file",
                "/mnt/sdcard/folder1/a/b/file5.file", 
                "/mnt/sdcard/folder1/e/c/file6.file", 
                "/mnt/sdcard/folder2/d/file7.file", 
                "/mnt/sdcard/folder2/d/file8.file", 
                "/mnt/sdcard/file9.file" 
        };

        MXMTree tree = new MXMTree(new MXMNode("root", "root"));
        for (String data : slist) {
            tree.addElement(data);
        }

        tree.printTree();
    }

}

Please tell me if you have some good advice about improvments :)

Answer 4

I would recommend reading up on data structures, particularly trees. In Java, you can represent these by creating a node class that has references to other nodes. For example:

public class Node {
    private Node[] children;
    /* snip other fields */
    public boolean isFile() {
         return children.count == 0;
    }
}

Obviously, you can store your node references anyway you like- arrays or collections will work with non-binary trees.

Given your list of files, you can read these and populate your tree structure.

Answer 5

Have a look in new Java 7 - nio2 package. All you need is inside.