Skip to content

Instantly share code, notes, and snippets.

@felipebizz
Last active May 28, 2016 00:36
Show Gist options
  • Save felipebizz/184f10cb46f16a4768d3bf284c1bed57 to your computer and use it in GitHub Desktop.
Save felipebizz/184f10cb46f16a4768d3bf284c1bed57 to your computer and use it in GitHub Desktop.
package br.com.arizona.visto.system.dam.util;
import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;
/**
* Percorre uma árvore em profundidade.
*/
public class DepthFirstTraversal<T> {
private final NodeStrategy<T> strategy;
private final Visitor<T> visitor;
public DepthFirstTraversal(final NodeStrategy<T> strategy, final Visitor<T> visitor) {
this.strategy = strategy;
this.visitor = visitor;
}
// /**
// * Percorre a árvore em profundidade, chamando o Visitor para cada nó pós-ordem, isto é, depois que os filhos foram
// * visitados.
// *
// * @param node nó inicial
// */
// public boolean traverse(T node) {
// for (T child : strategy.getChildren(node)) {
// final boolean keepGoing = traverse(child);
// if (!keepGoing) {
// return false;
// }
// }
// return visitor.visit(node);
// }
/**
* Percorre a árvore em profundidade, chamando o Visitor para cada nó pós-ordem, isto é, depois que os filhos foram
* visitados.
*
* @param node nó inicial
*/
public void traverse(T node) {
List<T> pending = new LinkedList<>();
Set<T> expanded = new HashSet<>(); // nós que não precisamos pegar os filhos novamente
pending.add(node);
while (!pending.isEmpty()) {
T current = pending.remove(pending.size() - 1);
if (!expanded.contains(current)) {
final List<T> children = strategy.getChildren(current);
if (!children.isEmpty()) {
expanded.add(current);
pending.add(current);
pending.addAll(children);
continue;
}
}
final boolean keepGoing = visitor.visit(current);
if (!keepGoing) {
break;
}
}
}
public static void main(final String[] args) {
/*
mkdir -p /tmp/test
mkdir -p /tmp/test/1
mkdir -p /tmp/test/2
mkdir -p /tmp/test/3
mkdir -p /tmp/test/1/a
mkdir -p /tmp/test/1/b
mkdir -p /tmp/test/2/x
mkdir -p /tmp/test/2/y
mkdir -p /tmp/test/2/z
mkdir -p /tmp/test/2/z/j
mkdir -p /tmp/test/3/a/b/c/d/e/f/g
*/
final NodeStrategy<String> fileSystemStrategy = new NodeStrategy<String>() {
@Override
public List<String> getChildren(String node) {
try {
final Path path = new File(node).toPath();
final LinkedList<String> result = new LinkedList<>();
for (Path child : Files.newDirectoryStream(path)) {
if (Files.isDirectory(child)) {
result.add(child.toString());
}
}
Collections.sort(result);
return result;
} catch (IOException e) {
throw new RuntimeException(e);
}
}
};
final Visitor<String> deleteVisitor = new Visitor<String>() {
@Override
public boolean visit(String node) {
try {
System.out.println(node);
Files.delete(new File(node).toPath());
return true;
} catch (IOException e) {
throw new RuntimeException(e);
}
}
};
final DepthFirstTraversal<String> traversal = new DepthFirstTraversal<>(fileSystemStrategy, deleteVisitor);
traversal.traverse("/tmp/test");
//traversal.visitor.visit();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment