From 66591707689b9ee5968fb1b8eb490529e5ceeab8 Mon Sep 17 00:00:00 2001 From: Robert Varga Date: Mon, 12 Jun 2017 16:56:50 +0200 Subject: [PATCH] BUG-7052: Move TopologicalSort to util package This utility has no dependencies on parser and is generally useful. Expose it as a beta API from util package. Change-Id: Iba50e8c0064748498307ca88f99273532c089168 Signed-off-by: Robert Varga --- .../yangtools/util/TopologicalSort.java | 203 ++++++++++++++++++ .../yangtools}/util/TopologicalSortTest.java | 17 +- .../parser/util/ModuleDependencySort.java | 8 +- .../yang/parser/util/NodeWrappedType.java | 8 +- .../yang/parser/util/TopologicalSort.java | 17 +- 5 files changed, 231 insertions(+), 22 deletions(-) create mode 100644 common/util/src/main/java/org/opendaylight/yangtools/util/TopologicalSort.java rename {yang/yang-parser-impl/src/test/java/org/opendaylight/yangtools/yang/parser => common/util/src/test/java/org/opendaylight/yangtools}/util/TopologicalSortTest.java (81%) diff --git a/common/util/src/main/java/org/opendaylight/yangtools/util/TopologicalSort.java b/common/util/src/main/java/org/opendaylight/yangtools/util/TopologicalSort.java new file mode 100644 index 0000000000..9a8c532285 --- /dev/null +++ b/common/util/src/main/java/org/opendaylight/yangtools/util/TopologicalSort.java @@ -0,0 +1,203 @@ +/* + * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved. + * + * This program and the accompanying materials are made available under the + * terms of the Eclipse Public License v1.0 which accompanies this distribution, + * and is available at http://www.eclipse.org/legal/epl-v10.html + */ +package org.opendaylight.yangtools.util; + +import com.google.common.annotations.Beta; +import com.google.common.base.Preconditions; +import java.util.ArrayList; +import java.util.HashSet; +import java.util.List; +import java.util.Objects; +import java.util.Set; + +/** + * Utility class that provides topological sort. + * + *

+ * Note this class is non-public to allow for API transition. + */ +@Beta +public final class TopologicalSort { + + /** + * It isn't desirable to create instance of this class. + */ + private TopologicalSort() { + } + + /** + * Topological sort of dependent nodes in acyclic graphs. + * + * @param nodes graph nodes + * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no dependencies starting. + * @throws IllegalStateException when cycle is present in the graph + */ + public static List sort(final Set nodes) { + List sortedNodes = new ArrayList<>(nodes.size()); + + Set dependentNodes = getDependentNodes(nodes); + + while (!dependentNodes.isEmpty()) { + Node node = dependentNodes.iterator().next(); + dependentNodes.remove(node); + + sortedNodes.add(node); + + for (Edge edge : node.getInEdges()) { + Node referent = edge.getFrom(); + referent.getOutEdges().remove(edge); + + if (referent.getOutEdges().isEmpty()) { + dependentNodes.add(referent); + } + } + } + + detectCycles(nodes); + + return sortedNodes; + } + + private static Set getDependentNodes(final Set nodes) { + Set dependentNodes = new HashSet<>(); + for (Node node : nodes) { + if (node.getOutEdges().isEmpty()) { + dependentNodes.add(node); + } + } + return dependentNodes; + } + + private static void detectCycles(final Set nodes) { + // Detect cycles + boolean cycle = false; + Node cycledNode = null; + + for (Node node : nodes) { + if (!node.getOutEdges().isEmpty()) { + cycle = true; + cycledNode = node; + break; + } + } + Preconditions.checkState(!cycle, "Cycle detected in graph around node: " + cycledNode); + } + + /** + * Interface for nodes in graph that can be sorted topologically. + */ + @Beta + public interface Node { + Set getInEdges(); + + Set getOutEdges(); + } + + /** + * Interface for edges in graph that can be sorted topologically. + */ + @Beta + public interface Edge { + Node getFrom(); + + Node getTo(); + } + + /** + * Basic Node implementation. + */ + @Beta + public static class NodeImpl implements Node { + private final Set inEdges; + private final Set outEdges; + + public NodeImpl() { + inEdges = new HashSet<>(); + outEdges = new HashSet<>(); + } + + @Override + public Set getInEdges() { + return inEdges; + } + + @Override + public Set getOutEdges() { + return outEdges; + } + + public void addEdge(final Node to) { + Edge edge = new EdgeImpl(this, to); + outEdges.add(edge); + to.getInEdges().add(edge); + } + } + + /** + * Basic Edge implementation. + */ + @Beta + public static class EdgeImpl implements Edge { + private final Node from; + private final Node to; + + public EdgeImpl(final Node from, final Node to) { + this.from = from; + this.to = to; + } + + @Override + public Node getFrom() { + return from; + } + + @Override + public Node getTo() { + return to; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + Objects.hashCode(from); + result = prime * result + Objects.hashCode(to); + return result; + } + + @Override + public boolean equals(final Object obj) { + if (this == obj) { + return true; + } + if (obj == null) { + return false; + } + if (getClass() != obj.getClass()) { + return false; + } + EdgeImpl other = (EdgeImpl) obj; + if (from == null) { + if (other.from != null) { + return false; + } + } else if (!from.equals(other.from)) { + return false; + } + if (to == null) { + if (other.to != null) { + return false; + } + } else if (!to.equals(other.to)) { + return false; + } + return true; + } + } + +} diff --git a/yang/yang-parser-impl/src/test/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSortTest.java b/common/util/src/test/java/org/opendaylight/yangtools/util/TopologicalSortTest.java similarity index 81% rename from yang/yang-parser-impl/src/test/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSortTest.java rename to common/util/src/test/java/org/opendaylight/yangtools/util/TopologicalSortTest.java index 6a7b00724e..32d215845d 100644 --- a/yang/yang-parser-impl/src/test/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSortTest.java +++ b/common/util/src/test/java/org/opendaylight/yangtools/util/TopologicalSortTest.java @@ -5,24 +5,22 @@ * terms of the Eclipse Public License v1.0 which accompanies this distribution, * and is available at http://www.eclipse.org/legal/epl-v10.html */ -package org.opendaylight.yangtools.yang.parser.util; +package org.opendaylight.yangtools.util; import static org.junit.Assert.assertEquals; -import com.google.common.collect.Sets; - +import java.util.HashSet; import java.util.List; import java.util.Set; - import org.junit.Test; -import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.Node; -import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl; +import org.opendaylight.yangtools.util.TopologicalSort.Node; +import org.opendaylight.yangtools.util.TopologicalSort.NodeImpl; public class TopologicalSortTest { @Test(expected = IllegalStateException.class) - public void test() throws Exception { - Set nodes = Sets.newHashSet(); + public void test() { + Set nodes = new HashSet<>(); NodeImpl node1 = new NodeImpl(); nodes.add(node1); @@ -41,7 +39,7 @@ public class TopologicalSortTest { @Test public void testValidSimple() throws Exception { - Set nodes = Sets.newHashSet(); + Set nodes = new HashSet<>(); Node node1 = new NodeImpl(); nodes.add(node1); @@ -64,5 +62,4 @@ public class TopologicalSortTest { assertEquals(node3, sorted.get(2)); assertEquals(node1, sorted.get(3)); } - } diff --git a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java index d707acd8c9..2960358e88 100644 --- a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java +++ b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/ModuleDependencySort.java @@ -19,11 +19,13 @@ import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Objects; +import org.opendaylight.yangtools.util.TopologicalSort; +import org.opendaylight.yangtools.util.TopologicalSort.Node; +import org.opendaylight.yangtools.util.TopologicalSort.NodeImpl; import org.opendaylight.yangtools.yang.common.SimpleDateFormatUtil; import org.opendaylight.yangtools.yang.common.YangVersion; import org.opendaylight.yangtools.yang.model.api.Module; import org.opendaylight.yangtools.yang.model.api.ModuleImport; -import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl; import org.slf4j.Logger; import org.slf4j.LoggerFactory; @@ -63,12 +65,12 @@ public final class ModuleDependencySort { * returned order. */ public static List sort(final Iterable modules) { - final List sorted = sortInternal(modules); + final List sorted = sortInternal(modules); // Cast to Module from Node and return return Lists.transform(sorted, input -> input == null ? null : ((ModuleNodeImpl) input).getReference()); } - private static List sortInternal(final Iterable modules) { + private static List sortInternal(final Iterable modules) { final Table moduleGraph = createModuleGraph(modules); return TopologicalSort.sort(new HashSet<>(moduleGraph.values())); } diff --git a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/NodeWrappedType.java b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/NodeWrappedType.java index fca683d246..db28e9147e 100644 --- a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/NodeWrappedType.java +++ b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/NodeWrappedType.java @@ -9,6 +9,10 @@ package org.opendaylight.yangtools.yang.parser.util; import org.opendaylight.yangtools.yang.parser.util.TopologicalSort.NodeImpl; +/** + * @deprecated This class is not used anywhere and is scheduled for removal with TopologicalSort. + */ +@Deprecated public final class NodeWrappedType extends NodeImpl { /** * The payload which is saved inside Node @@ -21,7 +25,7 @@ public final class NodeWrappedType extends NodeImpl { * @param wrappedType * object with payload data */ - public NodeWrappedType(Object wrappedType) { + public NodeWrappedType(final Object wrappedType) { this.wrappedType = wrappedType; } @@ -35,7 +39,7 @@ public final class NodeWrappedType extends NodeImpl { } @Override - public boolean equals(Object o) { + public boolean equals(final Object o) { if (this == o) { return true; } diff --git a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSort.java b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSort.java index 42db14607e..2f7377d178 100644 --- a/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSort.java +++ b/yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSort.java @@ -15,8 +15,11 @@ import java.util.Objects; import java.util.Set; /** - * Utility class that provides topological sort + * Utility class that provides topological sort. + * + * @deprecated Use {@link org.opendaylight.yangtools.util.TopologicalSort} instead. */ +@Deprecated public final class TopologicalSort { /** @@ -34,7 +37,7 @@ public final class TopologicalSort { * @throws IllegalStateException * when cycle is present in the graph */ - public static List sort(Set nodes) { + public static List sort(final Set nodes) { List sortedNodes = Lists.newArrayList(); Set dependentNodes = getDependentNodes(nodes); @@ -60,7 +63,7 @@ public final class TopologicalSort { return sortedNodes; } - private static Set getDependentNodes(Set nodes) { + private static Set getDependentNodes(final Set nodes) { Set dependentNodes = Sets.newHashSet(); for (Node n : nodes) { if (n.getOutEdges().isEmpty()) { @@ -70,7 +73,7 @@ public final class TopologicalSort { return dependentNodes; } - private static void detectCycles(Set nodes) { + private static void detectCycles(final Set nodes) { // Detect cycles boolean cycle = false; Node cycledNode = null; @@ -125,7 +128,7 @@ public final class TopologicalSort { return outEdges; } - public void addEdge(Node to) { + public void addEdge(final Node to) { Edge e = new EdgeImpl(this, to); outEdges.add(e); to.getInEdges().add(e); @@ -139,7 +142,7 @@ public final class TopologicalSort { private final Node from; private final Node to; - public EdgeImpl(Node from, Node to) { + public EdgeImpl(final Node from, final Node to) { this.from = from; this.to = to; } @@ -164,7 +167,7 @@ public final class TopologicalSort { } @Override - public boolean equals(Object obj) { + public boolean equals(final Object obj) { if (this == obj) { return true; } -- 2.36.6