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

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