/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.

 *

 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.

 *

 * The contents of this file are subject to the terms of either the GNU

 * General Public License Version 2 only ("GPL") or the Common

 * Development and Distribution License("CDDL") (collectively, the

 * "License"). You may not use this file except in compliance with the

 * License. You can obtain a copy of the License at

 * http://www.netbeans.org/cddl-gplv2.html

 * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the

 * specific language governing permissions and limitations under the

 * License.  When distributing the software, include this License Header

 * Notice in each file and include the License file at

 * nbbuild/licenses/CDDL-GPL-2-CP.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the GPL Version 2 section of the License file that

 * accompanied this code. If applicable, add the following below the

 * License Header, with the fields enclosed by brackets [] replaced by

 * your own identifying information:

 * "Portions Copyrighted [year] [name of copyright owner]"

 *

 * If you wish your version of this file to be governed by only the CDDL

 * or only the GPL Version 2, indicate your decision by adding

 * "[Contributor] elects to include this software in this distribution

 * under the [CDDL or GPL Version 2] license." If you do not indicate a

 * single choice of license, a recipient has the option to distribute

 * your version of this file under either the CDDL, the GPL Version 2 or

 * to extend the choice of license to its licensees as provided above.

 * However, if you add GPL Version 2 code and therefore, elected the GPL

 * Version 2 license, then the option applies only if the new code is

 * made subject to such option by the copyright holder.

 *

 * Contributor(s):

 *

 * Portions Copyrighted 2009 Sun Microsystems, Inc.

 */

package org.openide.nodes;

import java.util.logging.Logger;

import org.openide.util.Lookup;

import org.openide.util.Parameters;

/**

 * Tool for finding nodes within a subtree based on content.

 * One or more implementations may be placed in the {@linkplain Node#getLookup lookup}

 * of a node, in which case it knows where to find the node representing an object.

 * @see NodeOp#createPath

 */

public abstract class NodeFinder {

    private static final Logger LOG = Logger.getLogger(NodeFinder.class.getName());

    /**

     * Simple finder implementation which just searches children recursively.

     * The first child of {@linkplain Children#getNodes(boolean) getNodes(true)}

     * in which the item can be found is returned, else null.

     * Useful for "heterogeneous" parent nodes which have assorted children any

     * of which might contain the item, such as a project's root node.

     */

    public static final NodeFinder NAIVE = new NodeFinder() {

        public Node findNode(Node root, Object item) {

            for (Node child : root.getChildren().getNodes(true)) {

                Node n = findOrNull(child, item);

                if (n != null) {

                    return n;

                }

            }

            return null;

        }

    };

    /** No-op constructor for implementations. */

    protected NodeFinder() {}

    /**

     * Attempts to locate a child of this node containing a given item in its lookup.

     * @param root a root node to begin the search on; this may be the node in

     *             whose lookup the finder was placed, or a {@link FilterNode}

     *             or similar derivative of that node; also permits a singleton finder

     *             instance to be placed in the lookup of a whole class of nodes

     * @param item an object expected to be found in the lookup of some descendant of {@code root}

     * @return a (strict) descendant of {@code root} which either contains {@code item}

     *         in its {@linkplain Node#getLookup lookup}, or which is known to be

     *         the ancestor of a node which does; or {@code null} if nothing is

     *         known about the location of this particular item or class of item

     *         underneath the given root

     */

    public abstract Node findNode(Node root, Object item);

    /**

     * Attempts to locate a child node containing a given item in its lookup.

     * The algorithm is as follows:

     * <ol>

     * <li>If the root node contains the object, that is returned.

     * <li>If some finder present on the root node returns a real node,

     *     that is searched recursively and a result is returned if found.

     * <li>Otherwise, null is returned.

     * </ol>

     * @param root a root node to begin the search on

     * @param item an object expected to be found in the lookup of some descendant of the root node

     * @return a descendant of {@code root} (or the root itself) which contains {@code item}

     *         in its {@linkplain Node#getLookup lookup}; or {@code null} if none could be found

     */

    public static Node findOrNull(Node root, Object item) {

        Parameters.notNull("root", root);

        Parameters.notNull("item", item);

        if (contains(root, item)) {

            return root;

        }

        for (NodeFinder finder : root.getLookup().lookupAll(NodeFinder.class)) {

            Node n = finder.findNode(root, item);

            if (n == Node.EMPTY) {

                return null;

            }

            if (n != null) {

                if (!isStrictAncestor(root, n)) {

                    LOG.warning(finder + " returned " + n + " which is not a strict descendant of " + root);

                    continue;

                }

                Node r = findOrNull(n, item);

                if (r != null) {

                    return r;

                } else {

                    LOG.warning(finder + " returned " + n + " which did not in fact contain any descendant with " + item);

                }

            }

        }

        return null;

    }

    private static boolean contains(Node n, Object item) {

        Object r = n.getLookup().lookup(new Lookup.Template<Object>(null, null, item));

        if (r == null) {

            return false;

        }

        if (!r.equals(item)) {

            LOG.warning("lookup of " + n + " claimed to find " + item + " but actually found " + r);

        }

        return true;

    }

    private static boolean isStrictAncestor(Node root, Node n) {

        Node p = n.getParentNode();

        return p != null && (p == root || isStrictAncestor(root, p));

    }

}