001: // Copyright 2004, 2005 The Apache Software Foundation
002: //
003: // Licensed under the Apache License, Version 2.0 (the "License");
004: // you may not use this file except in compliance with the License.
005: // You may obtain a copy of the License at
006: //
007: // http://www.apache.org/licenses/LICENSE-2.0
008: //
009: // Unless required by applicable law or agreed to in writing, software
010: // distributed under the License is distributed on an "AS IS" BASIS,
011: // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
012: // See the License for the specific language governing permissions and
013: // limitations under the License.
014:
015: package org.apache.hivemind.order;
016:
017: import java.util.ArrayList;
018: import java.util.Collections;
019: import java.util.HashMap;
020: import java.util.Iterator;
021: import java.util.List;
022: import java.util.Map;
023:
024: import org.apache.commons.logging.Log;
025: import org.apache.commons.logging.LogFactory;
026: import org.apache.hivemind.ApplicationRuntimeException;
027: import org.apache.hivemind.ErrorHandler;
028: import org.apache.hivemind.ErrorLog;
029: import org.apache.hivemind.HiveMind;
030: import org.apache.hivemind.impl.ErrorLogImpl;
031: import org.apache.hivemind.util.Defense;
032: import org.apache.hivemind.util.StringUtils;
033:
034: /**
035: * Used to order objects into an "execution" order. Each object must have a name. It may specify a
036: * list of pre-requisites and a list of post-requisites.
037: *
038: * @author Howard Lewis Ship
039: */
040: public class Orderer {
041: private final ErrorLog _errorLog;
042:
043: private final String _objectType;
044:
045: private List _orderingsList = null;
046:
047: private Map _orderingsMap = null;
048:
049: private Map _nodeMap = null;
050:
051: private Node _leader;
052:
053: private Node _trailer;
054:
055: /**
056: * Creates an instance using <code>org.apache.hivemind.order.Orderer</code> as the Log.
057: */
058: public Orderer(ErrorHandler errorHandler, String objectType) {
059: this (LogFactory.getLog(Orderer.class), errorHandler, objectType);
060: }
061:
062: /**
063: * Creates a new instance, but directs all debug and error logging output to the provided log.
064: *
065: * @param log
066: * Used for logging any errors
067: * @param objectType
068: * user presentable name for the type of object to be ordered; used in some error
069: * messages
070: */
071: public Orderer(Log log, ErrorHandler errorHandler, String objectType) {
072: this (new ErrorLogImpl(errorHandler, log), objectType);
073: }
074:
075: /**
076: * Creates a new instance.
077: *
078: * @param errorLog
079: * Used for log any recoverable errors.
080: * @param objectType
081: * user presentable name for the type of object to be ordered; used in some error
082: * messages
083: */
084: public Orderer(ErrorLog errorLog, String objectType) {
085: Defense.notNull(errorLog, "errorLog");
086: Defense.notNull(objectType, "objectType");
087:
088: _errorLog = errorLog;
089: _objectType = objectType;
090: }
091:
092: /**
093: * Adds a new object. All invocations of {@link #add(Object, String, String, String)} should
094: * occur before invoking {@link #getOrderedObjects()}.
095: *
096: * @param object
097: * an object to be sorted into order based on prereqs and postreqs
098: * @param name
099: * a unique name for the
100: * @param prereqs
101: * a comma-separated list of the names of objects that should precede this object in
102: * the list (or null)
103: * @param postreqs
104: * a comma-separated list of the names of objects that should follow this object in
105: * the list (or null)
106: */
107: public void add(Object object, String name, String prereqs,
108: String postreqs) {
109: if (_orderingsMap == null) {
110: _orderingsMap = new HashMap();
111: _orderingsList = new ArrayList();
112: }
113:
114: ObjectOrdering o = getOrderable(name);
115:
116: if (o != null) {
117: _errorLog.error(OrdererMessages.duplicateName(_objectType,
118: name, object, o.getObject()), HiveMind
119: .getLocation(object), null);
120:
121: return;
122: }
123:
124: o = new ObjectOrdering(object, name, prereqs, postreqs);
125:
126: _orderingsMap.put(name, o);
127: _orderingsList.add(o);
128: }
129:
130: private ObjectOrdering getOrderable(String name) {
131: return (ObjectOrdering) _orderingsMap.get(name);
132: }
133:
134: /**
135: * Uses the information provided by {@link #add(Object, String, String, String)} to order the
136: * objects into an appropriate order based on the pre- and post-reqts provided. Errors such as
137: * cyclic dependencies or unrecognized names are logged and ignored.
138: */
139: public List getOrderedObjects() {
140: if (_orderingsMap == null)
141: return Collections.EMPTY_LIST;
142:
143: try {
144: _nodeMap = new HashMap();
145:
146: initializeGraph();
147:
148: return _trailer.getOrder();
149: } finally {
150: _nodeMap = null;
151: _leader = null;
152: _trailer = null;
153: }
154: }
155:
156: private void initializeGraph() {
157: addNodes();
158:
159: if (_leader == null)
160: _leader = new Node(null, "*-leader-*");
161:
162: if (_trailer == null)
163: _trailer = new Node(null, "*-trailer-*");
164:
165: addDependencies();
166: }
167:
168: private Node getNode(String name) {
169: return (Node) _nodeMap.get(getOrderable(name));
170: }
171:
172: private void addNodes() {
173: Iterator i = _orderingsList.iterator();
174:
175: while (i.hasNext()) {
176: ObjectOrdering o = (ObjectOrdering) i.next();
177:
178: Node node = new Node(o.getObject(), o.getName());
179:
180: _nodeMap.put(o, node);
181:
182: if ("*".equals(o.getPostreqs())) {
183: if (_leader == null)
184: _leader = node;
185: else
186: _errorLog.error(OrdererMessages.dupeLeader(
187: _objectType, o, getOrderable(_leader
188: .getName())), HiveMind
189: .getLocation(o.getObject()), null);
190: }
191:
192: if ("*".equals(o.getPrereqs())) {
193: if (_trailer == null)
194: _trailer = node;
195: else
196: _errorLog.error(OrdererMessages.dupeTrailer(
197: _objectType, o, getOrderable(_trailer
198: .getName())), HiveMind
199: .getLocation(o.getObject()), null);
200: }
201:
202: }
203: }
204:
205: private void addDependencies() {
206: Iterator i = _orderingsList.iterator();
207:
208: while (i.hasNext()) {
209: ObjectOrdering o = (ObjectOrdering) i.next();
210:
211: addDependencies(o, getNode(o.getName()));
212: }
213: }
214:
215: private void addDependencies(ObjectOrdering orderable, Node node) {
216: addPreRequisites(orderable, node);
217: addPostRequisites(orderable, node);
218:
219: try {
220: if (node != _leader)
221: node.addDependency(_leader);
222:
223: if (node != _trailer)
224: _trailer.addDependency(node);
225: } catch (ApplicationRuntimeException ex) {
226: // This code is unreachable ... but nonetheless.
227:
228: String name = node.getName();
229: ObjectOrdering trigger = getOrderable(name);
230:
231: _errorLog.error(OrdererMessages.dependencyCycle(
232: _objectType, orderable, ex), HiveMind
233: .getLocation(trigger.getObject()), ex);
234: }
235: }
236:
237: private void addPreRequisites(ObjectOrdering ordering, Node node) {
238: String prereqs = ordering.getPrereqs();
239:
240: if ("*".equals(prereqs))
241: return;
242:
243: String[] names = StringUtils.split(prereqs);
244:
245: for (int i = 0; i < names.length; i++) {
246: String prename = names[i];
247:
248: Node prenode = getNode(prename);
249:
250: if (prenode == null) {
251: _errorLog.error(OrdererMessages.badDependency(
252: _objectType, prename, ordering), HiveMind
253: .getLocation(ordering.getObject()), null);
254: continue;
255: }
256:
257: try {
258: node.addDependency(prenode);
259: } catch (ApplicationRuntimeException ex) {
260: _errorLog.error(OrdererMessages.dependencyCycle(
261: _objectType, ordering, ex), HiveMind
262: .getLocation(ordering.getObject()), ex);
263: }
264:
265: }
266: }
267:
268: private void addPostRequisites(ObjectOrdering ordering, Node node) {
269: String postreqs = ordering.getPostreqs();
270:
271: if ("*".equals(postreqs))
272: return;
273:
274: String[] names = StringUtils.split(postreqs);
275:
276: for (int i = 0; i < names.length; i++) {
277: String postname = names[i];
278:
279: Node postnode = getNode(postname);
280:
281: if (postnode == null) {
282: _errorLog.error(OrdererMessages.badDependency(
283: _objectType, postname, ordering), HiveMind
284: .getLocation(ordering.getObject()), null);
285: } else {
286: try {
287: postnode.addDependency(node);
288: } catch (ApplicationRuntimeException ex) {
289: _errorLog.error(OrdererMessages.dependencyCycle(
290: _objectType, ordering, ex), HiveMind
291: .getLocation(ordering.getObject()), ex);
292: }
293: }
294: }
295: }
296:
297: private static class Node {
298: private Object _object;
299:
300: private String _name;
301:
302: private List _dependencies;
303:
304: public Node(Object o, String name) {
305: _object = o;
306: _name = name;
307: _dependencies = new ArrayList();
308: }
309:
310: public String getName() {
311: return _name;
312: }
313:
314: public void addDependency(Node n) {
315: if (n.isReachable(this ))
316: throw new ApplicationRuntimeException(
317: "A cycle has been detected from the initial object ["
318: + _name + "]", HiveMind
319: .getLocation(_object), null);
320:
321: _dependencies.add(n);
322: }
323:
324: private boolean isReachable(Node n) {
325: boolean reachable = (n == this );
326: Iterator i = _dependencies.iterator();
327:
328: while (i.hasNext() && !reachable) {
329: Node dep = (Node) i.next();
330: reachable = (dep == n) ? true : dep.isReachable(n);
331: }
332:
333: return reachable;
334: }
335:
336: public List getOrder() {
337: List result = new ArrayList();
338: fillOrder(result);
339:
340: return result;
341: }
342:
343: private void fillOrder(List result) {
344: if (result.contains(_object))
345: return;
346:
347: Iterator i = _dependencies.iterator();
348:
349: while (i.hasNext()) {
350: Node dep = (Node) i.next();
351: dep.fillOrder(result);
352: }
353:
354: if (_object != null)
355: result.add(_object);
356: }
357: }
358:
359: }
|