12771457454

Committed 14 Jan 2025 03:47PM UTC coverage: 91.741% (+0.1%) from 91.62%

Build # 12771457454

Build Type

push

github

Committed by

mtf90

Commit Message

cleanup type parameters of EmptyWord

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

35 existing lines in 10 files now uncovered.

16551 of 18041 relevant lines covered (91.74%)

1.7 hits per line

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

98.48

/util/src/main/java/net/automatalib/util/automaton/conformance/StrictPriorityQueue.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.util.automaton.conformance;

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.Iterator;

import net.automatalib.common.util.array.ArrayStorage;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A priority queue which enforces that no two elements that it contains are equal wrt. the specified comparator (i.e.,
 * {@link Comparator#compare(Object, Object)} does not return {@code 0} for two distinct elements).
 * <p>
 * If an element is inserted which, according to the {@link Comparator}, is already present, the specified {@link
 * MergeOperation}'s {@link MergeOperation#merge(Object, Object)} method is invoked to determine the replacement
 * element.
 * <p>
 * The name derives from the fact that subsequent calls to {@link #poll()} will yield a <i>strictly</i> growing sequence
 * of elements.
 * <p>
 * This class does not disallow {@code null} values, but the supplied {@link Comparator} has to support them.
 *
 * @param <E>
 *         element type
 */
class StrictPriorityQueue<E> extends AbstractQueue<E> {

    private final ArrayStorage<E> storage = new ArrayStorage<>();
    private final Comparator<? super E> comparator;
    private final MergeOperation<E> mergeOp;
    private int size;

    /**
     * Constructor.
     *
     * @param comparator
     *         the comparator used to compare elements
     * @param mergeOp
     *         the merge operation to perform for equally-ranked elements
     */
    StrictPriorityQueue(Comparator<? super E> comparator, MergeOperation<E> mergeOp) {
        this.comparator = comparator;
        this.mergeOp = mergeOp;
    }

    @Override
    public boolean offer(E e) {
        storage.ensureCapacity(size + 1);
        storage.set(size++, e);
        if (!upHeap()) {
            size--;
            return false;
        }
        return true;
    }

    /**
     * Moves the last element upwards in the heap until the heap condition is restored.
     *
     * @return {@code true} if the element has been inserted, {@code false} if it has been merged with an existing
     * element.
     */
    @SuppressWarnings("PMD.AvoidArrayLoops") // we move non-contiguous elements that can't be batched
    private boolean upHeap() {
        int currIdx = size - 1;
        E elem = storage.get(currIdx);

        int steps = 0;

        while (currIdx > 0) {
            int parentIdx = currIdx / 2;
            E parent = storage.get(parentIdx);
            int cmp = comparator.compare(elem, parent);
            if (cmp == 0) {
                storage.set(parentIdx, mergeOp.merge(parent, elem));
                return false;
            } else if (cmp > 0) {
                break;
            }

            currIdx = parentIdx;
            steps++;
        }

        currIdx = size - 1;
        for (int i = 0; i < steps; i++) {
            int parentIdx = currIdx / 2;
            storage.set(currIdx, storage.get(parentIdx));
            currIdx = parentIdx;
        }
        storage.set(currIdx, elem);

        return true;
    }

    @Override
    @SuppressWarnings("nullness") // setting 'null' is fine, because we also decrease the size
    public @Nullable E poll() {
        if (size == 0) {
            return null;
        }
        E result = storage.get(0);
        size--;
        if (size > 0) {
            storage.set(0, storage.get(size));
            downHeap();
        }
        storage.set(size, null);

        return result;
    }

    /**
     * Sifts the topmost element down into the heap until the heap condition is restored.
     */
    private void downHeap() {
        E elem = storage.get(0);
        int currIdx = 0;

        while (2 * currIdx + 1 < size) {
            int childIdx = 2 * currIdx + 1;
            E child = storage.get(childIdx);
            int rightChildIdx = childIdx + 1;

            if (rightChildIdx < size) {
                E rightChild = storage.get(rightChildIdx);
                if (comparator.compare(child, rightChild) > 0) {
                    child = rightChild;
                    childIdx = rightChildIdx;
                }
            }

            if (comparator.compare(elem, child) > 0) {
                storage.set(currIdx, child);
                storage.set(childIdx, elem);
                currIdx = childIdx;
            } else {
                return;
            }
        }
    }

    @Override
    public @Nullable E peek() {
        if (size == 0) {
            return null;
        }
        return storage.get(0);
    }

    @Override
    public Iterator<E> iterator() {
        return storage.iterator();
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * The merge operation two perform on two equally-ranked elements.
     *
     * @param <E>
     *         element type
     */
    public interface MergeOperation<E> {

        /**
         * Merges the old element and the new element into a replacement element.
         * <p>
         * Implementations can assume that {@code cmp.compare(oldObject, newObject) == 0} holds for the comparator
         * {@code cmp} specified in {@link StrictPriorityQueue#StrictPriorityQueue(Comparator, MergeOperation)}. In
         * turn, they must guarantee that also {@code cmp.compare(result, oldObject) == 0} holds for the return value
         * {@code result}.
         *
         * @param oldObject
         *         the old element
         * @param newObject
         *         the new element
         *
         * @return the replacement element
         */
        E merge(E oldObject, E newObject);
    }

}

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.util.automaton.conformance;
17
18	import java.util.AbstractQueue;
19	import java.util.Comparator;
20	import java.util.Iterator;
21
22	import net.automatalib.common.util.array.ArrayStorage;
23	import org.checkerframework.checker.nullness.qual.Nullable;
24
25	/**
26	* A priority queue which enforces that no two elements that it contains are equal wrt. the specified comparator (i.e.,
27	* {@link Comparator#compare(Object, Object)} does not return {@code 0} for two distinct elements).
28	* <p>
29	* If an element is inserted which, according to the {@link Comparator}, is already present, the specified {@link
30	* MergeOperation}'s {@link MergeOperation#merge(Object, Object)} method is invoked to determine the replacement
31	* element.
32	* <p>
33	* The name derives from the fact that subsequent calls to {@link #poll()} will yield a <i>strictly</i> growing sequence
34	* of elements.
35	* <p>
36	* This class does not disallow {@code null} values, but the supplied {@link Comparator} has to support them.
37	*
38	* @param <E>
39	* element type
40	*/
41	class StrictPriorityQueue<E> extends AbstractQueue<E> {
42
43	private final ArrayStorage<E> storage = new ArrayStorage<>();	2✔
44	private final Comparator<? super E> comparator;
45	private final MergeOperation<E> mergeOp;
46	private int size;
47
48	/**
49	* Constructor.
50	*
51	* @param comparator
52	* the comparator used to compare elements
53	* @param mergeOp
54	* the merge operation to perform for equally-ranked elements
55	*/
56	StrictPriorityQueue(Comparator<? super E> comparator, MergeOperation<E> mergeOp) {	2✔
57	this.comparator = comparator;	2✔
58	this.mergeOp = mergeOp;	2✔
59	}	2✔
60
61	@Override
62	public boolean offer(E e) {
63	storage.ensureCapacity(size + 1);	2✔
64	storage.set(size++, e);	2✔
65	if (!upHeap()) {	2✔
66	size--;	2✔
67	return false;	2✔
68	}
69	return true;	2✔
70	}
71
72	/**
73	* Moves the last element upwards in the heap until the heap condition is restored.
74	*
75	* @return {@code true} if the element has been inserted, {@code false} if it has been merged with an existing
76	* element.
77	*/
78	@SuppressWarnings("PMD.AvoidArrayLoops") // we move non-contiguous elements that can't be batched
79	private boolean upHeap() {
80	int currIdx = size - 1;	2✔
81	E elem = storage.get(currIdx);	2✔
82
83	int steps = 0;	2✔
84
85	while (currIdx > 0) {	2✔
86	int parentIdx = currIdx / 2;	2✔
87	E parent = storage.get(parentIdx);	2✔
88	int cmp = comparator.compare(elem, parent);	2✔
89	if (cmp == 0) {	2✔
90	storage.set(parentIdx, mergeOp.merge(parent, elem));	2✔
91	return false;	2✔
92	} else if (cmp > 0) {	2✔
93	break;	2✔
94	}
95
96	currIdx = parentIdx;	2✔
97	steps++;	2✔
98	}	2✔
99
100	currIdx = size - 1;	2✔
101	for (int i = 0; i < steps; i++) {	2✔
102	int parentIdx = currIdx / 2;	2✔
103	storage.set(currIdx, storage.get(parentIdx));	2✔
104	currIdx = parentIdx;	2✔
105	}
106	storage.set(currIdx, elem);	2✔
107
108	return true;	2✔
109	}
110
111	@Override
112	@SuppressWarnings("nullness") // setting 'null' is fine, because we also decrease the size
113	public @Nullable E poll() {
114	if (size == 0) {	2✔
115	return null;	2✔
116	}
117	E result = storage.get(0);	2✔
118	size--;	2✔
119	if (size > 0) {	2✔
120	storage.set(0, storage.get(size));	2✔
121	downHeap();	2✔
122	}
123	storage.set(size, null);	2✔
124
125	return result;	2✔
126	}
127
128	/**
129	* Sifts the topmost element down into the heap until the heap condition is restored.
130	*/
131	private void downHeap() {
132	E elem = storage.get(0);	2✔
133	int currIdx = 0;	2✔
134
135	while (2 * currIdx + 1 < size) {	2✔
136	int childIdx = 2 * currIdx + 1;	2✔
137	E child = storage.get(childIdx);	2✔
138	int rightChildIdx = childIdx + 1;	2✔
139
140	if (rightChildIdx < size) {	2✔
141	E rightChild = storage.get(rightChildIdx);	2✔
142	if (comparator.compare(child, rightChild) > 0) {	2✔
143	child = rightChild;	2✔
144	childIdx = rightChildIdx;	2✔
145	}
146	}
147
148	if (comparator.compare(elem, child) > 0) {	2✔
149	storage.set(currIdx, child);	2✔
150	storage.set(childIdx, elem);	2✔
151	currIdx = childIdx;	2✔
152	} else {
153	return;	2✔
154	}
155	}	2✔
156	}	2✔
157
158	@Override
159	public @Nullable E peek() {
160	if (size == 0) {	2✔
161	return null;	2✔
162	}
163	return storage.get(0);	2✔
164	}
165
166	@Override
167	public Iterator<E> iterator() {
UNCOV 168	return storage.iterator();	×
169	}
170
171	@Override
172	public int size() {
173	return size;	2✔
174	}
175
176	@Override
177	public boolean isEmpty() {
178	return size == 0;	2✔
179	}
180
181	/**
182	* The merge operation two perform on two equally-ranked elements.
183	*
184	* @param <E>
185	* element type
186	*/
187	public interface MergeOperation<E> {
188
189	/**
190	* Merges the old element and the new element into a replacement element.
191	* <p>
192	* Implementations can assume that {@code cmp.compare(oldObject, newObject) == 0} holds for the comparator
193	* {@code cmp} specified in {@link StrictPriorityQueue#StrictPriorityQueue(Comparator, MergeOperation)}. In
194	* turn, they must guarantee that also {@code cmp.compare(result, oldObject) == 0} holds for the return value
195	* {@code result}.
196	*
197	* @param oldObject
198	* the old element
199	* @param newObject
200	* the new element
201	*
202	* @return the replacement element
203	*/
204	E merge(E oldObject, E newObject);
205	}
206
207	}

LearnLib / automatalib / 12771457454

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