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 java.util.ArrayList;
  24 import java.util.Collection;
  25 import java.util.HashMap;
  26 import java.util.HashSet;
  27 import java.util.Iterator;
  28 import java.util.List;
  29 import java.util.Map;
  30 import java.util.Objects;
  31 import java.util.Set;
  32 import jline.internal.Log;
  33
  34 import org.onap.aai.modelloader.entity.Artifact;
  35
  36 /**
  37  * Utility class to sort the given Models according to their dependencies.<br>
  38  * Example: Given a list of Models [A, B, C] <br>
  39  * where B depends on A, and A depends 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
  48         private final AbstractModelArtifact model;
  49         private final HashSet<Edge> inEdges;
  50         private final HashSet<Edge> outEdges;
  51
  52         public Node(AbstractModelArtifact model) {
  53             this.model = model;
  54             inEdges = new HashSet<>();
  55             outEdges = new HashSet<>();
  56         }
  57
  58         public Node addEdge(Node node) {
  59             Edge edge = new Edge(this, node);
  60             outEdges.add(edge);
  61             node.inEdges.add(edge);
  62             return this;
  63         }
  64
  65         @Override
  66         public String toString() {
  67             return model.getUniqueIdentifier();
  68         }
  69
  70         @Override
  71         public boolean equals(Object other) {
  72             if (other == null || this.getClass() != other.getClass()) {
  73                 return false;
  74             }
  75             AbstractModelArtifact otherModel = ((Node) other).model;
  76             return this.model.getUniqueIdentifier().equals(otherModel.getUniqueIdentifier());
  77         }
  78
  79         @Override
  80         public int hashCode() {
  81             return this.model.getUniqueIdentifier().hashCode();
  82         }
  83     }
  84
  85     /**
  86      * Represents a dependency between two Nodes.
  87      */
  88     static class Edge {
  89
  90         public final Node from;
  91         public final Node to;
  92
  93         public Edge(Node from, Node to) {
  94             this.from = from;
  95             this.to = to;
  96         }
  97
  98         @Override
  99         public boolean equals(Object obj) {
 100             if (obj == null || this.getClass() != obj.getClass()) {
 101                 return false;
 102             }
 103             Edge edge = (Edge) obj;
 104             return edge.from == from && edge.to == to;
 105         }
 106
 107         @Override
 108         public int hashCode() {
 109             return Objects.hash(this.from, this.to);
 110         }
 111     }
 112
 113     /**
 114      * Returns the list of models sorted by order of dependency.
 115      *
 116      * @param originalList the list that needs to be sorted
 117      * @return a list of sorted models
 118      */
 119     public List<Artifact> sort(List<Artifact> originalList) {
 120
 121         if (originalList.size() <= 1) {
 122             return originalList;
 123         }
 124
 125         Collection<Node> nodes = createNodes(originalList);
 126         Collection<Node> sortedNodes = sortNodes(nodes);
 127
 128         List<Artifact> sortedModelsList = new ArrayList<>(sortedNodes.size());
 129         for (Node node : sortedNodes) {
 130             sortedModelsList.add(node.model);
 131         }
 132
 133         return sortedModelsList;
 134     }
 135
 136     /**
 137      * Create nodes from the list of models and their dependencies.
 138      *
 139      * @param models what the nodes creation is based upon
 140      * @return Collection of Node objects
 141      */
 142     private Collection<Node> createNodes(Collection<Artifact> models) {
 143
 144         // load list of models into a map, so we can later replace referenceIds with real Models
 145         Map<String, AbstractModelArtifact> versionIdToModelMap = new HashMap<>();
 146         for (Artifact art : models) {
 147             AbstractModelArtifact ma = (AbstractModelArtifact) art;
 148             versionIdToModelMap.put(ma.getUniqueIdentifier(), ma);
 149         }
 150
 151         Map<String, Node> nodes = new HashMap<>();
 152         // create a node for each model and its referenced models
 153         for (Artifact art : models) {
 154
 155             AbstractModelArtifact model = (AbstractModelArtifact) art;
 156
 157             // node might have been created by another model referencing it
 158             Node node = nodes.get(model.getUniqueIdentifier());
 159
 160             if (null == node) {
 161                 node = new Node(model);
 162                 nodes.put(model.getUniqueIdentifier(), node);
 163             }
 164
 165             for (String referencedModelId : model.getDependentModelIds()) {
 166                 // node might have been created by another model referencing it
 167                 Node referencedNode = nodes.get(referencedModelId);
 168
 169                 if (null == referencedNode) {
 170                     // create node
 171                     AbstractModelArtifact referencedModel = versionIdToModelMap.get(referencedModelId);
 172                     if (referencedModel == null) {
 173                         Log.debug("ignoring " + referencedModelId);
 174                         continue; // referenced model not supplied, no need to sort it
 175                     }
 176                     referencedNode = new Node(referencedModel);
 177                     nodes.put(referencedModelId, referencedNode);
 178                 }
 179                 referencedNode.addEdge(node);
 180             }
 181         }
 182
 183         return nodes.values();
 184     }
 185
 186     /**
 187      * Sorts the given Nodes by order of dependency.
 188      *
 189      * @param unsortedNodes the collection of nodes to be sorted
 190      * @return a sorted collection of the given nodes
 191      */
 192     private Collection<Node> sortNodes(Collection<Node> unsortedNodes) {
 193         // L <- Empty list that will contain the sorted elements
 194         List<Node> nodeList = new ArrayList<>();
 195
 196         // S <- Set of all nodes with no incoming edges
 197         Set<Node> nodeSet = new HashSet<>();
 198         for (Node unsortedNode : unsortedNodes) {
 199             if (unsortedNode.inEdges.isEmpty()) {
 200                 nodeSet.add(unsortedNode);
 201             }
 202         }
 203
 204         // while S is non-empty do
 205         while (!nodeSet.isEmpty()) {
 206             // remove a node n from S
 207             Node node = nodeSet.iterator().next();
 208             nodeSet.remove(node);
 209
 210             // insert n into L
 211             nodeList.add(node);
 212
 213             // for each node m with an edge e from n to m do
 214             for (Iterator<Edge> it = node.outEdges.iterator(); it.hasNext();) {
 215                 // remove edge e from the graph
 216                 Edge edge = it.next();
 217                 Node to = edge.to;
 218                 it.remove();// Remove edge from n
 219                 to.inEdges.remove(edge);// Remove edge from m
 220
 221                 // if m has no other incoming edges then insert m into S
 222                 if (to.inEdges.isEmpty()) {
 223                     nodeSet.add(to);
 224                 }
 225             }
 226         }
 227         // Check to see if all edges are removed
 228         boolean cycle = false;
 229         for (Node node : unsortedNodes) {
 230             if (!node.inEdges.isEmpty()) {
 231                 cycle = true;
 232                 break;
 233             }
 234         }
 235         if (cycle) {
 236             throw new RuntimeException("Circular dependency present between models, topological sort not possible");
 237         }
 238
 239         return nodeList;
 240     }
 241
 242 }