Java - Predicate to find Node with set value

Question

I came upon object graphs while studying. And while they seem "cool" and useful, a related problem to the material made absolutely no sense to me.

public class Extensions {
     /**
     * Find any node in an object graph that satisfy a given predicate and return it.
     * @param root The root node.
     * @param predicate The given condition to satisfy.
     * @param getChildren Child selector.
     * @param <T> Type of object.
     * @return Node satisfying the condition, else null.
     */
    public static <T> T findWhere(T root, Predicate<T> predicate, Function<T, Iterable<T>> getChildren) {
        
        
    }
}

Root, trees and Nodes I am familiar with, but the rest i have no clue. I thought linked lists and similar data structures was THE method for Nodes. This seems very advanced as I have not come upon anything like this in 2 years of learning Java. While a solution would be great for me to examine and understand, a push in the right direction would be greatly appreciated.

Should return a single node matching the specified value in findWhere function (i believe).

The structure of the tree looks something like this.

A - B - C
        |
      |   |
     CA   CB

Answer 1

The idea of the findWhere method is that you've got some kind of tree structure, and you're going to search through it for a node that meets a particular condition. As soon as you find one, you can stop looking - there may be other such nodes, but you only have to return one of them. The predicate parameter is a method that you can use to check whether the condition is true. The getChildren parameter is a method that you can call to find all the children of whatever node you're currently looking at.

Here is an outline of how you might write the findWhere method.

1. Check the root node, by applying the predicate to it. If the root node satisfies the predicate, then you're done - just return the root node.
2. Call getChildren to get an iterable containing the children of the root node - maybe one of those children will contain the node you're looking for.
3. Iterate through the children, calling findWhere recursively until you get a node that satisfies the predicate. If you find such a node, then you can stop iterating, and just return the node that you found.
4. If you get to the end of the iterable without finding a node that satisfies the predicate, then there is no such node. In this case, you have to return null.

The full solution might look like this.

public static <T> T findWhere(T root, Predicate<T> predicate, Function<T, Iterable<T>> getChildren) {

    if (root == null) {
        return null;
    }

    if (predicate.test(root)) {
        return root;
    }

    for (T child : getChildren.apply(root)) {
        T result = findWhere(child, predicate, getChildren);
        if (result != null) {
            return result;
        }
    }

    return null;
}

I'm guessing you're allowed to assume that your structure is a tree, and that there are no cycles in it. In other words, you're not going to run across a node which is its own descendant. If there is a possiblity that your graph contains cycles (that is, somewhere there is a node which is a descendant of itself), then you should maintain a Set<T> of the nodes that you have visited already, and pass it from one recursive call to the next. This is so that you can prevent your recursion from finishing up in an endless loop, and overflowing your stack.

If this case is possible, then you will need to write something like this.

public static <T> T findWhere(T root, Predicate<T> predicate, Function<T, Iterable<T>> getChildren) {
    return findWhere(root, predicate, getChildren, new HashSet<T>());
}

public static <T> T findWhere(T root, Predicate<T> predicate, Function<T, Iterable<T>> getChildren, Set<T> nodesVisited) {

    if (root == null) {
        return null;
    }

    boolean seeingThisNodeForTheFirstTime = nodesVisited.add(root);

    if (! seeingThisNodeForTheFirstTime) {
        return null;
    }

    if (predicate.test(root)) {
        return root;
    }

    for (T child : getChildren.apply(root)) {
        T result = findWhere(child, predicate, getChildren, nodesVisited);
        if (result != null) {
            return result;
        }
    }

    return null;            
}