1 /*
2 * Copyright (c) 2003, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Consumer;
29 import java.util.function.Predicate;
30 import jdk.internal.access.SharedSecrets;
31
32 /**
33 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
34 * The elements of the priority queue are ordered according to their
35 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
36 * provided at queue construction time, depending on which constructor is
37 * used. A priority queue does not permit {@code null} elements.
38 * A priority queue relying on natural ordering also does not permit
39 * insertion of non-comparable objects (doing so may result in
40 * {@code ClassCastException}).
41 *
42 * <p>The <em>head</em> of this queue is the <em>least</em> element
43 * with respect to the specified ordering. If multiple elements are
44 * tied for least value, the head is one of those elements -- ties are
45 * broken arbitrarily. The queue retrieval operations {@code poll},
46 * {@code remove}, {@code peek}, and {@code element} access the
47 * element at the head of the queue.
48 *
49 * <p>A priority queue is unbounded, but has an internal
50 * <i>capacity</i> governing the size of an array used to store the
265 es = Arrays.copyOf(es, len, Object[].class);
266 if (len == 1 || this.comparator != null)
267 for (Object e : es)
268 if (e == null)
269 throw new NullPointerException();
270 this.queue = ensureNonEmpty(es);
271 this.size = len;
272 }
273
274 /**
275 * Initializes queue array with elements from the given Collection.
276 *
277 * @param c the collection
278 */
279 private void initFromCollection(Collection<? extends E> c) {
280 initElementsFromCollection(c);
281 heapify();
282 }
283
284 /**
285 * The maximum size of array to allocate.
286 * Some VMs reserve some header words in an array.
287 * Attempts to allocate larger arrays may result in
288 * OutOfMemoryError: Requested array size exceeds VM limit
289 */
290 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
291
292 /**
293 * Increases the capacity of the array.
294 *
295 * @param minCapacity the desired minimum capacity
296 */
297 private void grow(int minCapacity) {
298 int oldCapacity = queue.length;
299 // Double size if small; else grow by 50%
300 int newCapacity = oldCapacity + ((oldCapacity < 64) ?
301 (oldCapacity + 2) :
302 (oldCapacity >> 1));
303 // overflow-conscious code
304 if (newCapacity - MAX_ARRAY_SIZE > 0)
305 newCapacity = hugeCapacity(minCapacity);
306 queue = Arrays.copyOf(queue, newCapacity);
307 }
308
309 private static int hugeCapacity(int minCapacity) {
310 if (minCapacity < 0) // overflow
311 throw new OutOfMemoryError();
312 return (minCapacity > MAX_ARRAY_SIZE) ?
313 Integer.MAX_VALUE :
314 MAX_ARRAY_SIZE;
315 }
316
317 /**
318 * Inserts the specified element into this priority queue.
319 *
320 * @return {@code true} (as specified by {@link Collection#add})
321 * @throws ClassCastException if the specified element cannot be
322 * compared with elements currently in this priority queue
323 * according to the priority queue's ordering
324 * @throws NullPointerException if the specified element is null
325 */
326 public boolean add(E e) {
327 return offer(e);
328 }
329
330 /**
331 * Inserts the specified element into this priority queue.
332 *
333 * @return {@code true} (as specified by {@link Queue#offer})
334 * @throws ClassCastException if the specified element cannot be
|
1 /*
2 * Copyright (c) 2003, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.util.function.Consumer;
29 import java.util.function.Predicate;
30 import jdk.internal.access.SharedSecrets;
31 import jdk.internal.util.ArraysSupport;
32
33 /**
34 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
35 * The elements of the priority queue are ordered according to their
36 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
37 * provided at queue construction time, depending on which constructor is
38 * used. A priority queue does not permit {@code null} elements.
39 * A priority queue relying on natural ordering also does not permit
40 * insertion of non-comparable objects (doing so may result in
41 * {@code ClassCastException}).
42 *
43 * <p>The <em>head</em> of this queue is the <em>least</em> element
44 * with respect to the specified ordering. If multiple elements are
45 * tied for least value, the head is one of those elements -- ties are
46 * broken arbitrarily. The queue retrieval operations {@code poll},
47 * {@code remove}, {@code peek}, and {@code element} access the
48 * element at the head of the queue.
49 *
50 * <p>A priority queue is unbounded, but has an internal
51 * <i>capacity</i> governing the size of an array used to store the
266 es = Arrays.copyOf(es, len, Object[].class);
267 if (len == 1 || this.comparator != null)
268 for (Object e : es)
269 if (e == null)
270 throw new NullPointerException();
271 this.queue = ensureNonEmpty(es);
272 this.size = len;
273 }
274
275 /**
276 * Initializes queue array with elements from the given Collection.
277 *
278 * @param c the collection
279 */
280 private void initFromCollection(Collection<? extends E> c) {
281 initElementsFromCollection(c);
282 heapify();
283 }
284
285 /**
286 * Increases the capacity of the array.
287 *
288 * @param minCapacity the desired minimum capacity
289 */
290 private void grow(int minCapacity) {
291 int oldCapacity = queue.length;
292 // Double size if small; else grow by 50%
293 int newCapacity = ArraysSupport.calcLength(oldCapacity,
294 minCapacity - oldCapacity, /* minimum growth */
295 oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
296 /* preferred growth */);
297 queue = Arrays.copyOf(queue, newCapacity);
298 }
299
300 /**
301 * Inserts the specified element into this priority queue.
302 *
303 * @return {@code true} (as specified by {@link Collection#add})
304 * @throws ClassCastException if the specified element cannot be
305 * compared with elements currently in this priority queue
306 * according to the priority queue's ordering
307 * @throws NullPointerException if the specified element is null
308 */
309 public boolean add(E e) {
310 return offer(e);
311 }
312
313 /**
314 * Inserts the specified element into this priority queue.
315 *
316 * @return {@code true} (as specified by {@link Queue#offer})
317 * @throws ClassCastException if the specified element cannot be
|