KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > codehaus > loom > components > application > DependencyGraph


1 /* ====================================================================
2  * Loom Software License, version 1.1
3  *
4  * Copyright (c) 2003, Loom Group. All rights reserved.
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  * notice, this list of conditions and the following disclaimer in
14  * the documentation and/or other materials provided with the
15  * distribution.
16  *
17  * 3. Neither the name of the Loom Group nor the name "Loom" nor
18  * the names of its contributors may be used to endorse or promote
19  * products derived from this software without specific prior
20  * written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * ====================================================================
36  *
37  * Loom includes code from the Apache Software Foundation
38  *
39  * ====================================================================
40  * The Apache Software License, Version 1.1
41  *
42  * Copyright (c) 1997-2003 The Apache Software Foundation. All rights
43  * reserved.
44  *
45  * Redistribution and use in source and binary forms, with or without
46  * modification, are permitted provided that the following conditions
47  * are met:
48  *
49  * 1. Redistributions of source code must retain the above copyright
50  * notice, this list of conditions and the following disclaimer.
51  *
52  * 2. Redistributions in binary form must reproduce the above copyright
53  * notice, this list of conditions and the following disclaimer in
54  * the documentation and/or other materials provided with the
55  * distribution.
56  *
57  * 3. The end-user documentation included with the redistribution,
58  * if any, must include the following acknowledgment:
59  * "This product includes software developed by the
60  * Apache Software Foundation (http://www.apache.org/)."
61  * Alternately, this acknowledgment may appear in the software
62  * itself, if and wherever such third-party acknowledgments
63  * normally appear.
64  *
65  * 4. The names "Jakarta", "Avalon", and "Apache Software Foundation"
66  * must not be used to endorse or promote products derived from this
67  * software without prior written permission. For written
68  * permission, please contact apache@apache.org.
69  *
70  * 5. Products derived from this software may not be called "Apache",
71  * nor may "Apache" appear in their name, without prior written
72  * permission of the Apache Software Foundation.
73  *
74  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
75  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
76  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
77  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
78  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
79  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
80  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
81  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
82  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
83  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
84  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
85  * SUCH DAMAGE.
86  */

87 package org.codehaus.loom.components.application;
88
89 import java.util.ArrayList JavaDoc;
90
91 import org.codehaus.loom.components.util.info.DependencyDescriptor;
92 import org.codehaus.loom.components.util.metadata.DependencyDirective;
93 import org.codehaus.loom.components.util.profile.ComponentProfile;
94
95 /**
96  * @author Peter Donald
97  */

98 class DependencyGraph
99 {
100     ///Private constructor to block instantiation
101
private DependencyGraph()
102     {
103     }
104
105     /**
106      * Method to generate an ordering of nodes to traverse. It is expected that
107      * the specified Blocks have passed verification tests and are well formed.
108      *
109      * @param forward true if forward dependencys traced, false if dependencies
110      * reversed
111      * @param blocks the blocks to traverse
112      * @return the ordered node names
113      */

114     public static String JavaDoc[] walkGraph( final boolean forward,
115                                       final ComponentProfile[] blocks )
116     {
117         final ArrayList JavaDoc result = new ArrayList JavaDoc();
118
119         //temporary storage to record those
120
//that are already traversed
121
final ArrayList JavaDoc done = new ArrayList JavaDoc();
122
123         for( int i = 0; i < blocks.length; i++ )
124         {
125             visitBlock( blocks[ i ], blocks, forward, done, result );
126         }
127
128         return (String JavaDoc[])result.toArray( new String JavaDoc[ 0 ] );
129     }
130
131     private static void visitBlock( final ComponentProfile block,
132                                     final ComponentProfile[] blocks,
133                                     final boolean forward,
134                                     final ArrayList JavaDoc done,
135                                     final ArrayList JavaDoc order )
136     {
137         //If already visited this block then bug out early
138
final String JavaDoc name = block.getTemplate().getName();
139         if( done.contains( name ) )
140         {
141             return;
142         }
143         done.add( name );
144
145         if( forward )
146         {
147             visitDependencies( block, blocks, done, order );
148         }
149         else
150         {
151             visitReverseDependencies( block, blocks, done, order );
152         }
153
154         order.add( name );
155     }
156
157     /**
158      * Traverse dependencies of specified block.
159      *
160      * @param block the BlockMetaData
161      */

162     private static void visitDependencies( final ComponentProfile block,
163                                            final ComponentProfile[] blocks,
164                                            final ArrayList JavaDoc done,
165                                            final ArrayList JavaDoc order )
166     {
167         final DependencyDescriptor[] descriptors = block.getInfo()
168             .getDependencies();
169         for( int i = 0; i < descriptors.length; i++ )
170         {
171             final String JavaDoc key = descriptors[ i ].getKey();
172             final DependencyDirective[] dependencySet = block.getTemplate()
173                 .getDependencies( key );
174             for( int j = 0; j < dependencySet.length; j++ )
175             {
176                 final DependencyDirective dependency = dependencySet[ j ];
177                 final ComponentProfile other = getBlock(
178                     dependency.getProviderName(), blocks );
179                 visitBlock( other, blocks, true, done, order );
180             }
181         }
182     }
183
184     /**
185      * Traverse all reverse dependencies of specified block. A reverse
186      * dependency are those that dependend on block.
187      *
188      * @param block the ComponentProfile
189      */

190     private static void visitReverseDependencies( final ComponentProfile block,
191                                                   final ComponentProfile[] blocks,
192                                                   final ArrayList JavaDoc done,
193                                                   final ArrayList JavaDoc order )
194     {
195         final String JavaDoc name = block.getTemplate().getName();
196
197         for( int i = 0; i < blocks.length; i++ )
198         {
199             final ComponentProfile other = blocks[ i ];
200             final DependencyDirective[] roles = other.getTemplate()
201                 .getDependencies();
202
203             for( int j = 0; j < roles.length; j++ )
204             {
205                 final String JavaDoc depends = roles[ j ].getProviderName();
206                 if( depends.equals( name ) )
207                 {
208                     visitBlock( other, blocks, false, done, order );
209                 }
210             }
211         }
212     }
213
214     /**
215      * Utility method to get block with specified name from specified array.
216      *
217      * @param name the name of block
218      * @param blocks the Block array
219      * @return the Block
220      */

221     private static ComponentProfile getBlock( final String JavaDoc name,
222                                               final ComponentProfile[] blocks )
223     {
224         for( int i = 0; i < blocks.length; i++ )
225         {
226             if( blocks[ i ].getTemplate().getName().equals( name ) )
227             {
228                 return blocks[ i ];
229             }
230         }
231
232         //Should never happen if Verifier passed checks
233
throw new IllegalStateException JavaDoc();
234     }
235 }
236
Popular Tags