svn commit: r1305050 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning: DefaultSpanningTreeSourceSelector.java ReverseDeleteGraph.java

[marcosperanza]

Author: marcosperanza
Date: Sun Mar 25 14:27:24 2012
New Revision: 1305050

URL: http://svn.apache.org/viewvc?rev=1305050&view=rev
Log:
Replaced unordered list with a sorted queue.

Modified:
    
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
    
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java

Modified: 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
URL: 
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java?rev=1305050&r1=1305049&r2=1305050&view=diff
==============================================================================
--- 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
 (original)
+++ 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/DefaultSpanningTreeSourceSelector.java
 Sun Mar 25 14:27:24 2012
@@ -20,14 +20,14 @@ package org.apache.commons.graph.spannin
  */
 
 import static java.util.Collections.reverseOrder;
-import static java.util.Collections.sort;
 import static org.apache.commons.graph.CommonsGraph.findShortestPath;
 import static org.apache.commons.graph.utils.Assertions.checkNotNull;
 import static org.apache.commons.graph.utils.Assertions.checkState;
 
 import java.util.ArrayList;
-import java.util.Iterator;
 import java.util.List;
+import java.util.PriorityQueue;
+import java.util.Queue;
 
 import org.apache.commons.graph.Graph;
 import org.apache.commons.graph.Mapper;
@@ -86,23 +86,20 @@ final class DefaultSpanningTreeSourceSel
 
         checkNotNull( weightOperations, "The Reverse-Delete algorithm cannot 
be calulated with null weight operations" );
 
-        final List<WE> sortedEdge = new ArrayList<WE>();
+        final Queue<WE> sortedEdge = new PriorityQueue<WE>( 11, reverseOrder( 
new WeightedEdgesComparator<W, WE>( weightOperations, weightedEdges ) ) );
         final List<WE> visitedEdge = new ArrayList<WE>();
 
         Iterable<WE> edges = graph.getEdges();
         for ( WE we : edges )
         {
-            sortedEdge.add( we );
+            sortedEdge.offer( we );
         }
 
-        sort( sortedEdge, reverseOrder( new WeightedEdgesComparator<W, WE>( 
weightOperations, weightedEdges ) ) );
-
         Graph<V, WE> tmpGraph = new ReverseDeleteGraph<V, WE>( graph, 
sortedEdge, visitedEdge );
 
-        for ( Iterator<WE> iterator = sortedEdge.iterator(); 
iterator.hasNext(); )
+        for ( int i = 0; i < sortedEdge.size(); i++ ) 
         {
-            WE we = iterator.next();
-            iterator.remove();
+            WE we = sortedEdge.poll();
 
             VertexPair<V> vertices = graph.getVertices( we );
 

Modified: 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
URL: 
http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java?rev=1305050&r1=1305049&r2=1305050&view=diff
==============================================================================
--- 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
 (original)
+++ 
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/spanning/ReverseDeleteGraph.java
 Sun Mar 25 14:27:24 2012
@@ -20,6 +20,7 @@ package org.apache.commons.graph.spannin
  */
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 
 import org.apache.commons.graph.Graph;
@@ -38,11 +39,11 @@ final class ReverseDeleteGraph<V, WE>
 
     private final Graph<V, WE> graph;
 
-    private final List<WE> sortedEdge;
+    private final Collection<WE> sortedEdge;
 
-    private final List<WE> visitedEdge;
+    private final Collection<WE> visitedEdge;
 
-    public ReverseDeleteGraph( Graph<V, WE> graph, List<WE> sortedEdge, 
List<WE> visitedEdge )
+    public ReverseDeleteGraph( Graph<V, WE> graph, Collection<WE> sortedEdge, 
Collection<WE> visitedEdge )
     {
         this.graph = graph;
         this.sortedEdge = sortedEdge;