12459117572

Committed 22 Dec 2024 05:57PM UTC coverage: 91.532% (+0.3%) from 91.183%

Build # 12459117572

Build Type

push

github

Committed by

mtf90

Commit Message

cleanups

as reported by IntelliJ's analysis

Run Details

4 of 17 new or added lines in 10 files covered. (23.53%)

9 existing lines in 3 files now uncovered.

16581 of 18115 relevant lines covered (91.53%)

1.69 hits per line

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

90.07

/commons/smartcollections/src/main/java/net/automatalib/common/smartcollection/BinaryHeap.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.common.smartcollection;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Queue;

import net.automatalib.common.util.array.ResizingArrayStorage;
import org.checkerframework.checker.initialization.qual.UnknownInitialization;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A {@link PriorityQueue} implementation using a binary heap.
 *
 * @param <E>
 *         element class.
 */
public class BinaryHeap<E> extends AbstractSmartCollection<E>
        implements SmartDynamicPriorityQueue<E>, CapacityManagement, Queue<E> {

    private static final int DEFAULT_INITIAL_CAPACITY = 10;
    private final Comparator<? super E> comparator;
    // Entry storage.
    private final ResizingArrayStorage<Reference<E>> entries;
    // Number of entries in the queue.
    private int size;

    protected BinaryHeap(int initCapacity, Collection<? extends E> initValues, Comparator<? super E> comparator) {
        this(Math.max(initCapacity, initValues.size()), comparator);
        int i = 0;
        for (E e : initValues) {
            entries.array[i++] = new Reference<>(0, e);
        }
        size = initValues.size();
        for (int j = size / 2; j >= 0; j--) {
            downHeap(j);
        }
    }

    protected BinaryHeap(int initialCapacity, Comparator<? super E> comparator) {
        this.entries = new ResizingArrayStorage<>(Reference.class, initialCapacity);
        this.comparator = comparator;
    }

    /**
     * Move an element downwards inside the heap, until all of its children have a key greater or equal to its own.
     */
    private void downHeap(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
        Reference<E> e = entries.array[idx];

        int iter = idx;
        while (hasChildren(iter)) {
            int cidx = leftChild(iter);
            Reference<E> c = entries.array[cidx];

            if (hasRightChild(iter)) {
                int rcidx = rightChild(iter);
                Reference<E> rc = entries.array[rcidx];
                if (compare(rc, c) < 0) {
                    cidx = rcidx;
                    c = rc;
                }
            }

            if (compare(e, c) <= 0) {
                break;
            }

            entries.array[cidx] = e;
            entries.array[iter] = c;
            c.index = iter;
            iter = cidx;
        }

        e.index = iter;
    }

    /**
     * Checks whether the entry at the specified index has at least one child.
     */
    private boolean hasChildren(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
        return idx * 2 < size;
    }

    /**
     * Retrieves the index of the left child of a given parent index.
     */
    private static int leftChild(int parent) {
        return 2 * parent;
    }

    /**
     * Checks whether the entry at the specified index has two children.
     */
    private boolean hasRightChild(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
        return idx * 2 + 1 < size;
    }

    /**
     * Retrieves the index of the right child of a given parent index.
     */
    private static int rightChild(int parent) {
        return 2 * parent + 1;
    }

    /**
     * Compares the referenced elements.
     */
    private int compare(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, Reference<E> e1, Reference<E> e2) {
        return comparator.compare(e1.element, e2.element);
    }

    public static <E extends Comparable<E>> BinaryHeap<E> create() {
        return create(DEFAULT_INITIAL_CAPACITY);
    }

    public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity) {
        return new BinaryHeap<>(initialCapacity, Comparator.naturalOrder());
    }

    public static <E extends Comparable<E>> BinaryHeap<E> create(Collection<? extends E> initValues) {
        return create(0, initValues);
    }

    public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity,
                                                                 Collection<? extends E> initValues) {
        return new BinaryHeap<>(initialCapacity, initValues, Comparator.naturalOrder());
    }

    public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator) {
        return createCmp(comparator, DEFAULT_INITIAL_CAPACITY);
    }

    public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity) {
        return new BinaryHeap<>(initialCapacity, comparator);
    }

    public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, Collection<? extends E> initValues) {
        return createCmp(comparator, 0, initValues);
    }

    public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator,
                                              int initialCapacity,
                                              Collection<? extends E> initValues) {
        return new BinaryHeap<>(initialCapacity, initValues, comparator);
    }

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

    @Override
    public E get(ElementReference ref) {
        return BinaryHeap.<E>asHeapRef(ref).element;
    }

    @SuppressWarnings("unchecked")
    private static <E> Reference<E> asHeapRef(ElementReference ref) {
        if (ref.getClass() != Reference.class) {
            throw new InvalidReferenceException(
                    "Reference is of wrong class '" + ref.getClass().getName() + "', should be " +
                    Reference.class.getName() + ".");
        }
        return (Reference<E>) ref;
    }

    @Override
    public ElementReference referencedAdd(E elem) {
        ensureCapacity(size + 1);

        Reference<E> entry = new Reference<>(size, elem);
        entries.array[size] = entry;
        upHeap(size++);

        return entry;
    }

    @Override
    public void remove(ElementReference ref) {
        remove(asHeapRef(ref).index);
    }

    /**
     * Removes the element at the specified index from the heap. This is done by simulating a key decrease to -infinity
     * and then performing extractMin.
     */
    private void remove(int index) {
        forceToTop(index);
        extractMin();
    }

    @Override
    public E remove() {
        return extractMin();
    }

    private void forceToTop(int idx) {
        Reference<E> e = entries.array[idx];

        int iter = idx;
        while (hasParent(iter)) {
            int pidx = parent(iter);
            Reference<E> p = entries.array[pidx];
            entries.array[pidx] = e;
            entries.array[iter] = p;
            p.index = iter;
            iter = parent(iter);
        }
        e.index = iter;
    }

    @Override
    public Iterator<ElementReference> referenceIterator() {
        return new ReferenceIterator();
    }

    @Override
    public void replace(ElementReference ref, E newElement) {
        Reference<E> heapRef = asHeapRef(ref);
        heapRef.element = newElement;
        keyChanged(ref);
    }

    @Override
    public void keyChanged(ElementReference ref) {
        keyChanged(asHeapRef(ref).index);
    }

    public void keyChanged(int index) {
        upHeap(index);
        downHeap(index);
    }

    @Override
    public boolean ensureCapacity(int minCapacity) {
        return entries.ensureCapacity(minCapacity);
    }

    /**
     * Move an element upwards inside the heap, until it has a parent with a key less or equal to its own.
     */
    private void upHeap(int idx) {
        Reference<E> e = entries.array[idx];

        int iter = idx;
        while (hasParent(iter)) {
            int pidx = parent(iter);
            Reference<E> p = entries.array[pidx];
            if (compare(e, p) < 0) {
                entries.array[pidx] = e;
                entries.array[iter] = p;
                p.index = iter;
                iter = parent(iter);
            } else {
                break;
            }
        }
        e.index = iter;
    }

    /**
     * Checks if the specified index has a parent.
     */
    private static boolean hasParent(int idx) {
        return idx > 0;
    }

    /**
     * Retrieves, for a given child index, its parent index.
     */

    private static int parent(int child) {
        return child / 2;
    }

    @Override
    public boolean ensureAdditionalCapacity(int additionalCapacity) {
        return ensureCapacity(size + additionalCapacity);
    }

    @Override
    public void hintNextCapacity(int nextCapacityHint) {
        entries.hintNextCapacity(nextCapacityHint);
    }

    @Override
    public void quickClear() {
        size = 0;
    }

    @SuppressWarnings("nullness") // setting 'null' is fine, when (according to JavaDoc) calling quickClear() first
    @Override
    public void deepClear() {
        quickClear();
        entries.setAll(null);
    }

    @Override
    public boolean offer(E e) {
        add(e);
        return true;
    }

    @Override
    public @Nullable E poll() {
        if (size > 0) {
            return extractMin();
        }
        return null;
    }

    @Override
    public E element() {
        return peekMin();
    }

    @Override
    public E peekMin() {
        if (size <= 0) {
            throw new NoSuchElementException();
        }
        return entries.array[0].element;
    }

    @SuppressWarnings("nullness") // setting 'null' is fine, because we also decrease the size
    @Override
    public E extractMin() {
        if (size <= 0) {
            throw new NoSuchElementException();
        }
        E min = entries.array[0].element;
        entries.array[0] = entries.array[--size];
        entries.array[size] = null;

        if (size > 0) {
            downHeap(0);
        }

        return min;
    }

    @Override
    public @Nullable E peek() {
        if (size > 0) {
            return peekMin();
        }
        return null;
    }

    /**
     * Class for entries in a priority queue. Entry objects are returned by the {@link
     * SmartDynamicPriorityQueue#referencedAdd(Object)} method and are passed to the {@link
     * SmartDynamicPriorityQueue#keyChanged(ElementReference)} method. The usage of entry objects eliminates the
     * necessity of an extra element to index mapping.
     *
     * @param <E>
     *         element class.
     */
    private static final class Reference<E> implements ElementReference {

        private int index;
        private E element;

        /**
         * Constructor.
         *
         * @param index
         *         the index of the entry inside the queue.
         * @param element
         *         the element stored in this entry.
         */
        Reference(int index, E element) {
            this.element = element;
            this.index = index;
        }
    }

    private class ReferenceIterator implements Iterator<ElementReference> {

        private int current;

        @Override
        public boolean hasNext() {
            return current < size;
        }

        @Override
        public ElementReference next() {
            if (current >= size) {
                throw new NoSuchElementException();
            }
            return entries.array[current++];
        }

        @Override
        public void remove() {
            BinaryHeap.this.remove(--current);
        }
    }

}

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.common.smartcollection;
17
18	import java.util.Collection;
19	import java.util.Comparator;
20	import java.util.Iterator;
21	import java.util.NoSuchElementException;
22	import java.util.PriorityQueue;
23	import java.util.Queue;
24
25	import net.automatalib.common.util.array.ResizingArrayStorage;
26	import org.checkerframework.checker.initialization.qual.UnknownInitialization;
27	import org.checkerframework.checker.nullness.qual.Nullable;
28
29	/**
30	* A {@link PriorityQueue} implementation using a binary heap.
31	*
32	* @param <E>
33	* element class.
34	*/
35	public class BinaryHeap<E> extends AbstractSmartCollection<E>
36	implements SmartDynamicPriorityQueue<E>, CapacityManagement, Queue<E> {
37
38	private static final int DEFAULT_INITIAL_CAPACITY = 10;
39	private final Comparator<? super E> comparator;
40	// Entry storage.
41	private final ResizingArrayStorage<Reference<E>> entries;
42	// Number of entries in the queue.
43	private int size;
44
45	protected BinaryHeap(int initCapacity, Collection<? extends E> initValues, Comparator<? super E> comparator) {
46	this(Math.max(initCapacity, initValues.size()), comparator);	2✔
47	int i = 0;	2✔
48	for (E e : initValues) {	2✔
49	entries.array[i++] = new Reference<>(0, e);	2✔
50	}	2✔
51	size = initValues.size();	2✔
52	for (int j = size / 2; j >= 0; j--) {	2✔
53	downHeap(j);	2✔
54	}
55	}	2✔
56
57	protected BinaryHeap(int initialCapacity, Comparator<? super E> comparator) {	2✔
58	this.entries = new ResizingArrayStorage<>(Reference.class, initialCapacity);	2✔
59	this.comparator = comparator;	2✔
60	}	2✔
61
62	/**
63	* Move an element downwards inside the heap, until all of its children have a key greater or equal to its own.
64	*/
65	private void downHeap(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
66	Reference<E> e = entries.array[idx];	2✔
67
68	int iter = idx;	2✔
69	while (hasChildren(iter)) {	2✔
70	int cidx = leftChild(iter);	2✔
71	Reference<E> c = entries.array[cidx];	2✔
72
73	if (hasRightChild(iter)) {	2✔
74	int rcidx = rightChild(iter);	2✔
75	Reference<E> rc = entries.array[rcidx];	2✔
76	if (compare(rc, c) < 0) {	2✔
77	cidx = rcidx;	2✔
78	c = rc;	2✔
79	}
80	}
81
82	if (compare(e, c) <= 0) {	2✔
83	break;	2✔
84	}
85
86	entries.array[cidx] = e;	2✔
87	entries.array[iter] = c;	2✔
88	c.index = iter;	2✔
89	iter = cidx;	2✔
90	}	2✔
91
92	e.index = iter;	2✔
93	}	2✔
94
95	/**
96	* Checks whether the entry at the specified index has at least one child.
97	*/
98	private boolean hasChildren(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
99	return idx * 2 < size;	2✔
100	}
101
102	/**
103	* Retrieves the index of the left child of a given parent index.
104	*/
105	private static int leftChild(int parent) {
106	return 2 * parent;	2✔
107	}
108
109	/**
110	* Checks whether the entry at the specified index has two children.
111	*/
112	private boolean hasRightChild(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, int idx) {
113	return idx * 2 + 1 < size;	2✔
114	}
115
116	/**
117	* Retrieves the index of the right child of a given parent index.
118	*/
119	private static int rightChild(int parent) {
120	return 2 * parent + 1;	2✔
121	}
122
123	/**
124	* Compares the referenced elements.
125	*/
126	private int compare(@UnknownInitialization(BinaryHeap.class) BinaryHeap<E> this, Reference<E> e1, Reference<E> e2) {
127	return comparator.compare(e1.element, e2.element);	2✔
128	}
129
130	public static <E extends Comparable<E>> BinaryHeap<E> create() {
131	return create(DEFAULT_INITIAL_CAPACITY);	2✔
132	}
133
134	public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity) {
135	return new BinaryHeap<>(initialCapacity, Comparator.naturalOrder());	2✔
136	}
137
138	public static <E extends Comparable<E>> BinaryHeap<E> create(Collection<? extends E> initValues) {
139	return create(0, initValues);	2✔
140	}
141
142	public static <E extends Comparable<E>> BinaryHeap<E> create(int initialCapacity,
143	Collection<? extends E> initValues) {
144	return new BinaryHeap<>(initialCapacity, initValues, Comparator.naturalOrder());	2✔
145	}
146
147	public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator) {
148	return createCmp(comparator, DEFAULT_INITIAL_CAPACITY);	×
149	}
150
151	public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, int initialCapacity) {
152	return new BinaryHeap<>(initialCapacity, comparator);	×
153	}
154
155	public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator, Collection<? extends E> initValues) {
156	return createCmp(comparator, 0, initValues);	×
157	}
158
159	public static <E> BinaryHeap<E> createCmp(Comparator<? super E> comparator,
160	int initialCapacity,
161	Collection<? extends E> initValues) {
162	return new BinaryHeap<>(initialCapacity, initValues, comparator);	×
163	}
164
165	@Override
166	public int size() {
167	return size;	2✔
168	}
169
170	@Override
171	public E get(ElementReference ref) {
172	return BinaryHeap.<E>asHeapRef(ref).element;	2✔
173	}
174
175	@SuppressWarnings("unchecked")
176	private static <E> Reference<E> asHeapRef(ElementReference ref) {
177	if (ref.getClass() != Reference.class) {	2✔
178	throw new InvalidReferenceException(	×
179	"Reference is of wrong class '" + ref.getClass().getName() + "', should be " +	×
180	Reference.class.getName() + ".");	×
181	}
182	return (Reference<E>) ref;	2✔
183	}
184
185	@Override
186	public ElementReference referencedAdd(E elem) {
187	ensureCapacity(size + 1);	2✔
188
189	Reference<E> entry = new Reference<>(size, elem);	2✔
190	entries.array[size] = entry;	2✔
191	upHeap(size++);	2✔
192
193	return entry;	2✔
194	}
195
196	@Override
197	public void remove(ElementReference ref) {
198	remove(asHeapRef(ref).index);	2✔
199	}	2✔
200
201	/**
202	* Removes the element at the specified index from the heap. This is done by simulating a key decrease to -infinity
203	* and then performing extractMin.
204	*/
205	private void remove(int index) {
206	forceToTop(index);	2✔
207	extractMin();	2✔
208	}	2✔
209
210	@Override
211	public E remove() {
212	return extractMin();	×
213	}
214
215	private void forceToTop(int idx) {
216	Reference<E> e = entries.array[idx];	2✔
217
218	int iter = idx;	2✔
219	while (hasParent(iter)) {	2✔
220	int pidx = parent(iter);	2✔
221	Reference<E> p = entries.array[pidx];	2✔
222	entries.array[pidx] = e;	2✔
223	entries.array[iter] = p;	2✔
224	p.index = iter;	2✔
225	iter = parent(iter);	2✔
226	}	2✔
227	e.index = iter;	2✔
228	}	2✔
229
230	@Override
231	public Iterator<ElementReference> referenceIterator() {
232	return new ReferenceIterator();	2✔
233	}
234
235	@Override
236	public void replace(ElementReference ref, E newElement) {
237	Reference<E> heapRef = asHeapRef(ref);	2✔
238	heapRef.element = newElement;	2✔
239	keyChanged(ref);	2✔
240	}	2✔
241
242	@Override
243	public void keyChanged(ElementReference ref) {
244	keyChanged(asHeapRef(ref).index);	2✔
245	}	2✔
246
247	public void keyChanged(int index) {
248	upHeap(index);	2✔
249	downHeap(index);	2✔
250	}	2✔
251
252	@Override
253	public boolean ensureCapacity(int minCapacity) {
254	return entries.ensureCapacity(minCapacity);	2✔
255	}
256
257	/**
258	* Move an element upwards inside the heap, until it has a parent with a key less or equal to its own.
259	*/
260	private void upHeap(int idx) {
261	Reference<E> e = entries.array[idx];	2✔
262
263	int iter = idx;	2✔
264	while (hasParent(iter)) {	2✔
265	int pidx = parent(iter);	2✔
266	Reference<E> p = entries.array[pidx];	2✔
267	if (compare(e, p) < 0) {	2✔
268	entries.array[pidx] = e;	2✔
269	entries.array[iter] = p;	2✔
270	p.index = iter;	2✔
271	iter = parent(iter);	2✔
272	} else {
273	break;
274	}
275	}	2✔
276	e.index = iter;	2✔
277	}	2✔
278
279	/**
280	* Checks if the specified index has a parent.
281	*/
282	private static boolean hasParent(int idx) {
283	return idx > 0;	2✔
284	}
285
286	/**
287	* Retrieves, for a given child index, its parent index.
288	*/
289
290	private static int parent(int child) {
291	return child / 2;	2✔
292	}
293
294	@Override
295	public boolean ensureAdditionalCapacity(int additionalCapacity) {
296	return ensureCapacity(size + additionalCapacity);	×
297	}
298
299	@Override
300	public void hintNextCapacity(int nextCapacityHint) {
301	entries.hintNextCapacity(nextCapacityHint);	×
302	}	×
303
304	@Override
305	public void quickClear() {
306	size = 0;	2✔
307	}	2✔
308
309	@SuppressWarnings("nullness") // setting 'null' is fine, when (according to JavaDoc) calling quickClear() first
310	@Override
311	public void deepClear() {
312	quickClear();	2✔
313	entries.setAll(null);	2✔
314	}	2✔
315
316	@Override
317	public boolean offer(E e) {
318	add(e);	2✔
319	return true;	2✔
320	}
321
322	@Override
323	public @Nullable E poll() {
324	if (size > 0) {	2✔
325	return extractMin();	2✔
326	}
UNCOV 327	return null;	×
328	}
329
330	@Override
331	public E element() {
UNCOV 332	return peekMin();	×
333	}
334
335	@Override
336	public E peekMin() {
337	if (size <= 0) {	2✔
338	throw new NoSuchElementException();	2✔
339	}
340	return entries.array[0].element;	2✔
341	}
342
343	@SuppressWarnings("nullness") // setting 'null' is fine, because we also decrease the size
344	@Override
345	public E extractMin() {
346	if (size <= 0) {	2✔
UNCOV 347	throw new NoSuchElementException();	×
348	}
349	E min = entries.array[0].element;	2✔
350	entries.array[0] = entries.array[--size];	2✔
351	entries.array[size] = null;	2✔
352
353	if (size > 0) {	2✔
354	downHeap(0);	2✔
355	}
356
357	return min;	2✔
358	}
359
360	@Override
361	public @Nullable E peek() {
362	if (size > 0) {	2✔
363	return peekMin();	2✔
364	}
365	return null;	2✔
366	}
367
368	/**
369	* Class for entries in a priority queue. Entry objects are returned by the {@link
370	* SmartDynamicPriorityQueue#referencedAdd(Object)} method and are passed to the {@link
371	* SmartDynamicPriorityQueue#keyChanged(ElementReference)} method. The usage of entry objects eliminates the
372	* necessity of an extra element to index mapping.
373	*
374	* @param <E>
375	* element class.
376	*/
377	private static final class Reference<E> implements ElementReference {
378
379	private int index;
380	private E element;
381
382	/**
383	* Constructor.
384	*
385	* @param index
386	* the index of the entry inside the queue.
387	* @param element
388	* the element stored in this entry.
389	*/
390	Reference(int index, E element) {	2✔
391	this.element = element;	2✔
392	this.index = index;	2✔
393	}	2✔
394	}
395
396	private class ReferenceIterator implements Iterator<ElementReference> {	2✔
397
398	private int current;
399
400	@Override
401	public boolean hasNext() {
402	return current < size;	2✔
403	}
404
405	@Override
406	public ElementReference next() {
407	if (current >= size) {	2✔
408	throw new NoSuchElementException();	2✔
409	}
410	return entries.array[current++];	2✔
411	}
412
413	@Override
414	public void remove() {
415	BinaryHeap.this.remove(--current);	2✔
416	}	2✔
417	}
418
419	}

LearnLib / automatalib / 12459117572

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