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

90.0

/commons/smartcollections/src/main/java/net/automatalib/common/smartcollection/BinaryHeap.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.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.ArrayStorage;
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 ArrayStorage<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.set(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 ArrayStorage<>(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.get(idx);

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

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

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

            entries.set(cidx, e);
            entries.set(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.set(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.get(idx);

        int iter = idx;
        while (hasParent(iter)) {
            int pidx = parent(iter);
            Reference<E> p = entries.set(pidx, e);
            entries.set(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.get(idx);

        int iter = idx;
        while (hasParent(iter)) {
            int pidx = parent(iter);
            Reference<E> p = entries.get(pidx);
            if (compare(e, p) < 0) {
                entries.set(pidx, e);
                entries.set(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.ensureCapacity(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.get(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.get(0).element;
        entries.set(0, entries.get(--size));
        entries.set(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 final 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.get(current++);
        }

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

}

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.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.ArrayStorage;
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 ArrayStorage<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.set(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 ArrayStorage<>(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.get(idx);	2✔
67
68	int iter = idx;	2✔
69	while (hasChildren(iter)) {	2✔
70	int cidx = leftChild(iter);	2✔
71	Reference<E> c = entries.get(cidx);	2✔
72
73	if (hasRightChild(iter)) {	2✔
74	int rcidx = rightChild(iter);	2✔
75	Reference<E> rc = entries.get(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.set(cidx, e);	2✔
87	entries.set(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.set(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.get(idx);	2✔
217
218	int iter = idx;	2✔
219	while (hasParent(iter)) {	2✔
220	int pidx = parent(iter);	2✔
221	Reference<E> p = entries.set(pidx, e);	2✔
222	entries.set(iter, p);	2✔
223	p.index = iter;	2✔
224	iter = parent(iter);	2✔
225	}	2✔
226	e.index = iter;	2✔
227	}	2✔
228
229	@Override
230	public Iterator<ElementReference> referenceIterator() {
231	return new ReferenceIterator();	2✔
232	}
233
234	@Override
235	public void replace(ElementReference ref, E newElement) {
236	Reference<E> heapRef = asHeapRef(ref);	2✔
237	heapRef.element = newElement;	2✔
238	keyChanged(ref);	2✔
239	}	2✔
240
241	@Override
242	public void keyChanged(ElementReference ref) {
243	keyChanged(asHeapRef(ref).index);	2✔
244	}	2✔
245
246	public void keyChanged(int index) {
247	upHeap(index);	2✔
248	downHeap(index);	2✔
249	}	2✔
250
251	@Override
252	public boolean ensureCapacity(int minCapacity) {
253	return entries.ensureCapacity(minCapacity);	2✔
254	}
255
256	/**
257	* Move an element upwards inside the heap, until it has a parent with a key less or equal to its own.
258	*/
259	private void upHeap(int idx) {
260	Reference<E> e = entries.get(idx);	2✔
261
262	int iter = idx;	2✔
263	while (hasParent(iter)) {	2✔
264	int pidx = parent(iter);	2✔
265	Reference<E> p = entries.get(pidx);	2✔
266	if (compare(e, p) < 0) {	2✔
267	entries.set(pidx, e);	2✔
268	entries.set(iter, p);	2✔
269	p.index = iter;	2✔
270	iter = parent(iter);	2✔
271	} else {
272	break;
273	}
274	}	2✔
275	e.index = iter;	2✔
276	}	2✔
277
278	/**
279	* Checks if the specified index has a parent.
280	*/
281	private static boolean hasParent(int idx) {
282	return idx > 0;	2✔
283	}
284
285	/**
286	* Retrieves, for a given child index, its parent index.
287	*/
288
289	private static int parent(int child) {
290	return child / 2;	2✔
291	}
292
293	@Override
294	public boolean ensureAdditionalCapacity(int additionalCapacity) {
295	return ensureCapacity(size + additionalCapacity);	×
296	}
297
298	@Override
299	public void hintNextCapacity(int nextCapacityHint) {
300	entries.ensureCapacity(nextCapacityHint);	×
301	}	×
302
303	@Override
304	public void quickClear() {
305	size = 0;	2✔
306	}	2✔
307
308	@SuppressWarnings("nullness") // setting 'null' is fine, when (according to JavaDoc) calling quickClear() first
309	@Override
310	public void deepClear() {
311	quickClear();	2✔
312	entries.setAll(null);	2✔
313	}	2✔
314
315	@Override
316	public boolean offer(E e) {
317	add(e);	2✔
318	return true;	2✔
319	}
320
321	@Override
322	public @Nullable E poll() {
323	if (size > 0) {	2✔
324	return extractMin();	2✔
325	}
326	return null;	×
327	}
328
329	@Override
330	public E element() {
331	return peekMin();	×
332	}
333
334	@Override
335	public E peekMin() {
336	if (size <= 0) {	2✔
337	throw new NoSuchElementException();	2✔
338	}
339	return entries.get(0).element;	2✔
340	}
341
342	@SuppressWarnings("nullness") // setting 'null' is fine, because we also decrease the size
343	@Override
344	public E extractMin() {
345	if (size <= 0) {	2✔
346	throw new NoSuchElementException();	×
347	}
348	E min = entries.get(0).element;	2✔
349	entries.set(0, entries.get(--size));	2✔
350	entries.set(size, null);	2✔
351
352	if (size > 0) {	2✔
353	downHeap(0);	2✔
354	}
355
356	return min;	2✔
357	}
358
359	@Override
360	public @Nullable E peek() {
361	if (size > 0) {	2✔
362	return peekMin();	2✔
363	}
364	return null;	2✔
365	}
366
367	/**
368	* Class for entries in a priority queue. Entry objects are returned by the {@link
369	* SmartDynamicPriorityQueue#referencedAdd(Object)} method and are passed to the {@link
370	* SmartDynamicPriorityQueue#keyChanged(ElementReference)} method. The usage of entry objects eliminates the
371	* necessity of an extra element to index mapping.
372	*
373	* @param <E>
374	* element class.
375	*/
376	private static final class Reference<E> implements ElementReference {
377
378	private int index;
379	private E element;
380
381	/**
382	* Constructor.
383	*
384	* @param index
385	* the index of the entry inside the queue.
386	* @param element
387	* the element stored in this entry.
388	*/
389	Reference(int index, E element) {	2✔
390	this.element = element;	2✔
391	this.index = index;	2✔
392	}	2✔
393	}
394
395	private final class ReferenceIterator implements Iterator<ElementReference> {	2✔
396
397	private int current;
398
399	@Override
400	public boolean hasNext() {
401	return current < size;	2✔
402	}
403
404	@Override
405	public ElementReference next() {
406	if (current >= size) {	2✔
407	throw new NoSuchElementException();	2✔
408	}
409	return entries.get(current++);	2✔
410	}
411
412	@Override
413	public void remove() {
414	BinaryHeap.this.remove(--current);	2✔
415	}	2✔
416	}
417
418	}

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