KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > hivemind > order > Orderer


1 // Copyright 2004, 2005 The Apache Software Foundation
2
//
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 implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15 package org.apache.hivemind.order;
16
17 import java.util.ArrayList JavaDoc;
18 import java.util.Collections JavaDoc;
19 import java.util.HashMap JavaDoc;
20 import java.util.Iterator JavaDoc;
21 import java.util.List JavaDoc;
22 import java.util.Map JavaDoc;
23
24 import org.apache.commons.logging.Log;
25 import org.apache.commons.logging.LogFactory;
26 import org.apache.hivemind.ApplicationRuntimeException;
27 import org.apache.hivemind.ErrorHandler;
28 import org.apache.hivemind.ErrorLog;
29 import org.apache.hivemind.HiveMind;
30 import org.apache.hivemind.impl.ErrorLogImpl;
31 import org.apache.hivemind.util.Defense;
32 import org.apache.hivemind.util.StringUtils;
33
34 /**
35  * Used to order objects into an "execution" order. Each object must have a name. It may specify a
36  * list of pre-requisites and a list of post-requisites.
37  *
38  * @author Howard Lewis Ship
39  */

40 public class Orderer
41 {
42     private final ErrorLog _errorLog;
43
44     private final String JavaDoc _objectType;
45
46     private List JavaDoc _orderingsList = null;
47
48     private Map JavaDoc _orderingsMap = null;
49
50     private Map JavaDoc _nodeMap = null;
51
52     private Node _leader;
53
54     private Node _trailer;
55
56     /**
57      * Creates an instance using <code>org.apache.hivemind.order.Orderer</code> as the Log.
58      */

59     public Orderer(ErrorHandler errorHandler, String JavaDoc objectType)
60     {
61         this(LogFactory.getLog(Orderer.class), errorHandler, objectType);
62     }
63
64     /**
65      * Creates a new instance, but directs all debug and error logging output to the provided log.
66      *
67      * @param log
68      * Used for logging any errors
69      * @param objectType
70      * user presentable name for the type of object to be ordered; used in some error
71      * messages
72      */

73     public Orderer(Log log, ErrorHandler errorHandler, String JavaDoc objectType)
74     {
75         this(new ErrorLogImpl(errorHandler, log), objectType);
76     }
77
78     /**
79      * Creates a new instance.
80      *
81      * @param errorLog
82      * Used for log any recoverable errors.
83      * @param objectType
84      * user presentable name for the type of object to be ordered; used in some error
85      * messages
86      */

87     public Orderer(ErrorLog errorLog, String JavaDoc objectType)
88     {
89         Defense.notNull(errorLog, "errorLog");
90         Defense.notNull(objectType, "objectType");
91
92         _errorLog = errorLog;
93         _objectType = objectType;
94     }
95
96     /**
97      * Adds a new object. All invocations of {@link #add(Object, String, String, String)} should
98      * occur before invoking {@link #getOrderedObjects()}.
99      *
100      * @param object
101      * an object to be sorted into order based on prereqs and postreqs
102      * @param name
103      * a unique name for the
104      * @param prereqs
105      * a comma-separated list of the names of objects that should precede this object in
106      * the list (or null)
107      * @param postreqs
108      * a comma-separated list of the names of objects that should follow this object in
109      * the list (or null)
110      */

111     public void add(Object JavaDoc object, String JavaDoc name, String JavaDoc prereqs, String JavaDoc postreqs)
112     {
113         if (_orderingsMap == null)
114         {
115             _orderingsMap = new HashMap JavaDoc();
116             _orderingsList = new ArrayList JavaDoc();
117         }
118
119         ObjectOrdering o = getOrderable(name);
120
121         if (o != null)
122         {
123             _errorLog.error(
124                     OrdererMessages.duplicateName(_objectType, name, object, o.getObject()),
125                     HiveMind.getLocation(object),
126                     null);
127
128             return;
129         }
130
131         o = new ObjectOrdering(object, name, prereqs, postreqs);
132
133         _orderingsMap.put(name, o);
134         _orderingsList.add(o);
135     }
136
137     private ObjectOrdering getOrderable(String JavaDoc name)
138     {
139         return (ObjectOrdering) _orderingsMap.get(name);
140     }
141
142     /**
143      * Uses the information provided by {@link #add(Object, String, String, String)} to order the
144      * objects into an appropriate order based on the pre- and post-reqts provided. Errors such as
145      * cyclic dependencies or unrecognized names are logged and ignored.
146      */

147     public List JavaDoc getOrderedObjects()
148     {
149         if (_orderingsMap == null)
150             return Collections.EMPTY_LIST;
151
152         try
153         {
154             _nodeMap = new HashMap JavaDoc();
155
156             initializeGraph();
157
158             return _trailer.getOrder();
159         }
160         finally
161         {
162             _nodeMap = null;
163             _leader = null;
164             _trailer = null;
165         }
166     }
167
168     private void initializeGraph()
169     {
170         addNodes();
171
172         if (_leader == null)
173             _leader = new Node(null, "*-leader-*");
174
175         if (_trailer == null)
176             _trailer = new Node(null, "*-trailer-*");
177
178         addDependencies();
179     }
180
181     private Node getNode(String JavaDoc name)
182     {
183         return (Node) _nodeMap.get(getOrderable(name));
184     }
185
186     private void addNodes()
187     {
188         Iterator JavaDoc i = _orderingsList.iterator();
189
190         while (i.hasNext())
191         {
192             ObjectOrdering o = (ObjectOrdering) i.next();
193
194             Node node = new Node(o.getObject(), o.getName());
195
196             _nodeMap.put(o, node);
197
198             if ("*".equals(o.getPostreqs()))
199             {
200                 if (_leader == null)
201                     _leader = node;
202                 else
203                     _errorLog.error(OrdererMessages.dupeLeader(_objectType, o, getOrderable(_leader
204                             .getName())), HiveMind.getLocation(o.getObject()), null);
205             }
206
207             if ("*".equals(o.getPrereqs()))
208             {
209                 if (_trailer == null)
210                     _trailer = node;
211                 else
212                     _errorLog.error(
213                             OrdererMessages.dupeTrailer(_objectType, o, getOrderable(_trailer
214                                     .getName())),
215                             HiveMind.getLocation(o.getObject()),
216                             null);
217             }
218
219         }
220     }
221
222     private void addDependencies()
223     {
224         Iterator JavaDoc i = _orderingsList.iterator();
225
226         while (i.hasNext())
227         {
228             ObjectOrdering o = (ObjectOrdering) i.next();
229
230             addDependencies(o, getNode(o.getName()));
231         }
232     }
233
234     private void addDependencies(ObjectOrdering orderable, Node node)
235     {
236         addPreRequisites(orderable, node);
237         addPostRequisites(orderable, node);
238
239         try
240         {
241             if (node != _leader)
242                 node.addDependency(_leader);
243
244             if (node != _trailer)
245                 _trailer.addDependency(node);
246         }
247         catch (ApplicationRuntimeException ex)
248         {
249             // This code is unreachable ... but nonetheless.
250

251             String JavaDoc name = node.getName();
252             ObjectOrdering trigger = getOrderable(name);
253
254             _errorLog.error(OrdererMessages.dependencyCycle(_objectType, orderable, ex), HiveMind
255                     .getLocation(trigger.getObject()), ex);
256         }
257     }
258
259     private void addPreRequisites(ObjectOrdering ordering, Node node)
260     {
261         String JavaDoc prereqs = ordering.getPrereqs();
262
263         if ("*".equals(prereqs))
264             return;
265
266         String JavaDoc[] names = StringUtils.split(prereqs);
267
268         for (int i = 0; i < names.length; i++)
269         {
270             String JavaDoc prename = names[i];
271
272             Node prenode = getNode(prename);
273
274             if (prenode == null)
275             {
276                 _errorLog.error(
277                         OrdererMessages.badDependency(_objectType, prename, ordering),
278                         HiveMind.getLocation(ordering.getObject()),
279                         null);
280                 continue;
281             }
282
283             try
284             {
285                 node.addDependency(prenode);
286             }
287             catch (ApplicationRuntimeException ex)
288             {
289                 _errorLog.error(
290                         OrdererMessages.dependencyCycle(_objectType, ordering, ex),
291                         HiveMind.getLocation(ordering.getObject()),
292                         ex);
293             }
294
295         }
296     }
297
298     private void addPostRequisites(ObjectOrdering ordering, Node node)
299     {
300         String JavaDoc postreqs = ordering.getPostreqs();
301
302         if ("*".equals(postreqs))
303             return;
304
305         String JavaDoc[] names = StringUtils.split(postreqs);
306
307         for (int i = 0; i < names.length; i++)
308         {
309             String JavaDoc postname = names[i];
310
311             Node postnode = getNode(postname);
312
313             if (postnode == null)
314             {
315                 _errorLog.error(
316                         OrdererMessages.badDependency(_objectType, postname, ordering),
317                         HiveMind.getLocation(ordering.getObject()),
318                         null);
319             }
320             else
321             {
322                 try
323                 {
324                     postnode.addDependency(node);
325                 }
326                 catch (ApplicationRuntimeException ex)
327                 {
328                     _errorLog.error(
329                             OrdererMessages.dependencyCycle(_objectType, ordering, ex),
330                             HiveMind.getLocation(ordering.getObject()),
331                             ex);
332                 }
333             }
334         }
335     }
336
337     private static class Node
338     {
339         private Object JavaDoc _object;
340
341         private String JavaDoc _name;
342
343         private List JavaDoc _dependencies;
344
345         public Node(Object JavaDoc o, String JavaDoc name)
346         {
347             _object = o;
348             _name = name;
349             _dependencies = new ArrayList JavaDoc();
350         }
351
352         public String JavaDoc getName()
353         {
354             return _name;
355         }
356
357         public void addDependency(Node n)
358         {
359             if (n.isReachable(this))
360                 throw new ApplicationRuntimeException(
361                         "A cycle has been detected from the initial object [" + _name + "]",
362                         HiveMind.getLocation(_object), null);
363
364             _dependencies.add(n);
365         }
366
367         private boolean isReachable(Node n)
368         {
369             boolean reachable = (n == this);
370             Iterator JavaDoc i = _dependencies.iterator();
371
372             while (i.hasNext() && !reachable)
373             {
374                 Node dep = (Node) i.next();
375                 reachable = (dep == n) ? true : dep.isReachable(n);
376             }
377
378             return reachable;
379         }
380
381         public List JavaDoc getOrder()
382         {
383             List JavaDoc result = new ArrayList JavaDoc();
384             fillOrder(result);
385
386             return result;
387         }
388
389         private void fillOrder(List JavaDoc result)
390         {
391             if (result.contains(_object))
392                 return;
393
394             Iterator JavaDoc i = _dependencies.iterator();
395
396             while (i.hasNext())
397             {
398                 Node dep = (Node) i.next();
399                 dep.fillOrder(result);
400             }
401
402             if (_object != null)
403                 result.add(_object);
404         }
405     }
406
407 }
Popular Tags