impl/src/main/java/org/apache/myfaces/config/util/Vertex.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.myfaces.config.util;

import java.util.ArrayList;
import java.util.List;

/**
 * Vertex is used to track dependencies and each node in a graph.  Typical
 * uses would be to ensure components are started up and torn down in the
 * proper order, or bundles were loaded and unloaded in the proper order, etc.
 *
 * @author <a href="mailto:dev@avalon.apache.org">Avalon Development Team</a>
 * @version CVS $ Revision: 1.1 $
 */
public final class Vertex<T> implements Comparable<Vertex<T>>
{
    private final String m_name;
    private final T m_node;
    private int m_order;

    /** Flag used to keep track of whether or not a given vertex has been
     *   seen by the resolveOrder methods. */
    private boolean m_seen;

    /** List of all direct dependent Vertices. */
    private final List< Vertex<T> > m_dependencies;

    /**
     * A vertex wraps a node, which can be anything.
     *
     * @param node  The wrapped node.
     */
    public Vertex(final T node)
    {
        this(node.toString(), node);
    }

    /**
     * A vertex wraps a node, which can be anything.
     *
     * @param name  A name for the node which will be used to produce useful errors.
     * @param node  The wrapped node.
     */
    public Vertex(final String name, final T node)
    {
        m_name = name;
        m_node = node;
        m_dependencies = new ArrayList< Vertex<T> >();
        reset();
    }

    /**
     * Reset the Vertex so that all the flags and runtime states are set back
     * to the original values.
     */
    public void reset()
    {
        m_order = 0;
        m_seen = false;
    }

    /**
     * Returns the name of the Vertex.
     *
     * @return The name of the Vertex.
     */
    public String getName()
    {
        return m_name;
    }

    /**
     * Get the wrapped node that this Vertex represents.
     *
     * @return the node
     */
    public T getNode()
    {
        return m_node;
    }

    /**
     * Add a dependecy to this Vertex.  The Vertex that this one depends on will
     * be marked as referenced and then added to the list of dependencies.  The
     * list is checked before the dependency is added.
     *
     * @param v  The vertex we depend on.
     */
    public void addDependency(Vertex<T> v)
    {
        if (!m_dependencies.contains(v))
        {
            m_dependencies.add(v);
        }
    }

    /**
     * Recurse through the tree from this vertex assigning an order to each
     *  and at the same time checking for any cyclic dependencies.
     *
     * @throws CyclicDependencyException If a cyclic dependency is discovered.
     */
    public void resolveOrder() throws CyclicDependencyException
    {
        resolveOrder(getName());
    }

    /**
     * Recursively searches for cycles by travelling down the dependency lists
     *  of this vertex, looking for the start vertex.
     *
     * @param path The path to the Vertex.  It is worth the load as it makes a
     *             descriptive error message possible.
     *
     * @return The highest order of any of the dependent vertices.
     *
     * @throws CyclicDependencyException If a cyclic dependency is discovered.
     */
    private int resolveOrder(String path) throws CyclicDependencyException
    {
        m_seen = true;
        try
        {
            int highOrder = -1;
            for (Vertex<T> dv : m_dependencies)
            {
                if (dv.m_seen)
                {
                    throw new CyclicDependencyException(path + " -> "
                            + dv.getName());
                }
                else
                {
                    highOrder = Math.max(highOrder, dv.resolveOrder(path
                            + " -> " + dv.getName()));
                }
            }

            // Set this order so it is one higher than the highest dependency.
            m_order = highOrder + 1;
            return m_order;
        }
        finally
        {
            m_seen = false;
        }
    }

    /**
     * Get the list of dependencies.
     *
     * @return  The list of dependencies.
     */
    public List< Vertex<T> > getDependencies()
    {
        return m_dependencies;
    }

    /**
     * Used in the sort algorithm to sort all the Vertices so that they respect
     * the ordinal they were given during the topological sort.
     *
     * @param o  The other Vertex to compare with
     * @return -1 if this &lt; o, 0 if this == o, or 1 if this &gt; o
     */
    public int compareTo(final Vertex<T> o)
    {
        int orderInd;

        if (m_order < o.m_order)
        {
            orderInd = -1;
        }
        else if (m_order > o.m_order)
        {
            orderInd = 1;
        }
        else
        {
            orderInd = 0;
        }

        return orderInd;
    }

    /**
     * Get the ordinal for this vertex.
     *
     * @return  the order.
     */
    public int getOrder()
    {
        return m_order;
    }
}