package org.psjava.algo.graph.dfs;

import java.util.Iterator;
import java.util.function.Function;

import org.psjava.AdjacencyList;
import org.psjava.algo.graph.bfs.SimpleStopper;
import org.psjava.ds.PSCollection;
import org.psjava.ds.map.MutableMap;
import org.psjava.goods.GoodStackFactory;
import org.psjava.ds.stack.PSStack;
import org.psjava.goods.GoodMutableMapFactory;

public class DFSCore {

    private static class StackItem<V, E> {
        public V v;
        public E e;
        public int depth;
        Iterator<E> iter;

        StackItem(V v, E e, int d, Iterator<E> iter) {
            this.v = v;
            this.e = e;
            this.depth = d;
            this.iter = iter;
        }
    }

    public static <V> MutableMap<V, DFSStatus> createInitialStatus(PSCollection<V> vertices) {
        MutableMap<V, DFSStatus> r = GoodMutableMapFactory.getInstance().create();
        for (V v : vertices)
            r.add(v, DFSStatus.NOT_DISCOVERED); // TODO let empty as not discovered then vertices is not required
        return r;
    }

    public static <V, E> void traverse(AdjacencyList<V, E> adj, Function<E, V> destination, MutableMap<V, DFSStatus> status, V start, DFSVisitor<V, E> visitor) {
        PSStack<StackItem<V, E>> stack = GoodStackFactory.getInstance().create();
        status.replace(start, DFSStatus.DISCOVERED);
        SimpleStopper stopper = new SimpleStopper();
        visitor.onDiscovered(start, 0, stopper);
        Iterator<E> iterator = adj.get(start).iterator();
        stack.push(new StackItem<>(start, null, 0, iterator));

        while (!stack.isEmpty() && !stopper.isStopped()) {
            StackItem<V, E> item = stack.top();

            if (item.iter.hasNext()) {
                E edge = item.iter.next();
                V nextv = destination.apply(edge);
                DFSStatus nextc = status.get(nextv);
                if (nextc == DFSStatus.NOT_DISCOVERED) {
                    visitor.onWalkDown(edge);
                    status.replace(item.v, DFSStatus.DISCOVERED);
                    visitor.onDiscovered(nextv, item.depth + 1, stopper);
                    stack.push(new StackItem<>(nextv, edge, item.depth + 1, adj.get(nextv).iterator()));
                } else if (nextc == DFSStatus.DISCOVERED) {
                    visitor.onBackEdgeFound(edge);
                }
            } else {
                stack.pop();
                status.replace(item.v, DFSStatus.EXPLORED);
                visitor.onFinish(item.v, item.depth);
                if (item.e != null)
                    visitor.onWalkUp(item.e);
            }
        }
    }

    private DFSCore() {
    }

}

@@ -35,75 +35,8 @@
 %0D%0A%0D%0A
-import java.util.Iterator;%0D%0Aimport java.util.function.Function;%0D%0A%0D%0A
 impo
@@ -212,29 +212,34 @@
 a.goods.Good
-Stack
+MutableMap
 Factory;%0D%0Aim
@@ -240,90 +240,127 @@
 y;%0D%0A
+%0D%0A
 import 
-org.psjava.ds.stack.PSStack;%0D%0Aimport org.psjava.goods.GoodMutableMapFactory
+java.util.ArrayDeque;%0D%0Aimport java.util.Deque;%0D%0Aimport java.util.Iterator;%0D%0Aimport java.util.function.Function
 ;%0D%0A%0D
@@ -1242,15 +1242,13 @@
     
-PSStack
+Deque
 %3CSta
@@ -1273,45 +1273,24 @@
 k = 
-GoodStackFactory.getInstance().create
+new ArrayDeque%3C%3E
 ();%0D
@@ -1674,19 +1674,24 @@
 = stack.
-top
+peekLast
 ();%0D%0A%0D%0A 
@@ -2144,36 +2144,39 @@
           stack.
-push
+addLast
 (new StackItem%3C%3E
@@ -2413,17 +2413,22 @@
 stack.po
-p
+llLast
 ();%0D%0A   

remove one PSStack usage in DFSCore.