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