31619759710

Committed 12 Aug 2026 04:27PM UTC coverage: 95.488% (+1.1%) from 94.368%

Build # 31619759710

Build Type

push

github

Committed by

mtf90

Commit Message

use new version scheme

Coverage Stats

15533 of 16267 relevant lines covered (95.49%)

1.72 hits per line

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

89.89

/commons/datastructures/src/main/java/de/learnlib/datastructure/pta/BasePTA.java

/* Copyright (C) 2013-2026 TU Dortmund University
 * This file is part of LearnLib <https://learnlib.de>.
 *
 * 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 de.learnlib.datastructure.pta;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import de.learnlib.datastructure.pta.visualization.PTAVisualizationHelper;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.impl.Alphabets;
import net.automatalib.automaton.FiniteAlphabetAutomaton;
import net.automatalib.automaton.UniversalDeterministicAutomaton;
import net.automatalib.automaton.graph.TransitionEdge;
import net.automatalib.automaton.graph.TransitionEdge.Property;
import net.automatalib.automaton.graph.UniversalAutomatonGraphView;
import net.automatalib.common.smartcollection.IntSeq;
import net.automatalib.common.util.collection.AbstractSimplifiedIterator;
import net.automatalib.graph.UniversalGraph;
import net.automatalib.visualization.VisualizationHelper;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Base class for prefix tree acceptors.
 *
 * @param <S>
 *         state type
 * @param <SP>
 *         state property type
 * @param <TP>
 *         transition property type
 */
public class BasePTA<S extends AbstractBasePTAState<S, SP, TP>, SP, TP>
        implements UniversalDeterministicAutomaton<S, Integer, PTATransition<S>, SP, TP>,
                   FiniteAlphabetAutomaton<S, Integer, PTATransition<S>> {

    private final int alphabetSize;
    private final S root;

    /**
     * Constructor.
     *
     * @param alphabetSize
     *         the size of the input alphabet
     * @param root
     *         the root state
     */
    public BasePTA(int alphabetSize, S root) {
        this.alphabetSize = alphabetSize;
        this.root = root;
    }

    /**
     * Retrieves the root of the PTA.
     *
     * @return the root state
     */
    public S getRoot() {
        return root;
    }

    @Override
    public Alphabet<Integer> getInputAlphabet() {
        return Alphabets.integers(0, alphabetSize - 1);
    }

    /**
     * Adds a sample to the PTA, and sets the property of the last reached (or inserted) state accordingly.
     *
     * @param sample
     *         the word to add to the PTA
     * @param lastProperty
     *         the property of the last state to set
     */
    public void addSample(IntSeq sample, SP lastProperty) {
        S target = getOrCreateState(sample);
        target.mergeStateProperty(lastProperty);
    }

    /**
     * Retrieves the state reached by the given word. If there is no path for the word in the PTA, it will be added to
     * the PTA on-the-fly.
     *
     * @param word
     *         the word
     *
     * @return the state reached by this word, which might have been newly created (along with all required predecessor
     * states)
     */
    public S getOrCreateState(IntSeq word) {
        S curr = root;
        for (int sym : word) {
            curr = curr.getOrCreateSuccessor(sym, alphabetSize);
        }

        return curr;
    }

    public void addSampleWithStateProperties(IntSeq sample, List<? extends SP> lastStateProperties) {
        int sampleLen = sample.size();
        int skip = sampleLen + 1 - lastStateProperties.size();
        if (skip < 0) {
            throw new IllegalArgumentException();
        }

        S curr = getRoot();
        int i = 0;
        while (i < skip) {
            int sym = sample.get(i++);
            curr = curr.getOrCreateSuccessor(sym, alphabetSize);
        }

        Iterator<? extends SP> spIt = lastStateProperties.iterator();

        while (i < sampleLen) {
            curr.mergeStateProperty(spIt.next());
            int sym = sample.get(i++);
            curr = curr.getOrCreateSuccessor(sym, alphabetSize);
        }

        curr.mergeStateProperty(spIt.next());
    }

    public void addSampleWithTransitionProperties(IntSeq sample, List<? extends TP> lastTransitionProperties) {
        int sampleLen = sample.size();
        int skip = sampleLen - lastTransitionProperties.size();
        if (skip < 0) {
            throw new IllegalArgumentException();
        }

        S curr = getRoot();
        int i = 0;
        while (i < skip) {
            int sym = sample.get(i++);
            curr = curr.getOrCreateSuccessor(sym, alphabetSize);
        }

        Iterator<? extends TP> tpIt = lastTransitionProperties.iterator();
        while (i < sampleLen) {
            int sym = sample.get(i++);
            curr.mergeTransitionProperty(sym, alphabetSize, tpIt.next());
            curr = curr.getOrCreateSuccessor(sym, alphabetSize);
        }
    }

    @Override
    public S getSuccessor(PTATransition<S> transition) {
        return transition.getTarget();
    }

    @Override
    public @Nullable S getSuccessor(S state, Integer input) {
        return state.getSuccessor(input);
    }

    @Override
    public Iterator<S> iterator() {
        Set<S> visited = new HashSet<>();
        final Deque<S> bfsQueue = new ArrayDeque<>();
        bfsQueue.add(root);
        visited.add(root);

        return new AbstractSimplifiedIterator<>() {

            @Override
            protected boolean calculateNext() {
                final S next = bfsQueue.poll();
                if (next == null) {
                    return false;
                }
                super.nextValue = next;
                for (int i = 0; i < alphabetSize; i++) {
                    final S child = next.getSuccessor(i);
                    if (child != null && visited.add(child)) {
                        bfsQueue.offer(child);
                    }
                }
                return true;
            }
        };
    }

    @Override
    public Collection<S> getStates() {
        List<S> stateList = new ArrayList<>();
        Set<S> visited = new HashSet<>();

        int ptr = 0;
        stateList.add(root);
        visited.add(root);
        int numStates = 1;

        while (ptr < numStates) {
            S curr = stateList.get(ptr++);
            for (int i = 0; i < alphabetSize; i++) {
                S succ = curr.getSuccessor(i);
                if (succ != null && visited.add(succ)) {
                    stateList.add(succ);
                    numStates++;
                }
            }
        }

        return stateList;
    }

    @Override
    public S getInitialState() {
        return getRoot();
    }

    @Override
    public @Nullable PTATransition<S> getTransition(S state, Integer input) {
        if (state.getSuccessor(input) == null) {
            return null;
        }

        return new PTATransition<>(state, input);
    }

    @Override
    public SP getStateProperty(S state) {
        return state.getStateProperty();
    }

    @Override
    public TP getTransitionProperty(PTATransition<S> transition) {
        return transition.getSource().getTransProperty(transition.getIndex());
    }

    @Override
    public UniversalGraph<S, TransitionEdge<Integer, PTATransition<S>>, SP, Property<Integer, TP>> transitionGraphView(
            Collection<? extends Integer> inputs) {
        return new UniversalAutomatonGraphView<>(this, inputs) {

            @Override
            public VisualizationHelper<S, TransitionEdge<Integer, PTATransition<S>>> getVisualizationHelper() {
                return BasePTA.this.getVisualizationHelper();
            }
        };
    }

    protected VisualizationHelper<S, TransitionEdge<Integer, PTATransition<S>>> getVisualizationHelper() {
        return new PTAVisualizationHelper<>(this);
    }
}

1	/* Copyright (C) 2013-2026 TU Dortmund University
2	* This file is part of LearnLib <https://learnlib.de>.
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 de.learnlib.datastructure.pta;
17
18	import java.util.ArrayDeque;
19	import java.util.ArrayList;
20	import java.util.Collection;
21	import java.util.Deque;
22	import java.util.HashSet;
23	import java.util.Iterator;
24	import java.util.List;
25	import java.util.Set;
26
27	import de.learnlib.datastructure.pta.visualization.PTAVisualizationHelper;
28	import net.automatalib.alphabet.Alphabet;
29	import net.automatalib.alphabet.impl.Alphabets;
30	import net.automatalib.automaton.FiniteAlphabetAutomaton;
31	import net.automatalib.automaton.UniversalDeterministicAutomaton;
32	import net.automatalib.automaton.graph.TransitionEdge;
33	import net.automatalib.automaton.graph.TransitionEdge.Property;
34	import net.automatalib.automaton.graph.UniversalAutomatonGraphView;
35	import net.automatalib.common.smartcollection.IntSeq;
36	import net.automatalib.common.util.collection.AbstractSimplifiedIterator;
37	import net.automatalib.graph.UniversalGraph;
38	import net.automatalib.visualization.VisualizationHelper;
39	import org.checkerframework.checker.nullness.qual.Nullable;
40
41	/**
42	* Base class for prefix tree acceptors.
43	*
44	* @param <S>
45	* state type
46	* @param <SP>
47	* state property type
48	* @param <TP>
49	* transition property type
50	*/
51	public class BasePTA<S extends AbstractBasePTAState<S, SP, TP>, SP, TP>
52	implements UniversalDeterministicAutomaton<S, Integer, PTATransition<S>, SP, TP>,
53	FiniteAlphabetAutomaton<S, Integer, PTATransition<S>> {
54
55	private final int alphabetSize;
56	private final S root;
57
58	/**
59	* Constructor.
60	*
61	* @param alphabetSize
62	* the size of the input alphabet
63	* @param root
64	* the root state
65	*/
66	public BasePTA(int alphabetSize, S root) {	2✔
67	this.alphabetSize = alphabetSize;	2✔
68	this.root = root;	2✔
69	}	2✔
70
71	/**
72	* Retrieves the root of the PTA.
73	*
74	* @return the root state
75	*/
76	public S getRoot() {
77	return root;	2✔
78	}
79
80	@Override
81	public Alphabet<Integer> getInputAlphabet() {
82	return Alphabets.integers(0, alphabetSize - 1);	2✔
83	}
84
85	/**
86	* Adds a sample to the PTA, and sets the property of the last reached (or inserted) state accordingly.
87	*
88	* @param sample
89	* the word to add to the PTA
90	* @param lastProperty
91	* the property of the last state to set
92	*/
93	public void addSample(IntSeq sample, SP lastProperty) {
94	S target = getOrCreateState(sample);	2✔
95	target.mergeStateProperty(lastProperty);	2✔
96	}	2✔
97
98	/**
99	* Retrieves the state reached by the given word. If there is no path for the word in the PTA, it will be added to
100	* the PTA on-the-fly.
101	*
102	* @param word
103	* the word
104	*
105	* @return the state reached by this word, which might have been newly created (along with all required predecessor
106	* states)
107	*/
108	public S getOrCreateState(IntSeq word) {
109	S curr = root;	2✔
110	for (int sym : word) {	2✔
111	curr = curr.getOrCreateSuccessor(sym, alphabetSize);	2✔
112	}	2✔
113
114	return curr;	2✔
115	}
116
117	public void addSampleWithStateProperties(IntSeq sample, List<? extends SP> lastStateProperties) {
118	int sampleLen = sample.size();	2✔
119	int skip = sampleLen + 1 - lastStateProperties.size();	2✔
120	if (skip < 0) {	2✔
121	throw new IllegalArgumentException();	×
122	}
123
124	S curr = getRoot();	2✔
125	int i = 0;	2✔
126	while (i < skip) {	2✔
127	int sym = sample.get(i++);	×
128	curr = curr.getOrCreateSuccessor(sym, alphabetSize);	×
129	}	×
130
131	Iterator<? extends SP> spIt = lastStateProperties.iterator();	2✔
132
133	while (i < sampleLen) {	2✔
134	curr.mergeStateProperty(spIt.next());	2✔
135	int sym = sample.get(i++);	2✔
136	curr = curr.getOrCreateSuccessor(sym, alphabetSize);	2✔
137	}	2✔
138
139	curr.mergeStateProperty(spIt.next());	2✔
140	}	2✔
141
142	public void addSampleWithTransitionProperties(IntSeq sample, List<? extends TP> lastTransitionProperties) {
143	int sampleLen = sample.size();	2✔
144	int skip = sampleLen - lastTransitionProperties.size();	2✔
145	if (skip < 0) {	2✔
146	throw new IllegalArgumentException();	×
147	}
148
149	S curr = getRoot();	2✔
150	int i = 0;	2✔
151	while (i < skip) {	2✔
152	int sym = sample.get(i++);	×
153	curr = curr.getOrCreateSuccessor(sym, alphabetSize);	×
154	}	×
155
156	Iterator<? extends TP> tpIt = lastTransitionProperties.iterator();	2✔
157	while (i < sampleLen) {	2✔
158	int sym = sample.get(i++);	2✔
159	curr.mergeTransitionProperty(sym, alphabetSize, tpIt.next());	2✔
160	curr = curr.getOrCreateSuccessor(sym, alphabetSize);	2✔
161	}	2✔
162	}	2✔
163
164	@Override
165	public S getSuccessor(PTATransition<S> transition) {
166	return transition.getTarget();	2✔
167	}
168
169	@Override
170	public @Nullable S getSuccessor(S state, Integer input) {
171	return state.getSuccessor(input);	2✔
172	}
173
174	@Override
175	public Iterator<S> iterator() {
176	Set<S> visited = new HashSet<>();	2✔
177	final Deque<S> bfsQueue = new ArrayDeque<>();	2✔
178	bfsQueue.add(root);	2✔
179	visited.add(root);	2✔
180
181	return new AbstractSimplifiedIterator<>() {	2✔
182
183	@Override
184	protected boolean calculateNext() {
185	final S next = bfsQueue.poll();	2✔
186	if (next == null) {	2✔
187	return false;	2✔
188	}
189	super.nextValue = next;	2✔
190	for (int i = 0; i < alphabetSize; i++) {	2✔
191	final S child = next.getSuccessor(i);	2✔
192	if (child != null && visited.add(child)) {	2✔
193	bfsQueue.offer(child);	2✔
194	}
195	}
196	return true;	2✔
197	}
198	};
199	}
200
201	@Override
202	public Collection<S> getStates() {
203	List<S> stateList = new ArrayList<>();	2✔
204	Set<S> visited = new HashSet<>();	2✔
205
206	int ptr = 0;	2✔
207	stateList.add(root);	2✔
208	visited.add(root);	2✔
209	int numStates = 1;	2✔
210
211	while (ptr < numStates) {	2✔
212	S curr = stateList.get(ptr++);	2✔
213	for (int i = 0; i < alphabetSize; i++) {	2✔
214	S succ = curr.getSuccessor(i);	2✔
215	if (succ != null && visited.add(succ)) {	2✔
216	stateList.add(succ);	2✔
217	numStates++;	2✔
218	}
219	}
220	}	2✔
221
222	return stateList;	2✔
223	}
224
225	@Override
226	public S getInitialState() {
227	return getRoot();	2✔
228	}
229
230	@Override
231	public @Nullable PTATransition<S> getTransition(S state, Integer input) {
232	if (state.getSuccessor(input) == null) {	2✔
233	return null;	2✔
234	}
235
236	return new PTATransition<>(state, input);	2✔
237	}
238
239	@Override
240	public SP getStateProperty(S state) {
241	return state.getStateProperty();	2✔
242	}
243
244	@Override
245	public TP getTransitionProperty(PTATransition<S> transition) {
246	return transition.getSource().getTransProperty(transition.getIndex());	2✔
247	}
248
249	@Override
250	public UniversalGraph<S, TransitionEdge<Integer, PTATransition<S>>, SP, Property<Integer, TP>> transitionGraphView(
251	Collection<? extends Integer> inputs) {
252	return new UniversalAutomatonGraphView<>(this, inputs) {	2✔
253
254	@Override
255	public VisualizationHelper<S, TransitionEdge<Integer, PTATransition<S>>> getVisualizationHelper() {
256	return BasePTA.this.getVisualizationHelper();	2✔
257	}
258	};
259	}
260
261	protected VisualizationHelper<S, TransitionEdge<Integer, PTATransition<S>>> getVisualizationHelper() {
262	return new PTAVisualizationHelper<>(this);	×
263	}
264	}

LearnLib / learnlib / 31619759710

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