Skip to content

Instantly share code, notes, and snippets.

@NPException
Created February 25, 2016 13:47
Show Gist options
  • Save NPException/e570c4c8eddd6064fe5a to your computer and use it in GitHub Desktop.
Save NPException/e570c4c8eddd6064fe5a to your computer and use it in GitHub Desktop.
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
public interface INode {
/**
* @return node identifier
*/
public String getIdent();
/**
* @return number of children attached to this node
*/
public int getChildCount();
/**
* Iterates across this node's children from first to last
*/
Collection<? extends INode> children();
/**
* Searches for a descendant of this node with the given node ident.
* (Including this node itself)
* @param nodeID
* The node ident that should be searched for
* @param depthFirst
* If TRUE, a depth-first search will be used. Otherwise a breadth-first search.
* @return The descendant with the given node ident (may be THIS node), or null if not found.
*/
default INode findDescendant(final String nodeID, final boolean depthFirst) {
if (getIdent().equals(nodeID)) {
return this;
}
if (depthFirst) {
// DEPTH FIRST APPROACH //
final LinkedList<Iterator<? extends INode>> searchLevelStack = new LinkedList<>();
Iterator<? extends INode> currentSearchLevel = children().iterator();
while (currentSearchLevel != null) {
if (currentSearchLevel.hasNext()) {
// more children in this level:
// check next child
final INode child = currentSearchLevel.next();
if (child.getIdent().equals(nodeID)) {
return child;
}
// child did not match. Drop one level if possible.
if (child.getChildCount() > 0) {
searchLevelStack.push(currentSearchLevel);
currentSearchLevel = child.children().iterator();
}
} else {
// no more elements on this level:
// poll previous level from stack
currentSearchLevel = searchLevelStack.poll();
}
}
} else {
// BREADTH FIRST APPROACH //
final LinkedList<INode> nodes = new LinkedList<>();
nodes.add(this);
while (!nodes.isEmpty()) {
for (final INode child : nodes.removeFirst().children()) {
if (child.getIdent().equals(nodeID)) {
return child;
}
nodes.add(child);
}
}
}
return null;
}
}
import java.util.Collection;
import java.util.LinkedList;
public class Node implements INode {
private String nodeIdent;
private final LinkedList<Node> children = new LinkedList<>();
@Override
public Collection<Node> children() {
return children;
}
@Override
public String getIdent() {
return nodeIdent;
}
@Override
public int getChildCount() {
return children.size();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment