KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > avalon > phoenix > components > application > DependencyGraph


1 /*
2  * Copyright (C) The Apache Software Foundation. All rights reserved.
3  *
4  * This software is published under the terms of the Apache Software License
5  * version 1.1, a copy of which has been included with this distribution in
6  * the LICENSE.txt file.
7  */
8 package org.apache.avalon.phoenix.components.application;
9
10 import java.util.ArrayList JavaDoc;
11 import org.apache.avalon.phoenix.metadata.BlockMetaData;
12 import org.apache.avalon.phoenix.metadata.DependencyMetaData;
13 import org.apache.avalon.phoenix.metainfo.DependencyDescriptor;
14
15 /**
16  *
17  *
18  * @author <a HREF="mailto:peter at apache.org">Peter Donald</a>
19  */
20 class DependencyGraph
21 {
22     ///Private constructor to block instantiation
23 private DependencyGraph()
24     {
25     }
26
27     /**
28      * Method to generate an ordering of nodes to traverse.
29      * It is expected that the specified Blocks have passed
30      * verification tests and are well formed.
31      *
32      * @param forward true if forward dependencys traced, false if dependencies reversed
33      * @param blocks the blocks to traverse
34      * @return the ordered node names
35      */
36     public static String JavaDoc[] walkGraph( final boolean forward, final BlockMetaData[] blocks )
37     {
38         final ArrayList JavaDoc result = new ArrayList JavaDoc();
39
40         //temporary storage to record those
41 //that are already traversed
42 final ArrayList JavaDoc done = new ArrayList JavaDoc();
43
44         for( int i = 0; i < blocks.length; i++ )
45         {
46             visitBlock( blocks[ i ], blocks, forward, done, result );
47         }
48
49         return (String JavaDoc[])result.toArray( new String JavaDoc[ 0 ] );
50     }
51
52     private static void visitBlock( final BlockMetaData block,
53                                     final BlockMetaData[] blocks,
54                                     final boolean forward,
55                                     final ArrayList JavaDoc done,
56                                     final ArrayList JavaDoc order )
57     {
58         //If already visited this block then bug out early
59 final String JavaDoc name = block.getName();
60         if( done.contains( name ) )
61         {
62             return;
63         }
64         done.add( name );
65
66         if( forward )
67         {
68             visitDependencies( block, blocks, done, order );
69         }
70         else
71         {
72             visitReverseDependencies( block, blocks, done, order );
73         }
74
75         order.add( name );
76     }
77
78     /**
79      * Traverse dependencies of specified block.
80      *
81      * @param block the BlockMetaData
82      */
83     private static void visitDependencies( final BlockMetaData block,
84                                            final BlockMetaData[] blocks,
85                                            final ArrayList JavaDoc done,
86                                            final ArrayList JavaDoc order )
87     {
88         final DependencyDescriptor[] descriptors = block.getBlockInfo().getDependencies();
89         for( int i = 0; i < descriptors.length; i++ )
90         {
91             final DependencyMetaData dependency = block.getDependency( descriptors[ i ].getRole() );
92             final BlockMetaData other = getBlock( dependency.getName(), blocks );
93             visitBlock( other, blocks, true, done, order );
94         }
95     }
96
97     /**
98      * Traverse all reverse dependencies of specified block.
99      * A reverse dependency are those that dependend on block.
100      *
101      * @param block the BlockMetaData
102      */
103     private static void visitReverseDependencies( final BlockMetaData block,
104                                                   final BlockMetaData[] blocks,
105                                                   final ArrayList JavaDoc done,
106                                                   final ArrayList JavaDoc order )
107     {
108         final String JavaDoc name = block.getName();
109
110         for( int i = 0; i < blocks.length; i++ )
111         {
112             final BlockMetaData other = blocks[ i ];
113             final DependencyMetaData[] roles = other.getDependencies();
114
115             for( int j = 0; j < roles.length; j++ )
116             {
117                 final String JavaDoc depends = roles[ j ].getName();
118                 if( depends.equals( name ) )
119                 {
120                     visitBlock( other, blocks, false, done, order );
121                 }
122             }
123         }
124     }
125
126     /**
127      * Utility method to get block with specified name from specified array.
128      *
129      * @param name the name of block
130      * @param blocks the Block array
131      * @return the Block
132      */
133     private static BlockMetaData getBlock( final String JavaDoc name, final BlockMetaData[] blocks )
134     {
135         for( int i = 0; i < blocks.length; i++ )
136         {
137             if( blocks[ i ].getName().equals( name ) )
138             {
139                 return blocks[ i ];
140             }
141         }
142
143         //Should never happen if Verifier passed checks
144 throw new IllegalStateException JavaDoc();
145     }
146 }
147
Popular Tags