6611855081

Committed 23 Oct 2023 10:13AM UTC coverage: 93.275% (-0.003%) from 93.278%

Build # 6611855081

Build Type

push

github

Committed by

mtf90

Commit Message

partially revert f4f47b4

Make the (Base)PTA Integer-based again and instead use explicit wrapper classes to interpret it as a DFA/MealyMachine/etc.. This simplifies the internals of the (Base)PTA class and allows for more flexible usage (e.g., using the same PTA for different contexts). Performance-wise the number of symbol-to-index transformations should remain identical for the common use-cases (e.g., RPNI-based learning, etc.).

Run Details

98 of 98 new or added lines in 13 files covered. (100.0%)

11553 of 12386 relevant lines covered (93.27%)

1.69 hits per line

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

90.43

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

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.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.Map;
import java.util.Objects;
import java.util.Set;

import com.google.common.collect.AbstractIterator;
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.automaton.visualization.AutomatonVisualizationHelper;
import net.automatalib.common.smartcollection.IntSeq;
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 = Objects.requireNonNull(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 AbstractIterator<S>() {

            @Override
            protected S computeNext() {
                S next = bfsQueue.poll();
                if (next == null) {
                    return endOfData();
                }
                for (int i = 0; i < alphabetSize; i++) {
                    S child = next.getSuccessor(i);
                    if (child != null && visited.add(child)) {
                        bfsQueue.offer(child);
                    }
                }
                return next;
            }
        };
    }

    @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<S, Integer, PTATransition<S>, SP, TP, BasePTA<S, SP, TP>>(this, inputs) {

            @Override
            public VisualizationHelper<S, TransitionEdge<Integer, PTATransition<S>>> getVisualizationHelper() {
                return new AutomatonVisualizationHelper<S, Integer, PTATransition<S>, BasePTA<S, SP, TP>>(BasePTA.this) {

                    @Override
                    public boolean getEdgeProperties(S src,
                                                     TransitionEdge<Integer, PTATransition<S>> edge,
                                                     S tgt,
                                                     Map<String, String> properties) {
                        if (!super.getEdgeProperties(src, edge, tgt, properties)) {
                            return false;
                        }
                        final Integer input = edge.getInput();
                        properties.put(EdgeAttrs.LABEL, input + " / " + src.getTransProperty(input));
                        return true;
                    }

                    @Override
                    public boolean getNodeProperties(S node, Map<String, String> properties) {
                        properties.put(NodeAttrs.LABEL, Objects.toString(node.getProperty()));
                        return super.getNodeProperties(node, properties);
                    }
                };
            }
        };
    }
}

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

LearnLib / learnlib / 6611855081

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