12650654883

Committed 07 Jan 2025 11:26AM UTC coverage: 91.569%. First build

Build # 12650654883

Build Type

Pull #85

github

Committed by

web-flow

Commit Message

Merge 2499df5ae into d156e0830

Pull Request Pull Request #85: Update dependencies

Run Details

192 of 217 new or added lines in 63 files covered. (88.48%)

16573 of 18099 relevant lines covered (91.57%)

1.69 hits per line

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

88.5

/util/src/main/java/net/automatalib/util/ts/traversal/TSTraversal.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package net.automatalib.util.ts.traversal;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;

import net.automatalib.common.util.Holder;
import net.automatalib.ts.TransitionSystem;
import net.automatalib.util.traversal.TraversalOrder;
import net.automatalib.util.ts.traversal.DFRecord.LastTransition;
import org.checkerframework.checker.nullness.qual.NonNull;

public final class TSTraversal {

    public static final int NO_LIMIT = -1;

    private TSTraversal() {
        // prevent instantiation
    }

    /**
     * Traverses the given transition system in a breadth-first fashion. The traversal is steered by the specified
     * visitor.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     */
    public static <S, I, T, D> void breadthFirst(TransitionSystem<S, ? super I, T> ts,
                                                 Collection<? extends I> inputs,
                                                 TSTraversalVisitor<S, I, T, D> visitor) {
        breadthFirst(ts, NO_LIMIT, inputs, visitor);
    }

    /**
     * Traverses the given transition system in a breadth-first fashion. The traversal is steered by the specified
     * visitor.
     *
     * @param ts
     *         the transition system
     * @param limit
     *         the upper bound on the number of states to be visited
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
     */
    public static <S, I, T, D> boolean breadthFirst(TransitionSystem<S, ? super I, T> ts,
                                                    int limit,
                                                    Collection<? extends I> inputs,
                                                    TSTraversalVisitor<S, I, T, D> visitor) {
        Deque<BFSRecord<S, D>> bfsQueue = new ArrayDeque<>();

        // setting the following to false means that the traversal had to be aborted due to reaching the limit
        boolean complete = true;
        int stateCount = 0;

        Holder<D> dataHolder = new Holder<>();

        for (S initS : ts.getInitialStates()) {
            dataHolder.value = null;
            TSTraversalAction act = visitor.processInitial(initS, dataHolder);
            switch (act) {
                case ABORT_INPUT:
                case ABORT_STATE:
                case IGNORE:
                    continue;
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (stateCount == limit) {
                        complete = false;
                    } else {
                        bfsQueue.offer(new BFSRecord<>(initS, dataHolder.value));
                        stateCount++;
                    }
                    break;
                default:
                    throw new IllegalStateException("Unknown action " + act);
            }
        }

        while (!bfsQueue.isEmpty()) {
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull BFSRecord<S, D> current = bfsQueue.poll();

            S state = current.state;
            D data = current.data;

            if (!visitor.startExploration(state, data)) {
                continue;
            }

            inputs_loop:
            for (I input : inputs) {
                Collection<T> transitions = ts.getTransitions(state, input);

                for (T trans : transitions) {
                    S succ = ts.getSuccessor(trans);

                    dataHolder.value = null;
                    TSTraversalAction act = visitor.processTransition(state, data, input, trans, succ, dataHolder);

                    switch (act) {
                        case IGNORE:
                            continue;
                        case ABORT_INPUT:
                            continue inputs_loop;
                        case ABORT_STATE:
                            break inputs_loop;
                        case ABORT_TRAVERSAL:
                            return complete;
                        case EXPLORE:
                            if (stateCount == limit) {
                                complete = false;
                            } else {
                                bfsQueue.offer(new BFSRecord<>(succ, dataHolder.value));
                                stateCount++;
                            }
                            break;
                        default:
                            throw new IllegalStateException("Unknown action " + act);
                    }
                }
            }

            visitor.finishExploration(state, data);
        }

        return complete;
    }

    /**
     * Returns an {@link Iterable} for the (reachable) states of the given transition system in breadth-first order.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the inputs which should be considered for the traversal
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return an {@link Iterable} for the (reachable) states of the given transition system in breadth-first order
     */
    public static <S, I> Iterable<S> breadthFirstOrder(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
        return () -> breadthFirstIterator(ts, inputs);
    }

    /**
     * Returns an {@link Iterator} for the (reachable) states of the given transition system in breadth-first order.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the inputs which should be considered for the traversal
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return an {@link Iterator} for the (reachable) states of the given transition system in breadth-first order
     */
    public static <S, I> Iterator<S> breadthFirstIterator(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
        return new BreadthFirstIterator<>(ts, inputs);
    }

    /**
     * Traverses the given transition system in a depth-first fashion. The traversal is steered by the specified
     * visitor.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     */
    public static <S, I, T, D> void depthFirst(TransitionSystem<S, I, T> ts,
                                               Collection<? extends I> inputs,
                                               TSTraversalVisitor<S, I, T, D> visitor) {
        depthFirst(ts, NO_LIMIT, inputs, visitor);
    }

    /**
     * Traverses the given transition system in a depth-first fashion. The traversal is steered by the specified
     * visitor.
     *
     * @param ts
     *         the transition system
     * @param limit
     *         the upper bound on the number of states to be visited
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
     */
    public static <S, I, T, D> boolean depthFirst(TransitionSystem<S, ? super I, T> ts,
                                                  int limit,
                                                  Collection<? extends I> inputs,
                                                  TSTraversalVisitor<S, I, T, D> visitor) {
        Deque<DFRecord<S, I, T, D>> dfsStack = new ArrayDeque<>();
        Holder<D> dataHolder = new Holder<>();

        // setting the following to false means that the traversal had to be aborted due to reaching the limit
        boolean complete = true;
        int stateCount = 0;

        for (S initS : ts.getInitialStates()) {
            dataHolder.value = null;
            TSTraversalAction act = visitor.processInitial(initS, dataHolder);

            switch (act) {
                case ABORT_INPUT:
                case ABORT_STATE:
                case IGNORE:
                    continue;
                case ABORT_TRAVERSAL:
                    return complete;
                case EXPLORE:
                    if (stateCount == limit) {
                        complete = false;
                    } else {
                        dfsStack.push(new DFRecord<>(initS, inputs, dataHolder.value));
                        stateCount++;
                    }
                    break;
                default:
                    throw new IllegalStateException("Unknown action " + act);
            }
        }

        while (!dfsStack.isEmpty()) {
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull DFRecord<S, I, T, D> current = dfsStack.peek();

            S currState = current.state;
            D currData = current.data;

            if (current.start(ts) && !visitor.startExploration(currState, currData)) {
                dfsStack.pop();
                continue;
            }

            LastTransition<S, I, T, D> lastTransition = current.getLastTransition();
            if (lastTransition != null) {
                visitor.backtrackTransition(currState,
                                        currData,
                                        lastTransition.input,
                                        lastTransition.transition,
                                        lastTransition.state,
                                        lastTransition.data);
            }

            if (!current.hasNextTransition(ts)) {
                dfsStack.pop();
                visitor.finishExploration(currState, currData);
                continue;
            }

            I input = current.input();
            T trans = current.transition();

            S succ = ts.getSuccessor(trans);
            dataHolder.value = null;
            TSTraversalAction act = visitor.processTransition(currState, currData, input, trans, succ, dataHolder);

            switch (act) {
                case ABORT_INPUT:
                    current.advanceInput(ts);
                    break;
                case ABORT_STATE:
                    dfsStack.pop();
                    break;
                case ABORT_TRAVERSAL:
                    return complete;
                case IGNORE:
                    current.advance(ts);
                    break;
                case EXPLORE:
                    if (stateCount == limit) {
                        complete = false;
                    } else {
                        D data = dataHolder.value;
                        current.setLastTransition(input, trans, succ, data);
                        dfsStack.push(new DFRecord<>(succ, inputs, data));
                        stateCount++;
                    }
                    break;
                default:
                    throw new IllegalStateException("Unknown action " + act);
            }
        }

        return complete;
    }

    /**
     * Returns an {@link Iterable} for the (reachable) states of the given transition system in depth-first order.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the inputs which should be considered for the traversal
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return an {@link Iterable} for the (reachable) states of the given transition system in depth-first order
     */
    public static <S, I> Iterable<S> depthFirstOrder(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
        return () -> depthFirstIterator(ts, inputs);
    }

    /**
     * Returns an {@link Iterator} for the (reachable) states of the given transition system in depth-first order.
     *
     * @param ts
     *         the transition system
     * @param inputs
     *         the inputs which should be considered for the traversal
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     *
     * @return an {@link Iterator} for the (reachable) states of the given transition system in depth-first order
     */
    public static <S, I> Iterator<S> depthFirstIterator(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
        return new DepthFirstIterator<>(ts, inputs);
    }

    /**
     * Traverses the given transition system in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param ts
     *         the transition system
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     */
    public static <S, I, T, D> void traverse(TraversalOrder order,
                                             TransitionSystem<S, ? super I, T> ts,
                                             Collection<? extends I> inputs,
                                             TSTraversalVisitor<S, I, T, D> visitor) {
        traverse(order, ts, NO_LIMIT, inputs, visitor);
    }

    /**
     * Traverses the given transition system in a given order. The traversal is steered by the specified visitor.
     *
     * @param order
     *         the order in which the states should be traversed
     * @param ts
     *         the transition system
     * @param limit
     *         the upper bound on the number of states to be visited
     * @param inputs
     *         the input alphabet
     * @param visitor
     *         the visitor
     * @param <S>
     *         state type
     * @param <I>
     *         input symbol type
     * @param <T>
     *         transition type
     * @param <D>
     *         (user) data type
     *
     * @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
     */
    public static <S, I, T, D> boolean traverse(TraversalOrder order,
                                                TransitionSystem<S, ? super I, T> ts,
                                                int limit,
                                                Collection<? extends I> inputs,
                                                TSTraversalVisitor<S, I, T, D> visitor) {
        switch (order) {
            case BREADTH_FIRST:
                return breadthFirst(ts, limit, inputs, visitor);
            case DEPTH_FIRST:
                return depthFirst(ts, limit, inputs, visitor);
            default:
                throw new IllegalArgumentException("Unknown traversal order: " + order);
        }
    }

}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.automatalib.net/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package net.automatalib.util.ts.traversal;
17
18	import java.util.ArrayDeque;
19	import java.util.Collection;
20	import java.util.Deque;
21	import java.util.Iterator;
22
23	import net.automatalib.common.util.Holder;
24	import net.automatalib.ts.TransitionSystem;
25	import net.automatalib.util.traversal.TraversalOrder;
26	import net.automatalib.util.ts.traversal.DFRecord.LastTransition;
27	import org.checkerframework.checker.nullness.qual.NonNull;
28
29	public final class TSTraversal {
30
31	public static final int NO_LIMIT = -1;
32
33	private TSTraversal() {
34	// prevent instantiation
35	}
36
37	/**
38	* Traverses the given transition system in a breadth-first fashion. The traversal is steered by the specified
39	* visitor.
40	*
41	* @param ts
42	* the transition system
43	* @param inputs
44	* the input alphabet
45	* @param visitor
46	* the visitor
47	* @param <S>
48	* state type
49	* @param <I>
50	* input symbol type
51	* @param <T>
52	* transition type
53	* @param <D>
54	* (user) data type
55	*/
56	public static <S, I, T, D> void breadthFirst(TransitionSystem<S, ? super I, T> ts,
57	Collection<? extends I> inputs,
58	TSTraversalVisitor<S, I, T, D> visitor) {
59	breadthFirst(ts, NO_LIMIT, inputs, visitor);	2✔
60	}	2✔
61
62	/**
63	* Traverses the given transition system in a breadth-first fashion. The traversal is steered by the specified
64	* visitor.
65	*
66	* @param ts
67	* the transition system
68	* @param limit
69	* the upper bound on the number of states to be visited
70	* @param inputs
71	* the input alphabet
72	* @param visitor
73	* the visitor
74	* @param <S>
75	* state type
76	* @param <I>
77	* input symbol type
78	* @param <T>
79	* transition type
80	* @param <D>
81	* (user) data type
82	*
83	* @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
84	*/
85	public static <S, I, T, D> boolean breadthFirst(TransitionSystem<S, ? super I, T> ts,
86	int limit,
87	Collection<? extends I> inputs,
88	TSTraversalVisitor<S, I, T, D> visitor) {
89	Deque<BFSRecord<S, D>> bfsQueue = new ArrayDeque<>();	2✔
90
91	// setting the following to false means that the traversal had to be aborted due to reaching the limit
92	boolean complete = true;	2✔
93	int stateCount = 0;	2✔
94
95	Holder<D> dataHolder = new Holder<>();	2✔
96
97	for (S initS : ts.getInitialStates()) {	2✔
98	dataHolder.value = null;	2✔
99	TSTraversalAction act = visitor.processInitial(initS, dataHolder);	2✔
100	switch (act) {	2✔
101	case ABORT_INPUT:
102	case ABORT_STATE:
103	case IGNORE:
104	continue;	2✔
105	case ABORT_TRAVERSAL:
106	return complete;	2✔
107	case EXPLORE:
108	if (stateCount == limit) {	2✔
109	complete = false;	2✔
110	} else {
111	bfsQueue.offer(new BFSRecord<>(initS, dataHolder.value));	2✔
112	stateCount++;	2✔
113	}
114	break;	2✔
115	default:
116	throw new IllegalStateException("Unknown action " + act);	×
117	}
118	}	2✔
119
120	while (!bfsQueue.isEmpty()) {	2✔
121	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
122	@NonNull BFSRecord<S, D> current = bfsQueue.poll();	2✔
123
124	S state = current.state;	2✔
125	D data = current.data;	2✔
126
127	if (!visitor.startExploration(state, data)) {	2✔
128	continue;	×
129	}
130
131	inputs_loop:
132	for (I input : inputs) {	2✔
133	Collection<T> transitions = ts.getTransitions(state, input);	2✔
134
135	for (T trans : transitions) {	2✔
136	S succ = ts.getSuccessor(trans);	2✔
137
138	dataHolder.value = null;	2✔
139	TSTraversalAction act = visitor.processTransition(state, data, input, trans, succ, dataHolder);	2✔
140
141	switch (act) {	2✔
142	case IGNORE:
143	continue;	2✔
144	case ABORT_INPUT:
145	continue inputs_loop;	2✔
146	case ABORT_STATE:
147	break inputs_loop;	2✔
148	case ABORT_TRAVERSAL:
149	return complete;	×
150	case EXPLORE:
151	if (stateCount == limit) {	2✔
NEW 152	complete = false;	×
153	} else {
154	bfsQueue.offer(new BFSRecord<>(succ, dataHolder.value));	2✔
155	stateCount++;	2✔
156	}
157	break;	2✔
158	default:
159	throw new IllegalStateException("Unknown action " + act);	×
160	}
161	}	2✔
162	}	2✔
163
164	visitor.finishExploration(state, data);	2✔
165	}	2✔
166
167	return complete;	2✔
168	}
169
170	/**
171	* Returns an {@link Iterable} for the (reachable) states of the given transition system in breadth-first order.
172	*
173	* @param ts
174	* the transition system
175	* @param inputs
176	* the inputs which should be considered for the traversal
177	* @param <S>
178	* state type
179	* @param <I>
180	* input symbol type
181	*
182	* @return an {@link Iterable} for the (reachable) states of the given transition system in breadth-first order
183	*/
184	public static <S, I> Iterable<S> breadthFirstOrder(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
185	return () -> breadthFirstIterator(ts, inputs);	2✔
186	}
187
188	/**
189	* Returns an {@link Iterator} for the (reachable) states of the given transition system in breadth-first order.
190	*
191	* @param ts
192	* the transition system
193	* @param inputs
194	* the inputs which should be considered for the traversal
195	* @param <S>
196	* state type
197	* @param <I>
198	* input symbol type
199	*
200	* @return an {@link Iterator} for the (reachable) states of the given transition system in breadth-first order
201	*/
202	public static <S, I> Iterator<S> breadthFirstIterator(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
203	return new BreadthFirstIterator<>(ts, inputs);	2✔
204	}
205
206	/**
207	* Traverses the given transition system in a depth-first fashion. The traversal is steered by the specified
208	* visitor.
209	*
210	* @param ts
211	* the transition system
212	* @param inputs
213	* the input alphabet
214	* @param visitor
215	* the visitor
216	* @param <S>
217	* state type
218	* @param <I>
219	* input symbol type
220	* @param <T>
221	* transition type
222	* @param <D>
223	* (user) data type
224	*/
225	public static <S, I, T, D> void depthFirst(TransitionSystem<S, I, T> ts,
226	Collection<? extends I> inputs,
227	TSTraversalVisitor<S, I, T, D> visitor) {
228	depthFirst(ts, NO_LIMIT, inputs, visitor);	2✔
229	}	2✔
230
231	/**
232	* Traverses the given transition system in a depth-first fashion. The traversal is steered by the specified
233	* visitor.
234	*
235	* @param ts
236	* the transition system
237	* @param limit
238	* the upper bound on the number of states to be visited
239	* @param inputs
240	* the input alphabet
241	* @param visitor
242	* the visitor
243	* @param <S>
244	* state type
245	* @param <I>
246	* input symbol type
247	* @param <T>
248	* transition type
249	* @param <D>
250	* (user) data type
251	*
252	* @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
253	*/
254	public static <S, I, T, D> boolean depthFirst(TransitionSystem<S, ? super I, T> ts,
255	int limit,
256	Collection<? extends I> inputs,
257	TSTraversalVisitor<S, I, T, D> visitor) {
258	Deque<DFRecord<S, I, T, D>> dfsStack = new ArrayDeque<>();	2✔
259	Holder<D> dataHolder = new Holder<>();	2✔
260
261	// setting the following to false means that the traversal had to be aborted due to reaching the limit
262	boolean complete = true;	2✔
263	int stateCount = 0;	2✔
264
265	for (S initS : ts.getInitialStates()) {	2✔
266	dataHolder.value = null;	2✔
267	TSTraversalAction act = visitor.processInitial(initS, dataHolder);	2✔
268
269	switch (act) {	2✔
270	case ABORT_INPUT:
271	case ABORT_STATE:
272	case IGNORE:
273	continue;	2✔
274	case ABORT_TRAVERSAL:
275	return complete;	2✔
276	case EXPLORE:
277	if (stateCount == limit) {	2✔
278	complete = false;	2✔
279	} else {
280	dfsStack.push(new DFRecord<>(initS, inputs, dataHolder.value));	2✔
281	stateCount++;	2✔
282	}
283	break;	2✔
284	default:
285	throw new IllegalStateException("Unknown action " + act);	×
286	}
287	}	2✔
288
289	while (!dfsStack.isEmpty()) {	2✔
290	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
291	@NonNull DFRecord<S, I, T, D> current = dfsStack.peek();	2✔
292
293	S currState = current.state;	2✔
294	D currData = current.data;	2✔
295
296	if (current.start(ts) && !visitor.startExploration(currState, currData)) {	2✔
297	dfsStack.pop();	×
298	continue;	×
299	}
300
301	LastTransition<S, I, T, D> lastTransition = current.getLastTransition();	2✔
302	if (lastTransition != null) {	2✔
303	visitor.backtrackTransition(currState,	2✔
304	currData,
305	lastTransition.input,
306	lastTransition.transition,
307	lastTransition.state,
308	lastTransition.data);
309	}
310
311	if (!current.hasNextTransition(ts)) {	2✔
312	dfsStack.pop();	2✔
313	visitor.finishExploration(currState, currData);	2✔
314	continue;	2✔
315	}
316
317	I input = current.input();	2✔
318	T trans = current.transition();	2✔
319
320	S succ = ts.getSuccessor(trans);	2✔
321	dataHolder.value = null;	2✔
322	TSTraversalAction act = visitor.processTransition(currState, currData, input, trans, succ, dataHolder);	2✔
323
324	switch (act) {	2✔
325	case ABORT_INPUT:
326	current.advanceInput(ts);	2✔
327	break;	2✔
328	case ABORT_STATE:
329	dfsStack.pop();	2✔
330	break;	2✔
331	case ABORT_TRAVERSAL:
332	return complete;	2✔
333	case IGNORE:
334	current.advance(ts);	2✔
335	break;	2✔
336	case EXPLORE:
337	if (stateCount == limit) {	2✔
NEW 338	complete = false;	×
339	} else {
340	D data = dataHolder.value;	2✔
341	current.setLastTransition(input, trans, succ, data);	2✔
342	dfsStack.push(new DFRecord<>(succ, inputs, data));	2✔
343	stateCount++;	2✔
344	}
345	break;	2✔
346	default:
347	throw new IllegalStateException("Unknown action " + act);	×
348	}
349	}	2✔
350
351	return complete;	2✔
352	}
353
354	/**
355	* Returns an {@link Iterable} for the (reachable) states of the given transition system in depth-first order.
356	*
357	* @param ts
358	* the transition system
359	* @param inputs
360	* the inputs which should be considered for the traversal
361	* @param <S>
362	* state type
363	* @param <I>
364	* input symbol type
365	*
366	* @return an {@link Iterable} for the (reachable) states of the given transition system in depth-first order
367	*/
368	public static <S, I> Iterable<S> depthFirstOrder(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
369	return () -> depthFirstIterator(ts, inputs);	2✔
370	}
371
372	/**
373	* Returns an {@link Iterator} for the (reachable) states of the given transition system in depth-first order.
374	*
375	* @param ts
376	* the transition system
377	* @param inputs
378	* the inputs which should be considered for the traversal
379	* @param <S>
380	* state type
381	* @param <I>
382	* input symbol type
383	*
384	* @return an {@link Iterator} for the (reachable) states of the given transition system in depth-first order
385	*/
386	public static <S, I> Iterator<S> depthFirstIterator(TransitionSystem<S, I, ?> ts, Collection<? extends I> inputs) {
387	return new DepthFirstIterator<>(ts, inputs);	2✔
388	}
389
390	/**
391	* Traverses the given transition system in a given order. The traversal is steered by the specified visitor.
392	*
393	* @param order
394	* the order in which the states should be traversed
395	* @param ts
396	* the transition system
397	* @param inputs
398	* the input alphabet
399	* @param visitor
400	* the visitor
401	* @param <S>
402	* state type
403	* @param <I>
404	* input symbol type
405	* @param <T>
406	* transition type
407	* @param <D>
408	* (user) data type
409	*/
410	public static <S, I, T, D> void traverse(TraversalOrder order,
411	TransitionSystem<S, ? super I, T> ts,
412	Collection<? extends I> inputs,
413	TSTraversalVisitor<S, I, T, D> visitor) {
414	traverse(order, ts, NO_LIMIT, inputs, visitor);	×
415	}	×
416
417	/**
418	* Traverses the given transition system in a given order. The traversal is steered by the specified visitor.
419	*
420	* @param order
421	* the order in which the states should be traversed
422	* @param ts
423	* the transition system
424	* @param limit
425	* the upper bound on the number of states to be visited
426	* @param inputs
427	* the input alphabet
428	* @param visitor
429	* the visitor
430	* @param <S>
431	* state type
432	* @param <I>
433	* input symbol type
434	* @param <T>
435	* transition type
436	* @param <D>
437	* (user) data type
438	*
439	* @return {@code false} if the number of explored states reached {@code limit}, {@code true} otherwise
440	*/
441	public static <S, I, T, D> boolean traverse(TraversalOrder order,
442	TransitionSystem<S, ? super I, T> ts,
443	int limit,
444	Collection<? extends I> inputs,
445	TSTraversalVisitor<S, I, T, D> visitor) {
446	switch (order) {	2✔
447	case BREADTH_FIRST:
448	return breadthFirst(ts, limit, inputs, visitor);	2✔
449	case DEPTH_FIRST:
450	return depthFirst(ts, limit, inputs, visitor);	2✔
451	default:
452	throw new IllegalArgumentException("Unknown traversal order: " + order);	×
453	}
454	}
455
456	}

LearnLib / automatalib / 12650654883

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