package org.eclipse.aether.util.graph.transformer;
   
   /*
    * Licensed to the Apache Software Foundation (ASF) under one
    * or more contributor license agreements.  See the NOTICE file
    * distributed with this work for additional information
    * regarding copyright ownership.  The ASF licenses this file
    * to you under the Apache License, Version 2.0 (the
    * "License"); you may not use this file except in compliance
   * with the License.  You may obtain a copy of the License at
   * 
   *  http://www.apache.org/licenses/LICENSE-2.0
   * 
   * Unless required by applicable law or agreed to in writing,
   * software distributed under the License is distributed on an
   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   * KIND, either express or implied.  See the License for the
   * specific language governing permissions and limitations
   * under the License.
   */
  
  import java.util.Collection;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.IdentityHashMap;
  import java.util.Map;
  import java.util.Set;
  
  import org.eclipse.aether.RepositoryException;
  import org.eclipse.aether.artifact.Artifact;
  import org.eclipse.aether.collection.DependencyGraphTransformationContext;
  import org.eclipse.aether.collection.DependencyGraphTransformer;
  import org.eclipse.aether.graph.Dependency;
  import org.eclipse.aether.graph.DependencyNode;
  
  /**
   * A dependency graph transformer that identifies conflicting dependencies. When this transformer has executed, the
   * transformation context holds a {@code Map<DependencyNode, Object>} where dependency nodes that belong to the same
   * conflict group will have an equal conflict identifier. This map is stored using the key
   * {@link TransformationContextKeys#CONFLICT_IDS}.
   */
  public final class ConflictMarker
      implements DependencyGraphTransformer
  {
  
      /**
       * After the execution of this method, every DependencyNode with an attached dependency is member of one conflict
       * group.
       * 
       * @see DependencyGraphTransformer#transformGraph(DependencyNode, DependencyGraphTransformationContext)
       */
      public DependencyNode transformGraph( DependencyNode node, DependencyGraphTransformationContext context )
          throws RepositoryException
      {
          @SuppressWarnings( "unchecked" )
          Map<String, Object> stats = (Map<String, Object>) context.get( TransformationContextKeys.STATS );
          long time1 = System.nanoTime();
  
          Map<DependencyNode, Object> nodes = new IdentityHashMap<DependencyNode, Object>( 1024 );
          Map<Object, ConflictGroup> groups = new HashMap<Object, ConflictGroup>( 1024 );
  
          analyze( node, nodes, groups, new int[] { 0 } );
  
          long time2 = System.nanoTime();
  
          Map<DependencyNode, Object> conflictIds = mark( nodes.keySet(), groups );
  
          context.put( TransformationContextKeys.CONFLICT_IDS, conflictIds );
  
          if ( stats != null )
          {
              long time3 = System.nanoTime();
              stats.put( "ConflictMarker.analyzeTime", time2 - time1 );
              stats.put( "ConflictMarker.markTime", time3 - time2 );
              stats.put( "ConflictMarker.nodeCount", nodes.size() );
          }
  
          return node;
      }
  
      private void analyze( DependencyNode node, Map<DependencyNode, Object> nodes, Map<Object, ConflictGroup> groups,
                            int[] counter )
      {
          if ( nodes.put( node, Boolean.TRUE ) != null )
          {
              return;
          }
  
          Set<Object> keys = getKeys( node );
          if ( !keys.isEmpty() )
          {
              ConflictGroup group = null;
              boolean fixMappings = false;
  
              for ( Object key : keys )
              {
                  ConflictGroup g = groups.get( key );
  
                 if ( group != g )
                 {
                     if ( group == null )
                     {
                         Set<Object> newKeys = merge( g.keys, keys );
                         if ( newKeys == g.keys )
                         {
                             group = g;
                             break;
                         }
                         else
                         {
                             group = new ConflictGroup( newKeys, counter[0]++ );
                             fixMappings = true;
                         }
                     }
                     else if ( g == null )
                     {
                         fixMappings = true;
                     }
                     else
                     {
                         Set<Object> newKeys = merge( g.keys, group.keys );
                         if ( newKeys == g.keys )
                         {
                             group = g;
                             fixMappings = false;
                             break;
                         }
                         else if ( newKeys != group.keys )
                         {
                             group = new ConflictGroup( newKeys, counter[0]++ );
                             fixMappings = true;
                         }
                     }
                 }
             }
 
             if ( group == null )
             {
                 group = new ConflictGroup( keys, counter[0]++ );
                 fixMappings = true;
             }
             if ( fixMappings )
             {
                 for ( Object key : group.keys )
                 {
                     groups.put( key, group );
                 }
             }
         }
 
         for ( DependencyNode child : node.getChildren() )
         {
             analyze( child, nodes, groups, counter );
         }
     }
 
     private Set<Object> merge( Set<Object> keys1, Set<Object> keys2 )
     {
         int size1 = keys1.size();
         int size2 = keys2.size();
 
         if ( size1 < size2 )
         {
             if ( keys2.containsAll( keys1 ) )
             {
                 return keys2;
             }
         }
         else
         {
             if ( keys1.containsAll( keys2 ) )
             {
                 return keys1;
             }
         }
 
         Set<Object> keys = new HashSet<Object>();
         keys.addAll( keys1 );
         keys.addAll( keys2 );
         return keys;
     }
 
     private Set<Object> getKeys( DependencyNode node )
     {
         Set<Object> keys;
 
         Dependency dependency = node.getDependency();
 
         if ( dependency == null )
         {
             keys = Collections.emptySet();
         }
         else
         {
             Object key = toKey( dependency.getArtifact() );
 
             if ( node.getRelocations().isEmpty() && node.getAliases().isEmpty() )
             {
                 keys = Collections.singleton( key );
             }
             else
             {
                 keys = new HashSet<Object>();
                 keys.add( key );
 
                 for ( Artifact relocation : node.getRelocations() )
                 {
                     key = toKey( relocation );
                     keys.add( key );
                 }
 
                 for ( Artifact alias : node.getAliases() )
                 {
                     key = toKey( alias );
                     keys.add( key );
                 }
             }
         }
 
         return keys;
     }
 
     private Map<DependencyNode, Object> mark( Collection<DependencyNode> nodes, Map<Object, ConflictGroup> groups )
     {
         Map<DependencyNode, Object> conflictIds = new IdentityHashMap<DependencyNode, Object>( nodes.size() + 1 );
 
         for ( DependencyNode node : nodes )
         {
             Dependency dependency = node.getDependency();
             if ( dependency != null )
             {
                 Object key = toKey( dependency.getArtifact() );
                 conflictIds.put( node, groups.get( key ).index );
             }
         }
 
         return conflictIds;
     }
 
     private static Object toKey( Artifact artifact )
     {
         return new Key( artifact );
     }
 
     static class ConflictGroup
     {
 
         final Set<Object> keys;
 
         final int index;
 
         ConflictGroup( Set<Object> keys, int index )
         {
             this.keys = keys;
             this.index = index;
         }
 
         @Override
         public String toString()
         {
             return String.valueOf( keys );
         }
 
     }
 
     static class Key
     {
 
         private final Artifact artifact;
 
         Key( Artifact artifact )
         {
             this.artifact = artifact;
         }
 
         @Override
         public boolean equals( Object obj )
         {
             if ( obj == this )
             {
                 return true;
             }
             else if ( !( obj instanceof Key ) )
             {
                 return false;
             }
             Key that = (Key) obj;
             return artifact.getArtifactId().equals( that.artifact.getArtifactId() )
                 && artifact.getGroupId().equals( that.artifact.getGroupId() )
                 && artifact.getExtension().equals( that.artifact.getExtension() )
                 && artifact.getClassifier().equals( that.artifact.getClassifier() );
         }
 
         @Override
         public int hashCode()
         {
             int hash = 17;
             hash = hash * 31 + artifact.getArtifactId().hashCode();
             hash = hash * 31 + artifact.getGroupId().hashCode();
             hash = hash * 31 + artifact.getClassifier().hashCode();
             hash = hash * 31 + artifact.getExtension().hashCode();
             return hash;
         }
 
         @Override
         public String toString()
         {
             return artifact.getGroupId() + ':' + artifact.getArtifactId() + ':' + artifact.getClassifier() + ':'
                 + artifact.getExtension();
         }
 
     }
 
 }