KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > avalon > fortress > util > dag > Vertex


1 /*
2  * Copyright 2003-2004 The Apache Software Foundation
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
12  * implied.
13  *
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17
18 package org.apache.avalon.fortress.util.dag;
19
20 import java.util.ArrayList JavaDoc;
21 import java.util.Iterator JavaDoc;
22 import java.util.List JavaDoc;
23
24 /**
25  * Vertex is used to track dependencies and each node in a graph. Typical
26  * uses would be to ensure components are started up and torn down in the
27  * proper order, or bundles were loaded and unloaded in the proper order, etc.
28  *
29  * @author <a HREF="mailto:dev@avalon.apache.org">Avalon Development Team</a>
30  * @version CVS $ Revision: 1.1 $
31  */
32 public final class Vertex implements Comparable JavaDoc
33 {
34     private final String JavaDoc m_name;
35     private final Object JavaDoc m_node;
36     private int m_order;
37     
38     /** Flag used to keep track of whether or not a given vertex has been
39      * seen by the resolveOrder methods. */
40     private boolean m_seen;
41     
42     /** List of all direct dependent Vertices. */
43     private final List JavaDoc m_dependencies;
44
45     /**
46      * A vertex wraps a node, which can be anything.
47      *
48      * @param node The wrapped node.
49      */
50     public Vertex( final Object JavaDoc node )
51     {
52         this( node.toString(), node );
53     }
54     
55     /**
56      * A vertex wraps a node, which can be anything.
57      *
58      * @param name A name for the node which will be used to produce useful errors.
59      * @param node The wrapped node.
60      */
61     public Vertex( final String JavaDoc name, final Object JavaDoc node )
62     {
63         m_name = name;
64         m_node = node;
65         m_dependencies = new ArrayList JavaDoc();
66         reset();
67     }
68
69     /**
70      * Reset the Vertex so that all the flags and runtime states are set back
71      * to the original values.
72      */
73     public void reset()
74     {
75         m_order = 0;
76         m_seen = false;
77     }
78     
79     /**
80      * Returns the name of the Vertex.
81      *
82      * @return The name of the Vertex.
83      */
84     public String JavaDoc getName()
85     {
86         return m_name;
87     }
88     
89     /**
90      * Get the wrapped node that this Vertex represents.
91      *
92      * @return the node
93      */
94     public Object JavaDoc getNode()
95     {
96         return m_node;
97     }
98
99     /**
100      * Add a dependecy to this Vertex. The Vertex that this one depends on will
101      * be marked as referenced and then added to the list of dependencies. The
102      * list is checked before the dependency is added.
103      *
104      * @param v The vertex we depend on.
105      */
106     public void addDependency( Vertex v )
107     {
108         if ( !m_dependencies.contains( v ) )
109         {
110             m_dependencies.add( v );
111         }
112     }
113     
114     
115     /**
116      * Recurse through the tree from this vertex assigning an order to each
117      * and at the same time checking for any cyclic dependencies.
118      *
119      * @throws CyclicDependencyException If a cyclic dependency is discovered.
120      */
121     public void resolveOrder()
122         throws CyclicDependencyException
123     {
124         resolveOrder( getName() );
125     }
126     
127     /**
128      * Recursively searches for cycles by travelling down the dependency lists
129      * of this vertex, looking for the start vertex.
130      *
131      * @param path The path to the Vertex. It is worth the load as it makes a
132      * descriptive error message possible.
133      *
134      * @return The highest order of any of the dependent vertices.
135      *
136      * @throws CyclicDependencyException If a cyclic dependency is discovered.
137      */
138     private int resolveOrder( String JavaDoc path )
139         throws CyclicDependencyException
140     {
141         m_seen = true;
142         try
143         {
144             int highOrder = -1;
145             for ( Iterator JavaDoc iter = m_dependencies.iterator(); iter.hasNext(); )
146             {
147                 Vertex dv = (Vertex)iter.next();
148                 if ( dv.m_seen )
149                 {
150                     throw new CyclicDependencyException( path + " -> " + dv.getName() );
151                 }
152                 else
153                 {
154                     highOrder = Math.max(
155                         highOrder, dv.resolveOrder( path + " -> " + dv.getName() ) );
156                 }
157             }
158             
159             // Set this order so it is one higher than the highest dependency.
160 m_order = highOrder + 1;
161             return m_order;
162         }
163         finally
164         {
165             m_seen = false;
166         }
167     }
168
169     /**
170      * Get the list of dependencies.
171      *
172      * @return The list of dependencies.
173      */
174     public List JavaDoc getDependencies()
175     {
176         return m_dependencies;
177     }
178
179     /**
180      * Used in the sort algorithm to sort all the Vertices so that they respect
181      * the ordinal they were given during the topological sort.
182      *
183      * @param o The other Vertex to compare with
184      * @return -1 if this < o, 0 if this == o, or 1 if this > o
185      */
186     public int compareTo( final Object JavaDoc o )
187     {
188         final Vertex other = (Vertex) o;
189         int orderInd;
190
191         if ( m_order < other.m_order )
192         {
193             orderInd = -1;
194         }
195         else if ( m_order > other.m_order )
196         {
197             orderInd = 1;
198         }
199         else
200         {
201             orderInd = 0;
202         }
203
204         return orderInd;
205     }
206
207     /**
208      * Get the ordinal for this vertex.
209      *
210      * @return the order.
211      */
212     public int getOrder()
213     {
214         return m_order;
215     }
216 }
217
Popular Tags