Java Explicit Non-Recursive Filesystem
I need to create an application that uses a non-recursive walk through the filesystem and prints files that are at a certain depth. What do I have:
public void putFileToQueue() throws IOException, InterruptedException {
File root = new File(rootPath).getAbsoluteFile();
checkFile(root, depth);
Queue<DepthControl> queue = new ArrayDeque<DepthControl>();
DepthControl e = new DepthControl(0, root);
do {
root = e.getFileName();
if (root.isDirectory()) {
File[] files = root.listFiles();
if (files != null)
for (File file : files) {
if (e.getDepth() + 1 <= depth && file.isDirectory()) {
queue.offer(new DepthControl(e.getDepth() + 1,file));
}
if (file.getName().contains(mask)) {
if (e.getDepth() == depth) {
System.out.println(Thread.currentThread().getName()
+ " putting in queue: "
+ file.getAbsolutePath());
}
}
}
}
e = queue.poll();
} while (e != null);
}
And the helper class
public class DepthControl {
private int depth;
private File file;
public DepthControl(int depth, File file) {
this.depth = depth;
this.file = file;
}
public File getFileName() {
return file;
}
public int getDepth() {
return depth;
}
}
I got the answer that this program is using extra memory due to the search at the beginning of the Breadth (translation of the truth of hope). I have O (k ^ n) where k is the average number of subdirectories, n is the depth. This program can be easily executed in O (k * n). Help me fix my algorithm.
source to share
I think this should get the job done and is a little easier. It just keeps track of the files at the next level, expands them, and then repeats the process. The algorithm itself tracks depth, so there is no need for this additional class.
// start in home directory.
File root = new File(System.getProperty("user.dir"));
List<File> expand = new LinkedList<File>();
expand.add(root);
for (int depth = 0; depth < 10; depth++) {
File[] expandCopy = expand.toArray(new File[expand.size()]);
expand.clear();
for (File file : expandCopy) {
System.out.println(depth + " " + file);
if (file.isDirectory()) {
expand.addAll(Arrays.asList(file.listFiles()));
}
}
}
source to share
To avoid recursion when walking through a tree, there are basically two options:
- Use a "worklist" (similar to the one above) to keep track of the work in progress. As each item is explored, new work items that are "discovered" as a result are added to the worklist (can be FIFO, LIFO, or random order), not critical, although this often affects "link locality" for performance).
- Use a stack / drop-down list to essentially simulate a recursive scheme.
For # 2, you need to write an algorithm, which is sort of like a state machine, returning to the stack after each step to determine what to do next. The stack entries for tree walking basically contain the current tree node and the index into the child of the next child to check.
source to share
Assuming you want to limit the amount of space used and:
- you can assume that the list of files / directories is static during your traversal, AND
- you can assume that the list of files / directories in the referenced directory is always returned in the same order
- you have access to the parent directory of the current directory
Then you can navigate the directory using only the information about the last visit to node. In particular, something like strings
1. Keep track of the last Entry (directory or file) visited
2. Keep track of the current directory
3. Get a list of files in the current directory
4. Find the index of the last Entry visited in the list of files
5. If lastVisited is the last Entry in the current directory,
5.1.1 If current directory == start directory, we're done
5.1.2 Otherwise, lastVisited = the current directory and current directory is the parent directory
5.2. Otherwise, visit the element after lastVisited and set lastVisited to that element
6. Repeat from step 3
If I can, I'll try to write some code to show what I mean tomorrow ... but I just don't have time right now.
NOTE . This is not a good way to overcome the directory structure ... this is just a possible way. Outside of a normal box, and probably for a good reason.
You will have to forgive me for not offering a sample Java code, I have no time to work on this atm. Doing this in Tcl is faster for me and shouldn't be too hard to figure out. So it says:
proc getFiles {dir} {
set result {}
foreach entry [glob -tails -directory $dir * .*] {
if { $entry != "." && $entry != ".." } {
lappend result [file join $dir $entry]
}
}
return [lsort $result]
}
proc listdir {startDir} {
if {! ([file exists $startDir] && [file isdirectory $startDir])} {
error "File '$startDir' either doesn't exist or isnt a directory"
}
set result {}
set startDir [file normalize $startDir]
set currDir $startDir
set currFile {}
set fileList [getFiles $currDir]
for {set i 0} {$i < 1000} {incr i} { # use for to avoid infinate loop
set index [expr {1 + ({} == $currFile ? -1 : [lsearch $fileList $currFile])}]
if {$index < ([llength $fileList])} {
set currFile [lindex $fileList $index]
lappend result $currFile
if { [file isdirectory $currFile] } {
set currDir $currFile
set fileList [getFiles $currDir]
set currFile {}
}
} else {
# at last entry in the dir, move up one dir
if {$currDir == $startDir} {
# at the starting directory, we're done
return $result
}
set currFile $currDir
set currDir [file dirname $currDir]
set fileList [getFiles $currDir]
}
}
}
puts "Files:\n\t[join [listdir [lindex $argv 0]] \n\t]"
And by running it:
VirtualBox:~/Programming/temp$ ./dirlist.tcl /usr/share/gnome-media/icons/hicolor
Files:
/usr/share/gnome-media/icons/hicolor/16x16
/usr/share/gnome-media/icons/hicolor/16x16/status
/usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-high.png
/usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-low.png
/usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-medium.png
/usr/share/gnome-media/icons/hicolor/16x16/status/audio-input-microphone-muted.png
/usr/share/gnome-media/icons/hicolor/22x22
[snip]
/usr/share/gnome-media/icons/hicolor/48x48/devices/audio-subwoofer-testing.svg
/usr/share/gnome-media/icons/hicolor/48x48/devices/audio-subwoofer.svg
/usr/share/gnome-media/icons/hicolor/scalable
/usr/share/gnome-media/icons/hicolor/scalable/status
/usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-high.svg
/usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-low.svg
/usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-medium.svg
/usr/share/gnome-media/icons/hicolor/scalable/status/audio-input-microphone-muted.svg
source to share
If you are using Java 7, there is a very elegant way to traverse file trees. You will need to confirm if it suits your needs with recursion.
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;
import static java.nio.file.FileVisitResult.*;
public class myFinder extends SimpleFileVisitor<Path> {
public FileVisitResult visitFile(Path file, BasicFileAttributes attr) { }
public FileVisitResult postVisitDirectory(Path dir, IOException exc) { }
public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) { }
public FileVisitResult visitFileFailed(Path file, IOException exc) { }
<snip>
}
Basically, it does the first walk through the tree and calls certain methods when entering / leaving directories and when visiting a file.
I believe this is especially the case for Java 7.
http://docs.oracle.com/javase/tutorial/essential/io/walk.html
source to share
And of course, there is always a multithreading option to avoid recursion.
- Create a file queue.
- If the file adds it to the queue.
- If it's a folder, start a new thread to list the files in it that also serve this queue.
- Get the next item.
- Repeat from 2 if necessary.
Obviously, this may not display files in a predictable order.
source to share