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.ArrayList;
  import java.util.Collection;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  
  import org.eclipse.aether.RepositoryException;
  import org.eclipse.aether.collection.UnsolvableVersionConflictException;
  import org.eclipse.aether.graph.DependencyFilter;
  import org.eclipse.aether.graph.DependencyNode;
  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictContext;
  import org.eclipse.aether.util.graph.transformer.ConflictResolver.ConflictItem;
  import org.eclipse.aether.util.graph.transformer.ConflictResolver.VersionSelector;
  import org.eclipse.aether.util.graph.visitor.PathRecordingDependencyVisitor;
  import org.eclipse.aether.version.Version;
  import org.eclipse.aether.version.VersionConstraint;
  
  /**
   * A version selector for use with {@link ConflictResolver} that resolves version conflicts using a nearest-wins
   * strategy. If there is no single node that satisfies all encountered version ranges, the selector will fail.
   */
  public final class NearestVersionSelector
      extends VersionSelector
  {
  
      /**
       * Creates a new instance of this version selector.
       */
      public NearestVersionSelector()
      {
      }
  
      @Override
      public void selectVersion( ConflictContext context )
          throws RepositoryException
      {
          ConflictGroup group = new ConflictGroup();
          for ( ConflictItem item : context.getItems() )
          {
              DependencyNode node = item.getNode();
              VersionConstraint constraint = node.getVersionConstraint();
  
              boolean backtrack = false;
              boolean hardConstraint = constraint.getRange() != null;
  
              if ( hardConstraint )
              {
                  if ( group.constraints.add( constraint ) )
                  {
                      if ( group.winner != null && !constraint.containsVersion( group.winner.getNode().getVersion() ) )
                      {
                          backtrack = true;
                      }
                  }
              }
  
              if ( isAcceptable( group, node.getVersion() ) )
              {
                  group.candidates.add( item );
  
                  if ( backtrack )
                  {
                      backtrack( group, context );
                  }
                  else if ( group.winner == null || isNearer( item, group.winner ) )
                  {
                      group.winner = item;
                  }
              }
              else if ( backtrack )
              {
                  backtrack( group, context );
              }
          }
          context.setWinner( group.winner );
      }
  
      private void backtrack( ConflictGroup group, ConflictContext context )
         throws UnsolvableVersionConflictException
     {
         group.winner = null;
 
         for ( Iterator<ConflictItem> it = group.candidates.iterator(); it.hasNext(); )
         {
             ConflictItem candidate = it.next();
 
             if ( !isAcceptable( group, candidate.getNode().getVersion() ) )
             {
                 it.remove();
             }
             else if ( group.winner == null || isNearer( candidate, group.winner ) )
             {
                 group.winner = candidate;
             }
         }
 
         if ( group.winner == null )
         {
             throw newFailure( context );
         }
     }
 
     private boolean isAcceptable( ConflictGroup group, Version version )
     {
         for ( VersionConstraint constraint : group.constraints )
         {
             if ( !constraint.containsVersion( version ) )
             {
                 return false;
             }
         }
         return true;
     }
 
     private boolean isNearer( ConflictItem item1, ConflictItem item2 )
     {
         if ( item1.isSibling( item2 ) )
         {
             return item1.getNode().getVersion().compareTo( item2.getNode().getVersion() ) > 0;
         }
         else
         {
             return item1.getDepth() < item2.getDepth();
         }
     }
 
     private UnsolvableVersionConflictException newFailure( final ConflictContext context )
     {
         DependencyFilter filter = new DependencyFilter()
         {
             public boolean accept( DependencyNode node, List<DependencyNode> parents )
             {
                 return context.isIncluded( node );
             }
         };
         PathRecordingDependencyVisitor visitor = new PathRecordingDependencyVisitor( filter );
         context.getRoot().accept( visitor );
         return new UnsolvableVersionConflictException( visitor.getPaths() );
     }
 
     static final class ConflictGroup
     {
 
         final Collection<VersionConstraint> constraints;
 
         final Collection<ConflictItem> candidates;
 
         ConflictItem winner;
 
         ConflictGroup()
         {
             constraints = new HashSet<>();
             candidates = new ArrayList<>( 64 );
         }
 
         @Override
         public String toString()
         {
             return String.valueOf( winner );
         }
 
     }
 
 }