avalon-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dona...@apache.org
Subject cvs commit: jakarta-avalon-excalibur/containerkit/src/java/org/apache/excalibur/containerkit/kernel DependencyGraph.java
Date Tue, 18 Jun 2002 07:34:19 GMT
donaldp     2002/06/18 00:34:18

  Added:       containerkit/src/java/org/apache/excalibur/containerkit/dependency
                        DependencyGraph.java
  Removed:     containerkit/src/java/org/apache/excalibur/containerkit/kernel
                        DependencyGraph.java
  Log:
  Move dependencyGraph object to new package
  
  Revision  Changes    Path
  1.1                  jakarta-avalon-excalibur/containerkit/src/java/org/apache/excalibur/containerkit/dependency/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.dependency;
  
  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:peter@apache.org">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.getProviderName(), 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 ].getProviderName();
                  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:avalon-cvs-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:avalon-cvs-help@jakarta.apache.org>


Mime
View raw message