6805330902

Committed 08 Nov 2023 11:40PM UTC coverage: 93.335% (+0.008%) from 93.327%

Build # 6805330902

Build Type

push

github

Committed by

mtf90

Commit Message

typo

Run Details

11736 of 12574 relevant lines covered (93.34%)

1.69 hits per line

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

92.31

/algorithms/active/ttt/src/main/java/de/learnlib/algorithm/ttt/base/AbstractTTTHypothesis.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.algorithm.ttt.base;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Map;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.Alphabets;
import net.automatalib.alphabet.GrowingAlphabet;
import net.automatalib.alphabet.SupportsGrowingAlphabet;
import net.automatalib.automaton.DeterministicAutomaton;
import net.automatalib.automaton.FiniteAlphabetAutomaton;
import net.automatalib.automaton.fsa.DFA;
import net.automatalib.graph.Graph;
import net.automatalib.visualization.DefaultVisualizationHelper;
import net.automatalib.visualization.VisualizationHelper;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Hypothesis DFA for the {@link AbstractTTTLearner TTT algorithm}.
 *
 * @param <S>
 *         state class type
 * @param <I>
 *         input symbol type
 * @param <D>
 *         output domain type
 * @param <T>
 *         transition type
 */
public abstract class AbstractTTTHypothesis<S extends TTTState<I, D>, I, D, T>
        implements DeterministicAutomaton<S, I, T>,
                   FiniteAlphabetAutomaton<S, I, T>,
                   DeterministicAutomaton.FullIntAbstraction<T>,
                   SupportsGrowingAlphabet<I> {

    protected final List<S> states = new ArrayList<>();

    private final Alphabet<I> alphabet;
    private int alphabetSize;

    private S initialState;

    /**
     * Constructor.
     *
     * @param alphabet
     *         the input alphabet
     */
    public AbstractTTTHypothesis(Alphabet<I> alphabet) {
        this.alphabet = alphabet;
        this.alphabetSize = this.alphabet.size();
    }

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

    @Override
    public T getTransition(int stateId, int symIdx) {
        S state = states.get(stateId);
        TTTTransition<I, D> trans = getInternalTransition(state, symIdx);
        return mapTransition(trans);
    }

    @Override
    public @Nullable T getTransition(S state, I input) {
        TTTTransition<I, D> trans = getInternalTransition(state, input);
        return trans == null ? null : mapTransition(trans);
    }

    /**
     * Retrieves the <i>internal</i> transition (i.e., the {@link TTTTransition} object) for a given state and input.
     * This method is required since the {@link DFA} interface requires the return value of
     * {@link #getTransition(TTTState, Object)} to refer to the successor state directly.
     *
     * @param state
     *         the source state
     * @param input
     *         the input symbol triggering the transition
     *
     * @return the transition object
     */
    public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, I input) {
        int inputIdx = alphabet.getSymbolIndex(input);
        return getInternalTransition(state, inputIdx);
    }

    public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, int input) {
        return state.getTransition(input);
    }

    protected abstract T mapTransition(TTTTransition<I, D> internalTransition);

    /**
     * Initializes the automaton, adding an initial state. Whether the initial state is accepting needs to be known at
     * this point.
     *
     * @return the initial state of this newly initialized automaton
     */
    public S initialize() {
        assert !isInitialized();

        initialState = createState(null);
        return initialState;
    }

    /**
     * Checks whether this automaton was initialized (i.e., {@link #initialize()} has been called).
     *
     * @return {@code true} if this automaton was initialized, {@code false} otherwise.
     */
    public boolean isInitialized() {
        return initialState != null;
    }

    public S createState(TTTTransition<I, D> parent) {
        S state = newState(alphabet.size(), parent, states.size());
        states.add(state);
        if (parent != null) {
            parent.makeTree(state);
        }
        return state;
    }

    protected abstract S newState(int alphabetSize, TTTTransition<I, D> parent, int id);

    @Override
    public Alphabet<I> getInputAlphabet() {
        return alphabet;
    }

    @Override
    public GraphView graphView() {
        return new GraphView();
    }

    @Override
    public int getIntInitialState() {
        return 0;
    }

    @Override
    public int numInputs() {
        return alphabet.size();
    }

    @Override
    public int getIntSuccessor(T trans) {
        return getSuccessor(trans).id;
    }

    @Override
    public DeterministicAutomaton.FullIntAbstraction<T> fullIntAbstraction(Alphabet<I> alphabet) {
        if (alphabet == this.alphabet) {
            return this;
        }
        return DeterministicAutomaton.super.fullIntAbstraction(alphabet);
    }

    @Override
    public void addAlphabetSymbol(I symbol) {
        final GrowingAlphabet<I> growingAlphabet = Alphabets.toGrowingAlphabetOrThrowException(this.alphabet);

        if (!growingAlphabet.containsSymbol(symbol)) {
            growingAlphabet.addSymbol(symbol);
        }

        final int newAlphabetSize = growingAlphabet.size();

        if (alphabetSize < newAlphabetSize) {
            for (TTTState<I, D> s : this.getStates()) {
                s.ensureInputCapacity(newAlphabetSize);
            }

            alphabetSize = newAlphabetSize;
        }
    }

    @Override
    public Collection<S> getStates() {
        return Collections.unmodifiableList(states);
    }

    @Override
    public int size() {
        return states.size();
    }

    public static final class TTTEdge<I, D> {

        public final TTTTransition<I, D> transition;
        public final TTTState<I, D> target;

        public TTTEdge(TTTTransition<I, D> transition, TTTState<I, D> target) {
            this.transition = transition;
            this.target = target;
        }
    }

    public class GraphView implements Graph<TTTState<I, D>, TTTEdge<I, D>> {

        @Override
        public Collection<TTTState<I, D>> getNodes() {
            return Collections.unmodifiableList(states);
        }

        @Override
        public Collection<TTTEdge<I, D>> getOutgoingEdges(TTTState<I, D> node) {
            List<TTTEdge<I, D>> result = new ArrayList<>();
            for (TTTTransition<I, D> trans : node.getTransitions()) {
                for (TTTState<I, D> target : trans.getDTTarget().subtreeStates()) {
                    result.add(new TTTEdge<>(trans, target));
                }
            }
            return result;
        }

        @Override
        public TTTState<I, D> getTarget(TTTEdge<I, D> edge) {
            return edge.target;
        }

        @Override
        public VisualizationHelper<TTTState<I, D>, TTTEdge<I, D>> getVisualizationHelper() {
            return new DefaultVisualizationHelper<TTTState<I, D>, TTTEdge<I, D>>() {

                @Override
                public boolean getEdgeProperties(TTTState<I, D> src,
                                                 TTTEdge<I, D> edge,
                                                 TTTState<I, D> tgt,
                                                 Map<String, String> properties) {
                    super.getEdgeProperties(src, edge, tgt, properties);

                    properties.put(EdgeAttrs.LABEL, String.valueOf(edge.transition.getInput()));
                    if (edge.transition.isTree()) {
                        properties.put(EdgeAttrs.STYLE, EdgeStyles.BOLD);
                    } else if (edge.transition.getDTTarget().isInner()) {
                        properties.put(EdgeAttrs.STYLE, EdgeStyles.DOTTED);
                    }

                    return true;
                }
            };
        }
    }
}

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.algorithm.ttt.base;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.List;
22	import java.util.Map;
23
24	import net.automatalib.alphabet.Alphabet;
25	import net.automatalib.alphabet.Alphabets;
26	import net.automatalib.alphabet.GrowingAlphabet;
27	import net.automatalib.alphabet.SupportsGrowingAlphabet;
28	import net.automatalib.automaton.DeterministicAutomaton;
29	import net.automatalib.automaton.FiniteAlphabetAutomaton;
30	import net.automatalib.automaton.fsa.DFA;
31	import net.automatalib.graph.Graph;
32	import net.automatalib.visualization.DefaultVisualizationHelper;
33	import net.automatalib.visualization.VisualizationHelper;
34	import org.checkerframework.checker.nullness.qual.Nullable;
35
36	/**
37	* Hypothesis DFA for the {@link AbstractTTTLearner TTT algorithm}.
38	*
39	* @param <S>
40	* state class type
41	* @param <I>
42	* input symbol type
43	* @param <D>
44	* output domain type
45	* @param <T>
46	* transition type
47	*/
48	public abstract class AbstractTTTHypothesis<S extends TTTState<I, D>, I, D, T>	2✔
49	implements DeterministicAutomaton<S, I, T>,
50	FiniteAlphabetAutomaton<S, I, T>,
51	DeterministicAutomaton.FullIntAbstraction<T>,
52	SupportsGrowingAlphabet<I> {
53
54	protected final List<S> states = new ArrayList<>();	2✔
55
56	private final Alphabet<I> alphabet;
57	private int alphabetSize;
58
59	private S initialState;
60
61	/**
62	* Constructor.
63	*
64	* @param alphabet
65	* the input alphabet
66	*/
67	public AbstractTTTHypothesis(Alphabet<I> alphabet) {	2✔
68	this.alphabet = alphabet;	2✔
69	this.alphabetSize = this.alphabet.size();	2✔
70	}	2✔
71
72	@Override
73	public S getInitialState() {
74	return initialState;	2✔
75	}
76
77	@Override
78	public T getTransition(int stateId, int symIdx) {
79	S state = states.get(stateId);	2✔
80	TTTTransition<I, D> trans = getInternalTransition(state, symIdx);	2✔
81	return mapTransition(trans);	2✔
82	}
83
84	@Override
85	public @Nullable T getTransition(S state, I input) {
86	TTTTransition<I, D> trans = getInternalTransition(state, input);	2✔
87	return trans == null ? null : mapTransition(trans);	2✔
88	}
89
90	/**
91	* Retrieves the <i>internal</i> transition (i.e., the {@link TTTTransition} object) for a given state and input.
92	* This method is required since the {@link DFA} interface requires the return value of
93	* {@link #getTransition(TTTState, Object)} to refer to the successor state directly.
94	*
95	* @param state
96	* the source state
97	* @param input
98	* the input symbol triggering the transition
99	*
100	* @return the transition object
101	*/
102	public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, I input) {
103	int inputIdx = alphabet.getSymbolIndex(input);	2✔
104	return getInternalTransition(state, inputIdx);	2✔
105	}
106
107	public TTTTransition<I, D> getInternalTransition(TTTState<I, D> state, int input) {
108	return state.getTransition(input);	2✔
109	}
110
111	protected abstract T mapTransition(TTTTransition<I, D> internalTransition);
112
113	/**
114	* Initializes the automaton, adding an initial state. Whether the initial state is accepting needs to be known at
115	* this point.
116	*
117	* @return the initial state of this newly initialized automaton
118	*/
119	public S initialize() {
120	assert !isInitialized();	2✔
121
122	initialState = createState(null);	2✔
123	return initialState;	2✔
124	}
125
126	/**
127	* Checks whether this automaton was initialized (i.e., {@link #initialize()} has been called).
128	*
129	* @return {@code true} if this automaton was initialized, {@code false} otherwise.
130	*/
131	public boolean isInitialized() {
132	return initialState != null;	2✔
133	}
134
135	public S createState(TTTTransition<I, D> parent) {
136	S state = newState(alphabet.size(), parent, states.size());	2✔
137	states.add(state);	2✔
138	if (parent != null) {	2✔
139	parent.makeTree(state);	2✔
140	}
141	return state;	2✔
142	}
143
144	protected abstract S newState(int alphabetSize, TTTTransition<I, D> parent, int id);
145
146	@Override
147	public Alphabet<I> getInputAlphabet() {
148	return alphabet;	2✔
149	}
150
151	@Override
152	public GraphView graphView() {
153	return new GraphView();	2✔
154	}
155
156	@Override
157	public int getIntInitialState() {
158	return 0;	2✔
159	}
160
161	@Override
162	public int numInputs() {
163	return alphabet.size();	2✔
164	}
165
166	@Override
167	public int getIntSuccessor(T trans) {
168	return getSuccessor(trans).id;	2✔
169	}
170
171	@Override
172	public DeterministicAutomaton.FullIntAbstraction<T> fullIntAbstraction(Alphabet<I> alphabet) {
173	if (alphabet == this.alphabet) {	×
174	return this;	×
175	}
176	return DeterministicAutomaton.super.fullIntAbstraction(alphabet);	×
177	}
178
179	@Override
180	public void addAlphabetSymbol(I symbol) {
181	final GrowingAlphabet<I> growingAlphabet = Alphabets.toGrowingAlphabetOrThrowException(this.alphabet);	2✔
182
183	if (!growingAlphabet.containsSymbol(symbol)) {	2✔
184	growingAlphabet.addSymbol(symbol);	×
185	}
186
187	final int newAlphabetSize = growingAlphabet.size();	2✔
188
189	if (alphabetSize < newAlphabetSize) {	2✔
190	for (TTTState<I, D> s : this.getStates()) {	2✔
191	s.ensureInputCapacity(newAlphabetSize);	2✔
192	}	2✔
193
194	alphabetSize = newAlphabetSize;	2✔
195	}
196	}	2✔
197
198	@Override
199	public Collection<S> getStates() {
200	return Collections.unmodifiableList(states);	2✔
201	}
202
203	@Override
204	public int size() {
205	return states.size();	2✔
206	}
207
208	public static final class TTTEdge<I, D> {
209
210	public final TTTTransition<I, D> transition;
211	public final TTTState<I, D> target;
212
213	public TTTEdge(TTTTransition<I, D> transition, TTTState<I, D> target) {	2✔
214	this.transition = transition;	2✔
215	this.target = target;	2✔
216	}	2✔
217	}
218
219	public class GraphView implements Graph<TTTState<I, D>, TTTEdge<I, D>> {	2✔
220
221	@Override
222	public Collection<TTTState<I, D>> getNodes() {
223	return Collections.unmodifiableList(states);	2✔
224	}
225
226	@Override
227	public Collection<TTTEdge<I, D>> getOutgoingEdges(TTTState<I, D> node) {
228	List<TTTEdge<I, D>> result = new ArrayList<>();	2✔
229	for (TTTTransition<I, D> trans : node.getTransitions()) {	2✔
230	for (TTTState<I, D> target : trans.getDTTarget().subtreeStates()) {	2✔
231	result.add(new TTTEdge<>(trans, target));	2✔
232	}	2✔
233	}
234	return result;	2✔
235	}
236
237	@Override
238	public TTTState<I, D> getTarget(TTTEdge<I, D> edge) {
239	return edge.target;	2✔
240	}
241
242	@Override
243	public VisualizationHelper<TTTState<I, D>, TTTEdge<I, D>> getVisualizationHelper() {
244	return new DefaultVisualizationHelper<TTTState<I, D>, TTTEdge<I, D>>() {	2✔
245
246	@Override
247	public boolean getEdgeProperties(TTTState<I, D> src,
248	TTTEdge<I, D> edge,
249	TTTState<I, D> tgt,
250	Map<String, String> properties) {
251	super.getEdgeProperties(src, edge, tgt, properties);	2✔
252
253	properties.put(EdgeAttrs.LABEL, String.valueOf(edge.transition.getInput()));	2✔
254	if (edge.transition.isTree()) {	2✔
255	properties.put(EdgeAttrs.STYLE, EdgeStyles.BOLD);	2✔
256	} else if (edge.transition.getDTTarget().isInner()) {	2✔
257	properties.put(EdgeAttrs.STYLE, EdgeStyles.DOTTED);	×
258	}
259
260	return true;	2✔
261	}
262	};
263	}
264	}
265	}

LearnLib / learnlib / 6805330902

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