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 */ 020 package org.sonar.api.utils.dag; 021 022 import org.sonar.api.utils.SonarException; 023 024 import java.util.*; 025 026 /** 027 * <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph">http://en.wikipedia.org/wiki/Directed_acyclic_graph</a> 028 * 029 * @since 1.10 030 */ 031 public class DirectAcyclicGraph { 032 033 private Map<Object, Node> registeredObjects = new HashMap<Object, Node>(); 034 private List<Node> nodes = new ArrayList<Node>(); 035 036 public DirectAcyclicGraph(final Object... objects) { 037 if (objects != null) { 038 for (Object object : objects) { 039 add(object); 040 } 041 } 042 } 043 044 public Node add(final Object object, final Object... dependencies) { 045 Node node = registeredObjects.get(object); 046 if (node == null) { 047 node = new Node(object); 048 nodes.add(node); 049 registeredObjects.put(object, node); 050 } 051 052 if (dependencies != null) { 053 for (Object dependency : dependencies) { 054 Node depNode = add(dependency); 055 node.addDependency(depNode); 056 } 057 } 058 return node; 059 } 060 061 public List sort() { 062 sortNodes(); 063 064 List result = new ArrayList(); 065 for (Node node : nodes) { 066 result.add(node.getObject()); 067 } 068 return result; 069 } 070 071 private List<Node> sortNodes() { 072 verify(); 073 Collections.sort(nodes); 074 return nodes; 075 } 076 077 private void verify() { 078 for (Node node : nodes) { 079 node.reset(); 080 } 081 082 for (Node node : nodes) { 083 for (Node dep : node.getDependencies()) { 084 if (!nodes.contains(dep)) { 085 throw new SonarException("A dependent node (" + dep + ") of " 086 + " (" + node + ") was not included in the nodes list."); 087 } 088 } 089 090 node.resolveOrder(); 091 } 092 } 093 }