package org.jboss.da.communication.aprox.model;

import org.jboss.da.model.rest.GAV;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.NoArgsConstructor;
import lombok.NonNull;
import lombok.RequiredArgsConstructor;
import lombok.Setter;

@NoArgsConstructor
@RequiredArgsConstructor
@AllArgsConstructor
public class GAVDependencyTree implements Comparable<GAVDependencyTree> {

    @Getter
    @Setter
    @NonNull
    private GAV gav;

    @Getter
    private Set<GAVDependencyTree> dependencies = new TreeSet<>();

    public void addDependency(GAVDependencyTree dep) {
        dependencies.add(dep);
    }

    /**
     * Prune duplicate subtrees leaving one instance for each duplicate.
     */
    public void prune(){
        Map<GAV, Set<GAVDependencyTree>> forest = new HashMap<>();
        fillForest(this, forest);
        Map<GAV, Set<GAVDependencyTree>> candidates = forest.entrySet().stream()
                .filter(e -> e.getValue().size() > 1)
                .collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue()));
              
        int previous;
        do{
            previous = candidates.size();
            pruneLeaves(this, candidates);
        }while(!candidates.isEmpty() && previous > candidates.size());
    }

    private static void fillForest(GAVDependencyTree tree, Map<GAV, Set<GAVDependencyTree>> forest) {
        Set<GAVDependencyTree> trees = forest.computeIfAbsent(tree.getGav(), (k) -> new HashSet<>());
        trees.add(tree);
        for(GAVDependencyTree t : tree.getDependencies()){
            fillForest(t, forest);
        }
    }

    private static void pruneLeaves(GAVDependencyTree tree,
            Map<GAV, Set<GAVDependencyTree>> candidates) {
        // Sort the dependencies by GAV so the prunnig will be deterministic
        List<GAVDependencyTree> deps = new ArrayList<>(tree.getDependencies());
        Collections.sort(deps, (a,b) -> a.gav.toString().compareTo(b.gav.toString()));

        for (GAVDependencyTree d : deps) {
            pruneLeaves(d, candidates);
        }
        Iterator<GAVDependencyTree> it = tree.getDependencies().iterator();
        while (it.hasNext()) {
            GAVDependencyTree d = it.next();
            if (d.getDependencies().isEmpty() && candidates.containsKey(d.getGav())) {
                it.remove();
                Set<GAVDependencyTree> forest = candidates.get(d.getGav());
                forest.remove(d);
                if (forest.size() <= 1) {
                    candidates.remove(d.getGav());
                }
            }
        }
    }

    @Override
    public int compareTo(GAVDependencyTree o) {
        return this.gav.compareTo(o.gav);
    }
}

@@ -100,47 +100,13 @@
 til.
-ArrayList;%0Aimport java.util.Collections
+Deque
 ;%0Aim
@@ -199,16 +199,22 @@
 va.util.
+Linked
 List;%0Aim
@@ -229,24 +229,48 @@
 a.util.Map;%0A
+import java.util.Queue;%0A
 import java.
@@ -2000,76 +2000,63 @@
     
-// Sort the dependencies by GAV so the prunnig will be deterministic
+Queue%3CGAVDependencyTree%3E bfsQueue = new LinkedList%3C%3E();
 %0A   
@@ -2060,20 +2060,21 @@
         
-List
+Deque
 %3CGAVDepe
@@ -2089,54 +2089,163 @@
 ee%3E 
-deps
+reverseLevelOrder
  = new 
-Array
+Linked
 List%3C%3E(
-tree.getDependencies
+);%0A        bfsQueue.add(tree);%0A        while (!bfsQueue.isEmpty()) %7B%0A            GAVDependencyTree t = bfsQueue.poll
 ()
-)
 ;%0A  
@@ -2254,87 +2254,199 @@
     
+ 
-Collections.sort(deps, (a,b) -%3E a.gav.toString().compareTo(b.gav.toString()));%0A
+   reverseLevelOrder.push(t);%0A            for (GAVDependencyTree d : t.dependencies) %7B%0A                bfsQueue.add(d);%0A            %7D%0A        %7D%0A        while (!reverseLevelOrder.isEmpty()) %7B
 %0A   
@@ -2442,37 +2442,36 @@
 ty()) %7B%0A        
-for (
+    
 GAVDependencyTre
@@ -2476,19 +2476,36 @@
 ree 
-d : deps) %7B
+t = reverseLevelOrder.pop();
 %0A   
@@ -2525,13 +2525,11 @@
 eLea
-ves(d
+f(t
 , ca
@@ -2541,32 +2541,156 @@
 tes);%0A        %7D%0A
+    %7D%0A%0A    private static void pruneLeaf(GAVDependencyTree tree,%0A            Map%3CGAV, Set%3CGAVDependencyTree%3E%3E candidates) %7B%0A
         Iterator

Fix pruning of GAVDependencyTree by pruning deapest leaves first