src/main/java/org/openecomp/modelloader/entity/model/ModelSorter.java

   1 /**\r
   2  * ============LICENSE_START=======================================================\r
   3  * Model Loader\r
   4  * ================================================================================\r
   5  * Copyright © 2017 AT&T Intellectual Property.\r
   6  * Copyright © 2017 Amdocs\r
   7  * All rights reserved.\r
   8  * ================================================================================\r
   9  * Licensed under the Apache License, Version 2.0 (the "License");\r
  10  * you may not use this file except in compliance with the License.\r
  11  * You may obtain a copy of the License at\r
  12  * http://www.apache.org/licenses/LICENSE-2.0\r
  13  * Unless required by applicable law or agreed to in writing, software\r
  14  * distributed under the License is distributed on an "AS IS" BASIS,\r
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  16  * See the License for the specific language governing permissions and\r
  17  * limitations under the License.\r
  18  * ============LICENSE_END=========================================================\r
  19  *\r
  20  * ECOMP and OpenECOMP are trademarks\r
  21  * and service marks of AT&T Intellectual Property.\r
  22  */\r
  23 package org.openecomp.modelloader.entity.model;\r
  24 \r
  25 import jline.internal.Log;\r
  26 \r
  27 import org.openecomp.modelloader.entity.Artifact;\r
  28 \r
  29 import java.util.ArrayList;\r
  30 import java.util.Collection;\r
  31 import java.util.HashMap;\r
  32 import java.util.HashSet;\r
  33 import java.util.Iterator;\r
  34 import java.util.List;\r
  35 \r
  36 /**\r
  37  * Utility class to sort the given Models according to their dependencies.\r
  38  * Example: Given a list of Models [A, B, C] where B depends on A, and A depends\r
  39  * on C, the sorted result will be [C, A, B]\r
  40  */\r
  41 public class ModelSorter {\r
  42 \r
  43   /**\r
  44    * Wraps a Model object to form dependencies other Models using Edges.\r
  45    */\r
  46   static class Node {\r
  47     private final ModelArtifact model;\r
  48     private final HashSet<Edge> inEdges;\r
  49     private final HashSet<Edge> outEdges;\r
  50 \r
  51     public Node(ModelArtifact model) {\r
  52       this.model = model;\r
  53       inEdges = new HashSet<Edge>();\r
  54       outEdges = new HashSet<Edge>();\r
  55     }\r
  56 \r
  57     public Node addEdge(Node node) {\r
  58       Edge edge = new Edge(this, node);\r
  59       outEdges.add(edge);\r
  60       node.inEdges.add(edge);\r
  61       return this;\r
  62     }\r
  63 \r
  64     @Override\r
  65     public String toString() {\r
  66       return model.getModelInvariantId();\r
  67     }\r
  68 \r
  69     @Override\r
  70     public boolean equals(Object other) {\r
  71       ModelArtifact otherModel = ((Node) other).model;\r
  72       return this.model.getModelInvariantId().equals(otherModel.getModelInvariantId());\r
  73     }\r
  74 \r
  75     @Override\r
  76     public int hashCode() {\r
  77       return this.model.getModelInvariantId().hashCode();\r
  78 \r
  79     }\r
  80   }\r
  81 \r
  82   /**\r
  83    * Represents a dependency between two Nodes.\r
  84    */\r
  85   static class Edge {\r
  86     public final Node from;\r
  87     public final Node to;\r
  88 \r
  89     public Edge(Node from, Node to) {\r
  90       this.from = from;\r
  91       this.to = to;\r
  92     }\r
  93 \r
  94     @Override\r
  95     public boolean equals(Object obj) {\r
  96       Edge edge = (Edge) obj;\r
  97       return edge.from == from && edge.to == to;\r
  98     }\r
  99   }\r
 100 \r
 101   /**\r
 102    * Returns the list of models sorted by order of dependency.\r
 103    * \r
 104    * @param originalList\r
 105    *          the list that needs to be sorted\r
 106    * @return a list of sorted models\r
 107    */\r
 108   public List<Artifact> sort(List<Artifact> originalList) {\r
 109 \r
 110     if (originalList.size() <= 1) {\r
 111       return originalList;\r
 112     }\r
 113 \r
 114     Collection<Node> nodes = createNodes(originalList);\r
 115     Collection<Node> sortedNodes = sortNodes(nodes);\r
 116 \r
 117     List<Artifact> sortedModelsList = new ArrayList<Artifact>(sortedNodes.size());\r
 118     for (Node node : sortedNodes) {\r
 119       sortedModelsList.add(node.model);\r
 120     }\r
 121 \r
 122     return sortedModelsList;\r
 123   }\r
 124 \r
 125   /**\r
 126    * Create nodes from the list of models and their dependencies.\r
 127    * \r
 128    * @param models\r
 129    *          what the nodes creation is based upon\r
 130    * @return Collection of Node objects\r
 131    */\r
 132   private Collection<Node> createNodes(Collection<Artifact> models) {\r
 133 \r
 134     // load list of models into a map, so we can later replace referenceIds with\r
 135     // real Models\r
 136     HashMap<String, ModelArtifact> versionIdToModelMap = new HashMap<String, ModelArtifact>();\r
 137     for (Artifact art : models) {\r
 138       ModelArtifact ma = (ModelArtifact) art;\r
 139       versionIdToModelMap.put(ma.getModelModelVerCombinedKey(), ma);\r
 140     }\r
 141 \r
 142     HashMap<String, Node> nodes = new HashMap<String, Node>();\r
 143     // create a node for each model and its referenced models\r
 144     for (Artifact art : models) {\r
 145       ModelArtifact model = (ModelArtifact) art;\r
 146 \r
 147       // node might have been created by another model referencing it\r
 148       Node node = nodes.get(model.getModelModelVerCombinedKey());\r
 149 \r
 150       if (null == node) {\r
 151         node = new Node(model);\r
 152         nodes.put(model.getModelModelVerCombinedKey(), node);\r
 153       }\r
 154 \r
 155       for (String referencedModelId : model.getDependentModelIds()) {\r
 156         // node might have been created by another model referencing it\r
 157         Node referencedNode = nodes.get(referencedModelId);\r
 158 \r
 159         if (null == referencedNode) {\r
 160           // create node\r
 161           ModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);\r
 162           if (referencedModel == null) {\r
 163             Log.debug("ignoring " + referencedModelId);\r
 164             continue; // referenced model not supplied, no need to sort it\r
 165           }\r
 166           referencedNode = new Node(referencedModel);\r
 167           nodes.put(referencedModelId, referencedNode);\r
 168         }\r
 169         referencedNode.addEdge(node);\r
 170       }\r
 171     }\r
 172 \r
 173     return nodes.values();\r
 174   }\r
 175 \r
 176   /**\r
 177    * Sorts the given Nodes by order of dependency.\r
 178    * \r
 179    * @param originalList\r
 180    *          the collection of nodes to be sorted\r
 181    * @return a sorted collection of the given nodes\r
 182    */\r
 183   private Collection<Node> sortNodes(Collection<Node> unsortedNodes) {\r
 184 \r
 185     // L <- Empty list that will contain the sorted elements\r
 186     ArrayList<Node> nodeList = new ArrayList<Node>();\r
 187 \r
 188     // S <- Set of all nodes with no incoming edges\r
 189     HashSet<Node> nodeSet = new HashSet<Node>();\r
 190     for (Node unsortedNode : unsortedNodes) {\r
 191       if (unsortedNode.inEdges.size() == 0) {\r
 192         nodeSet.add(unsortedNode);\r
 193       }\r
 194     }\r
 195 \r
 196     // while S is non-empty do\r
 197     while (!nodeSet.isEmpty()) {\r
 198       // remove a node n from S\r
 199       Node node = nodeSet.iterator().next();\r
 200       nodeSet.remove(node);\r
 201 \r
 202       // insert n into L\r
 203       nodeList.add(node);\r
 204 \r
 205       // for each node m with an edge e from n to m do\r
 206       for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {\r
 207         // remove edge e from the graph\r
 208         Edge edge = it.next();\r
 209         Node to = edge.to;\r
 210         it.remove();// Remove edge from n\r
 211         to.inEdges.remove(edge);// Remove edge from m\r
 212 \r
 213         // if m has no other incoming edges then insert m into S\r
 214         if (to.inEdges.isEmpty()) {\r
 215           nodeSet.add(to);\r
 216         }\r
 217       }\r
 218     }\r
 219     // Check to see if all edges are removed\r
 220     boolean cycle = false;\r
 221     for (Node node : unsortedNodes) {\r
 222       if (!node.inEdges.isEmpty()) {\r
 223         cycle = true;\r
 224         break;\r
 225       }\r
 226     }\r
 227     if (cycle) {\r
 228       throw new RuntimeException(\r
 229           "Circular dependency present between models, topological sort not possible");\r
 230     }\r
 231 \r
 232     return nodeList;\r
 233   }\r
 234 \r
 235 }\r