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