source.dussan.org Git - archiva.git/blob

   1 package org.apache.maven.archiva.dependency.graph.tasks;
   2
   3 /*
   4  * Licensed to the Apache Software Foundation (ASF) under one
   5  * or more contributor license agreements.  See the NOTICE file
   6  * distributed with this work for additional information
   7  * regarding copyright ownership.  The ASF licenses this file
   8  * to you under the Apache License, Version 2.0 (the
   9  * "License"); you may not use this file except in compliance
  10  * with the License.  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,
  15  * software distributed under the License is distributed on an
  16  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  17  * KIND, either express or implied.  See the License for the
  18  * specific language governing permissions and limitations
  19  * under the License.
  20  */
  21
  22 import org.apache.maven.archiva.dependency.graph.DependencyGraph;
  23 import org.apache.maven.archiva.dependency.graph.DependencyGraphEdge;
  24 import org.apache.maven.archiva.dependency.graph.DependencyGraphKeys;
  25 import org.apache.maven.archiva.dependency.graph.DependencyGraphNode;
  26 import org.apache.maven.archiva.dependency.graph.walk.DependencyGraphVisitor;
  27
  28 import java.util.ArrayList;
  29 import java.util.Collections;
  30 import java.util.Comparator;
  31 import java.util.HashMap;
  32 import java.util.Iterator;
  33 import java.util.List;
  34 import java.util.Map;
  35
  36 /**
  37  * Perform a transitive reduction of the graph.
  38  *
  39  * @version $Id$
  40  */
  41 public class ReduceTransitiveEdgesVisitor
  42     extends AbstractReduceEdgeVisitor
  43     implements DependencyGraphVisitor
  44 {
  45     class EdgeInfo
  46     {
  47         public DependencyGraphEdge edge;
  48
  49         public int depth = Integer.MAX_VALUE;
  50     }
  51
  52     class EdgeInfoDepthComparator
  53         implements Comparator
  54     {
  55         public int compare( Object obj0, Object obj1 )
  56         {
  57             EdgeInfo edgeInfo0 = (EdgeInfo) obj0;
  58             EdgeInfo edgeInfo1 = (EdgeInfo) obj1;
  59
  60             return edgeInfo0.depth - edgeInfo1.depth;
  61         }
  62     }
  63
  64     /**
  65      * A Map of &lt;(Node To) ArtifactReference, Map of &lt;(Node From) ArtifactReference, EdgeInfo&gt;&gt;
  66      */
  67     private Map /*<ArtifactReference,<ArtifactReference,EdgeInfo>>*/nodeDistanceMap = new HashMap();
  68
  69     private int currentDepth;
  70
  71     public void discoverGraph( DependencyGraph graph )
  72     {
  73         super.discoverGraph( graph );
  74         nodeDistanceMap.clear();
  75         currentDepth = 0;
  76     }
  77
  78     public void discoverEdge( DependencyGraphEdge edge )
  79     {
  80         /* WARNING: it is unwise to remove the edge at this point.
  81          *          as modifying the graph as it's being walked is dangerous.
  82          *
  83          * Just record the edge's current depth.
  84          */
  85
  86         String nodeTo = DependencyGraphKeys.toKey( edge.getNodeTo() );
  87         String nodeFrom = DependencyGraphKeys.toKey( edge.getNodeFrom() );
  88
  89         // Get sub-map
  90         Map edgeInfoMap = (Map) nodeDistanceMap.get( nodeTo );
  91
  92         // Create sub-map if not present (yet)
  93         if ( edgeInfoMap == null )
  94         {
  95             edgeInfoMap = new HashMap();
  96             nodeDistanceMap.put( nodeTo, edgeInfoMap );
  97         }
  98
  99         // Get sub-map-value.
 100         EdgeInfo edgeInfo = (EdgeInfo) edgeInfoMap.get( nodeFrom );
 101
 102         if ( edgeInfo == null )
 103         {
 104             // Create a new edgeinfo.
 105             edgeInfo = new EdgeInfo();
 106             edgeInfo.edge = edge;
 107             edgeInfo.depth = currentDepth;
 108             edgeInfoMap.put( nodeFrom, edgeInfo );
 109         }
 110         // test the current depth, if it is less than previous depth, save it
 111         else if ( currentDepth < edgeInfo.depth )
 112         {
 113             edgeInfo.depth = currentDepth;
 114             edgeInfoMap.put( nodeFrom, edgeInfo );
 115         }
 116
 117         nodeDistanceMap.put( nodeTo, edgeInfoMap );
 118     }
 119
 120     public void discoverNode( DependencyGraphNode node )
 121     {
 122         super.discoverNode( node );
 123         currentDepth++;
 124
 125     }
 126
 127     public void finishNode( DependencyGraphNode node )
 128     {
 129         super.finishNode( node );
 130         currentDepth--;
 131     }
 132
 133     public void finishGraph( DependencyGraph graph )
 134     {
 135         super.finishGraph( graph );
 136
 137         // Now we prune/remove the edges that are transitive in nature.
 138
 139         Comparator edgeInfoDepthComparator = new EdgeInfoDepthComparator();
 140
 141         Iterator it = nodeDistanceMap.values().iterator();
 142         while ( it.hasNext() )
 143         {
 144             Map edgeInfoMap = (Map) it.next();
 145
 146             if ( edgeInfoMap.size() > 1 )
 147             {
 148                 List edgeInfos = new ArrayList();
 149                 edgeInfos.addAll( edgeInfoMap.values() );
 150                 Collections.sort( edgeInfos, edgeInfoDepthComparator );
 151
 152                 for ( int i = 1; i < edgeInfos.size(); i++ )
 153                 {
 154                     EdgeInfo edgeInfo = (EdgeInfo) edgeInfos.get( i );
 155                     graph.removeEdge( edgeInfo.edge );
 156                 }
 157             }
 158         }
 159     }
 160 }