13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 hits per line

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

96.67

/core/src/main/java/net/automatalib/automaton/base/AbstractCompactSimpleNondet.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://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.base;

import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.Set;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.automaton.fsa.NFA;
import net.automatalib.common.util.collection.PositiveIntSet;
import net.automatalib.ts.PowersetViewTS;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Abstract super class that refines {@link AbstractCompact} for transition-property-less automata. As a result,
 * transitions may be represented as integers (where a transition object effectively <i>is</i> the successor).
 * <p>
 * <b>Implementation note:</b> This class uses {@link BitSet}s to store the successors of each state. This makes the
 * memory consumption of this class depend on the number of states rather than the density of its adjacency matrix
 * (since the maximum bit/index determines the size of each {@link BitSet}). For the majority of cases (tests showed if
 * the average number of outgoing transitions per state is more than 0.2% of the number of states) this still requires
 * less memory than using e.g. a {@link Set} of {@link Integer}s. However, for very large but very sparse {@link NFA}s
 * one may consider using the {@link AbstractFastMutableNondet} class instead.
 *
 * @param <I>
 *         input symbol type
 * @param <SP>
 *         state property type
 */
public abstract class AbstractCompactSimpleNondet<I, SP> extends AbstractCompact<I, Integer, SP, Void> {

    private final BitSet initial;
    private @Nullable BitSet[] transitions;

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

        this.transitions = new BitSet[stateCapacity * numInputs()];
        this.initial = new BitSet();
    }

    protected AbstractCompactSimpleNondet(Alphabet<I> alphabet, AbstractCompactSimpleNondet<?, ?> other) {
        super(alphabet, other);
        this.transitions = other.transitions.clone();
        for (int i = 0; i < transitions.length; i++) {
            final BitSet tgts = transitions[i];
            if (tgts != null) {
                transitions[i] = (BitSet) tgts.clone();
            }
        }

        this.initial = (BitSet) other.initial.clone();
    }

    @Override
    protected void updateTransitionStorage(Payload payload) {
        this.transitions = updateTransitionStorage(this.transitions, BitSet[]::new, null, payload);
    }

    @Override
    public Void getTransitionProperty(Integer transition) {
        return null;
    }

    @Override
    public void setInitial(Integer state, boolean initial) {
        setInitial(state.intValue(), initial);
    }

    public void setInitial(int state, boolean initial) {
        if (initial) {
            this.initial.set(state);
        } else {
            this.initial.clear(state);
        }
    }

    @Override
    public void clear() {
        Arrays.fill(transitions, 0, size() * numInputs(), null);
        this.initial.clear();

        super.clear();
    }

    @Override
    public void setTransitionProperty(Integer transition, Void property) {}

    @Override
    public void removeTransition(Integer state, I input, Integer transition) {
        removeTransition(state.intValue(), input, transition.intValue());
    }

    public void removeTransition(int stateId, I input, int successorId) {
        removeTransition(stateId, getSymbolIndex(input), successorId);
    }

    public void removeTransition(int stateId, int inputIdx, int successorId) {
        final BitSet successors = transitions[toMemoryIndex(stateId, inputIdx)];
        if (successors != null) {
            successors.clear(successorId);
        }
    }

    @Override
    public void removeAllTransitions(Integer state, I input) {
        removeAllTransitions(state.intValue(), input);
    }

    public void removeAllTransitions(int stateId, I input) {
        removeAllTransitions(stateId, getSymbolIndex(input));
    }

    public void removeAllTransitions(int stateId, int inputIdx) {
        transitions[toMemoryIndex(stateId, inputIdx)] = null;
    }

    @Override
    public void removeAllTransitions(Integer state) {
        removeAllTransitions(state.intValue());
    }

    public void removeAllTransitions(int state) {
        final int lower = state * numInputs();
        final int upper = lower + numInputs();

        Arrays.fill(transitions, lower, upper, null);
    }

    @Override
    public void addTransition(Integer state, I input, Integer transition) {
        addTransition(state.intValue(), input, transition.intValue());
    }

    public void addTransition(int stateId, I input, int succId) {
        addTransition(stateId, getSymbolIndex(input), succId);
    }

    public void addTransition(int stateId, int inputIdx, int succId) {
        final int transIdx = toMemoryIndex(stateId, inputIdx);
        BitSet successors = transitions[transIdx];
        if (successors == null) {
            successors = new BitSet();
            transitions[transIdx] = successors;
        }
        successors.set(succId);
    }

    @Override
    public Integer copyTransition(Integer trans, Integer succ) {
        return succ;
    }

    @Override
    public Integer createTransition(Integer successor, Void properties) {
        return successor;
    }

    @Override
    public void setTransitions(Integer state, I input, Collection<? extends Integer> transitions) {
        setTransitions(state.intValue(), input, transitions);
    }

    public void setTransitions(int state, I input, Collection<? extends Integer> successors) {
        setTransitions(state, getSymbolIndex(input), successors);
    }

    public void setTransitions(int state, int inputIdx, Collection<? extends Integer> successors) {
        final int transIdx = toMemoryIndex(state, inputIdx);
        BitSet succs = transitions[transIdx];
        if (succs == null) {
            succs = new BitSet();
            transitions[transIdx] = succs;
        } else {
            succs.clear();
        }
        successors.forEach(succs::set);
    }

    @Override
    public Integer getSuccessor(Integer transition) {
        return transition;
    }

    @Override
    public Collection<Integer> getTransitions(Integer state, I input) {
        return getTransitions(state.intValue(), input);
    }

    public Set<Integer> getTransitions(int state, I input) {
        return getTransitions(state, getSymbolIndex(input));
    }

    public Set<Integer> getTransitions(int state, int inputIdx) {
        final BitSet transition = transitions[toMemoryIndex(state, inputIdx)];
        return transition == null ? Collections.emptySet() : new PositiveIntSet(transition);
    }

    @Override
    public Set<Integer> getInitialStates() {
        return new PositiveIntSet(initial);
    }

    @Override
    public PowersetViewTS<BitSet, I, BitSet, Integer, Integer> powersetView() {
        return new CompactPowersetDTS();
    }

    protected class CompactPowersetDTS implements PowersetViewTS<BitSet, I, BitSet, Integer, Integer> {

        @Override
        public @Nullable BitSet getTransition(BitSet state, I input) {
            final BitSet result = new BitSet(AbstractCompactSimpleNondet.this.size());
            final int inputIdx = getSymbolIndex(input);

            for (int i = state.nextSetBit(0); i >= 0; i = state.nextSetBit(i+1)) {
                final BitSet transitions = AbstractCompactSimpleNondet.this.transitions[toMemoryIndex(i, inputIdx)];
                if (transitions != null) {
                    result.or(transitions);
                }
            }

            return result;
        }

        @Override
        public BitSet getSuccessor(BitSet transition) {
            return transition;
        }

        @Override
        public BitSet getInitialState() {
            return initial;
        }

        @Override
        public Collection<Integer> getOriginalStates(BitSet state) {
            return new PositiveIntSet(state);
        }

        @Override
        public Collection<Integer> getOriginalTransitions(BitSet transition) {
            return new PositiveIntSet(transition);
        }
    }
}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of AutomataLib <https://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.base;
17
18	import java.util.Arrays;
19	import java.util.BitSet;
20	import java.util.Collection;
21	import java.util.Collections;
22	import java.util.Set;
23
24	import net.automatalib.alphabet.Alphabet;
25	import net.automatalib.automaton.fsa.NFA;
26	import net.automatalib.common.util.collection.PositiveIntSet;
27	import net.automatalib.ts.PowersetViewTS;
28	import org.checkerframework.checker.nullness.qual.Nullable;
29
30	/**
31	* Abstract super class that refines {@link AbstractCompact} for transition-property-less automata. As a result,
32	* transitions may be represented as integers (where a transition object effectively <i>is</i> the successor).
33	* <p>
34	* <b>Implementation note:</b> This class uses {@link BitSet}s to store the successors of each state. This makes the
35	* memory consumption of this class depend on the number of states rather than the density of its adjacency matrix
36	* (since the maximum bit/index determines the size of each {@link BitSet}). For the majority of cases (tests showed if
37	* the average number of outgoing transitions per state is more than 0.2% of the number of states) this still requires
38	* less memory than using e.g. a {@link Set} of {@link Integer}s. However, for very large but very sparse {@link NFA}s
39	* one may consider using the {@link AbstractFastMutableNondet} class instead.
40	*
41	* @param <I>
42	* input symbol type
43	* @param <SP>
44	* state property type
45	*/
46	public abstract class AbstractCompactSimpleNondet<I, SP> extends AbstractCompact<I, Integer, SP, Void> {
47
48	private final BitSet initial;
49	private @Nullable BitSet[] transitions;
50
51	public AbstractCompactSimpleNondet(Alphabet<I> alphabet, int stateCapacity, float resizeFactor) {
52	super(alphabet, stateCapacity, resizeFactor);	2✔
53
54	this.transitions = new BitSet[stateCapacity * numInputs()];	2✔
55	this.initial = new BitSet();	2✔
56	}	2✔
57
58	protected AbstractCompactSimpleNondet(Alphabet<I> alphabet, AbstractCompactSimpleNondet<?, ?> other) {
59	super(alphabet, other);	2✔
60	this.transitions = other.transitions.clone();	2✔
61	for (int i = 0; i < transitions.length; i++) {	2✔
62	final BitSet tgts = transitions[i];	2✔
63	if (tgts != null) {	2✔
64	transitions[i] = (BitSet) tgts.clone();	2✔
65	}
66	}
67
68	this.initial = (BitSet) other.initial.clone();	2✔
69	}	2✔
70
71	@Override
72	protected void updateTransitionStorage(Payload payload) {
73	this.transitions = updateTransitionStorage(this.transitions, BitSet[]::new, null, payload);	2✔
74	}	2✔
75
76	@Override
77	public Void getTransitionProperty(Integer transition) {
78	return null;	2✔
79	}
80
81	@Override
82	public void setInitial(Integer state, boolean initial) {
83	setInitial(state.intValue(), initial);	2✔
84	}	2✔
85
86	public void setInitial(int state, boolean initial) {
87	if (initial) {	2✔
88	this.initial.set(state);	2✔
89	} else {
90	this.initial.clear(state);	2✔
91	}
92	}	2✔
93
94	@Override
95	public void clear() {
96	Arrays.fill(transitions, 0, size() * numInputs(), null);	2✔
97	this.initial.clear();	2✔
98
99	super.clear();	2✔
100	}	2✔
101
102	@Override
103	public void setTransitionProperty(Integer transition, Void property) {}	2✔
104
105	@Override
106	public void removeTransition(Integer state, I input, Integer transition) {
107	removeTransition(state.intValue(), input, transition.intValue());	2✔
108	}	2✔
109
110	public void removeTransition(int stateId, I input, int successorId) {
111	removeTransition(stateId, getSymbolIndex(input), successorId);	2✔
112	}	2✔
113
114	public void removeTransition(int stateId, int inputIdx, int successorId) {
115	final BitSet successors = transitions[toMemoryIndex(stateId, inputIdx)];	2✔
116	if (successors != null) {	2✔
117	successors.clear(successorId);	2✔
118	}
119	}	2✔
120
121	@Override
122	public void removeAllTransitions(Integer state, I input) {
123	removeAllTransitions(state.intValue(), input);	2✔
124	}	2✔
125
126	public void removeAllTransitions(int stateId, I input) {
127	removeAllTransitions(stateId, getSymbolIndex(input));	2✔
128	}	2✔
129
130	public void removeAllTransitions(int stateId, int inputIdx) {
131	transitions[toMemoryIndex(stateId, inputIdx)] = null;	2✔
132	}	2✔
133
134	@Override
135	public void removeAllTransitions(Integer state) {
136	removeAllTransitions(state.intValue());	2✔
137	}	2✔
138
139	public void removeAllTransitions(int state) {
140	final int lower = state * numInputs();	2✔
141	final int upper = lower + numInputs();	2✔
142
143	Arrays.fill(transitions, lower, upper, null);	2✔
144	}	2✔
145
146	@Override
147	public void addTransition(Integer state, I input, Integer transition) {
148	addTransition(state.intValue(), input, transition.intValue());	2✔
149	}	2✔
150
151	public void addTransition(int stateId, I input, int succId) {
152	addTransition(stateId, getSymbolIndex(input), succId);	2✔
153	}	2✔
154
155	public void addTransition(int stateId, int inputIdx, int succId) {
156	final int transIdx = toMemoryIndex(stateId, inputIdx);	2✔
157	BitSet successors = transitions[transIdx];	2✔
158	if (successors == null) {	2✔
159	successors = new BitSet();	2✔
160	transitions[transIdx] = successors;	2✔
161	}
162	successors.set(succId);	2✔
163	}	2✔
164
165	@Override
166	public Integer copyTransition(Integer trans, Integer succ) {
167	return succ;	×
168	}
169
170	@Override
171	public Integer createTransition(Integer successor, Void properties) {
172	return successor;	2✔
173	}
174
175	@Override
176	public void setTransitions(Integer state, I input, Collection<? extends Integer> transitions) {
177	setTransitions(state.intValue(), input, transitions);	2✔
178	}	2✔
179
180	public void setTransitions(int state, I input, Collection<? extends Integer> successors) {
181	setTransitions(state, getSymbolIndex(input), successors);	2✔
182	}	2✔
183
184	public void setTransitions(int state, int inputIdx, Collection<? extends Integer> successors) {
185	final int transIdx = toMemoryIndex(state, inputIdx);	2✔
186	BitSet succs = transitions[transIdx];	2✔
187	if (succs == null) {	2✔
188	succs = new BitSet();	2✔
189	transitions[transIdx] = succs;	2✔
190	} else {
191	succs.clear();	×
192	}
193	successors.forEach(succs::set);	2✔
194	}	2✔
195
196	@Override
197	public Integer getSuccessor(Integer transition) {
198	return transition;	2✔
199	}
200
201	@Override
202	public Collection<Integer> getTransitions(Integer state, I input) {
203	return getTransitions(state.intValue(), input);	2✔
204	}
205
206	public Set<Integer> getTransitions(int state, I input) {
207	return getTransitions(state, getSymbolIndex(input));	2✔
208	}
209
210	public Set<Integer> getTransitions(int state, int inputIdx) {
211	final BitSet transition = transitions[toMemoryIndex(state, inputIdx)];	2✔
212	return transition == null ? Collections.emptySet() : new PositiveIntSet(transition);	2✔
213	}
214
215	@Override
216	public Set<Integer> getInitialStates() {
217	return new PositiveIntSet(initial);	2✔
218	}
219
220	@Override
221	public PowersetViewTS<BitSet, I, BitSet, Integer, Integer> powersetView() {
222	return new CompactPowersetDTS();	×
223	}
224
225	protected class CompactPowersetDTS implements PowersetViewTS<BitSet, I, BitSet, Integer, Integer> {	2✔
226
227	@Override
228	public @Nullable BitSet getTransition(BitSet state, I input) {
229	final BitSet result = new BitSet(AbstractCompactSimpleNondet.this.size());	2✔
230	final int inputIdx = getSymbolIndex(input);	2✔
231
232	for (int i = state.nextSetBit(0); i >= 0; i = state.nextSetBit(i+1)) {	2✔
233	final BitSet transitions = AbstractCompactSimpleNondet.this.transitions[toMemoryIndex(i, inputIdx)];	2✔
234	if (transitions != null) {	2✔
235	result.or(transitions);	2✔
236	}
237	}
238
239	return result;	2✔
240	}
241
242	@Override
243	public BitSet getSuccessor(BitSet transition) {
244	return transition;	2✔
245	}
246
247	@Override
248	public BitSet getInitialState() {
249	return initial;	2✔
250	}
251
252	@Override
253	public Collection<Integer> getOriginalStates(BitSet state) {
254	return new PositiveIntSet(state);	2✔
255	}
256
257	@Override
258	public Collection<Integer> getOriginalTransitions(BitSet transition) {
259	return new PositiveIntSet(transition);	2✔
260	}
261	}
262	}

LearnLib / automatalib / 13138848026

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