2009/04/15 - Apache HiveMind has been retired.

For more information, please explore the Attic.

Clover coverage report - Code Coverage for hivemind release 1.2.1
Coverage timestamp: Fri Feb 10 2006 16:33:43 PST
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 407   Methods: 19
NCLOC: 269   Classes: 2
 
 Source file Conditionals Statements Methods TOTAL
Orderer.java 100% 97.2% 100% 98.3%
coverage coverage
 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;
 18    import java.util.Collections;
 19    import java.util.HashMap;
 20    import java.util.Iterator;
 21    import java.util.List;
 22    import java.util.Map;
 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 _objectType;
 45   
 46    private List _orderingsList = null;
 47   
 48    private Map _orderingsMap = null;
 49   
 50    private Map _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  10 public Orderer(ErrorHandler errorHandler, String objectType)
 60    {
 61  10 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  36 public Orderer(Log log, ErrorHandler errorHandler, String objectType)
 74    {
 75  36 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  36 public Orderer(ErrorLog errorLog, String objectType)
 88    {
 89  36 Defense.notNull(errorLog, "errorLog");
 90  36 Defense.notNull(objectType, "objectType");
 91   
 92  36 _errorLog = errorLog;
 93  36 _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  83 public void add(Object object, String name, String prereqs, String postreqs)
 112    {
 113  83 if (_orderingsMap == null)
 114    {
 115  35 _orderingsMap = new HashMap();
 116  35 _orderingsList = new ArrayList();
 117    }
 118   
 119  83 ObjectOrdering o = getOrderable(name);
 120   
 121  83 if (o != null)
 122    {
 123  1 _errorLog.error(
 124    OrdererMessages.duplicateName(_objectType, name, object, o.getObject()),
 125    HiveMind.getLocation(object),
 126    null);
 127   
 128  1 return;
 129    }
 130   
 131  82 o = new ObjectOrdering(object, name, prereqs, postreqs);
 132   
 133  82 _orderingsMap.put(name, o);
 134  82 _orderingsList.add(o);
 135    }
 136   
 137  207 private ObjectOrdering getOrderable(String name)
 138    {
 139  207 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  36 public List getOrderedObjects()
 148    {
 149  36 if (_orderingsMap == null)
 150  1 return Collections.EMPTY_LIST;
 151   
 152  35 try
 153    {
 154  35 _nodeMap = new HashMap();
 155   
 156  35 initializeGraph();
 157   
 158  35 return _trailer.getOrder();
 159    }
 160    finally
 161    {
 162  35 _nodeMap = null;
 163  35 _leader = null;
 164  35 _trailer = null;
 165    }
 166    }
 167   
 168  35 private void initializeGraph()
 169    {
 170  35 addNodes();
 171   
 172  35 if (_leader == null)
 173  31 _leader = new Node(null, "*-leader-*");
 174   
 175  35 if (_trailer == null)
 176  33 _trailer = new Node(null, "*-trailer-*");
 177   
 178  35 addDependencies();
 179    }
 180   
 181  122 private Node getNode(String name)
 182    {
 183  122 return (Node) _nodeMap.get(getOrderable(name));
 184    }
 185   
 186  35 private void addNodes()
 187    {
 188  35 Iterator i = _orderingsList.iterator();
 189   
 190  35 while (i.hasNext())
 191    {
 192  82 ObjectOrdering o = (ObjectOrdering) i.next();
 193   
 194  82 Node node = new Node(o.getObject(), o.getName());
 195   
 196  82 _nodeMap.put(o, node);
 197   
 198  82 if ("*".equals(o.getPostreqs()))
 199    {
 200  5 if (_leader == null)
 201  4 _leader = node;
 202    else
 203  1 _errorLog.error(OrdererMessages.dupeLeader(_objectType, o, getOrderable(_leader
 204    .getName())), HiveMind.getLocation(o.getObject()), null);
 205    }
 206   
 207  82 if ("*".equals(o.getPrereqs()))
 208    {
 209  3 if (_trailer == null)
 210  2 _trailer = node;
 211    else
 212  1 _errorLog.error(
 213    OrdererMessages.dupeTrailer(_objectType, o, getOrderable(_trailer
 214    .getName())),
 215    HiveMind.getLocation(o.getObject()),
 216    null);
 217    }
 218   
 219    }
 220    }
 221   
 222  35 private void addDependencies()
 223    {
 224  35 Iterator i = _orderingsList.iterator();
 225   
 226  35 while (i.hasNext())
 227    {
 228  82 ObjectOrdering o = (ObjectOrdering) i.next();
 229   
 230  82 addDependencies(o, getNode(o.getName()));
 231    }
 232    }
 233   
 234  82 private void addDependencies(ObjectOrdering orderable, Node node)
 235    {
 236  82 addPreRequisites(orderable, node);
 237  82 addPostRequisites(orderable, node);
 238   
 239  82 try
 240    {
 241  82 if (node != _leader)
 242  78 node.addDependency(_leader);
 243   
 244  82 if (node != _trailer)
 245  80 _trailer.addDependency(node);
 246    }
 247    catch (ApplicationRuntimeException ex)
 248    {
 249    // This code is unreachable ... but nonetheless.
 250   
 251  0 String name = node.getName();
 252  0 ObjectOrdering trigger = getOrderable(name);
 253   
 254  0 _errorLog.error(OrdererMessages.dependencyCycle(_objectType, orderable, ex), HiveMind
 255    .getLocation(trigger.getObject()), ex);
 256    }
 257    }
 258   
 259  82 private void addPreRequisites(ObjectOrdering ordering, Node node)
 260    {
 261  82 String prereqs = ordering.getPrereqs();
 262   
 263  82 if ("*".equals(prereqs))
 264  3 return;
 265   
 266  79 String[] names = StringUtils.split(prereqs);
 267   
 268  79 for (int i = 0; i < names.length; i++)
 269    {
 270  14 String prename = names[i];
 271   
 272  14 Node prenode = getNode(prename);
 273   
 274  14 if (prenode == null)
 275    {
 276  1 _errorLog.error(
 277    OrdererMessages.badDependency(_objectType, prename, ordering),
 278    HiveMind.getLocation(ordering.getObject()),
 279    null);
 280  1 continue;
 281    }
 282   
 283  13 try
 284    {
 285  13 node.addDependency(prenode);
 286    }
 287    catch (ApplicationRuntimeException ex)
 288    {
 289  1 _errorLog.error(
 290    OrdererMessages.dependencyCycle(_objectType, ordering, ex),
 291    HiveMind.getLocation(ordering.getObject()),
 292    ex);
 293    }
 294   
 295    }
 296    }
 297   
 298  82 private void addPostRequisites(ObjectOrdering ordering, Node node)
 299    {
 300  82 String postreqs = ordering.getPostreqs();
 301   
 302  82 if ("*".equals(postreqs))
 303  5 return;
 304   
 305  77 String[] names = StringUtils.split(postreqs);
 306   
 307  77 for (int i = 0; i < names.length; i++)
 308    {
 309  26 String postname = names[i];
 310   
 311  26 Node postnode = getNode(postname);
 312   
 313  26 if (postnode == null)
 314    {
 315  1 _errorLog.error(
 316    OrdererMessages.badDependency(_objectType, postname, ordering),
 317    HiveMind.getLocation(ordering.getObject()),
 318    null);
 319    }
 320    else
 321    {
 322  25 try
 323    {
 324  25 postnode.addDependency(node);
 325    }
 326    catch (ApplicationRuntimeException ex)
 327    {
 328  1 _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 _object;
 340   
 341    private String _name;
 342   
 343    private List _dependencies;
 344   
 345  146 public Node(Object o, String name)
 346    {
 347  146 _object = o;
 348  146 _name = name;
 349  146 _dependencies = new ArrayList();
 350    }
 351   
 352  2 public String getName()
 353    {
 354  2 return _name;
 355    }
 356   
 357  196 public void addDependency(Node n)
 358    {
 359  196 if (n.isReachable(this))
 360  2 throw new ApplicationRuntimeException(
 361    "A cycle has been detected from the initial object [" + _name + "]",
 362    HiveMind.getLocation(_object), null);
 363   
 364  194 _dependencies.add(n);
 365    }
 366   
 367  397 private boolean isReachable(Node n)
 368    {
 369  397 boolean reachable = (n == this);
 370  397 Iterator i = _dependencies.iterator();
 371   
 372  397 while (i.hasNext() && !reachable)
 373    {
 374  203 Node dep = (Node) i.next();
 375  203 reachable = (dep == n) ? true : dep.isReachable(n);
 376    }
 377   
 378  397 return reachable;
 379    }
 380   
 381  35 public List getOrder()
 382    {
 383  35 List result = new ArrayList();
 384  35 fillOrder(result);
 385   
 386  35 return result;
 387    }
 388   
 389  229 private void fillOrder(List result)
 390    {
 391  229 if (result.contains(_object))
 392  46 return;
 393   
 394  183 Iterator i = _dependencies.iterator();
 395   
 396  183 while (i.hasNext())
 397    {
 398  194 Node dep = (Node) i.next();
 399  194 dep.fillOrder(result);
 400    }
 401   
 402  183 if (_object != null)
 403  82 result.add(_object);
 404    }
 405    }
 406   
 407    }
 
CloverReport generated by Clover Code Coverage v1.3.8
Fri Feb 10 2006 16:33:59 PST.		   Open Source License registered to the Apache Software Foundation. This license of Clover is provided to support projects of the Apache Software Foundation only.