12304577693

Committed 12 Dec 2024 08:51PM UTC coverage: 91.182% (+0.4%) from 90.804%

Build # 12304577693

Build Type

push

github

Committed by

web-flow

Commit Message

Overhaul minimization code (#83)

* add valmaris algorithm

* initial PT refactoring

* implement bisimulation via valmari

* add documentation

* cleanups

* add invasive hopcroft methods

* some more universal tests

* performance tweaks

* move OneSEVPAMinimizer

* improve documentation

* cleanup

* wording

* fix javadoc errors

Run Details

564 of 581 new or added lines in 25 files covered. (97.07%)

1 existing line in 1 file now uncovered.

16535 of 18134 relevant lines covered (91.18%)

1.69 hits per line

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

98.36

/core/src/main/java/net/automatalib/automaton/impl/UniversalCompactDet.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * 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 net.automatalib.automaton.impl;

import java.util.Arrays;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.automaton.AutomatonCreator;
import net.automatalib.automaton.base.AbstractCompact;
import net.automatalib.automaton.base.AbstractCompactDeterministic;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A default implementation for {@link AbstractCompactDeterministic} that uses {@link CompactTransition} as transition
 * type and supports various types of state and transition properties.
 *
 * @param <I>
 *         input symbol type
 * @param <SP>
 *         state property type
 * @param <TP>
 *         transition property type
 */
public class UniversalCompactDet<I, SP, TP> extends AbstractCompactDeterministic<I, CompactTransition<TP>, SP, TP> {

    private int[] transitions;
    private @Nullable Object[] stateProperties;
    private @Nullable Object[] transitionProperties;

    public UniversalCompactDet(Alphabet<I> alphabet) {
        this(alphabet, DEFAULT_INIT_CAPACITY, DEFAULT_RESIZE_FACTOR);
    }

    public UniversalCompactDet(Alphabet<I> alphabet, int stateCapacity) {
        this(alphabet, stateCapacity, DEFAULT_RESIZE_FACTOR);
    }

    public UniversalCompactDet(Alphabet<I> alphabet, int stateCapacity, float resizeFactor) {
        super(alphabet, stateCapacity, resizeFactor);

        final int numTrans = stateCapacity * numInputs();
        this.transitions = new int[numTrans];
        this.stateProperties = new Object[stateCapacity];
        this.transitionProperties = new Object[numTrans];

        Arrays.fill(this.transitions, AbstractCompact.INVALID_STATE);
    }

    protected UniversalCompactDet(Alphabet<I> alphabet, UniversalCompactDet<?, SP, TP> other) {
        super(alphabet, other);
        this.transitions = other.transitions.clone();
        this.stateProperties = other.stateProperties.clone();
        this.transitionProperties = other.transitionProperties.clone();
    }

    @Override
    public @Nullable CompactTransition<TP> getTransition(int state, int input) {
        final int idx = toMemoryIndex(state, input);
        final int succ = transitions[idx];

        if (succ == AbstractCompact.INVALID_STATE) {
            return null;
        }

        @SuppressWarnings("unchecked")
        final TP output = (TP) transitionProperties[idx];

        return new CompactTransition<>(idx, succ, output);
    }

    @Override
    public int getIntSuccessor(CompactTransition<TP> transition) {
        return transition.getSuccId();
    }

    @Override
    public void setStateProperty(int state, @Nullable SP property) {
        this.stateProperties[state] = property;
    }

    @Override
    public void setTransitionProperty(CompactTransition<TP> transition, TP property) {
        transition.setProperty(property);

        if (transition.isAutomatonTransition()) {
            transitionProperties[transition.getMemoryIdx()] = property;
        }
    }

    @Override
    public CompactTransition<TP> createTransition(int successor, TP property) {
        return new CompactTransition<>(successor, property);
    }

    @Override
    public void removeAllTransitions(Integer state) {
        final int lower = state * numInputs();
        final int upper = lower + numInputs();
        Arrays.fill(transitions, lower, upper, AbstractCompact.INVALID_STATE);
        Arrays.fill(transitionProperties, lower, upper, null);

    }

    @Override
    public void setTransition(int state, int input, @Nullable CompactTransition<TP> transition) {
        if (transition == null) {
            setTransition(state, input, AbstractCompact.INVALID_STATE, null);
        } else {
            setTransition(state, input, transition.getSuccId(), transition.getProperty());
            transition.setMemoryIdx(toMemoryIndex(state, input));
        }
    }

    @Override
    public void setTransition(int state, int input, int successor, @Nullable TP property) {
        final int idx = toMemoryIndex(state, input);
        transitions[idx] = successor;
        transitionProperties[idx] = property;
    }

    @Override
    @SuppressWarnings("unchecked")
    public SP getStateProperty(int state) {
        return (SP) stateProperties[state];
    }

    @Override
    public TP getTransitionProperty(CompactTransition<TP> transition) {
        return transition.getProperty();
    }

    @Override
    public void clear() {
        int endIdx = size() * numInputs();
        Arrays.fill(stateProperties, 0, size(), null);
        Arrays.fill(transitions, 0, endIdx, AbstractCompact.INVALID_STATE);
        Arrays.fill(transitionProperties, 0, endIdx, null);

        super.clear();
    }

    @Override
    protected void updateStateStorage(Payload payload) {
        this.stateProperties = updateStateStorage(this.stateProperties, null, payload);
        super.updateStateStorage(payload);
    }

    @Override
    protected void updateTransitionStorage(Payload payload) {
        this.transitions = updateTransitionStorage(this.transitions, AbstractCompact.INVALID_STATE, payload);
        this.transitionProperties = updateTransitionStorage(this.transitionProperties, null, payload);
    }

    public static final class Creator<I, SP, TP> implements AutomatonCreator<UniversalCompactDet<I, SP, TP>, I> {

        @Override
        public UniversalCompactDet<I, SP, TP> createAutomaton(Alphabet<I> alphabet, int numStates) {
            return new UniversalCompactDet<>(alphabet, numStates);
        }

        @Override
        public UniversalCompactDet<I, SP, TP> createAutomaton(Alphabet<I> alphabet) {
            return new UniversalCompactDet<>(alphabet);
        }
    }
}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.automatalib.net/.
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 net.automatalib.automaton.impl;
17
18	import java.util.Arrays;
19
20	import net.automatalib.alphabet.Alphabet;
21	import net.automatalib.automaton.AutomatonCreator;
22	import net.automatalib.automaton.base.AbstractCompact;
23	import net.automatalib.automaton.base.AbstractCompactDeterministic;
24	import org.checkerframework.checker.nullness.qual.Nullable;
25
26	/**
27	* A default implementation for {@link AbstractCompactDeterministic} that uses {@link CompactTransition} as transition
28	* type and supports various types of state and transition properties.
29	*
30	* @param <I>
31	* input symbol type
32	* @param <SP>
33	* state property type
34	* @param <TP>
35	* transition property type
36	*/
37	public class UniversalCompactDet<I, SP, TP> extends AbstractCompactDeterministic<I, CompactTransition<TP>, SP, TP> {
38
39	private int[] transitions;
40	private @Nullable Object[] stateProperties;
41	private @Nullable Object[] transitionProperties;
42
43	public UniversalCompactDet(Alphabet<I> alphabet) {
44	this(alphabet, DEFAULT_INIT_CAPACITY, DEFAULT_RESIZE_FACTOR);	2✔
45	}	2✔
46
47	public UniversalCompactDet(Alphabet<I> alphabet, int stateCapacity) {
48	this(alphabet, stateCapacity, DEFAULT_RESIZE_FACTOR);	1✔
49	}	1✔
50
51	public UniversalCompactDet(Alphabet<I> alphabet, int stateCapacity, float resizeFactor) {
52	super(alphabet, stateCapacity, resizeFactor);	2✔
53
54	final int numTrans = stateCapacity * numInputs();	2✔
55	this.transitions = new int[numTrans];	2✔
56	this.stateProperties = new Object[stateCapacity];	2✔
57	this.transitionProperties = new Object[numTrans];	2✔
58
59	Arrays.fill(this.transitions, AbstractCompact.INVALID_STATE);	2✔
60	}	2✔
61
62	protected UniversalCompactDet(Alphabet<I> alphabet, UniversalCompactDet<?, SP, TP> other) {
63	super(alphabet, other);	1✔
64	this.transitions = other.transitions.clone();	1✔
65	this.stateProperties = other.stateProperties.clone();	1✔
66	this.transitionProperties = other.transitionProperties.clone();	1✔
67	}	1✔
68
69	@Override
70	public @Nullable CompactTransition<TP> getTransition(int state, int input) {
71	final int idx = toMemoryIndex(state, input);	2✔
72	final int succ = transitions[idx];	2✔
73
74	if (succ == AbstractCompact.INVALID_STATE) {	2✔
75	return null;	2✔
76	}
77
78	@SuppressWarnings("unchecked")
79	final TP output = (TP) transitionProperties[idx];	2✔
80
81	return new CompactTransition<>(idx, succ, output);	2✔
82	}
83
84	@Override
85	public int getIntSuccessor(CompactTransition<TP> transition) {
86	return transition.getSuccId();	2✔
87	}
88
89	@Override
90	public void setStateProperty(int state, @Nullable SP property) {
91	this.stateProperties[state] = property;	2✔
92	}	2✔
93
94	@Override
95	public void setTransitionProperty(CompactTransition<TP> transition, TP property) {
96	transition.setProperty(property);	2✔
97
98	if (transition.isAutomatonTransition()) {	2✔
99	transitionProperties[transition.getMemoryIdx()] = property;	1✔
100	}
101	}	2✔
102
103	@Override
104	public CompactTransition<TP> createTransition(int successor, TP property) {
105	return new CompactTransition<>(successor, property);	2✔
106	}
107
108	@Override
109	public void removeAllTransitions(Integer state) {
110	final int lower = state * numInputs();	2✔
111	final int upper = lower + numInputs();	2✔
112	Arrays.fill(transitions, lower, upper, AbstractCompact.INVALID_STATE);	2✔
113	Arrays.fill(transitionProperties, lower, upper, null);	2✔
114
115	}	2✔
116
117	@Override
118	public void setTransition(int state, int input, @Nullable CompactTransition<TP> transition) {
119	if (transition == null) {	2✔
120	setTransition(state, input, AbstractCompact.INVALID_STATE, null);	2✔
121	} else {
122	setTransition(state, input, transition.getSuccId(), transition.getProperty());	2✔
123	transition.setMemoryIdx(toMemoryIndex(state, input));	2✔
124	}
125	}	2✔
126
127	@Override
128	public void setTransition(int state, int input, int successor, @Nullable TP property) {
129	final int idx = toMemoryIndex(state, input);	2✔
130	transitions[idx] = successor;	2✔
131	transitionProperties[idx] = property;	2✔
132	}	2✔
133
134	@Override
135	@SuppressWarnings("unchecked")
136	public SP getStateProperty(int state) {
137	return (SP) stateProperties[state];	2✔
138	}
139
140	@Override
141	public TP getTransitionProperty(CompactTransition<TP> transition) {
142	return transition.getProperty();	2✔
143	}
144
145	@Override
146	public void clear() {
147	int endIdx = size() * numInputs();	2✔
148	Arrays.fill(stateProperties, 0, size(), null);	2✔
149	Arrays.fill(transitions, 0, endIdx, AbstractCompact.INVALID_STATE);	2✔
150	Arrays.fill(transitionProperties, 0, endIdx, null);	2✔
151
152	super.clear();	2✔
153	}	2✔
154
155	@Override
156	protected void updateStateStorage(Payload payload) {
157	this.stateProperties = updateStateStorage(this.stateProperties, null, payload);	2✔
158	super.updateStateStorage(payload);	2✔
159	}	2✔
160
161	@Override
162	protected void updateTransitionStorage(Payload payload) {
163	this.transitions = updateTransitionStorage(this.transitions, AbstractCompact.INVALID_STATE, payload);	2✔
164	this.transitionProperties = updateTransitionStorage(this.transitionProperties, null, payload);	2✔
165	}	2✔
166
167	public static final class Creator<I, SP, TP> implements AutomatonCreator<UniversalCompactDet<I, SP, TP>, I> {	1✔
168
169	@Override
170	public UniversalCompactDet<I, SP, TP> createAutomaton(Alphabet<I> alphabet, int numStates) {
171	return new UniversalCompactDet<>(alphabet, numStates);	1✔
172	}
173
174	@Override
175	public UniversalCompactDet<I, SP, TP> createAutomaton(Alphabet<I> alphabet) {
NEW 176	return new UniversalCompactDet<>(alphabet);	×
177	}
178	}
179	}

LearnLib / automatalib / 12304577693

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