6763327895

Committed 05 Nov 2023 07:29PM UTC coverage: 89.726% (-0.1%) from 89.868%

Build # 6763327895

Build Type

push

github

Committed by

mtf90

Commit Message

fix typo

Run Details

4 of 4 new or added lines in 4 files covered. (100.0%)

99 existing lines in 18 files now uncovered.

15677 of 17472 relevant lines covered (89.73%)

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

LearnLib / automatalib / 6763327895

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