src/main/java/org/onap/aai/modelloader/entity/model/ModelSorter.java

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