donaldp 2002/06/14 00:31:12
Added: containerkit/src/java/org/apache/excalibur/containerkit/kernel
DependencyGraph.java
Log:
Add utility class that generates a list of
dependencies created by preorder traversal of
dependency tree.
Revision Changes Path
1.1
jakarta-avalon-excalibur/containerkit/src/java/org/apache/excalibur/containerkit/kernel/DependencyGraph.java
Index: DependencyGraph.java
===================================================================
/*
* Copyright (C) The Apache Software Foundation. All rights reserved.
*
* This software is published under the terms of the Apache Software License
* version 1.1, a copy of which has been included with this distribution in
* the LICENSE.txt file.
*/
package org.apache.excalibur.containerkit.kernel;
import java.util.ArrayList;
import org.apache.excalibur.containerkit.metadata.ComponentMetaData;
import org.apache.excalibur.containerkit.metadata.DependencyMetaData;
import org.apache.excalibur.containerkit.metainfo.DependencyDescriptor;
/**
* This is a utility class to generate an ordered list of meta
* data. The order represents the order in which the components
* represented by metadata should be instantiated.
*
* <p>If all of the MetaData object explicitly represent their
* dependencies then the list generated is the result of a
* preorder traversal of the dependency tree.</p>
*
* <p><b>Note that the following behaviour is no longer
* supported</b></p>
*
* <p>If some of the MetaData in the dependency tree does not
* define dependencies then those components are placed in the
* list as late as possible. In effect this means that the dependency
* is processed multiple times. The first pass collects all nodes
* that fully specify dependencies. As soon as a node is encountered
* that does not specify dependencies then that node and all parent
* nodes are excluded from first pass. The second pass then collects
* the remaining nodes after a preorder traversal of dependency tree.</p>
*
* @author <a href="mailto:[EMAIL PROTECTED]">Peter Donald</a>
*/
public class DependencyGraph
{
///Private constructor to component instantiation
private DependencyGraph()
{
}
/**
* Method to generate an ordering of nodes to traverse.
* It is expected that the specified components have passed
* verification tests and are well formed.
*
* @param forward true if forward dependencys traced, false if
dependencies reversed
* @param components the components to traverse
* @return the ordered node names
*/
public static String[] walkGraph( final boolean forward,
final ComponentMetaData[] components )
{
final ArrayList result = new ArrayList();
//temporary storage to record those
//that are already traversed
final ArrayList done = new ArrayList();
for( int i = 0; i < components.length; i++ )
{
visitcomponent( components[ i ], components, forward, done,
result );
}
return (String[])result.toArray( new String[ 0 ] );
}
private static void visitcomponent( final ComponentMetaData component,
final ComponentMetaData[] components,
final boolean forward,
final ArrayList done,
final ArrayList order )
{
//If already visited this component then bug out early
final String name = component.getName();
if( done.contains( name ) )
{
return;
}
done.add( name );
if( forward )
{
visitDependencies( component, components, done, order );
}
else
{
visitReverseDependencies( component, components, done, order );
}
order.add( name );
}
/**
* Traverse dependencies of specified component.
*
* @param component the ComponentMetaData
*/
private static void visitDependencies( final ComponentMetaData component,
final ComponentMetaData[]
components,
final ArrayList done,
final ArrayList order )
{
final DependencyDescriptor[] descriptors =
component.getComponentInfo().getDependencies();
for( int i = 0; i < descriptors.length; i++ )
{
final DependencyMetaData dependency =
component.getDependency( descriptors[ i ].getRole() );
final ComponentMetaData other =
getComponent( dependency.getName(), components );
visitcomponent( other, components, true, done, order );
}
}
/**
* Traverse all reverse dependencies of specified component.
* A reverse dependency are those that dependend on component.
*
* @param component the ComponentMetaData
*/
private static void visitReverseDependencies( final ComponentMetaData
component,
final ComponentMetaData[]
components,
final ArrayList done,
final ArrayList order )
{
final String name = component.getName();
for( int i = 0; i < components.length; i++ )
{
final ComponentMetaData other = components[ i ];
final DependencyMetaData[] roles = other.getDependencies();
if( null == roles )
{
continue;
}
for( int j = 0; j < roles.length; j++ )
{
final String depends = roles[ j ].getName();
if( depends.equals( name ) )
{
visitcomponent( other, components, false, done, order );
}
}
}
}
/**
* Utility method to get component with specified name from specified
array.
*
* @param name the name of component
* @param components the component array
* @return the component
*/
private static ComponentMetaData getComponent( final String name,
final ComponentMetaData[]
components )
{
for( int i = 0; i < components.length; i++ )
{
if( components[ i ].getName().equals( name ) )
{
return components[ i ];
}
}
//Should never happen if Verifier passed checks
throw new IllegalStateException();
}
}
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
