001/*
002 * Sonar, open source software quality management tool.
003 * Copyright (C) 2008-2012 SonarSource
004 * mailto:contact AT sonarsource DOT com
005 *
006 * Sonar is free software; you can redistribute it and/or
007 * modify it under the terms of the GNU Lesser General Public
008 * License as published by the Free Software Foundation; either
009 * version 3 of the License, or (at your option) any later version.
010 *
011 * Sonar is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014 * Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public
017 * License along with Sonar; if not, write to the Free Software
018 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
019 */
020package org.sonar.api.utils.dag;
021
022import com.google.common.collect.Lists;
023
024import org.sonar.api.utils.SonarException;
025
026import java.util.*;
027
028/**
029 * <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">http://en.wikipedia.org/wiki/Directed_acyclic_graph</a>
030 *
031 * @since 1.10
032 */
033public class DirectAcyclicGraph {
034
035  private Map<Object, Node> registeredObjects = new HashMap<Object, Node>();
036  private List<Node> nodes = new ArrayList<Node>();
037
038  public DirectAcyclicGraph(final Object... objects) {
039    if (objects != null) {
040      for (Object object : objects) {
041        add(object);
042      }
043    }
044  }
045
046  public Node add(final Object object, final Object... dependencies) {
047    Node node = registeredObjects.get(object);
048    if (node == null) {
049      node = new Node(object);
050      nodes.add(node);
051      registeredObjects.put(object, node);
052    }
053
054    if (dependencies != null) {
055      for (Object dependency : dependencies) {
056        Node depNode = add(dependency);
057        node.addDependency(depNode);
058      }
059    }
060    return node;
061  }
062
063  public List sort() {
064    sortNodes();
065
066    List<Object> result = Lists.newArrayList();
067    for (Node node : nodes) {
068      result.add(node.getObject());
069    }
070    return result;
071  }
072
073  private List<Node> sortNodes() {
074    verify();
075    Collections.sort(nodes);
076    return nodes;
077  }
078
079  private void verify() {
080    for (Node node : nodes) {
081      node.reset();
082    }
083
084    for (Node node : nodes) {
085      for (Node dep : node.getDependencies()) {
086        if (!nodes.contains(dep)) {
087          throw new SonarException("A dependent node (" + dep + ") of "
088              + " (" + node + ") was not included in the nodes list.");
089        }
090      }
091
092      node.resolveOrder();
093    }
094  }
095}