6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

96.15

/algorithms/active/adt/src/main/java/de/learnlib/algorithms/adt/util/ADTUtil.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.algorithms.adt.util;

import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.function.Function;

import de.learnlib.algorithms.adt.adt.ADTLeafNode;
import de.learnlib.algorithms.adt.adt.ADTNode;
import de.learnlib.algorithms.adt.adt.ADTSymbolNode;
import net.automatalib.automata.transducers.MealyMachine;
import net.automatalib.commons.util.Pair;
import net.automatalib.graphs.ads.ADSNode;
import net.automatalib.words.Word;
import net.automatalib.words.WordBuilder;

/**
 * Utility class, that offers some operations revolving around adaptive distinguishing sequences.
 */
public final class ADTUtil {

    private ADTUtil() {
        // prevent instantiation
    }

    public static <S, I, O> boolean isSymbolNode(ADTNode<S, I, O> node) {
        return checkNodeType(node, ADTNode.NodeType.SYMBOL_NODE);
    }

    private static <S, I, O> boolean checkNodeType(ADTNode<S, I, O> node, ADTNode.NodeType type) {
        return node != null && node.getNodeType() == type;
    }

    public static <S, I, O> ADTNode<S, I, O> getStartOfADS(ADTNode<S, I, O> node) {

        ADTNode<S, I, O> iter = node;

        while (iter.getParent() != null && !ADTUtil.isResetNode(iter.getParent())) {
            iter = iter.getParent();
        }

        return iter;
    }

    public static <S, I, O> boolean isResetNode(ADTNode<S, I, O> node) {
        return checkNodeType(node, ADTNode.NodeType.RESET_NODE);
    }

    public static <S, I, O> Set<S> collectHypothesisStates(ADTNode<S, I, O> root) {
        final Set<S> result = new LinkedHashSet<>();
        collectTransformedLeavesRecursively(result, root, ADTNode::getHypothesisState);
        return result;
    }

    public static <S, I, O> Set<ADTNode<S, I, O>> collectLeaves(ADTNode<S, I, O> root) {
        final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();
        collectTransformedLeavesRecursively(result, root, Function.identity());
        return result;
    }

    private static <S, I, O, T> void collectTransformedLeavesRecursively(Set<T> nodes,
                                                                         ADTNode<S, I, O> current,
                                                                         Function<ADTNode<S, I, O>, T> transformer) {
        if (ADTUtil.isLeafNode(current)) {
            nodes.add(transformer.apply(current));
        } else {
            for (ADTNode<S, I, O> n : current.getChildren().values()) {
                collectTransformedLeavesRecursively(nodes, n, transformer);
            }
        }
    }

    public static <S, I, O> Set<ADTNode<S, I, O>> collectADSNodes(ADTNode<S, I, O> root) {
        final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();
        result.add(root);
        collectADSNodesRecursively(result, root);
        return result;
    }

    private static <S, I, O> void collectADSNodesRecursively(Set<ADTNode<S, I, O>> nodes,
                                                             ADTNode<S, I, O> current) {
        if (ADTUtil.isResetNode(current)) {
            nodes.addAll(current.getChildren().values());
        }

        for (ADTNode<S, I, O> n : current.getChildren().values()) {
            collectADSNodesRecursively(nodes, n);
        }
    }

    public static <S, I, O> Set<ADTNode<S, I, O>> collectResetNodes(ADTNode<S, I, O> root) {
        final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();
        collectResetNodesRecursively(result, root);
        return result;
    }

    private static <S, I, O> void collectResetNodesRecursively(Set<ADTNode<S, I, O>> nodes, ADTNode<S, I, O> current) {
        if (ADTUtil.isResetNode(current)) {
            nodes.add(current);
        }

        for (ADTNode<S, I, O> n : current.getChildren().values()) {
            collectResetNodesRecursively(nodes, n);
        }
    }

    public static <S, I, O> Set<ADTNode<S, I, O>> collectDirectSubADSs(ADTNode<S, I, O> node) {
        final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();
        collectDirectSubTreesRecursively(result, node);
        return result;

    }

    private static <S, I, O> void collectDirectSubTreesRecursively(Set<ADTNode<S, I, O>> nodes,
                                                                   ADTNode<S, I, O> current) {
        if (ADTUtil.isResetNode(current)) {
            nodes.addAll(current.getChildren().values());
        } else {
            for (ADTNode<S, I, O> n : current.getChildren().values()) {
                collectDirectSubTreesRecursively(nodes, n);
            }
        }
    }

    public static <S, I, O> Pair<Word<I>, Word<O>> buildTraceForNode(ADTNode<S, I, O> node) {

        ADTNode<S, I, O> parentIter = node.getParent();
        ADTNode<S, I, O> nodeIter = node;
        final WordBuilder<I> inputBuilder = new WordBuilder<>();
        final WordBuilder<O> outputBuilder = new WordBuilder<>();

        while (parentIter != null && !ADTUtil.isResetNode(parentIter)) {
            inputBuilder.append(parentIter.getSymbol());
            outputBuilder.append(ADTUtil.getOutputForSuccessor(parentIter, nodeIter));

            nodeIter = parentIter;
            parentIter = parentIter.getParent();
        }

        return Pair.of(inputBuilder.reverse().toWord(), outputBuilder.reverse().toWord());
    }

    public static <S, I, O> O getOutputForSuccessor(ADTNode<S, I, O> node, ADTNode<S, I, O> successor) {

        if (!node.equals(successor.getParent())) {
            throw new IllegalArgumentException("No parent relationship");
        }

        for (Map.Entry<O, ADTNode<S, I, O>> entry : node.getChildren().entrySet()) {
            if (entry.getValue().equals(successor)) {
                return entry.getKey();
            }
        }

        throw new IllegalArgumentException("No child relationship");
    }

    /**
     * Utility method that wraps an ADS of type {@link ADSNode} into the equivalent ADS of type {@link ADTNode}.
     *
     * @param node
     *         the root node of the ADS
     * @param <S>
     *         (hypothesis) state type
     * @param <I>
     *         input alphabet type
     * @param <O>
     *         output alphabet type
     *
     * @return an equivalent ADS using the {@link ADTNode} interface
     */
    public static <S, I, O> ADTNode<S, I, O> buildFromADS(ADSNode<S, I, O> node) {

        if (node.isLeaf()) {
            return new ADTLeafNode<>(null, node.getHypothesisState());
        }

        final ADTNode<S, I, O> result = new ADTSymbolNode<>(null, node.getSymbol());

        for (Map.Entry<O, ADSNode<S, I, O>> entry : node.getChildren().entrySet()) {
            final O adsOutput = entry.getKey();
            final ADSNode<S, I, O> adsNode = entry.getValue();

            final ADTNode<S, I, O> newChild = buildFromADS(adsNode);
            newChild.setParent(result);
            result.getChildren().put(adsOutput, newChild);
        }

        return result;
    }

    /**
     * Computes how often reset nodes are encountered when traversing from the given node to the leaves of the induced
     * subtree of the given node.
     *
     * @param adt
     *         the node whose subtree should be analyzed
     * @param <S>
     *         (hypothesis) state type
     * @param <I>
     *         input alphabet type
     * @param <O>
     *         output alphabet type
     *
     * @return the number of encountered reset nodes
     */
    public static <S, I, O> int computeEffectiveResets(ADTNode<S, I, O> adt) {
        return computeEffectiveResetsInternal(adt, 0);
    }

    private static <S, I, O> int computeEffectiveResetsInternal(ADTNode<S, I, O> ads, int accumulatedResets) {
        if (ADTUtil.isLeafNode(ads)) {
            return accumulatedResets;
        }

        final int nextCosts = ADTUtil.isResetNode(ads) ? accumulatedResets + 1 : accumulatedResets;

        return ads.getChildren().values().stream().mapToInt(x -> computeEffectiveResetsInternal(x, nextCosts)).sum();
    }

    public static <S, I, O> Pair<ADTNode<S, I, O>, ADTNode<S, I, O>> buildADSFromTrace(MealyMachine<S, I, ?, O> automaton,
                                                                                       Word<I> trace,
                                                                                       S state) {

        final Iterator<I> sequenceIter = trace.iterator();
        final I input = sequenceIter.next();
        final ADTNode<S, I, O> head = new ADTSymbolNode<>(null, input);

        ADTNode<S, I, O> tempADS = head;
        I tempInput = input;
        S tempState = state;

        while (sequenceIter.hasNext()) {
            final I nextInput = sequenceIter.next();
            final ADTNode<S, I, O> nextNode = new ADTSymbolNode<>(tempADS, nextInput);

            final O oldOutput = automaton.getOutput(tempState, tempInput);

            tempADS.getChildren().put(oldOutput, nextNode);

            tempADS = nextNode;
            tempState = automaton.getSuccessor(tempState, tempInput);
            tempInput = nextInput;
        }

        return Pair.of(head, tempADS);
    }

    /**
     * Build a single trace ADS from the given information.
     *
     * @param input
     *         the input sequence of the trace
     * @param output
     *         the output sequence of the trace
     * @param finalState
     *         the hypothesis state that should be referenced in the leaf of the ADS
     * @param <S>
     *         (hypothesis) state type
     * @param <I>
     *         input alphabet type
     * @param <O>
     *         output alphabet type
     *
     * @return the root node of the constructed ADS
     */
    public static <S, I, O> ADTNode<S, I, O> buildADSFromObservation(Word<I> input,
                                                                     Word<O> output,
                                                                     S finalState) {

        if (input.size() != output.size()) {
            throw new IllegalArgumentException("Arguments differ in length");
        }

        final Iterator<I> inputIterator = input.iterator();
        final Iterator<O> outputIterator = output.iterator();

        final ADTNode<S, I, O> result = new ADTSymbolNode<>(null, inputIterator.next());
        ADTNode<S, I, O> nodeIter = result;

        while (inputIterator.hasNext()) {
            final ADTNode<S, I, O> nextNode = new ADTSymbolNode<>(nodeIter, inputIterator.next());
            nodeIter.getChildren().put(outputIterator.next(), nextNode);

            nodeIter = nextNode;
        }

        final ADTNode<S, I, O> finalNode = new ADTLeafNode<>(nodeIter, finalState);
        nodeIter.getChildren().put(outputIterator.next(), finalNode);

        return result;
    }

    /**
     * Tries to merge the given (single trace) ADSs (which only contains one leaf) into the given parent ADSs. If
     * possible, the parent ADS is altered as a side effect
     *
     * @param parent
     *         the parent ADS in which the given child ADS should be merged into
     * @param child
     *         the (single trace) ADS which should be incorporated into the parent ADS.
     * @param <S>
     *         (hypothesis) state type
     * @param <I>
     *         input alphabet type
     * @param <O>
     *         output alphabet type
     *
     * @return {@code true} if ADSs could be merged, {@code false} otherwise
     */
    public static <S, I, O> boolean mergeADS(ADTNode<S, I, O> parent, ADTNode<S, I, O> child) {

        ADTNode<S, I, O> parentIter = parent, childIter = child;

        while (!(ADTUtil.isLeafNode(parentIter) || ADTUtil.isResetNode(parentIter)) && !ADTUtil.isLeafNode(childIter)) {

            if (!Objects.equals(parentIter.getSymbol(), childIter.getSymbol())) {
                return false;
            }

            final Map<O, ADTNode<S, I, O>> childSuccessors = childIter.getChildren();

            if (childSuccessors.size() != 1) {
                throw new IllegalArgumentException("No single trace child");
            }

            final Map<O, ADTNode<S, I, O>> parentSuccessors = parentIter.getChildren();

            final Map.Entry<O, ADTNode<S, I, O>> childSuccessor = childSuccessors.entrySet().iterator().next();
            final O childOutput = childSuccessor.getKey();
            final ADTNode<S, I, O> childADS = childSuccessor.getValue();

            if (!parentSuccessors.containsKey(childOutput)) {
                parentSuccessors.put(childOutput, childADS);
                childADS.setParent(parentIter);
                return true;
            }

            parentIter = parentSuccessors.get(childOutput);
            childIter = childADS;
        }

        return false;
    }

    public static <S, I, O> boolean isLeafNode(ADTNode<S, I, O> node) {
        return checkNodeType(node, ADTNode.NodeType.LEAF_NODE);
    }
}

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.algorithms.adt.util;
17
18	import java.util.Iterator;
19	import java.util.LinkedHashSet;
20	import java.util.Map;
21	import java.util.Objects;
22	import java.util.Set;
23	import java.util.function.Function;
24
25	import de.learnlib.algorithms.adt.adt.ADTLeafNode;
26	import de.learnlib.algorithms.adt.adt.ADTNode;
27	import de.learnlib.algorithms.adt.adt.ADTSymbolNode;
28	import net.automatalib.automata.transducers.MealyMachine;
29	import net.automatalib.commons.util.Pair;
30	import net.automatalib.graphs.ads.ADSNode;
31	import net.automatalib.words.Word;
32	import net.automatalib.words.WordBuilder;
33
34	/**
35	* Utility class, that offers some operations revolving around adaptive distinguishing sequences.
36	*/
37	public final class ADTUtil {
38
39	private ADTUtil() {
40	// prevent instantiation
41	}
42
43	public static <S, I, O> boolean isSymbolNode(ADTNode<S, I, O> node) {
44	return checkNodeType(node, ADTNode.NodeType.SYMBOL_NODE);	2✔
45	}
46
47	private static <S, I, O> boolean checkNodeType(ADTNode<S, I, O> node, ADTNode.NodeType type) {
48	return node != null && node.getNodeType() == type;	2✔
49	}
50
51	public static <S, I, O> ADTNode<S, I, O> getStartOfADS(ADTNode<S, I, O> node) {
52
53	ADTNode<S, I, O> iter = node;	2✔
54
55	while (iter.getParent() != null && !ADTUtil.isResetNode(iter.getParent())) {	2✔
56	iter = iter.getParent();	2✔
57	}
58
59	return iter;	2✔
60	}
61
62	public static <S, I, O> boolean isResetNode(ADTNode<S, I, O> node) {
63	return checkNodeType(node, ADTNode.NodeType.RESET_NODE);	2✔
64	}
65
66	public static <S, I, O> Set<S> collectHypothesisStates(ADTNode<S, I, O> root) {
67	final Set<S> result = new LinkedHashSet<>();	2✔
68	collectTransformedLeavesRecursively(result, root, ADTNode::getHypothesisState);	2✔
69	return result;	2✔
70	}
71
72	public static <S, I, O> Set<ADTNode<S, I, O>> collectLeaves(ADTNode<S, I, O> root) {
73	final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();	2✔
74	collectTransformedLeavesRecursively(result, root, Function.identity());	2✔
75	return result;	2✔
76	}
77
78	private static <S, I, O, T> void collectTransformedLeavesRecursively(Set<T> nodes,
79	ADTNode<S, I, O> current,
80	Function<ADTNode<S, I, O>, T> transformer) {
81	if (ADTUtil.isLeafNode(current)) {	2✔
82	nodes.add(transformer.apply(current));	2✔
83	} else {
84	for (ADTNode<S, I, O> n : current.getChildren().values()) {	2✔
85	collectTransformedLeavesRecursively(nodes, n, transformer);	2✔
86	}	2✔
87	}
88	}	2✔
89
90	public static <S, I, O> Set<ADTNode<S, I, O>> collectADSNodes(ADTNode<S, I, O> root) {
91	final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();	2✔
92	result.add(root);	2✔
93	collectADSNodesRecursively(result, root);	2✔
94	return result;	2✔
95	}
96
97	private static <S, I, O> void collectADSNodesRecursively(Set<ADTNode<S, I, O>> nodes,
98	ADTNode<S, I, O> current) {
99	if (ADTUtil.isResetNode(current)) {	2✔
100	nodes.addAll(current.getChildren().values());	2✔
101	}
102
103	for (ADTNode<S, I, O> n : current.getChildren().values()) {	2✔
104	collectADSNodesRecursively(nodes, n);	2✔
105	}	2✔
106	}	2✔
107
108	public static <S, I, O> Set<ADTNode<S, I, O>> collectResetNodes(ADTNode<S, I, O> root) {
109	final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();	2✔
110	collectResetNodesRecursively(result, root);	2✔
111	return result;	2✔
112	}
113
114	private static <S, I, O> void collectResetNodesRecursively(Set<ADTNode<S, I, O>> nodes, ADTNode<S, I, O> current) {
115	if (ADTUtil.isResetNode(current)) {	2✔
116	nodes.add(current);	2✔
117	}
118
119	for (ADTNode<S, I, O> n : current.getChildren().values()) {	2✔
120	collectResetNodesRecursively(nodes, n);	2✔
121	}	2✔
122	}	2✔
123
124	public static <S, I, O> Set<ADTNode<S, I, O>> collectDirectSubADSs(ADTNode<S, I, O> node) {
125	final Set<ADTNode<S, I, O>> result = new LinkedHashSet<>();	2✔
126	collectDirectSubTreesRecursively(result, node);	2✔
127	return result;	2✔
128
129	}
130
131	private static <S, I, O> void collectDirectSubTreesRecursively(Set<ADTNode<S, I, O>> nodes,
132	ADTNode<S, I, O> current) {
133	if (ADTUtil.isResetNode(current)) {	2✔
134	nodes.addAll(current.getChildren().values());	2✔
135	} else {
136	for (ADTNode<S, I, O> n : current.getChildren().values()) {	2✔
137	collectDirectSubTreesRecursively(nodes, n);	2✔
138	}	2✔
139	}
140	}	2✔
141
142	public static <S, I, O> Pair<Word<I>, Word<O>> buildTraceForNode(ADTNode<S, I, O> node) {
143
144	ADTNode<S, I, O> parentIter = node.getParent();	2✔
145	ADTNode<S, I, O> nodeIter = node;	2✔
146	final WordBuilder<I> inputBuilder = new WordBuilder<>();	2✔
147	final WordBuilder<O> outputBuilder = new WordBuilder<>();	2✔
148
149	while (parentIter != null && !ADTUtil.isResetNode(parentIter)) {	2✔
150	inputBuilder.append(parentIter.getSymbol());	2✔
151	outputBuilder.append(ADTUtil.getOutputForSuccessor(parentIter, nodeIter));	2✔
152
153	nodeIter = parentIter;	2✔
154	parentIter = parentIter.getParent();	2✔
155	}
156
157	return Pair.of(inputBuilder.reverse().toWord(), outputBuilder.reverse().toWord());	2✔
158	}
159
160	public static <S, I, O> O getOutputForSuccessor(ADTNode<S, I, O> node, ADTNode<S, I, O> successor) {
161
162	if (!node.equals(successor.getParent())) {	2✔
163	throw new IllegalArgumentException("No parent relationship");	×
164	}
165
166	for (Map.Entry<O, ADTNode<S, I, O>> entry : node.getChildren().entrySet()) {	2✔
167	if (entry.getValue().equals(successor)) {	2✔
168	return entry.getKey();	2✔
169	}
170	}	2✔
171
172	throw new IllegalArgumentException("No child relationship");	×
173	}
174
175	/**
176	* Utility method that wraps an ADS of type {@link ADSNode} into the equivalent ADS of type {@link ADTNode}.
177	*
178	* @param node
179	* the root node of the ADS
180	* @param <S>
181	* (hypothesis) state type
182	* @param <I>
183	* input alphabet type
184	* @param <O>
185	* output alphabet type
186	*
187	* @return an equivalent ADS using the {@link ADTNode} interface
188	*/
189	public static <S, I, O> ADTNode<S, I, O> buildFromADS(ADSNode<S, I, O> node) {
190
191	if (node.isLeaf()) {	2✔
192	return new ADTLeafNode<>(null, node.getHypothesisState());	2✔
193	}
194
195	final ADTNode<S, I, O> result = new ADTSymbolNode<>(null, node.getSymbol());	2✔
196
197	for (Map.Entry<O, ADSNode<S, I, O>> entry : node.getChildren().entrySet()) {	2✔
198	final O adsOutput = entry.getKey();	2✔
199	final ADSNode<S, I, O> adsNode = entry.getValue();	2✔
200
201	final ADTNode<S, I, O> newChild = buildFromADS(adsNode);	2✔
202	newChild.setParent(result);	2✔
203	result.getChildren().put(adsOutput, newChild);	2✔
204	}	2✔
205
206	return result;	2✔
207	}
208
209	/**
210	* Computes how often reset nodes are encountered when traversing from the given node to the leaves of the induced
211	* subtree of the given node.
212	*
213	* @param adt
214	* the node whose subtree should be analyzed
215	* @param <S>
216	* (hypothesis) state type
217	* @param <I>
218	* input alphabet type
219	* @param <O>
220	* output alphabet type
221	*
222	* @return the number of encountered reset nodes
223	*/
224	public static <S, I, O> int computeEffectiveResets(ADTNode<S, I, O> adt) {
225	return computeEffectiveResetsInternal(adt, 0);	2✔
226	}
227
228	private static <S, I, O> int computeEffectiveResetsInternal(ADTNode<S, I, O> ads, int accumulatedResets) {
229	if (ADTUtil.isLeafNode(ads)) {	2✔
230	return accumulatedResets;	2✔
231	}
232
233	final int nextCosts = ADTUtil.isResetNode(ads) ? accumulatedResets + 1 : accumulatedResets;	2✔
234
235	return ads.getChildren().values().stream().mapToInt(x -> computeEffectiveResetsInternal(x, nextCosts)).sum();	2✔
236	}
237
238	public static <S, I, O> Pair<ADTNode<S, I, O>, ADTNode<S, I, O>> buildADSFromTrace(MealyMachine<S, I, ?, O> automaton,
239	Word<I> trace,
240	S state) {
241
242	final Iterator<I> sequenceIter = trace.iterator();	2✔
243	final I input = sequenceIter.next();	2✔
244	final ADTNode<S, I, O> head = new ADTSymbolNode<>(null, input);	2✔
245
246	ADTNode<S, I, O> tempADS = head;	2✔
247	I tempInput = input;	2✔
248	S tempState = state;	2✔
249
250	while (sequenceIter.hasNext()) {	2✔
251	final I nextInput = sequenceIter.next();	2✔
252	final ADTNode<S, I, O> nextNode = new ADTSymbolNode<>(tempADS, nextInput);	2✔
253
254	final O oldOutput = automaton.getOutput(tempState, tempInput);	2✔
255
256	tempADS.getChildren().put(oldOutput, nextNode);	2✔
257
258	tempADS = nextNode;	2✔
259	tempState = automaton.getSuccessor(tempState, tempInput);	2✔
260	tempInput = nextInput;	2✔
261	}	2✔
262
263	return Pair.of(head, tempADS);	2✔
264	}
265
266	/**
267	* Build a single trace ADS from the given information.
268	*
269	* @param input
270	* the input sequence of the trace
271	* @param output
272	* the output sequence of the trace
273	* @param finalState
274	* the hypothesis state that should be referenced in the leaf of the ADS
275	* @param <S>
276	* (hypothesis) state type
277	* @param <I>
278	* input alphabet type
279	* @param <O>
280	* output alphabet type
281	*
282	* @return the root node of the constructed ADS
283	*/
284	public static <S, I, O> ADTNode<S, I, O> buildADSFromObservation(Word<I> input,
285	Word<O> output,
286	S finalState) {
287
288	if (input.size() != output.size()) {	2✔
289	throw new IllegalArgumentException("Arguments differ in length");	×
290	}
291
292	final Iterator<I> inputIterator = input.iterator();	2✔
293	final Iterator<O> outputIterator = output.iterator();	2✔
294
295	final ADTNode<S, I, O> result = new ADTSymbolNode<>(null, inputIterator.next());	2✔
296	ADTNode<S, I, O> nodeIter = result;	2✔
297
298	while (inputIterator.hasNext()) {	2✔
299	final ADTNode<S, I, O> nextNode = new ADTSymbolNode<>(nodeIter, inputIterator.next());	2✔
300	nodeIter.getChildren().put(outputIterator.next(), nextNode);	2✔
301
302	nodeIter = nextNode;	2✔
303	}	2✔
304
305	final ADTNode<S, I, O> finalNode = new ADTLeafNode<>(nodeIter, finalState);	2✔
306	nodeIter.getChildren().put(outputIterator.next(), finalNode);	2✔
307
308	return result;	2✔
309	}
310
311	/**
312	* Tries to merge the given (single trace) ADSs (which only contains one leaf) into the given parent ADSs. If
313	* possible, the parent ADS is altered as a side effect
314	*
315	* @param parent
316	* the parent ADS in which the given child ADS should be merged into
317	* @param child
318	* the (single trace) ADS which should be incorporated into the parent ADS.
319	* @param <S>
320	* (hypothesis) state type
321	* @param <I>
322	* input alphabet type
323	* @param <O>
324	* output alphabet type
325	*
326	* @return {@code true} if ADSs could be merged, {@code false} otherwise
327	*/
328	public static <S, I, O> boolean mergeADS(ADTNode<S, I, O> parent, ADTNode<S, I, O> child) {
329
330	ADTNode<S, I, O> parentIter = parent, childIter = child;	2✔
331
332	while (!(ADTUtil.isLeafNode(parentIter) \|\| ADTUtil.isResetNode(parentIter)) && !ADTUtil.isLeafNode(childIter)) {	2✔
333
334	if (!Objects.equals(parentIter.getSymbol(), childIter.getSymbol())) {	2✔
335	return false;	×
336	}
337
338	final Map<O, ADTNode<S, I, O>> childSuccessors = childIter.getChildren();	2✔
339
340	if (childSuccessors.size() != 1) {	2✔
341	throw new IllegalArgumentException("No single trace child");	×
342	}
343
344	final Map<O, ADTNode<S, I, O>> parentSuccessors = parentIter.getChildren();	2✔
345
346	final Map.Entry<O, ADTNode<S, I, O>> childSuccessor = childSuccessors.entrySet().iterator().next();	2✔
347	final O childOutput = childSuccessor.getKey();	2✔
348	final ADTNode<S, I, O> childADS = childSuccessor.getValue();	2✔
349
350	if (!parentSuccessors.containsKey(childOutput)) {	2✔
351	parentSuccessors.put(childOutput, childADS);	2✔
352	childADS.setParent(parentIter);	2✔
353	return true;	2✔
354	}
355
356	parentIter = parentSuccessors.get(childOutput);	2✔
357	childIter = childADS;	2✔
358	}	2✔
359
360	return false;	2✔
361	}
362
363	public static <S, I, O> boolean isLeafNode(ADTNode<S, I, O> node) {
364	return checkNodeType(node, ADTNode.NodeType.LEAF_NODE);	2✔
365	}
366	}

LearnLib / learnlib / 6433387082

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