Skip to content

Instantly share code, notes, and snippets.

@geoand geoand/iddfs.groovy
Created Apr 28, 2016

Embed
What would you like to do?
Groovy implementation of a simplistic Iterative deepening depth-first search
import groovy.transform.TailRecursive
import groovy.transform.ToString
@ToString(includePackage = false)
class Node<T> {
T data
List<Node<T>> nodes = []
}
final builder = new ObjectGraphBuilder(classLoader: getClass().classLoader)
final Node<String> root = builder.node(data: '1') {
node(data: '2a') {
node(data: '3a1')
node(data: '3a2')
}
node(data: '2b') {
node(data: '3a')
node(data: '3b')
node(data: '3c') {
node(data: '4a')
}
}
}
def <T> boolean iddfs(Node<T> root, T item) {
if (!root) {
return true
}
final queue = new LinkedList<Node<T>>()
queue.add(root)
return iddfs_recursive(item, queue)
}
@TailRecursive
def static <T> boolean iddfs_recursive(T item, Queue<Node<T>> queue) {
if (queue.isEmpty()) {
return false
}
final first = queue.remove()
if (first.data == item) {
return true
}
queue.addAll(first.nodes)
return iddfs_recursive(item, queue)
}
assert iddfs(root, '1')
assert iddfs(root, '2a')
assert iddfs(root, '2b')
assert iddfs(root, '3a')
assert iddfs(root, '3b')
assert iddfs(root, '3c')
assert iddfs(root, '4a')
assert !iddfs(root, 'dummy')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.