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

88.06

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

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

import de.learnlib.algorithms.adt.api.LeafSplitter;
import de.learnlib.algorithms.adt.config.LeafSplitters;
import de.learnlib.algorithms.adt.util.ADTUtil;
import de.learnlib.api.oracle.SymbolQueryOracle;
import net.automatalib.words.Word;

/**
 * The adaptive discrimination tree class. Essentially holds a reference to the root {@link ADTNode} and offers some
 * utility methods used throughout the learning process.
 *
 * @param <S>
 *         (hypothesis) state type
 * @param <I>
 *         input alphabet type
 * @param <O>
 *         output alphabet type
 */
public class ADT<S, I, O> {

    private ADTNode<S, I, O> root;

    /**
     * Initializes the ADT with a single leaf node.
     *
     * @param state
     *         the referenced state of the leaf
     */
    public void initialize(S state) {
        this.root = new ADTLeafNode<>(null, state);
    }

    /**
     * Returns the root node of this ADT.
     *
     * @return the root
     */
    public ADTNode<S, I, O> getRoot() {
        return this.root;
    }

    /**
     * Replaces an existing node in the tree with a new one and updates the references of parent/child nodes
     * accordingly.
     *
     * @param oldNode
     *         the node to replace
     * @param newNode
     *         the replacement
     */
    public void replaceNode(ADTNode<S, I, O> oldNode, ADTNode<S, I, O> newNode) {

        if (this.root.equals(oldNode)) {
            this.root = newNode;
        } else if (ADTUtil.isResetNode(oldNode)) {
            final ADTNode<S, I, O> endOfPreviousADS = oldNode.getParent();
            final O outputToReset = ADTUtil.getOutputForSuccessor(endOfPreviousADS, oldNode);

            newNode.setParent(endOfPreviousADS);
            endOfPreviousADS.getChildren().put(outputToReset, newNode);
        } else {
            final ADTNode<S, I, O> oldNodeParent = oldNode.getParent(); //reset node

            assert ADTUtil.isResetNode(oldNodeParent);

            final ADTNode<S, I, O> endOfPreviousADS = oldNodeParent.getParent();
            final O outputToReset = ADTUtil.getOutputForSuccessor(endOfPreviousADS, oldNodeParent);
            final ADTNode<S, I, O> newResetNode = new ADTResetNode<>(newNode);

            newResetNode.setParent(endOfPreviousADS);
            newNode.setParent(newResetNode);
            endOfPreviousADS.getChildren().put(outputToReset, newResetNode);
        }
    }

    /**
     * Successively sifts a word through the ADT induced by the given node. Stops when reaching a leaf.
     *
     * @param word
     *         the word to sift
     * @param subtree
     *         the node whose subtree is considered
     *
     * @return the leaf (see {@link ADTNode#sift(SymbolQueryOracle, Word)})
     */
    public ADTNode<S, I, O> sift(SymbolQueryOracle<I, O> oracle, Word<I> word, ADTNode<S, I, O> subtree) {

        ADTNode<S, I, O> current = subtree;

        while (!ADTUtil.isLeafNode(current)) {
            current = current.sift(oracle, word);
        }

        return current;
    }

    /**
     * Splitting a leaf node by extending the trace leading into the node to split.
     *
     * @param nodeToSplit
     *         the leaf node to extends
     * @param distinguishingSuffix
     *         the input sequence that splits the hypothesis state of the leaf to split and the new node. The current
     *         trace leading into the node to split must be a prefix of this word.
     * @param oldOutput
     *         the hypothesis output of the node to split given the distinguishing suffix
     * @param newOutput
     *         the hypothesis output of the new leaf given the distinguishing suffix
     * @param leafSplitter
     *         the split strategy in case the root node needs to be split
     *
     * @return the new leaf node
     */
    public ADTNode<S, I, O> extendLeaf(ADTNode<S, I, O> nodeToSplit,
                                       Word<I> distinguishingSuffix,
                                       Word<O> oldOutput,
                                       Word<O> newOutput,
                                       LeafSplitter leafSplitter) {

        if (!ADTUtil.isLeafNode(nodeToSplit)) {
            throw new IllegalArgumentException("Node to split is not a leaf node");
        }
        if (!(distinguishingSuffix.length() == oldOutput.length() && oldOutput.length() == newOutput.length())) {
            throw new IllegalArgumentException("Distinguishing suffixes and outputs differ in length");
        }
        if (oldOutput.equals(newOutput)) {
            throw new IllegalArgumentException("Old and new output are equal");
        }

        // initial split
        if (this.root.equals(nodeToSplit)) {
            return splitLeaf(nodeToSplit, distinguishingSuffix, oldOutput, newOutput, leafSplitter);
        }
        return LeafSplitters.splitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);
    }

    /**
     * Splits a leaf node using a given {@link LeafSplitter}.
     *
     * @param nodeToSplit
     *         the leaf node to split
     * @param distinguishingSuffix
     *         the input sequence that splits the hypothesis state of the leaf to split and the new node
     * @param oldOutput
     *         the hypothesis output of the node to split given the distinguishing suffix
     * @param newOutput
     *         the hypothesis output of the new leaf given the distinguishing suffix
     * @param leafSplitter
     *         the split strategy for leaves
     *
     * @return the new leaf node
     */
    public ADTNode<S, I, O> splitLeaf(ADTNode<S, I, O> nodeToSplit,
                                      Word<I> distinguishingSuffix,
                                      Word<O> oldOutput,
                                      Word<O> newOutput,
                                      LeafSplitter leafSplitter) {

        if (!ADTUtil.isLeafNode(nodeToSplit)) {
            throw new IllegalArgumentException("Node to split is not a final node");
        }
        if (!(distinguishingSuffix.length() == oldOutput.length() && oldOutput.length() == newOutput.length())) {
            throw new IllegalArgumentException("Distinguishing suffixes and outputs differ in length");
        }
        if (oldOutput.equals(newOutput)) {
            throw new IllegalArgumentException("Old and new output are equal");
        }

        final boolean wasRoot = this.root.equals(nodeToSplit);

        final ADTNode<S, I, O> result = leafSplitter.split(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);

        if (wasRoot) {
            this.root = ADTUtil.getStartOfADS(nodeToSplit);
        }

        return result;
    }

    /**
     * Return the lowest common ancestor for the given two nodes.
     *
     * @param s1
     *         first node
     * @param s2
     *         second node
     *
     * @return A {@link LCAInfo} containing the lowest common {@link ADTNode}, the output determining the subtree of the
     * first node and the output determining the subtree of the second node
     */
    public LCAInfo<S, I, O> findLCA(ADTNode<S, I, O> s1, ADTNode<S, I, O> s2) {

        final Map<ADTNode<S, I, O>, ADTNode<S, I, O>> s1ParentsToS1 = new HashMap<>();

        ADTNode<S, I, O> s1Iter = s1;
        ADTNode<S, I, O> s2Iter = s2;

        while (s1Iter.getParent() != null) {
            s1ParentsToS1.put(s1Iter.getParent(), s1Iter);
            s1Iter = s1Iter.getParent();
        }

        final Set<ADTNode<S, I, O>> s1Parents = s1ParentsToS1.keySet();

        while (s2Iter.getParent() != null) {

            if (s1Parents.contains(s2Iter.getParent())) {
                if (!ADTUtil.isSymbolNode(s2Iter.getParent())) {
                    throw new IllegalStateException("Only Symbol Nodes should be LCAs");
                }

                final ADTNode<S, I, O> lca = s2Iter.getParent();
                final O s1Out = ADTUtil.getOutputForSuccessor(lca, s1ParentsToS1.get(lca));
                final O s2Out = ADTUtil.getOutputForSuccessor(lca, s2Iter);

                return new LCAInfo<>(lca, s1Out, s2Out);
            }

            s2Iter = s2Iter.getParent();
        }

        throw new IllegalStateException("Nodes do not share a parent node");
    }

    public static class LCAInfo<S, I, O> {

        public final ADTNode<S, I, O> adtNode;
        public final O firstOutput;
        public final O secondOutput;

        LCAInfo(ADTNode<S, I, O> adtNode, O firstOutput, O secondOutput) {
            this.adtNode = adtNode;
            this.firstOutput = firstOutput;
            this.secondOutput = secondOutput;
        }
    }
}

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.adt;
17
18	import java.util.HashMap;
19	import java.util.Map;
20	import java.util.Set;
21
22	import de.learnlib.algorithms.adt.api.LeafSplitter;
23	import de.learnlib.algorithms.adt.config.LeafSplitters;
24	import de.learnlib.algorithms.adt.util.ADTUtil;
25	import de.learnlib.api.oracle.SymbolQueryOracle;
26	import net.automatalib.words.Word;
27
28	/**
29	* The adaptive discrimination tree class. Essentially holds a reference to the root {@link ADTNode} and offers some
30	* utility methods used throughout the learning process.
31	*
32	* @param <S>
33	* (hypothesis) state type
34	* @param <I>
35	* input alphabet type
36	* @param <O>
37	* output alphabet type
38	*/
39	public class ADT<S, I, O> {	2✔
40
41	private ADTNode<S, I, O> root;
42
43	/**
44	* Initializes the ADT with a single leaf node.
45	*
46	* @param state
47	* the referenced state of the leaf
48	*/
49	public void initialize(S state) {
50	this.root = new ADTLeafNode<>(null, state);	2✔
51	}	2✔
52
53	/**
54	* Returns the root node of this ADT.
55	*
56	* @return the root
57	*/
58	public ADTNode<S, I, O> getRoot() {
59	return this.root;	2✔
60	}
61
62	/**
63	* Replaces an existing node in the tree with a new one and updates the references of parent/child nodes
64	* accordingly.
65	*
66	* @param oldNode
67	* the node to replace
68	* @param newNode
69	* the replacement
70	*/
71	public void replaceNode(ADTNode<S, I, O> oldNode, ADTNode<S, I, O> newNode) {
72
73	if (this.root.equals(oldNode)) {	2✔
74	this.root = newNode;	2✔
75	} else if (ADTUtil.isResetNode(oldNode)) {	2✔
76	final ADTNode<S, I, O> endOfPreviousADS = oldNode.getParent();	2✔
77	final O outputToReset = ADTUtil.getOutputForSuccessor(endOfPreviousADS, oldNode);	2✔
78
79	newNode.setParent(endOfPreviousADS);	2✔
80	endOfPreviousADS.getChildren().put(outputToReset, newNode);	2✔
81	} else {	2✔
82	final ADTNode<S, I, O> oldNodeParent = oldNode.getParent(); //reset node	2✔
83
84	assert ADTUtil.isResetNode(oldNodeParent);	2✔
85
86	final ADTNode<S, I, O> endOfPreviousADS = oldNodeParent.getParent();	2✔
87	final O outputToReset = ADTUtil.getOutputForSuccessor(endOfPreviousADS, oldNodeParent);	2✔
88	final ADTNode<S, I, O> newResetNode = new ADTResetNode<>(newNode);	2✔
89
90	newResetNode.setParent(endOfPreviousADS);	2✔
91	newNode.setParent(newResetNode);	2✔
92	endOfPreviousADS.getChildren().put(outputToReset, newResetNode);	2✔
93	}
94	}	2✔
95
96	/**
97	* Successively sifts a word through the ADT induced by the given node. Stops when reaching a leaf.
98	*
99	* @param word
100	* the word to sift
101	* @param subtree
102	* the node whose subtree is considered
103	*
104	* @return the leaf (see {@link ADTNode#sift(SymbolQueryOracle, Word)})
105	*/
106	public ADTNode<S, I, O> sift(SymbolQueryOracle<I, O> oracle, Word<I> word, ADTNode<S, I, O> subtree) {
107
108	ADTNode<S, I, O> current = subtree;	2✔
109
110	while (!ADTUtil.isLeafNode(current)) {	2✔
111	current = current.sift(oracle, word);	2✔
112	}
113
114	return current;	2✔
115	}
116
117	/**
118	* Splitting a leaf node by extending the trace leading into the node to split.
119	*
120	* @param nodeToSplit
121	* the leaf node to extends
122	* @param distinguishingSuffix
123	* the input sequence that splits the hypothesis state of the leaf to split and the new node. The current
124	* trace leading into the node to split must be a prefix of this word.
125	* @param oldOutput
126	* the hypothesis output of the node to split given the distinguishing suffix
127	* @param newOutput
128	* the hypothesis output of the new leaf given the distinguishing suffix
129	* @param leafSplitter
130	* the split strategy in case the root node needs to be split
131	*
132	* @return the new leaf node
133	*/
134	public ADTNode<S, I, O> extendLeaf(ADTNode<S, I, O> nodeToSplit,
135	Word<I> distinguishingSuffix,
136	Word<O> oldOutput,
137	Word<O> newOutput,
138	LeafSplitter leafSplitter) {
139
140	if (!ADTUtil.isLeafNode(nodeToSplit)) {	2✔
141	throw new IllegalArgumentException("Node to split is not a leaf node");	×
142	}
143	if (!(distinguishingSuffix.length() == oldOutput.length() && oldOutput.length() == newOutput.length())) {	2✔
144	throw new IllegalArgumentException("Distinguishing suffixes and outputs differ in length");	×
145	}
146	if (oldOutput.equals(newOutput)) {	2✔
147	throw new IllegalArgumentException("Old and new output are equal");	×
148	}
149
150	// initial split
151	if (this.root.equals(nodeToSplit)) {	2✔
152	return splitLeaf(nodeToSplit, distinguishingSuffix, oldOutput, newOutput, leafSplitter);	2✔
153	}
154	return LeafSplitters.splitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);	2✔
155	}
156
157	/**
158	* Splits a leaf node using a given {@link LeafSplitter}.
159	*
160	* @param nodeToSplit
161	* the leaf node to split
162	* @param distinguishingSuffix
163	* the input sequence that splits the hypothesis state of the leaf to split and the new node
164	* @param oldOutput
165	* the hypothesis output of the node to split given the distinguishing suffix
166	* @param newOutput
167	* the hypothesis output of the new leaf given the distinguishing suffix
168	* @param leafSplitter
169	* the split strategy for leaves
170	*
171	* @return the new leaf node
172	*/
173	public ADTNode<S, I, O> splitLeaf(ADTNode<S, I, O> nodeToSplit,
174	Word<I> distinguishingSuffix,
175	Word<O> oldOutput,
176	Word<O> newOutput,
177	LeafSplitter leafSplitter) {
178
179	if (!ADTUtil.isLeafNode(nodeToSplit)) {	2✔
180	throw new IllegalArgumentException("Node to split is not a final node");	×
181	}
182	if (!(distinguishingSuffix.length() == oldOutput.length() && oldOutput.length() == newOutput.length())) {	2✔
183	throw new IllegalArgumentException("Distinguishing suffixes and outputs differ in length");	×
184	}
185	if (oldOutput.equals(newOutput)) {	2✔
186	throw new IllegalArgumentException("Old and new output are equal");	×
187	}
188
189	final boolean wasRoot = this.root.equals(nodeToSplit);	2✔
190
191	final ADTNode<S, I, O> result = leafSplitter.split(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);	2✔
192
193	if (wasRoot) {	2✔
194	this.root = ADTUtil.getStartOfADS(nodeToSplit);	2✔
195	}
196
197	return result;	2✔
198	}
199
200	/**
201	* Return the lowest common ancestor for the given two nodes.
202	*
203	* @param s1
204	* first node
205	* @param s2
206	* second node
207	*
208	* @return A {@link LCAInfo} containing the lowest common {@link ADTNode}, the output determining the subtree of the
209	* first node and the output determining the subtree of the second node
210	*/
211	public LCAInfo<S, I, O> findLCA(ADTNode<S, I, O> s1, ADTNode<S, I, O> s2) {
212
213	final Map<ADTNode<S, I, O>, ADTNode<S, I, O>> s1ParentsToS1 = new HashMap<>();	2✔
214
215	ADTNode<S, I, O> s1Iter = s1;	2✔
216	ADTNode<S, I, O> s2Iter = s2;	2✔
217
218	while (s1Iter.getParent() != null) {	2✔
219	s1ParentsToS1.put(s1Iter.getParent(), s1Iter);	2✔
220	s1Iter = s1Iter.getParent();	2✔
221	}
222
223	final Set<ADTNode<S, I, O>> s1Parents = s1ParentsToS1.keySet();	2✔
224
225	while (s2Iter.getParent() != null) {	2✔
226
227	if (s1Parents.contains(s2Iter.getParent())) {	2✔
228	if (!ADTUtil.isSymbolNode(s2Iter.getParent())) {	2✔
229	throw new IllegalStateException("Only Symbol Nodes should be LCAs");	×
230	}
231
232	final ADTNode<S, I, O> lca = s2Iter.getParent();	2✔
233	final O s1Out = ADTUtil.getOutputForSuccessor(lca, s1ParentsToS1.get(lca));	2✔
234	final O s2Out = ADTUtil.getOutputForSuccessor(lca, s2Iter);	2✔
235
236	return new LCAInfo<>(lca, s1Out, s2Out);	2✔
237	}
238
239	s2Iter = s2Iter.getParent();	2✔
240	}
241
242	throw new IllegalStateException("Nodes do not share a parent node");	×
243	}
244
245	public static class LCAInfo<S, I, O> {
246
247	public final ADTNode<S, I, O> adtNode;
248	public final O firstOutput;
249	public final O secondOutput;
250
251	LCAInfo(ADTNode<S, I, O> adtNode, O firstOutput, O secondOutput) {	2✔
252	this.adtNode = adtNode;	2✔
253	this.firstOutput = firstOutput;	2✔
254	this.secondOutput = secondOutput;	2✔
255	}	2✔
256	}
257	}

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