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

98.33

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

import java.util.Iterator;
import java.util.Map;
import java.util.Objects;

import de.learnlib.algorithms.adt.adt.ADTLeafNode;
import de.learnlib.algorithms.adt.adt.ADTNode;
import de.learnlib.algorithms.adt.adt.ADTResetNode;
import de.learnlib.algorithms.adt.adt.ADTSymbolNode;
import de.learnlib.algorithms.adt.api.LeafSplitter;
import de.learnlib.algorithms.adt.util.ADTUtil;
import net.automatalib.commons.util.Pair;
import net.automatalib.words.Word;

/**
 * A collection of default {@link LeafSplitter} configurations.
 */
public final class LeafSplitters {

    public static final LeafSplitter DEFAULT_SPLITTER = LeafSplitters::splitIntoNewADS;

    public static final LeafSplitter EXTEND_PARENT = new LeafSplitter() {

        @Override
        public <S, I, O> ADTNode<S, I, O> split(ADTNode<S, I, O> nodeToSplit,
                                                Word<I> distinguishingSuffix,
                                                Word<O> oldOutput,
                                                Word<O> newOutput) {

            if (canSplitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput)) {
                return splitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);
            }

            return splitIntoNewADS(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);
        }
    };

    private LeafSplitters() {
        // prevent instantiation
    }

    private static <S, I, O> boolean canSplitParent(ADTNode<S, I, O> nodeToSplit,
                                                    Word<I> distinguishingSuffix,
                                                    Word<O> hypothesisOutput,
                                                    Word<O> newOutput) {

        // initial split
        if (nodeToSplit.getParent() == null) {
            return false;
        }

        final Pair<Word<I>, Word<O>> trace = ADTUtil.buildTraceForNode(nodeToSplit);
        final Word<I> traceInput = trace.getFirst();
        final Word<O> traceOutput = trace.getSecond();

        return traceInput.isPrefixOf(distinguishingSuffix) && traceOutput.isPrefixOf(newOutput) &&
               traceOutput.isPrefixOf(hypothesisOutput);
    }

    private static <S, I, O> ADTNode<S, I, O> splitIntoNewADS(ADTNode<S, I, O> nodeToSplit,
                                                              Word<I> distinguishingSuffix,
                                                              Word<O> oldOutput,
                                                              Word<O> newOutput) {

        final Iterator<I> suffixIter = distinguishingSuffix.iterator();

        // Replace old final state
        final ADTNode<S, I, O> parent = nodeToSplit.getParent();
        final ADTNode<S, I, O> newADS = new ADTSymbolNode<>(null, suffixIter.next());

        if (parent != null) { // if parent == null, we split the initial node
            boolean foundSuccessor = false;
            for (Map.Entry<O, ADTNode<S, I, O>> entry : parent.getChildren().entrySet()) {
                if (entry.getValue().equals(nodeToSplit)) {
                    final ADTNode<S, I, O> reset = new ADTResetNode<>(newADS);

                    reset.setParent(parent);
                    parent.getChildren().put(entry.getKey(), reset);
                    newADS.setParent(reset);

                    foundSuccessor = true;
                    break;
                }
            }

            if (!foundSuccessor) {
                throw new IllegalStateException();
            }
        }

        return finalizeSplit(nodeToSplit, newADS, suffixIter, oldOutput.iterator(), newOutput.iterator());
    }

    private static <S, I, O> ADTNode<S, I, O> finalizeSplit(ADTNode<S, I, O> nodeToSplit,
                                                            ADTNode<S, I, O> adtRoot,
                                                            Iterator<I> suffixIter,
                                                            Iterator<O> oldIter,
                                                            Iterator<O> newIter) {

        ADTNode<S, I, O> previous = adtRoot;
        O oldOut = oldIter.next();
        O newOut = newIter.next();

        while (Objects.equals(oldOut, newOut)) {
            final ADTNode<S, I, O> next = new ADTSymbolNode<>(previous, suffixIter.next());

            previous.getChildren().put(oldOut, next);

            oldOut = oldIter.next();
            newOut = newIter.next();
            previous = next;
        }

        final ADTNode<S, I, O> oldFinalNode = nodeToSplit;
        final ADTNode<S, I, O> newFinalNode = new ADTLeafNode<>(previous, null);

        oldFinalNode.setParent(previous);
        newFinalNode.setParent(previous);

        previous.getChildren().put(oldOut, oldFinalNode);
        previous.getChildren().put(newOut, newFinalNode);

        return newFinalNode;
    }

    public static <S, I, O> ADTNode<S, I, O> splitParent(ADTNode<S, I, O> nodeToSplit,
                                                         Word<I> distinguishingSuffix,
                                                         Word<O> oldOutput,
                                                         Word<O> newOutput) {

        final ADTNode<S, I, O> previousADS = ADTUtil.getStartOfADS(nodeToSplit);

        final Iterator<I> suffixIter = distinguishingSuffix.iterator();
        final Iterator<O> oldIter = oldOutput.iterator();
        final Iterator<O> newIter = newOutput.iterator();
        ADTNode<S, I, O> adsIter = previousADS;
        O newSuffixOutput = null;

        while (!ADTUtil.isLeafNode(adsIter)) {

            // Forward other iterators
            suffixIter.next();
            newIter.next();
            newSuffixOutput = oldIter.next();

            adsIter = adsIter.getChildren().get(newSuffixOutput);
        }

        final ADTNode<S, I, O> continuedADS = new ADTSymbolNode<>(adsIter.getParent(), suffixIter.next());

        adsIter.getParent().getChildren().put(newSuffixOutput, continuedADS);

        return finalizeSplit(nodeToSplit, continuedADS, suffixIter, oldIter, newIter);
    }
}

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.config;
17
18	import java.util.Iterator;
19	import java.util.Map;
20	import java.util.Objects;
21
22	import de.learnlib.algorithms.adt.adt.ADTLeafNode;
23	import de.learnlib.algorithms.adt.adt.ADTNode;
24	import de.learnlib.algorithms.adt.adt.ADTResetNode;
25	import de.learnlib.algorithms.adt.adt.ADTSymbolNode;
26	import de.learnlib.algorithms.adt.api.LeafSplitter;
27	import de.learnlib.algorithms.adt.util.ADTUtil;
28	import net.automatalib.commons.util.Pair;
29	import net.automatalib.words.Word;
30
31	/**
32	* A collection of default {@link LeafSplitter} configurations.
33	*/
34	public final class LeafSplitters {
35
36	public static final LeafSplitter DEFAULT_SPLITTER = LeafSplitters::splitIntoNewADS;	2✔
37
38	public static final LeafSplitter EXTEND_PARENT = new LeafSplitter() {	2✔
39
40	@Override
41	public <S, I, O> ADTNode<S, I, O> split(ADTNode<S, I, O> nodeToSplit,
42	Word<I> distinguishingSuffix,
43	Word<O> oldOutput,
44	Word<O> newOutput) {
45
46	if (canSplitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput)) {	2✔
47	return splitParent(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);	2✔
48	}
49
50	return splitIntoNewADS(nodeToSplit, distinguishingSuffix, oldOutput, newOutput);	2✔
51	}
52	};
53
54	private LeafSplitters() {
55	// prevent instantiation
56	}
57
58	private static <S, I, O> boolean canSplitParent(ADTNode<S, I, O> nodeToSplit,
59	Word<I> distinguishingSuffix,
60	Word<O> hypothesisOutput,
61	Word<O> newOutput) {
62
63	// initial split
64	if (nodeToSplit.getParent() == null) {	2✔
65	return false;	2✔
66	}
67
68	final Pair<Word<I>, Word<O>> trace = ADTUtil.buildTraceForNode(nodeToSplit);	2✔
69	final Word<I> traceInput = trace.getFirst();	2✔
70	final Word<O> traceOutput = trace.getSecond();	2✔
71
72	return traceInput.isPrefixOf(distinguishingSuffix) && traceOutput.isPrefixOf(newOutput) &&	2✔
73	traceOutput.isPrefixOf(hypothesisOutput);	2✔
74	}
75
76	private static <S, I, O> ADTNode<S, I, O> splitIntoNewADS(ADTNode<S, I, O> nodeToSplit,
77	Word<I> distinguishingSuffix,
78	Word<O> oldOutput,
79	Word<O> newOutput) {
80
81	final Iterator<I> suffixIter = distinguishingSuffix.iterator();	2✔
82
83	// Replace old final state
84	final ADTNode<S, I, O> parent = nodeToSplit.getParent();	2✔
85	final ADTNode<S, I, O> newADS = new ADTSymbolNode<>(null, suffixIter.next());	2✔
86
87	if (parent != null) { // if parent == null, we split the initial node	2✔
88	boolean foundSuccessor = false;	2✔
89	for (Map.Entry<O, ADTNode<S, I, O>> entry : parent.getChildren().entrySet()) {	2✔
90	if (entry.getValue().equals(nodeToSplit)) {	2✔
91	final ADTNode<S, I, O> reset = new ADTResetNode<>(newADS);	2✔
92
93	reset.setParent(parent);	2✔
94	parent.getChildren().put(entry.getKey(), reset);	2✔
95	newADS.setParent(reset);	2✔
96
97	foundSuccessor = true;	2✔
98	break;	2✔
99	}
100	}	2✔
101
102	if (!foundSuccessor) {	2✔
103	throw new IllegalStateException();	×
104	}
105	}
106
107	return finalizeSplit(nodeToSplit, newADS, suffixIter, oldOutput.iterator(), newOutput.iterator());	2✔
108	}
109
110	private static <S, I, O> ADTNode<S, I, O> finalizeSplit(ADTNode<S, I, O> nodeToSplit,
111	ADTNode<S, I, O> adtRoot,
112	Iterator<I> suffixIter,
113	Iterator<O> oldIter,
114	Iterator<O> newIter) {
115
116	ADTNode<S, I, O> previous = adtRoot;	2✔
117	O oldOut = oldIter.next();	2✔
118	O newOut = newIter.next();	2✔
119
120	while (Objects.equals(oldOut, newOut)) {	2✔
121	final ADTNode<S, I, O> next = new ADTSymbolNode<>(previous, suffixIter.next());	2✔
122
123	previous.getChildren().put(oldOut, next);	2✔
124
125	oldOut = oldIter.next();	2✔
126	newOut = newIter.next();	2✔
127	previous = next;	2✔
128	}	2✔
129
130	final ADTNode<S, I, O> oldFinalNode = nodeToSplit;	2✔
131	final ADTNode<S, I, O> newFinalNode = new ADTLeafNode<>(previous, null);	2✔
132
133	oldFinalNode.setParent(previous);	2✔
134	newFinalNode.setParent(previous);	2✔
135
136	previous.getChildren().put(oldOut, oldFinalNode);	2✔
137	previous.getChildren().put(newOut, newFinalNode);	2✔
138
139	return newFinalNode;	2✔
140	}
141
142	public static <S, I, O> ADTNode<S, I, O> splitParent(ADTNode<S, I, O> nodeToSplit,
143	Word<I> distinguishingSuffix,
144	Word<O> oldOutput,
145	Word<O> newOutput) {
146
147	final ADTNode<S, I, O> previousADS = ADTUtil.getStartOfADS(nodeToSplit);	2✔
148
149	final Iterator<I> suffixIter = distinguishingSuffix.iterator();	2✔
150	final Iterator<O> oldIter = oldOutput.iterator();	2✔
151	final Iterator<O> newIter = newOutput.iterator();	2✔
152	ADTNode<S, I, O> adsIter = previousADS;	2✔
153	O newSuffixOutput = null;	2✔
154
155	while (!ADTUtil.isLeafNode(adsIter)) {	2✔
156
157	// Forward other iterators
158	suffixIter.next();	2✔
159	newIter.next();	2✔
160	newSuffixOutput = oldIter.next();	2✔
161
162	adsIter = adsIter.getChildren().get(newSuffixOutput);	2✔
163	}
164
165	final ADTNode<S, I, O> continuedADS = new ADTSymbolNode<>(adsIter.getParent(), suffixIter.next());	2✔
166
167	adsIter.getParent().getChildren().put(newSuffixOutput, continuedADS);	2✔
168
169	return finalizeSplit(nodeToSplit, continuedADS, suffixIter, oldIter, newIter);	2✔
170	}
171	}

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