6685076669

Committed 29 Oct 2023 06:24PM UTC coverage: 89.857% (+0.06%) from 89.796%

Build # 6685076669

Build Type

push

github

Committed by

mtf90

Commit Message

align core packages with api packages

Run Details

15814 of 17599 relevant lines covered (89.86%)

1.67 hits per line

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

96.1

/api/src/main/java/net/automatalib/alphabet/VPAlphabet.java

/* Copyright (C) 2013-2023 TU Dortmund
 * 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.alphabet;

import net.automatalib.word.Word;

/**
 * Alphabet definition for visible push-down automata. Partitions the overall input alphabet into call-, internal-, and
 * return symbols.
 *
 * @param <I>
 *         input alphabet type
 */
public interface VPAlphabet<I> extends Alphabet<I> {

    /**
     * Returns the call symbols of {@code this} alphabet as a (sub-) alphabet.
     *
     * @return the call symbols of {@code this} alphabet
     */
    Alphabet<I> getCallAlphabet();

    /**
     * The {@link Alphabet#getSymbol(int)} variant for the call alphabet. Note that the index must be relative to the
     * {@link #getCallAlphabet() call alphabet} and not to {@code this} alphabet.
     *
     * @param index
     *         the index of the symbol
     *
     * @throws IllegalArgumentException
     *         if there is no symbol with this index
     */
    I getCallSymbol(int index);

    /**
     * The {@link Alphabet#getSymbolIndex(Object)} variant for the call alphabet. Note that the index is relative to the
     * {@link #getCallAlphabet() call alphabet} and not to {@code this} alphabet.
     *
     * @param symbol
     *         the symbol whose index should be determined
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the call alphabet.
     */
    int getCallSymbolIndex(I symbol);

    /**
     * The {@link Alphabet#size()} variant for the call alphabet.
     *
     * @return the number of call symbols
     */
    int getNumCalls();

    /**
     * Returns the internal symbols of {@code this} alphabet as a (sub-) alphabet.
     *
     * @return the internal symbols of {@code this} alphabet
     */
    Alphabet<I> getInternalAlphabet();

    /**
     * The {@link Alphabet#getSymbol(int)} variant for the internal alphabet. Note that the index must be relative to
     * the {@link #getInternalAlphabet() internal alphabet} and not to {@code this} alphabet.
     *
     * @param index
     *         the index of the symbol
     *
     * @throws IllegalArgumentException
     *         if there is no symbol with this index
     */
    I getInternalSymbol(int index);

    /**
     * The {@link Alphabet#getSymbolIndex(Object)} variant for the internal alphabet. Note that the index is relative to
     * the {@link #getInternalAlphabet() internal alphabet} and not to {@code this} alphabet.
     *
     * @param symbol
     *         the symbol whose index should be determined
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the internal alphabet.
     */
    int getInternalSymbolIndex(I symbol);

    /**
     * The {@link Alphabet#size()} variant for the internal alphabet.
     *
     * @return the number of internal symbols
     */
    int getNumInternals();

    /**
     * Returns the return symbols of {@code this} alphabet as a (sub-) alphabet.
     *
     * @return the return symbols of {@code this} alphabet
     */
    Alphabet<I> getReturnAlphabet();

    /**
     * The {@link Alphabet#getSymbol(int)} variant for the return alphabet. Note that the index must be relative to the
     * {@link #getReturnAlphabet() return alphabet} and not to {@code this} alphabet.
     *
     * @param index
     *         the index of the symbol
     *
     * @throws IllegalArgumentException
     *         if there is no symbol with this index
     */
    I getReturnSymbol(int index);

    /**
     * The {@link Alphabet#getSymbolIndex(Object)} variant for the return alphabet. Note that the index is relative to
     * the {@link #getReturnAlphabet() return alphabet} and not to {@code this} alphabet.
     *
     * @param symbol
     *         the symbol whose index should be determined
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the return alphabet.
     */
    int getReturnSymbolIndex(I symbol);

    /**
     * The {@link Alphabet#size()} variant for the return alphabet.
     *
     * @return the number of return symbols
     */
    int getNumReturns();

    /**
     * Returns the {@link SymbolType symbol type} of the given alphabet symbol.
     *
     * @param symbol
     *         the symbol whose type should be returned
     *
     * @return the {@link SymbolType symbol type} of the given alphabet symbol.
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the alphabet.
     */
    SymbolType getSymbolType(I symbol);

    /**
     * Returns whether the given symbol is a call symbol of {@code this} alphabet.
     *
     * @param symbol
     *         the symbol to analyze
     *
     * @return {@code true} if the given symbol is a call symbol of this alphabet, {@code false} otherwise
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the alphabet.
     */
    default boolean isCallSymbol(I symbol) {
        return getSymbolType(symbol) == SymbolType.CALL;
    }

    /**
     * Returns whether the given symbol is an internal symbol of {@code this} alphabet.
     *
     * @param symbol
     *         the symbol to analyze
     *
     * @return {@code true} if the given symbol is an internal symbol of this alphabet, {@code false} otherwise
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the alphabet.
     */
    default boolean isInternalSymbol(I symbol) {
        return getSymbolType(symbol) == SymbolType.INTERNAL;
    }

    /**
     * Returns whether the given symbol is a return symbol of {@code this} alphabet.
     *
     * @param symbol
     *         the symbol to analyze
     *
     * @return {@code true} if the given symbol is a return symbol of this alphabet, {@code false} otherwise
     *
     * @throws IllegalArgumentException
     *         if the provided symbol does not belong to the alphabet.
     */
    default boolean isReturnSymbol(I symbol) {
        return getSymbolType(symbol) == SymbolType.RETURN;
    }

    /**
     * Returns the call-return balance of the given word relative to this alphabet. The call-return balance is positive,
     * if the given word contains more call symbols than return symbols, negative if the given word contains more return
     * symbols than call symbols, and 0 if it contains an equal number of call symbols and return symbols.
     *
     * @param word
     *         the word to analyze
     *
     * @return the call-return balance
     */
    default int callReturnBalance(Word<I> word) {
        int crb = 0;
        for (I sym : word) {
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    break;
                case RETURN:
                    crb--;
                    break;
                default:
            }
        }
        return crb;
    }

    /**
     * Returns whether the given word is call-matched relative to {@code this} alphabet. A word is call-matched if every
     * call symbol is at one point succeeded by a matching return symbol and there exist no un-matched call symbols.
     * Note that a call-matched word may still contain un-matched return symbols.
     *
     * @param word
     *         the word to analyze
     *
     * @return {@code true} if the given word is call-matched, {@code false} otherwise
     */
    default boolean isCallMatched(Word<I> word) {
        int crb = 0;
        for (I sym : word) {
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    break;
                case RETURN:
                    if (crb > 0) {
                        crb--;
                    }
                    break;
                default:
            }
        }
        return crb == 0;
    }

    /**
     * Returns whether the given word is return-matched relative to {@code this} alphabet. A word is return-matched if
     * every return symbol is at one point preceded by a matching call symbol and there exist no un-matched return
     * symbols. Note that a return-matched word may still contain un-matched call symbols.
     *
     * @param word
     *         the word to analyze
     *
     * @return {@code true} if the given word is return-matched, {@code false} otherwise
     */
    default boolean isReturnMatched(Word<I> word) {
        int crb = 0;
        for (I sym : word) {
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    break;
                case RETURN:
                    crb--;
                    if (crb < 0) {
                        return false;
                    }
                    break;
                default:
            }
        }

        return true;
    }

    /**
     * Returns whether the given word is well-matched relative to {@code this} alphabet. A word is well-matched if every
     * call symbol is at one point succeeded by a matching return symbol and there exist no un-matched call symbols or
     * return symbols.
     *
     * @param word
     *         the word to analyze
     *
     * @return {@code true} if the given word is well-matched, {@code false} otherwise
     */
    default boolean isWellMatched(Word<I> word) {
        int crb = 0;
        for (I sym : word) {
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    break;
                case RETURN:
                    crb--;
                    if (crb < 0) {
                        return false;
                    }
                    break;
                default:
            }
        }

        return crb == 0;
    }

    /**
     * Return the longest {@link #isWellMatched(Word) well-matched} (relative to {@code this} alphabet) prefix of the
     * given word.
     *
     * @param word
     *         the word to analyze
     *
     * @return the longest well-matched prefix of the given word
     */
    default Word<I> longestWellMatchedPrefix(Word<I> word) {
        int idx = 0;
        int len = word.length();
        int crb = 0;
        int lastzero = 0;
        outer:
        while (idx < len) {
            final I sym = word.getSymbol(idx);
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    break;
                case RETURN:
                    crb--;
                    if (crb < 0) {
                        break outer;
                    }
                    break;
                default:
            }
            if (crb == 0) {
                lastzero = idx + 1;
            }
            idx++;
        }
        return word.prefix(lastzero);
    }

    /**
     * Return the longest {@link #isWellMatched(Word) well-matched} (relative to {@code this} alphabet) suffix of the
     * given word.
     *
     * @param word
     *         the word to analyze
     *
     * @return the longest well-matched suffix of the given word
     */
    default Word<I> longestWellMatchedSuffix(Word<I> word) {
        int idx = word.length();
        int crb = 0;
        int lastZero = idx;
        outer:
        while (idx > 0) {
            final I sym = word.getSymbol(--idx);
            switch (getSymbolType(sym)) {
                case CALL:
                    crb++;
                    if (crb > 0) {
                        break outer;
                    }
                    break;
                case RETURN:
                    crb--;
                    break;
                default:
            }
            if (crb == 0) {
                lastZero = idx;
            }
        }
        return word.subWord(lastZero);
    }

    /**
     * Classifies an input symbol either as a call symbol, an internal symbol, or a return symbol.
     */
    enum SymbolType {
        CALL,
        INTERNAL,
        RETURN
    }

}

1	/* Copyright (C) 2013-2023 TU Dortmund
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.alphabet;
17
18	import net.automatalib.word.Word;
19
20	/**
21	* Alphabet definition for visible push-down automata. Partitions the overall input alphabet into call-, internal-, and
22	* return symbols.
23	*
24	* @param <I>
25	* input alphabet type
26	*/
27	public interface VPAlphabet<I> extends Alphabet<I> {
28
29	/**
30	* Returns the call symbols of {@code this} alphabet as a (sub-) alphabet.
31	*
32	* @return the call symbols of {@code this} alphabet
33	*/
34	Alphabet<I> getCallAlphabet();
35
36	/**
37	* The {@link Alphabet#getSymbol(int)} variant for the call alphabet. Note that the index must be relative to the
38	* {@link #getCallAlphabet() call alphabet} and not to {@code this} alphabet.
39	*
40	* @param index
41	* the index of the symbol
42	*
43	* @throws IllegalArgumentException
44	* if there is no symbol with this index
45	*/
46	I getCallSymbol(int index);
47
48	/**
49	* The {@link Alphabet#getSymbolIndex(Object)} variant for the call alphabet. Note that the index is relative to the
50	* {@link #getCallAlphabet() call alphabet} and not to {@code this} alphabet.
51	*
52	* @param symbol
53	* the symbol whose index should be determined
54	*
55	* @throws IllegalArgumentException
56	* if the provided symbol does not belong to the call alphabet.
57	*/
58	int getCallSymbolIndex(I symbol);
59
60	/**
61	* The {@link Alphabet#size()} variant for the call alphabet.
62	*
63	* @return the number of call symbols
64	*/
65	int getNumCalls();
66
67	/**
68	* Returns the internal symbols of {@code this} alphabet as a (sub-) alphabet.
69	*
70	* @return the internal symbols of {@code this} alphabet
71	*/
72	Alphabet<I> getInternalAlphabet();
73
74	/**
75	* The {@link Alphabet#getSymbol(int)} variant for the internal alphabet. Note that the index must be relative to
76	* the {@link #getInternalAlphabet() internal alphabet} and not to {@code this} alphabet.
77	*
78	* @param index
79	* the index of the symbol
80	*
81	* @throws IllegalArgumentException
82	* if there is no symbol with this index
83	*/
84	I getInternalSymbol(int index);
85
86	/**
87	* The {@link Alphabet#getSymbolIndex(Object)} variant for the internal alphabet. Note that the index is relative to
88	* the {@link #getInternalAlphabet() internal alphabet} and not to {@code this} alphabet.
89	*
90	* @param symbol
91	* the symbol whose index should be determined
92	*
93	* @throws IllegalArgumentException
94	* if the provided symbol does not belong to the internal alphabet.
95	*/
96	int getInternalSymbolIndex(I symbol);
97
98	/**
99	* The {@link Alphabet#size()} variant for the internal alphabet.
100	*
101	* @return the number of internal symbols
102	*/
103	int getNumInternals();
104
105	/**
106	* Returns the return symbols of {@code this} alphabet as a (sub-) alphabet.
107	*
108	* @return the return symbols of {@code this} alphabet
109	*/
110	Alphabet<I> getReturnAlphabet();
111
112	/**
113	* The {@link Alphabet#getSymbol(int)} variant for the return alphabet. Note that the index must be relative to the
114	* {@link #getReturnAlphabet() return alphabet} and not to {@code this} alphabet.
115	*
116	* @param index
117	* the index of the symbol
118	*
119	* @throws IllegalArgumentException
120	* if there is no symbol with this index
121	*/
122	I getReturnSymbol(int index);
123
124	/**
125	* The {@link Alphabet#getSymbolIndex(Object)} variant for the return alphabet. Note that the index is relative to
126	* the {@link #getReturnAlphabet() return alphabet} and not to {@code this} alphabet.
127	*
128	* @param symbol
129	* the symbol whose index should be determined
130	*
131	* @throws IllegalArgumentException
132	* if the provided symbol does not belong to the return alphabet.
133	*/
134	int getReturnSymbolIndex(I symbol);
135
136	/**
137	* The {@link Alphabet#size()} variant for the return alphabet.
138	*
139	* @return the number of return symbols
140	*/
141	int getNumReturns();
142
143	/**
144	* Returns the {@link SymbolType symbol type} of the given alphabet symbol.
145	*
146	* @param symbol
147	* the symbol whose type should be returned
148	*
149	* @return the {@link SymbolType symbol type} of the given alphabet symbol.
150	*
151	* @throws IllegalArgumentException
152	* if the provided symbol does not belong to the alphabet.
153	*/
154	SymbolType getSymbolType(I symbol);
155
156	/**
157	* Returns whether the given symbol is a call symbol of {@code this} alphabet.
158	*
159	* @param symbol
160	* the symbol to analyze
161	*
162	* @return {@code true} if the given symbol is a call symbol of this alphabet, {@code false} otherwise
163	*
164	* @throws IllegalArgumentException
165	* if the provided symbol does not belong to the alphabet.
166	*/
167	default boolean isCallSymbol(I symbol) {
168	return getSymbolType(symbol) == SymbolType.CALL;	×
169	}
170
171	/**
172	* Returns whether the given symbol is an internal symbol of {@code this} alphabet.
173	*
174	* @param symbol
175	* the symbol to analyze
176	*
177	* @return {@code true} if the given symbol is an internal symbol of this alphabet, {@code false} otherwise
178	*
179	* @throws IllegalArgumentException
180	* if the provided symbol does not belong to the alphabet.
181	*/
182	default boolean isInternalSymbol(I symbol) {
183	return getSymbolType(symbol) == SymbolType.INTERNAL;	×
184	}
185
186	/**
187	* Returns whether the given symbol is a return symbol of {@code this} alphabet.
188	*
189	* @param symbol
190	* the symbol to analyze
191	*
192	* @return {@code true} if the given symbol is a return symbol of this alphabet, {@code false} otherwise
193	*
194	* @throws IllegalArgumentException
195	* if the provided symbol does not belong to the alphabet.
196	*/
197	default boolean isReturnSymbol(I symbol) {
198	return getSymbolType(symbol) == SymbolType.RETURN;	×
199	}
200
201	/**
202	* Returns the call-return balance of the given word relative to this alphabet. The call-return balance is positive,
203	* if the given word contains more call symbols than return symbols, negative if the given word contains more return
204	* symbols than call symbols, and 0 if it contains an equal number of call symbols and return symbols.
205	*
206	* @param word
207	* the word to analyze
208	*
209	* @return the call-return balance
210	*/
211	default int callReturnBalance(Word<I> word) {
212	int crb = 0;	1✔
213	for (I sym : word) {	1✔
214	switch (getSymbolType(sym)) {	1✔
215	case CALL:
216	crb++;	1✔
217	break;	1✔
218	case RETURN:
219	crb--;	1✔
220	break;	1✔
221	default:
222	}
223	}	1✔
224	return crb;	1✔
225	}
226
227	/**
228	* Returns whether the given word is call-matched relative to {@code this} alphabet. A word is call-matched if every
229	* call symbol is at one point succeeded by a matching return symbol and there exist no un-matched call symbols.
230	* Note that a call-matched word may still contain un-matched return symbols.
231	*
232	* @param word
233	* the word to analyze
234	*
235	* @return {@code true} if the given word is call-matched, {@code false} otherwise
236	*/
237	default boolean isCallMatched(Word<I> word) {
238	int crb = 0;	1✔
239	for (I sym : word) {	1✔
240	switch (getSymbolType(sym)) {	1✔
241	case CALL:
242	crb++;	1✔
243	break;	1✔
244	case RETURN:
245	if (crb > 0) {	1✔
246	crb--;	1✔
247	}
248	break;
249	default:
250	}
251	}	1✔
252	return crb == 0;	1✔
253	}
254
255	/**
256	* Returns whether the given word is return-matched relative to {@code this} alphabet. A word is return-matched if
257	* every return symbol is at one point preceded by a matching call symbol and there exist no un-matched return
258	* symbols. Note that a return-matched word may still contain un-matched call symbols.
259	*
260	* @param word
261	* the word to analyze
262	*
263	* @return {@code true} if the given word is return-matched, {@code false} otherwise
264	*/
265	default boolean isReturnMatched(Word<I> word) {
266	int crb = 0;	1✔
267	for (I sym : word) {	1✔
268	switch (getSymbolType(sym)) {	1✔
269	case CALL:
270	crb++;	1✔
271	break;	1✔
272	case RETURN:
273	crb--;	1✔
274	if (crb < 0) {	1✔
275	return false;	1✔
276	}
277	break;
278	default:
279	}
280	}	1✔
281
282	return true;	1✔
283	}
284
285	/**
286	* Returns whether the given word is well-matched relative to {@code this} alphabet. A word is well-matched if every
287	* call symbol is at one point succeeded by a matching return symbol and there exist no un-matched call symbols or
288	* return symbols.
289	*
290	* @param word
291	* the word to analyze
292	*
293	* @return {@code true} if the given word is well-matched, {@code false} otherwise
294	*/
295	default boolean isWellMatched(Word<I> word) {
296	int crb = 0;	1✔
297	for (I sym : word) {	1✔
298	switch (getSymbolType(sym)) {	1✔
299	case CALL:
300	crb++;	1✔
301	break;	1✔
302	case RETURN:
303	crb--;	1✔
304	if (crb < 0) {	1✔
305	return false;	1✔
306	}
307	break;
308	default:
309	}
310	}	1✔
311
312	return crb == 0;	1✔
313	}
314
315	/**
316	* Return the longest {@link #isWellMatched(Word) well-matched} (relative to {@code this} alphabet) prefix of the
317	* given word.
318	*
319	* @param word
320	* the word to analyze
321	*
322	* @return the longest well-matched prefix of the given word
323	*/
324	default Word<I> longestWellMatchedPrefix(Word<I> word) {
325	int idx = 0;	1✔
326	int len = word.length();	1✔
327	int crb = 0;	1✔
328	int lastzero = 0;	1✔
329	outer:
330	while (idx < len) {	1✔
331	final I sym = word.getSymbol(idx);	1✔
332	switch (getSymbolType(sym)) {	1✔
333	case CALL:
334	crb++;	1✔
335	break;	1✔
336	case RETURN:
337	crb--;	1✔
338	if (crb < 0) {	1✔
339	break outer;	1✔
340	}
341	break;
342	default:
343	}
344	if (crb == 0) {	1✔
345	lastzero = idx + 1;	1✔
346	}
347	idx++;	1✔
348	}	1✔
349	return word.prefix(lastzero);	1✔
350	}
351
352	/**
353	* Return the longest {@link #isWellMatched(Word) well-matched} (relative to {@code this} alphabet) suffix of the
354	* given word.
355	*
356	* @param word
357	* the word to analyze
358	*
359	* @return the longest well-matched suffix of the given word
360	*/
361	default Word<I> longestWellMatchedSuffix(Word<I> word) {
362	int idx = word.length();	1✔
363	int crb = 0;	1✔
364	int lastZero = idx;	1✔
365	outer:
366	while (idx > 0) {	1✔
367	final I sym = word.getSymbol(--idx);	1✔
368	switch (getSymbolType(sym)) {	1✔
369	case CALL:
370	crb++;	1✔
371	if (crb > 0) {	1✔
372	break outer;	1✔
373	}
374	break;
375	case RETURN:
376	crb--;	1✔
377	break;	1✔
378	default:
379	}
380	if (crb == 0) {	1✔
381	lastZero = idx;	1✔
382	}
383	}	1✔
384	return word.subWord(lastZero);	1✔
385	}
386
387	/**
388	* Classifies an input symbol either as a call symbol, an internal symbol, or a return symbol.
389	*/
390	enum SymbolType {	1✔
391	CALL,	1✔
392	INTERNAL,	1✔
393	RETURN	1✔
394	}
395
396	}

LearnLib / automatalib / 6685076669

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