public PreviewTreeModel(Collection<FileDescription> files)
{
// contains all files in the tree
this.files = new ArrayList<FileDescription>(files);
// add missing parents
for (FileDescription description : files)
{
FileDescription parent = new FileDescription(description.getFile().getParentFile(), false);
// add missing parents
File parentFile = parent.getFile();
List<FileDescription> parents = new Vector<FileDescription>();
while (parentFile != null)
{
FileDescription parentDescription = new FileDescription(parentFile, false);
// connected to an existing file
if (this.files.contains(parentDescription))
{
this.files.addAll(parents); // complete connection
break;
}
parents.add(parentDescription);
parentFile = parentFile.getParentFile();
}
}
// find roots
this.roots = this.findRoots(files);
// make sure all roots are folders
for (FileDescription root : this.roots)
if (root.isFile())
{
this.roots.remove(root);
this.roots.add(new FileDescription(root.getFile().getParentFile(), false));
}
}
private Collection<FileDescription> findRoots(Collection<FileDescription> descriptions)
{
logger.trace("findRoots(" + descriptions + ")");
Collection<FileDescription> files;
Collection<FileDescription> roots = descriptions;
do
{
files = new Vector<FileDescription>(roots);
roots = new Vector<FileDescription>();
for (FileDescription fileA : files)
for (FileDescription fileB : files)
if (!fileA.equals(fileB))
{
FileDescription ancestor = this.findAncestor(fileA, fileB);
if (ancestor != null && !roots.contains(ancestor))
roots.add(ancestor);
}
}
while (!roots.isEmpty());
return files;
}
private FileDescription findAncestor(FileDescription a, FileDescription b)
{
logger.trace("findAncestor(" + a + "," + b + ")");
String[] partsA = a.getFile().getAbsolutePath().split("\\\\");
String[] partsB = b.getFile().getAbsolutePath().split("\\\\");
int minLength = Math.min(partsA.length, partsB.length);
List<String> ancestorParts = new Vector<String>();
for (int i = 0; i < minLength; i++)
if (partsA[i].equals(partsB[i]))
ancestorParts.add(partsA[i]);
else
break;
String ancestor = "";
for (String part : ancestorParts)
ancestor += part + "\\";
if (ancestor.isEmpty())
return null;
else
return new FileDescription(new File(ancestor), false);
}
Refactorings
No refactoring yet !
spoon!
April 14, 2008, April 14, 2008 02:30, permalink
No rating.
Login to rate!
import java.util.*;
import java.io.File;
import java.util.regex.Pattern;
// I don't know how your FileDescription class is defined
// but I just make a simplified example here
class FileDescription
{
private File file;
public FileDescription(String s) { file = new File(s); }
public File getFile() { return file; }
}
// DirTree = anything in the filesystem, including file or directory
class DirTree
{
// if it is a non-empty directory, contents will be non-null
public Map<String,DirTree> contents;
// if it is a file given in the input, then description will be non-null
public FileDescription description;
public void print() { print("", 0); }
// recursively print directory tree
public void print(String prefix, int depth) {
for (int i = 0; i < depth; i++)
System.out.print("-");
System.out.println(prefix);
if (contents != null)
for (Map.Entry<String,DirTree> e : contents.entrySet()) {
String name = e.getKey();
DirTree subTree = e.getValue();
subTree.print(prefix + "\\" + name, depth + 1);
}
}
}
public class PreviewTreeNode
{
public static DirTree generateTree(Collection<FileDescription> files) {
DirTree root = new DirTree();
for (FileDescription fd : files) {
String path = fd.getFile().getAbsolutePath();
// keeps track of location in tree
DirTree current = root;
// iterate through each directory in path
for (String part : path.split(Pattern.quote("\\"))) {
if (current.contents == null)
current.contents = new HashMap<String,DirTree>();
// add it if it is not already in the directory tree
if (!current.contents.containsKey(part))
current.contents.put(part, new DirTree());
// go in to the next deeper level
current = current.contents.get(part);
}
// now current refers to the location of the file we want
current.description = fd;
}
return root;
}
public static void main(String[] args) {
Collection<FileDescription> files =
Arrays.asList(new FileDescription("A:\\Folder1\\Folder2\\Folder3\\File1.txt"),
new FileDescription("A:\\Folder1\\File2.txt"),
new FileDescription("B:\\Folder4\\Folder5\\File3.txt"),
new FileDescription("B:\\Folder4\\Folder5\\File4.txt"));
DirTree root = generateTree(files);
root.print();
}
}
I would like to transform a set of files into a tree structure. The problem is that not all files making up the directory tree are in the set.
Here is an example:
The files:
A:\Folder1\Folder2\Folder3\File1.txt
A:\Folder1\File2.txt
B:\Folder4\Folder5\File3.txt
B:\Folder4\Folder5\File4.txt
The resulting tree should look like this:
A:\Folder1
-Folder2
--Folder3
---File1.txt
-File2.txt
B:\Folder4\Folder5
-File3.txt
-File4.txt
Technically, these are two trees, and I will need to be able to identify the root of each. The accompanying code shows the algorithm I use now. It works, but it is horribly slow. Any thoughts on how to improve its efficiency will be greatly appreciated.
Note: in the code, the object FileDescription can be thought of as a regular java.io.File. A FileDescription contains a file and a hashmap with properties. (For example, in the case of an audio file, 'volume = 10' or something along those lines.)
If I left anything unclear, I will gladly answer questions.