12755372168

Committed 13 Jan 2025 08:13PM UTC coverage: 94.2% (-0.002%) from 94.202%

Build # 12755372168

Build Type

push

github

Committed by

mtf90

Commit Message

cleanup some ADT code

Run Details

83 of 86 new or added lines in 10 files covered. (96.51%)

1 existing line in 1 file now uncovered.

11776 of 12501 relevant lines covered (94.2%)

1.71 hits per line

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

86.96

/algorithms/active/adt/src/main/java/de/learnlib/algorithm/adt/adt/ADT.java

/* Copyright (C) 2013-2025 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.algorithm.adt.adt;

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

import de.learnlib.algorithm.adt.api.LeafSplitter;
import de.learnlib.algorithm.adt.config.LeafSplitters;
import de.learnlib.algorithm.adt.util.ADTUtil;
import net.automatalib.word.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();
            assert endOfPreviousADS != null;
            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();
            assert endOfPreviousADS != null;

            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);
        }
    }

    /**
     * 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> s1ParentIter = s1.getParent();

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

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

        ADTNode<S, I, O> s2Iter = s2;
        ADTNode<S, I, O> s2ParentIter = s2.getParent();

        while (s2ParentIter != null) {

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

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

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

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

LearnLib / learnlib / 12755372168

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