commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1295586 - /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
Date Thu, 01 Mar 2012 14:39:20 GMT
Author: simonetripodi
Date: Thu Mar  1 14:39:20 2012
New Revision: 1295586

URL: http://svn.apache.org/viewvc?rev=1295586&view=rev
Log:
there's no needs of an Aux class that wraps the linked list

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java?rev=1295586&r1=1295585&r2=1295586&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/visit/DefaultVisitAlgorithmsSelector.java
Thu Mar  1 14:39:20 2012
@@ -24,9 +24,7 @@ import static org.apache.commons.graph.u
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
-import java.util.Queue;
 import java.util.Set;
-import java.util.Stack;
 
 import org.apache.commons.graph.DirectedGraph;
 import org.apache.commons.graph.Edge;
@@ -76,7 +74,7 @@ final class DefaultVisitAlgorithmsSelect
      */
     public <O> O applyingBreadthFirstSearch( GraphVisitHandler<V, E, G, O> handler
)
     {
-        return applyingSearch( handler, new QueueOrStack<V>( true ) );
+        return applyingSearch( handler, true );
     }
 
     /**
@@ -84,7 +82,7 @@ final class DefaultVisitAlgorithmsSelect
      */
     public <O> O applyingDepthFirstSearch( GraphVisitHandler<V, E, G, O> handler
)
     {
-        return applyingSearch( handler, new QueueOrStack<V>( false ) );
+        return applyingSearch( handler, false );
     }
 
     /**
@@ -98,16 +96,18 @@ final class DefaultVisitAlgorithmsSelect
      * </ul>
      *
      * @param handler the handler intercepts visits
-     * @param vertexList the collection used to traverse the graph
+     * @param enqueue defines the collection behavior used to traverse the graph: true is
a Queue, false is a Stack
      * @return the result of {@link GraphVisitHandler#onCompleted()}
      */
-    private <O> O applyingSearch( GraphVisitHandler<V, E, G, O> handler, QueueOrStack<V>
vertexList )
+    private <O> O applyingSearch( GraphVisitHandler<V, E, G, O> handler, boolean
enqueue )
     {
         handler = checkNotNull( handler, "Graph visitor handler can not be null." );
 
         handler.discoverGraph( graph );
 
-        vertexList.push( new VertexPair<V>( source, source ) );
+        final LinkedList<VertexPair<V>> vertexList = new LinkedList<VertexPair<V>>();
+
+        vertexList.addLast( new VertexPair<V>( source, source ) );
 
         final Set<V> visitedVertices = new HashSet<V>();
         visitedVertices.add( source );
@@ -116,7 +116,8 @@ final class DefaultVisitAlgorithmsSelect
 
         while ( visitingGraph && !vertexList.isEmpty() )
         {
-            final VertexPair<V> pair = vertexList.pop();
+            // if dequeue, remove the first element, otherwise the last
+            final VertexPair<V> pair = enqueue ? vertexList.removeFirst() : vertexList.removeLast();
             final V v = pair.getHead();
             final V prevHead = pair.getTail();
             final E e = prevHead.equals( v ) ? null : graph.getEdge( prevHead, v );
@@ -148,7 +149,7 @@ final class DefaultVisitAlgorithmsSelect
                     V w = connected.next();
                     if ( !visitedVertices.contains( w ) )
                     {
-                        vertexList.push( new VertexPair<V>( w, v ) );
+                        vertexList.addLast( new VertexPair<V>( w, v ) );
                         visitedVertices.add( w );
                     }
                 }
@@ -165,63 +166,4 @@ final class DefaultVisitAlgorithmsSelect
         return handler.onCompleted();
     }
 
-    /**
-     * A wrapper class around a {@link LinkedList} to provide a common
-     * interface for {@link Stack} or {@link Queue} implementations. The class
-     * is used to support a common algorithm for depth-first and breadth-first
-     * search, by switching from queue (FIFO) to stack (LIFO) behavior.
-     *
-     * @param <V> the Graph vertices type
-     */
-    private static final class QueueOrStack<V extends Vertex>
-    {
-        /** indicated the collection behavior. */
-        private boolean isQueue;
-
-        /** the underlying linked list implementation. */
-        private final LinkedList<VertexPair<V>> list;
-
-        /**
-         * Create a new {@link QueueOrStack} instance with the desired
-         * behavior, indicated by <code>isQueue</code>.
-         *
-         * @param isQueue if <code>true</code> the collection behaves as a FIFO
queue,
-         * otherwise as a LIFO stack.
-         */
-        public QueueOrStack( final boolean isQueue )
-        {
-            this.isQueue = isQueue;
-            this.list = new LinkedList<VertexPair<V>>();
-        }
-
-        /**
-         * Add an element to the collection.
-         *
-         * @param element the element to be added
-         */
-        public void push( VertexPair<V> element )
-        {
-            list.addLast( element );
-        }
-
-        /**
-         * Removes and returns the element from the collection according to the
-         * defined behavior (LIFO vs. FIFO).
-         * @return the next element
-         */
-        public VertexPair<V> pop()
-        {
-            return isQueue ? list.removeFirst() : list.removeLast();
-        }
-
-        /**
-         * Returns <code>true</code> if the collection contains no elements.
-         * @return <code>true</code> if the collection is empty, <code>false</code>
otherwise
-         */
-        public boolean isEmpty()
-        {
-            return list.isEmpty();
-        }
-    }
-
 }



Mime
View raw message