001 /* 002 * SonarQube, open source software quality management tool. 003 * Copyright (C) 2008-2014 SonarSource 004 * mailto:contact AT sonarsource DOT com 005 * 006 * SonarQube 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 * SonarQube 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 License 017 * along with this program; if not, write to the Free Software Foundation, 018 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 019 */ 020 package org.sonar.api.utils.dag; 021 022 import com.google.common.collect.Lists; 023 024 import org.sonar.api.utils.SonarException; 025 026 import 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 */ 033 public 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 }