wurstscript / WurstScript / 266

Committed 29 Sep 2025 09:10AM UTC coverage: 62.244% (+0.02%) from 62.222%

Build # 266

Build Type

Pull #1096

circleci

Committed by

Frotty

Commit Message

Optimize imports

Pull Request Pull Request #1096: Perf improvements

Run Details

17480 of 28083 relevant lines covered (62.24%)

0.62 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

80.85

de.peeeq.wurstscript/src/main/java/de/peeeq/datastructures/GraphInterpreter.java

package de.peeeq.datastructures;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;
import de.peeeq.wurstscript.utils.Utils;
import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
import org.eclipse.jdt.annotation.Nullable;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public abstract class GraphInterpreter<T> {

    protected abstract Collection<T> getIncidentNodes(T t);

    public TopsortResult<T> topSort(List<T> nodes) {
        Set<T> seen = Sets.newHashSet();
        List<T> seenStack = Lists.newArrayList();
        List<T> result = Lists.newArrayList();

        for (T t : nodes) {
            if (!seen.contains(t)) {
                @Nullable TopsortResult<T> r = topSort_add(result, seen, seenStack, t);
                if (r != null) {
                    return r;
                }
            }
        }
        return new TopsortResult<>(false, result);
    }

    private @Nullable TopsortResult<T> topSort_add(List<T> result, Set<T> seen, List<T> seenStack, T n) {
        for (int i = seenStack.size() - 1; i >= 0; i--) {
            if (seenStack.get(i) == n) {
                // cycle
                return new TopsortResult<>(true, Utils.subList(seenStack, i));
            }
        }
        if (!seen.contains(n)) {
            seenStack.add(n);
            for (T m : getIncidentNodes(n)) {
                TopsortResult<T> r = topSort_add(result, seen, seenStack, m);
                if (r != null) {
                    return r;
                }
            }
            seenStack.remove(seenStack.size() - 1);
            seen.add(n);
            result.add(n);
        }
        return null;
    }

    public static class TopsortResult<T> {
        private final boolean isCycle;
        private final List<T> result;

        public TopsortResult(boolean isCycle, List<T> result) {
            this.isCycle = isCycle;
            this.result = result;
        }

        public boolean isCycle() {
            return isCycle;
        }

        public List<T> getResult() {
            return result;
        }
    }

    /**
     * Like topsort, but will find bigger cycles.
     * This is an iterative implementation of the path-based strong component algorithm
     * to prevent StackOverflowErrors on deep graphs.
     * <p>
     * See https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm
     */
    public Set<Set<T>> findStronglyConnectedComponents(List<T> nodes) {
        Deque<T> s = new ArrayDeque<>();
        Deque<T> p = new ArrayDeque<>();
        AtomicInteger c = new AtomicInteger();
        AtomicInteger componentCount = new AtomicInteger();
        Object2IntLinkedOpenHashMap<T> preorderNumber = new Object2IntLinkedOpenHashMap<>();
        Object2IntLinkedOpenHashMap<T> component      = new Object2IntLinkedOpenHashMap<>();

        // This stack simulates the recursive calls
        Deque<T> traversalStack = new ArrayDeque<>();
        // This map holds iterators for the children of each node
        Map<T, Iterator<T>> iterators = new HashMap<>();

        for (T startNode : nodes) {
            if (!preorderNumber.containsKey(startNode)) {
                traversalStack.push(startNode);

                while (!traversalStack.isEmpty()) {
                    T v = traversalStack.peek();

                    // Pre-order processing (first time visiting node v)
                    if (!preorderNumber.containsKey(v)) {
                        preorderNumber.put(v, c.getAndIncrement());
                        s.push(v);
                        p.push(v);
                        iterators.put(v, getIncidentNodes(v).iterator());
                    }

                    boolean foundNewChild = false;
                    Iterator<T> children = iterators.get(v);

                    // Iterate over children to find the next one to visit
                    while (children.hasNext()) {
                        T w = children.next();
                        if (!preorderNumber.containsKey(w)) {
                            // Found an unvisited child, push to stack to simulate recursive call
                            traversalStack.push(w);
                            foundNewChild = true;
                            break;
                        } else if (!component.containsKey(w)) {
                            // Child w has been visited but is not yet in a component
                            while (!p.isEmpty() && preorderNumber.getOrDefault(p.peek(), -1) > preorderNumber.get(w)) {
                                p.pop();
                            }
                        }
                    }

                    if (foundNewChild) {
                        // Continue the loop to process the new child on top of the stack
                        continue;
                    }

                    // Post-order processing (all children of v have been visited)
                    traversalStack.pop(); // Finished with v, pop it
                    iterators.remove(v); // Clean up iterator

                    if (!p.isEmpty() && p.peek() == v) {
                        Integer newComponent = componentCount.incrementAndGet();
                        while (true) {
                            T popped = s.pop();
                            component.put(popped, newComponent);
                            if (popped == v) {
                                break;
                            }
                        }
                        p.pop();
                    }
                }
            }
        }
        return ImmutableSet.copyOf(Utils.inverseMapToSet(component).values());
    }

    public String generateDotFile(List<T> nodes) {
        StringBuilder sb = new StringBuilder();
        Set<T> visited = new HashSet<>();
        Deque<T> todo = new ArrayDeque<>(nodes);
        sb.append("digraph G{\n");
        while (!todo.isEmpty()) {
            T node = todo.removeFirst();
            if (!visited.add(node)) {
                continue;
            }
            sb.append("  \"").append(node).append("\";\n");
            for (T n : getIncidentNodes(node)) {
                sb.append("  ");
                sb.append("\"").append(node).append("\" -> ");
                sb.append("\"").append(n.toString()).append("\";\n\n");
                todo.addFirst(n);
            }
        }
        sb.append("}\n");
        return sb.toString();
    }
}

1	package de.peeeq.datastructures;
2
3	import com.google.common.collect.ImmutableSet;
4	import com.google.common.collect.Lists;
5	import com.google.common.collect.Sets;
6	import de.peeeq.wurstscript.utils.Utils;
7	import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
8	import org.eclipse.jdt.annotation.Nullable;
9
10	import java.util.*;
11	import java.util.concurrent.atomic.AtomicInteger;
12
13	public abstract class GraphInterpreter<T> {	1✔
14
15	protected abstract Collection<T> getIncidentNodes(T t);
16
17	public TopsortResult<T> topSort(List<T> nodes) {
18	Set<T> seen = Sets.newHashSet();	1✔
19	List<T> seenStack = Lists.newArrayList();	1✔
20	List<T> result = Lists.newArrayList();	1✔
21
22	for (T t : nodes) {	1✔
23	if (!seen.contains(t)) {	1✔
24	@Nullable TopsortResult<T> r = topSort_add(result, seen, seenStack, t);	1✔
25	if (r != null) {	1✔
26	return r;	1✔
27	}
28	}
29	}	1✔
30	return new TopsortResult<>(false, result);	1✔
31	}
32
33	private @Nullable TopsortResult<T> topSort_add(List<T> result, Set<T> seen, List<T> seenStack, T n) {
34	for (int i = seenStack.size() - 1; i >= 0; i--) {	1✔
35	if (seenStack.get(i) == n) {	1✔
36	// cycle
37	return new TopsortResult<>(true, Utils.subList(seenStack, i));	1✔
38	}
39	}
40	if (!seen.contains(n)) {	1✔
41	seenStack.add(n);	1✔
42	for (T m : getIncidentNodes(n)) {	1✔
43	TopsortResult<T> r = topSort_add(result, seen, seenStack, m);	1✔
44	if (r != null) {	1✔
45	return r;	1✔
46	}
47	}	1✔
48	seenStack.remove(seenStack.size() - 1);	1✔
49	seen.add(n);	1✔
50	result.add(n);	1✔
51	}
52	return null;	1✔
53	}
54
55	public static class TopsortResult<T> {
56	private final boolean isCycle;
57	private final List<T> result;
58
59	public TopsortResult(boolean isCycle, List<T> result) {	1✔
60	this.isCycle = isCycle;	1✔
61	this.result = result;	1✔
62	}	1✔
63
64	public boolean isCycle() {
65	return isCycle;	1✔
66	}
67
68	public List<T> getResult() {
69	return result;	1✔
70	}
71	}
72
73	/**
74	* Like topsort, but will find bigger cycles.
75	* This is an iterative implementation of the path-based strong component algorithm
76	* to prevent StackOverflowErrors on deep graphs.
77	* <p>
78	* See https://en.wikipedia.org/wiki/Path-based_strong_component_algorithm
79	*/
80	public Set<Set<T>> findStronglyConnectedComponents(List<T> nodes) {
81	Deque<T> s = new ArrayDeque<>();	1✔
82	Deque<T> p = new ArrayDeque<>();	1✔
83	AtomicInteger c = new AtomicInteger();	1✔
84	AtomicInteger componentCount = new AtomicInteger();	1✔
85	Object2IntLinkedOpenHashMap<T> preorderNumber = new Object2IntLinkedOpenHashMap<>();	1✔
86	Object2IntLinkedOpenHashMap<T> component = new Object2IntLinkedOpenHashMap<>();	1✔
87
88	// This stack simulates the recursive calls
89	Deque<T> traversalStack = new ArrayDeque<>();	1✔
90	// This map holds iterators for the children of each node
91	Map<T, Iterator<T>> iterators = new HashMap<>();	1✔
92
93	for (T startNode : nodes) {	1✔
94	if (!preorderNumber.containsKey(startNode)) {	1✔
95	traversalStack.push(startNode);	1✔
96
97	while (!traversalStack.isEmpty()) {	1✔
98	T v = traversalStack.peek();	1✔
99
100	// Pre-order processing (first time visiting node v)
101	if (!preorderNumber.containsKey(v)) {	1✔
102	preorderNumber.put(v, c.getAndIncrement());	1✔
103	s.push(v);	1✔
104	p.push(v);	1✔
105	iterators.put(v, getIncidentNodes(v).iterator());	1✔
106	}
107
108	boolean foundNewChild = false;	1✔
109	Iterator<T> children = iterators.get(v);	1✔
110
111	// Iterate over children to find the next one to visit
112	while (children.hasNext()) {	1✔
113	T w = children.next();	1✔
114	if (!preorderNumber.containsKey(w)) {	1✔
115	// Found an unvisited child, push to stack to simulate recursive call
116	traversalStack.push(w);	1✔
117	foundNewChild = true;	1✔
118	break;	1✔
119	} else if (!component.containsKey(w)) {	1✔
120	// Child w has been visited but is not yet in a component
121	while (!p.isEmpty() && preorderNumber.getOrDefault(p.peek(), -1) > preorderNumber.get(w)) {	1✔
122	p.pop();	1✔
123	}
124	}
125	}	1✔
126
127	if (foundNewChild) {	1✔
128	// Continue the loop to process the new child on top of the stack
129	continue;	1✔
130	}
131
132	// Post-order processing (all children of v have been visited)
133	traversalStack.pop(); // Finished with v, pop it	1✔
134	iterators.remove(v); // Clean up iterator	1✔
135
136	if (!p.isEmpty() && p.peek() == v) {	1✔
137	Integer newComponent = componentCount.incrementAndGet();	1✔
138	while (true) {
139	T popped = s.pop();	1✔
140	component.put(popped, newComponent);	1✔
141	if (popped == v) {	1✔
142	break;	1✔
143	}
144	}	1✔
145	p.pop();	1✔
146	}
147	}	1✔
148	}
149	}	1✔
150	return ImmutableSet.copyOf(Utils.inverseMapToSet(component).values());	1✔
151	}
152
153	public String generateDotFile(List<T> nodes) {
154	StringBuilder sb = new StringBuilder();	×
155	Set<T> visited = new HashSet<>();	×
156	Deque<T> todo = new ArrayDeque<>(nodes);	×
157	sb.append("digraph G{\n");	×
158	while (!todo.isEmpty()) {	×
159	T node = todo.removeFirst();	×
160	if (!visited.add(node)) {	×
161	continue;	×
162	}
163	sb.append(" \"").append(node).append("\";\n");	×
164	for (T n : getIncidentNodes(node)) {	×
165	sb.append(" ");	×
166	sb.append("\"").append(node).append("\" -> ");	×
167	sb.append("\"").append(n.toString()).append("\";\n\n");	×
168	todo.addFirst(n);	×
169	}	×
170	}	×
171	sb.append("}\n");	×
172	return sb.toString();	×
173	}
174	}

wurstscript / WurstScript / 266

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous