appc-dg/appc-dg-shared/appc-dg-dependency-model/src/main/java/org/openecomp/appc/dg/flowbuilder/impl/ReverseFlowStrategy.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * openECOMP : APP-C
   4  * ================================================================================
   5  * Copyright (C) 2017 AT&T Intellectual Property. All rights
   6  *                                              reserved.
   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
  22 package org.openecomp.appc.dg.flowbuilder.impl;
  23
  24 import java.util.*;
  25
  26 import org.openecomp.appc.dg.flowbuilder.exception.InvalidDependencyModel;
  27 import org.openecomp.appc.domainmodel.Vnfc;
  28
  29
  30 public class ReverseFlowStrategy extends AbstractFlowStrategy {
  31
  32     @Override
  33     protected List<List<Vnfc>> orderDependencies() {
  34         ArrayList<List<Vnfc>> arrayList = new ArrayList<>();
  35
  36         Queue<Vnfc> queue1 = new LinkedList();
  37         Set<Vnfc> queue2 = new LinkedHashSet<>();
  38
  39         Set<Vnfc> uniqueElementSet = new HashSet<>();
  40         Set<Vnfc> duplicateElementSet = new HashSet<>();
  41
  42         // identifying independent nodes in queue1
  43         for(int colIndex=0;colIndex<graph.getSize();colIndex++){
  44             Integer sum = 0;
  45             for(int rowIndex=0;rowIndex<graph.getSize();rowIndex++){
  46                 sum+= graph.getDependencyMatrix()[rowIndex][colIndex];
  47             }
  48             if(sum==0){
  49                 Vnfc vnfc = graph.getVertexList().get(colIndex);
  50                 queue1.add(vnfc);
  51             }
  52         }
  53         if(queue1.isEmpty()){
  54             throw new InvalidDependencyModel("There seems to be no leaf node for Vnfc dependencies");
  55         }
  56         arrayList.add((List<Vnfc>)queue1);
  57         queue1 = new LinkedList<>(queue1);
  58
  59         boolean flag = true;
  60
  61         while(flag){
  62             // iterating over queue1 and for each node in it finding all dependent nodes and putting them on queue2
  63             while(!queue1.isEmpty()){
  64                 Vnfc listItem = queue1.remove();
  65                 Integer rowIndex = graph.getIndex(listItem);
  66                 for(Integer index =0;index<graph.getSize();index++){
  67                     Integer value = graph.getDependencyMatrix()[rowIndex][index];
  68                     if(value ==1){
  69                         Vnfc vnfc = graph.getVertexList().get(index);
  70                         queue2.add(vnfc);
  71                     }
  72                 }
  73             }
  74             for(Vnfc vnfc:queue2){
  75                 if(!uniqueElementSet.add(vnfc)){
  76                     duplicateElementSet.add(vnfc);
  77                 }
  78             }
  79             if(queue2.isEmpty()){
  80                 flag= false; // empty queue2 indicates that all leaf nodes have been identified, i.e. stop the iteration
  81             }
  82             else{
  83                 arrayList.add(new ArrayList<Vnfc>(queue2));
  84                 if(arrayList.size()>graph.getSize()){
  85                     // dependency list cannot be larger than total number of nodes
  86                     // if it happens indicates cycle in the dependency
  87                     throw new InvalidDependencyModel("Cycle detected in the VNFC dependencies");
  88                 }
  89                 queue1.addAll(queue2);
  90                 queue2 = new LinkedHashSet<>();
  91             }
  92         }
  93         // If any node depends on multiple nodes present in different execution sequence,
  94         // its execution should happen on the higher order, removing its presence on lower execution sequence
  95         if(!duplicateElementSet.isEmpty()){
  96             for(Vnfc vnfc:duplicateElementSet){
  97                 boolean firstOccurrence= true;
  98                 for(int i=0;i<arrayList.size();i++){
  99                     List<Vnfc> list = arrayList.get(i);
 100                     if(list.contains(vnfc)){
 101                         if(firstOccurrence){
 102                             firstOccurrence =false;
 103                             list.remove(vnfc);
 104                         }
 105                         else{
 106                             continue;
 107                         }
 108                     }
 109
 110                 }
 111             }
 112         }
 113         return  arrayList;
 114     }
 115 }