From d43046735ec9b1dd2b93aba4182cc8b94ee80f1c Mon Sep 17 00:00:00 2001
From: Kristóf Marussy <kristof@marussy.com>
Date: Thu, 31 Aug 2023 17:36:36 +0200
Subject: refactor(viatra): replace Stack with Deque

---
 .../viatra/runtime/rete/itc/alg/misc/scc/SCC.java  | 25 ++++++++++------------
 .../itc/alg/misc/topsort/TopologicalSorting.java   | 10 ++++-----
 2 files changed, 16 insertions(+), 19 deletions(-)

diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java
index f6ef9847..de070839 100644
--- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/scc/SCC.java
@@ -9,13 +9,10 @@
 
 package tools.refinery.viatra.runtime.rete.itc.alg.misc.scc;
 
-import java.util.HashSet;
-import java.util.Map;
-import java.util.Set;
-import java.util.Stack;
-
-import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
 import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
+
+import java.util.*;
 
 /**
  * Efficient algorithms to compute the Strongly Connected Components in a directed graph.
@@ -52,10 +49,10 @@ public class SCC<V> {
         Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap();
 
         // stores the nodes during the traversal
-        Stack<V> nodeStack = new Stack<V>();
+        Deque<V> nodeStack = new ArrayDeque<V>();
 
         // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time)
-        Stack<V> sccStack = new Stack<V>();
+        Deque<V> sccStack = new  ArrayDeque<V>();
 
         boolean sink = false, finishedTraversal = true;
 
@@ -71,14 +68,14 @@ public class SCC<V> {
                 nodeStack.push(n);
 
                 while (!nodeStack.isEmpty()) {
-                    V currentNode = nodeStack.peek();
+                    V currentNode = nodeStack.peekLast();
                     sink = false;
                     finishedTraversal = false;
                     SCCProperty prop = nodeMap.get(currentNode);
 
                     if (nodeMap.get(currentNode).getIndex() == 0) {
                         index++;
-                        sccStack.push(currentNode);
+                        sccStack.addLast(currentNode);
                         prop.setIndex(index);
                         prop.setLowlink(index);
 
@@ -97,7 +94,7 @@ public class SCC<V> {
                         if (targetNodeMap.get(currentNode).size() == 0) {
                             targetNodeMap.remove(currentNode);
 
-                            nodeStack.pop();
+                            nodeStack.removeLast();
 
                             for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) {
                                 if (notVisitedMap.get(currentNode).contains(targetNode)) {
@@ -115,13 +112,13 @@ public class SCC<V> {
                             // and mark it in the notVisitedMap
                             if (nodeMap.get(targetNode).getIndex() == 0) {
                                 notVisitedMap.get(currentNode).add(targetNode);
-                                nodeStack.add(targetNode);
+                                nodeStack.addLast(targetNode);
                             }
                         }
                     }
                     // if currentNode has no target nodes
                     else {
-                        nodeStack.pop();
+                        nodeStack.removeLast();
                         sink = true;
                     }
 
@@ -131,7 +128,7 @@ public class SCC<V> {
                         V targetNode = null;
 
                         do {
-                            targetNode = sccStack.pop();
+                            targetNode = sccStack.removeLast();
                             sc.add(targetNode);
                         } while (!targetNode.equals(currentNode));
 
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java
index db46d178..89be6804 100644
--- a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java
@@ -40,15 +40,15 @@ public class TopologicalSorting {
     public static <T> List<T> compute(final IGraphDataSource<T> gds) {
         final Set<T> visited = new HashSet<T>();
         final LinkedList<T> result = new LinkedList<T>();
-        final Stack<Pair<T>> dfsStack = new Stack<Pair<T>>();
+        final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>();
 
         for (final T node : gds.getAllNodes()) {
             if (!visited.contains(node)) {
-                dfsStack.push(new Pair<T>(node, false));
+                dfsStack.addLast(new Pair<T>(node, false));
             }
 
             while (!dfsStack.isEmpty()) {
-                final Pair<T> head = dfsStack.pop();
+                final Pair<T> head = dfsStack.removeLast();
                 final T source = head.element;
 
                 if (head.isParent) {
@@ -57,11 +57,11 @@ public class TopologicalSorting {
                 } else {
                     // first time we see source, continue with its children
                     visited.add(source);
-                    dfsStack.push(new Pair<T>(source, true));
+                    dfsStack.addLast(new Pair<T>(source, true));
 
                     for (final T target : gds.getTargetNodes(source).distinctValues()) {
                         if (!visited.contains(target)) {
-                            dfsStack.push(new Pair<T>(target, false));
+                            dfsStack.addLast(new Pair<T>(target, false));
                         }
                     }
                 }
-- 
cgit v1.2.3-54-g00ecf