X-Git-Url: https://gerrit.onap.org/r/gitweb?a=blobdiff_plain;f=src%2Fmain%2Fjava%2Forg%2Fopenecomp%2Fmodelloader%2Fentity%2Fmodel%2FModelSorter.java;h=79f1c294d31be32ee8bab43c8da09328fc0c2797;hb=578368fce559ad28eb3bc62064e4c39858fa3339;hp=4dcda71133b705c82d147b88f33ca3f186f00add;hpb=ef768a7c864f0d807d8696449f5eed7a4552316f;p=aai%2Fmodel-loader.git diff --git a/src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java b/src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java index 4dcda71..79f1c29 100644 --- a/src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java +++ b/src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java @@ -1,233 +1,235 @@ -/*- - * ============LICENSE_START======================================================= - * MODEL LOADER SERVICE - * ================================================================================ - * Copyright (C) 2017 AT&T Intellectual Property. All rights reserved. - * ================================================================================ - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - * ============LICENSE_END========================================================= - */ - -package org.openecomp.modelloader.entity.model; - -import jline.internal.Log; - -import org.openecomp.modelloader.entity.Artifact; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.HashMap; -import java.util.HashSet; -import java.util.Iterator; -import java.util.List; - -/** - * Utility class to sort the given Models according to their dependencies. - * Example: Given a list of Models [A, B, C] where B depends on A, and A depends - * on C, the sorted result will be [C, A, B] - */ -public class ModelSorter { - - /** - * Wraps a Model object to form dependencies other Models using Edges. - */ - static class Node { - private final ModelArtifact model; - private final HashSet inEdges; - private final HashSet outEdges; - - public Node(ModelArtifact model) { - this.model = model; - inEdges = new HashSet(); - outEdges = new HashSet(); - } - - public Node addEdge(Node node) { - Edge edge = new Edge(this, node); - outEdges.add(edge); - node.inEdges.add(edge); - return this; - } - - @Override - public String toString() { - return model.getNameVersionId(); - } - - @Override - public boolean equals(Object other) { - ModelArtifact otherModel = ((Node) other).model; - return this.model.getNameVersionId().equals(otherModel.getNameVersionId()); - } - - @Override - public int hashCode() { - return this.model.getNameVersionId().hashCode(); - - } - } - - /** - * Represents a dependency between two Nodes. - */ - static class Edge { - public final Node from; - public final Node to; - - public Edge(Node from, Node to) { - this.from = from; - this.to = to; - } - - @Override - public boolean equals(Object obj) { - Edge edge = (Edge) obj; - return edge.from == from && edge.to == to; - } - } - - /** - * Returns the list of models sorted by order of dependency. - * - * @param originalList - * the list that needs to be sorted - * @return a list of sorted models - */ - public List sort(List originalList) { - - if (originalList.size() <= 1) { - return originalList; - } - - Collection nodes = createNodes(originalList); - Collection sortedNodes = sortNodes(nodes); - - List sortedModelsList = new ArrayList(sortedNodes.size()); - for (Node node : sortedNodes) { - sortedModelsList.add(node.model); - } - - return sortedModelsList; - } - - /** - * Create nodes from the list of models and their dependencies. - * - * @param models - * what the nodes creation is based upon - * @return Collection of Node objects - */ - private Collection createNodes(Collection models) { - - // load list of models into a map, so we can later replace referenceIds with - // real Models - HashMap versionIdToModelMap = new HashMap(); - for (Artifact art : models) { - ModelArtifact ma = (ModelArtifact) art; - versionIdToModelMap.put(ma.getNameVersionId(), ma); - } - - HashMap nodes = new HashMap(); - // create a node for each model and its referenced models - for (Artifact art : models) { - ModelArtifact model = (ModelArtifact) art; - - // node might have been created by another model referencing it - Node node = nodes.get(model.getNameVersionId()); - - if (null == node) { - node = new Node(model); - nodes.put(model.getNameVersionId(), node); - } - - for (String referencedModelId : model.getDependentModelIds()) { - // node might have been created by another model referencing it - Node referencedNode = nodes.get(referencedModelId); - - if (null == referencedNode) { - // create node - ModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId); - if (referencedModel == null) { - Log.debug("ignoring " + referencedModelId); - continue; // referenced model not supplied, no need to sort it - } - referencedNode = new Node(referencedModel); - nodes.put(referencedModelId, referencedNode); - } - referencedNode.addEdge(node); - } - } - - return nodes.values(); - } - - /** - * Sorts the given Nodes by order of dependency. - * - * @param originalList - * the collection of nodes to be sorted - * @return a sorted collection of the given nodes - */ - private Collection sortNodes(Collection unsortedNodes) { - - // L <- Empty list that will contain the sorted elements - ArrayList nodeList = new ArrayList(); - - // S <- Set of all nodes with no incoming edges - HashSet nodeSet = new HashSet(); - for (Node unsortedNode : unsortedNodes) { - if (unsortedNode.inEdges.size() == 0) { - nodeSet.add(unsortedNode); - } - } - - // while S is non-empty do - while (!nodeSet.isEmpty()) { - // remove a node n from S - Node node = nodeSet.iterator().next(); - nodeSet.remove(node); - - // insert n into L - nodeList.add(node); - - // for each node m with an edge e from n to m do - for (Iterator it = node.outEdges.iterator(); it.hasNext();) { - // remove edge e from the graph - Edge edge = it.next(); - Node to = edge.to; - it.remove();// Remove edge from n - to.inEdges.remove(edge);// Remove edge from m - - // if m has no other incoming edges then insert m into S - if (to.inEdges.isEmpty()) { - nodeSet.add(to); - } - } - } - // Check to see if all edges are removed - boolean cycle = false; - for (Node node : unsortedNodes) { - if (!node.inEdges.isEmpty()) { - cycle = true; - break; - } - } - if (cycle) { - throw new RuntimeException( - "Circular dependency present between models, topological sort not possible"); - } - - return nodeList; - } - -} +/** + * ============LICENSE_START======================================================= + * Model Loader + * ================================================================================ + * Copyright © 2017 AT&T Intellectual Property. + * Copyright © 2017 Amdocs + * All rights reserved. + * ================================================================================ + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * http://www.apache.org/licenses/LICENSE-2.0 + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * ============LICENSE_END========================================================= + * + * ECOMP and OpenECOMP are trademarks + * and service marks of AT&T Intellectual Property. + */ +package org.openecomp.modelloader.entity.model; + +import jline.internal.Log; + +import org.openecomp.modelloader.entity.Artifact; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; + +/** + * Utility class to sort the given Models according to their dependencies. + * Example: Given a list of Models [A, B, C] where B depends on A, and A depends + * on C, the sorted result will be [C, A, B] + */ +public class ModelSorter { + + /** + * Wraps a Model object to form dependencies other Models using Edges. + */ + static class Node { + private final ModelArtifact model; + private final HashSet inEdges; + private final HashSet outEdges; + + public Node(ModelArtifact model) { + this.model = model; + inEdges = new HashSet(); + outEdges = new HashSet(); + } + + public Node addEdge(Node node) { + Edge edge = new Edge(this, node); + outEdges.add(edge); + node.inEdges.add(edge); + return this; + } + + @Override + public String toString() { + return model.getModelInvariantId(); + } + + @Override + public boolean equals(Object other) { + ModelArtifact otherModel = ((Node) other).model; + return this.model.getModelInvariantId().equals(otherModel.getModelInvariantId()); + } + + @Override + public int hashCode() { + return this.model.getModelInvariantId().hashCode(); + + } + } + + /** + * Represents a dependency between two Nodes. + */ + static class Edge { + public final Node from; + public final Node to; + + public Edge(Node from, Node to) { + this.from = from; + this.to = to; + } + + @Override + public boolean equals(Object obj) { + Edge edge = (Edge) obj; + return edge.from == from && edge.to == to; + } + } + + /** + * Returns the list of models sorted by order of dependency. + * + * @param originalList + * the list that needs to be sorted + * @return a list of sorted models + */ + public List sort(List originalList) { + + if (originalList.size() <= 1) { + return originalList; + } + + Collection nodes = createNodes(originalList); + Collection sortedNodes = sortNodes(nodes); + + List sortedModelsList = new ArrayList(sortedNodes.size()); + for (Node node : sortedNodes) { + sortedModelsList.add(node.model); + } + + return sortedModelsList; + } + + /** + * Create nodes from the list of models and their dependencies. + * + * @param models + * what the nodes creation is based upon + * @return Collection of Node objects + */ + private Collection createNodes(Collection models) { + + // load list of models into a map, so we can later replace referenceIds with + // real Models + HashMap versionIdToModelMap = new HashMap(); + for (Artifact art : models) { + ModelArtifact ma = (ModelArtifact) art; + versionIdToModelMap.put(ma.getModelModelVerCombinedKey(), ma); + } + + HashMap nodes = new HashMap(); + // create a node for each model and its referenced models + for (Artifact art : models) { + ModelArtifact model = (ModelArtifact) art; + + // node might have been created by another model referencing it + Node node = nodes.get(model.getModelModelVerCombinedKey()); + + if (null == node) { + node = new Node(model); + nodes.put(model.getModelModelVerCombinedKey(), node); + } + + for (String referencedModelId : model.getDependentModelIds()) { + // node might have been created by another model referencing it + Node referencedNode = nodes.get(referencedModelId); + + if (null == referencedNode) { + // create node + ModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId); + if (referencedModel == null) { + Log.debug("ignoring " + referencedModelId); + continue; // referenced model not supplied, no need to sort it + } + referencedNode = new Node(referencedModel); + nodes.put(referencedModelId, referencedNode); + } + referencedNode.addEdge(node); + } + } + + return nodes.values(); + } + + /** + * Sorts the given Nodes by order of dependency. + * + * @param originalList + * the collection of nodes to be sorted + * @return a sorted collection of the given nodes + */ + private Collection sortNodes(Collection unsortedNodes) { + + // L <- Empty list that will contain the sorted elements + ArrayList nodeList = new ArrayList(); + + // S <- Set of all nodes with no incoming edges + HashSet nodeSet = new HashSet(); + for (Node unsortedNode : unsortedNodes) { + if (unsortedNode.inEdges.size() == 0) { + nodeSet.add(unsortedNode); + } + } + + // while S is non-empty do + while (!nodeSet.isEmpty()) { + // remove a node n from S + Node node = nodeSet.iterator().next(); + nodeSet.remove(node); + + // insert n into L + nodeList.add(node); + + // for each node m with an edge e from n to m do + for (Iterator it = node.outEdges.iterator(); it.hasNext();) { + // remove edge e from the graph + Edge edge = it.next(); + Node to = edge.to; + it.remove();// Remove edge from n + to.inEdges.remove(edge);// Remove edge from m + + // if m has no other incoming edges then insert m into S + if (to.inEdges.isEmpty()) { + nodeSet.add(to); + } + } + } + // Check to see if all edges are removed + boolean cycle = false; + for (Node node : unsortedNodes) { + if (!node.inEdges.isEmpty()) { + cycle = true; + break; + } + } + if (cycle) { + throw new RuntimeException( + "Circular dependency present between models, topological sort not possible"); + } + + return nodeList; + } + +}