package com.atlassian.plugin.manager;
   
   import com.atlassian.plugin.Plugin;
   import com.atlassian.plugin.PluginDependencies;
   import com.google.common.collect.ArrayListMultimap;
   import com.google.common.collect.Maps;
   import com.google.common.collect.Multimap;
   import com.google.common.collect.Sets;
   import io.atlassian.fugue.Pair;
  
  import javax.annotation.Nonnull;
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.Deque;
  import java.util.EnumSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.Set;
  import java.util.SortedMap;
  import java.util.TreeMap;
  
  import static io.atlassian.fugue.Pair.pair;
  
  /**
   * A collection of dependent plugins
   *
   * @since v4.0
   */
  final class DependentPlugins {
      private final SortedMap<Plugin, PluginDependencies.Type> plugins;
  
      /**
       * Obtain the plugins which require, possibly indirectly, given plugins specified by keys.
       * <p>
       * The plugins with given keys is not included in the returned map.
       * <p>
       * Plugins mapped by their most significant dependency type, with the following order of significance:
       * {@link PluginDependencies.Type#MANDATORY},{@link PluginDependencies.Type#OPTIONAL}, {@link
       * PluginDependencies.Type#DYNAMIC}.
       *
       * @param rootPluginKeys  plugin keys to list dependents of.
       * @param pluginList      a List of plugins
       * @param dependencyTypes only include plugins with these dependency types
       */
      public DependentPlugins(final Collection<String> rootPluginKeys, final Iterable<Plugin> pluginList, final Set<PluginDependencies.Type> dependencyTypes) {
          if (dependencyTypes.isEmpty()) {
              throw new IllegalArgumentException("Dependency types must be provided");
          }
          plugins = new TreeMap<>();
          final PluginDependencies.Type leastSignificantType = getLeastSignificantType(dependencyTypes);
          buildPluginDependencies(rootPluginKeys, dependencyTypes, dependencyMap(pluginList, leastSignificantType));
      }
  
      private void buildPluginDependencies(final Collection<String> rootPluginKeys,
                                           final Set<PluginDependencies.Type> dependencyTypes,
                                           final Multimap<String, Pair<Plugin, PluginDependencies.Type>> dependencies) {
          // A queue of the plugin keys with capped dependency type we have yet to explore dependencies of
          final DependencyQueue queue = new DependencyQueue();
  
          final Set<CappedDep> visited = Sets.newHashSet();
          for (String rootPluginKey : rootPluginKeys) {
              queue.addLast(new CappedDep(rootPluginKey, PluginDependencies.Type.MANDATORY));
              for (PluginDependencies.Type type : PluginDependencies.Type.values()) {
                  visited.add(new CappedDep(rootPluginKey, type));
              }
          }
  
          while (!queue.isEmpty()) {
              final CappedDep currentPlugin = queue.removeFirst();
              for (final Pair<Plugin, PluginDependencies.Type> pluginWithDependencyType : dependencies.get(currentPlugin.key)) {
                  final PluginDependencies.Type dependencyType = currentPlugin.cap(pluginWithDependencyType.right());
  
                  if (dependencyTypes.contains(dependencyType)) {
                      final Plugin dependentPlugin = pluginWithDependencyType.left();
                      final String dependentPluginKey = dependentPlugin.getKey();
  
                      final CappedDep newDep = new CappedDep(dependentPluginKey, dependencyType);
                      if (visited.add(newDep)) {
                          this.add(dependentPlugin, dependencyType);
  
                          queue.addLast(newDep);
                      }
                  }
  
              }
          }
      }
  
      /**
       * Compute dependencies map from a key to each plugin that requires it,
       * cutting out dependencies less significant than the leastSignificantType
       */
      private Multimap<String, Pair<Plugin, PluginDependencies.Type>> dependencyMap(final Iterable<Plugin> pluginList, final PluginDependencies.Type leastSignificantType) {
          final Multimap<String, Pair<Plugin, PluginDependencies.Type>> dependencies = ArrayListMultimap.create();
          for (final Plugin p : pluginList) {
              for (final Map.Entry<String, PluginDependencies.Type> keyType : p.getDependencies().getByPluginKey().entries()) {
                  if (!keyType.getValue().lessSignificant(leastSignificantType)) {
                     // Cut out dependencies that less significant that we want
                     dependencies.put(keyType.getKey(), pair(p, keyType.getValue()));
                 }
             }
         }
         return dependencies;
     }
 
     private PluginDependencies.Type getLeastSignificantType(final Set<PluginDependencies.Type> dependencyTypes) {
         PluginDependencies.Type leastSignificantType = PluginDependencies.Type.MANDATORY;
         for (final PluginDependencies.Type type : dependencyTypes) {
             if (type.lessSignificant(leastSignificantType)) {
                 leastSignificantType = type;
             }
         }
         return leastSignificantType;
     }
 
     /**
      * Add <code>plugin/dependencyType</code> to <code>map</code>.
      * <p>
      * Dependency significance will be followed when deciding to overwrite an existing type, with the following order:
      * {@link PluginDependencies.Type#MANDATORY},
      * {@link PluginDependencies.Type#OPTIONAL},
      * {@link PluginDependencies.Type#DYNAMIC}.
      */
     private void add(final Plugin plugin, final PluginDependencies.Type dependencyType) {
         final PluginDependencies.Type existingDependencyType = plugins.get(plugin);
         if (existingDependencyType == null || existingDependencyType.lessSignificant(dependencyType)) {
             plugins.put(plugin, dependencyType);
         }
     }
 
     public Iterable<String> toPluginKeyDependencyTypes(final Set<PluginDependencies.Type> dependencyTypes) {
         final List<String> output = new ArrayList<>();
         for (final Map.Entry<Plugin, PluginDependencies.Type> entry : plugins.entrySet()) {
             if (dependencyTypes.contains(entry.getValue())) {
                 output.add(entry.getKey().getKey() + "(" + entry.getValue() + ")");
             }
         }
         return output;
     }
 
     public Iterable<String> toPluginKeyDependencyTypes() {
         return toPluginKeyDependencyTypes(EnumSet.allOf(PluginDependencies.Type.class));
     }
 
     /**
      * Get all plugins
      *
      * @return a {@link Set} of plugins
      */
     public Set<Plugin> get() {
         return plugins.keySet();
     }
 
     public Set<Plugin> getByTypes(final Set<PluginDependencies.Type> dependencyTypes) {
         return Maps.filterEntries(plugins, input -> dependencyTypes.contains(input.getValue())).keySet();
     }
 
     /**
      * A dependecy with a cap on transient dependency type
      */
     private static class CappedDep {
         @Nonnull
         final public String key;
         @Nonnull
         final public PluginDependencies.Type cap;
 
         public CappedDep(final String key, final PluginDependencies.Type cap) {
             this.key = key;
             this.cap = cap;
         }
 
         // Cap the depType by significance
         public PluginDependencies.Type cap(final PluginDependencies.Type depType) {
             return depType.lessSignificant(cap) ? depType : cap;
         }
 
         @Override
         public boolean equals(final Object o) {
             if (this == o) {
                 return true;
             }
             if (o == null || getClass() != o.getClass()) {
                 return false;
             }
 
             final CappedDep cappedDep = (CappedDep) o;
 
             if (!key.equals(cappedDep.key)) {
                 return false;
             }
             return cap == cappedDep.cap;
         }
 
         @Override
         public int hashCode() {
             int result = key.hashCode();
             result = 31 * result + cap.hashCode();
             return result;
         }
     }
 
     /**
      * A queue of dependencies
      */
     private static class DependencyQueue {
         private final Deque<CappedDep> queue = new ArrayDeque<>();
 
         public CappedDep removeFirst() {
             return queue.removeFirst();
         }
 
         public boolean isEmpty() {
             return queue.isEmpty();
         }
 
         /**
          * Add, replace or do nothing depending on the new dependency significance
          */
         public void addLast(final CappedDep newDep) {
             boolean addToQueue = true;
             for (final Iterator<CappedDep> iter = queue.iterator(); iter.hasNext(); ) {
                 final CappedDep next = iter.next();
 
                 if (next.key.equals(newDep.key)) {
                     addToQueue = next.cap(newDep.cap) != newDep.cap;
                     if (addToQueue) {
                         // remove if we have the same key lined up with less significant dependency
                         iter.remove();
                     }
                     // only one should exist in the queue
                     break;
                 }
             }
             if (addToQueue) {
                 queue.addLast(newDep);
             }
         }
     }
 }