11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the License 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or implied. See the License for the specific language governing permissions and limitations under 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Preconditions; 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.ArrayDeque; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.Deque; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.PriorityQueue; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Queue; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ArrayBlockingQueue; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.BlockingQueue; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.ConcurrentLinkedQueue; 283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.concurrent.LinkedBlockingDeque; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.LinkedBlockingQueue; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.PriorityBlockingQueue; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.SynchronousQueue; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.concurrent.TimeUnit; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Static utility methods pertaining to {@link Queue} and {@link Deque} instances. 367dd252788645e940eada959bdde927426e2531c9Paul Duffin * Also see this class's counterparts {@link Lists}, {@link Sets}, and {@link Maps}. 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Kurt Alfred Kluever 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class Queues { 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Queues() {} 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // ArrayBlockingQueue 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code ArrayBlockingQueue} with the given (fixed) capacity 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * and nonfair access policy. 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ArrayBlockingQueue<E> newArrayBlockingQueue(int capacity) { 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ArrayBlockingQueue<E>(capacity); 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin 543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // ArrayDeque 553ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 563ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 573ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an empty {@code ArrayDeque}. 583ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 593ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 12.0 603ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 613ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> ArrayDeque<E> newArrayDeque() { 623ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ArrayDeque<E>(); 633ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 643ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 653ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an {@code ArrayDeque} containing the elements of the specified iterable, 673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in the order they are returned by the iterable's iterator. 683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 12.0 703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> ArrayDeque<E> newArrayDeque(Iterable<? extends E> elements) { 723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (elements instanceof Collection) { 733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new ArrayDeque<E>(Collections2.cast(elements)); 743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin ArrayDeque<E> deque = new ArrayDeque<E>(); 763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Iterables.addAll(deque, elements); 773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return deque; 783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // ConcurrentLinkedQueue 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code ConcurrentLinkedQueue}. 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ConcurrentLinkedQueue<E> newConcurrentLinkedQueue() { 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ConcurrentLinkedQueue<E>(); 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code ConcurrentLinkedQueue} containing the elements of the specified iterable, 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * in the order they are returned by the iterable's iterator. 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> ConcurrentLinkedQueue<E> newConcurrentLinkedQueue( 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends E> elements) { 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Collection) { 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ConcurrentLinkedQueue<E>(Collections2.cast(elements)); 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ConcurrentLinkedQueue<E> queue = new ConcurrentLinkedQueue<E>(); 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(queue, elements); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return queue; 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin // LinkedBlockingDeque 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an empty {@code LinkedBlockingDeque} with a capacity of {@link Integer#MAX_VALUE}. 1073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 12.0 1093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque() { 1113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new LinkedBlockingDeque<E>(); 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates an empty {@code LinkedBlockingDeque} with the given (fixed) capacity. 1163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @throws IllegalArgumentException if {@code capacity} is less than 1 1183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 12.0 1193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque(int capacity) { 1213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new LinkedBlockingDeque<E>(capacity); 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Creates a {@code LinkedBlockingDeque} with a capacity of {@link Integer#MAX_VALUE}, 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * containing the elements of the specified iterable, 1273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * in the order they are returned by the iterable's iterator. 1283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 12.0 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> LinkedBlockingDeque<E> newLinkedBlockingDeque(Iterable<? extends E> elements) { 1323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (elements instanceof Collection) { 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new LinkedBlockingDeque<E>(Collections2.cast(elements)); 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin LinkedBlockingDeque<E> deque = new LinkedBlockingDeque<E>(); 1363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin Iterables.addAll(deque, elements); 1373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return deque; 1383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // LinkedBlockingQueue 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}. 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue() { 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LinkedBlockingQueue<E>(); 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code LinkedBlockingQueue} with the given (fixed) capacity. 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code capacity} is less than 1 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue(int capacity) { 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LinkedBlockingQueue<E>(capacity); 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}, 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * containing the elements of the specified iterable, 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * in the order they are returned by the iterable's iterator. 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param elements the elements that the queue should contain, in order 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return a new {@code LinkedBlockingQueue} containing those elements 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> LinkedBlockingQueue<E> newLinkedBlockingQueue(Iterable<? extends E> elements) { 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Collection) { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LinkedBlockingQueue<E>(Collections2.cast(elements)); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LinkedBlockingQueue<E> queue = new LinkedBlockingQueue<E>(); 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(queue, elements); 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return queue; 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // LinkedList: see {@link com.google.common.collect.Lists} 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // PriorityBlockingQueue 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code PriorityBlockingQueue} with the ordering given by its 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements' natural ordering. 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 (requires that {@code E} be {@code Comparable} since 15.0). 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable> PriorityBlockingQueue<E> newPriorityBlockingQueue() { 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new PriorityBlockingQueue<E>(); 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code PriorityBlockingQueue} containing the given elements. 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <b>Note:</b> If the specified iterable is a {@code SortedSet} or a {@code PriorityQueue}, 1930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * this priority queue will be ordered according to the same ordering. 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 (requires that {@code E} be {@code Comparable} since 15.0). 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable> PriorityBlockingQueue<E> newPriorityBlockingQueue( 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends E> elements) { 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Collection) { 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new PriorityBlockingQueue<E>(Collections2.cast(elements)); 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert PriorityBlockingQueue<E> queue = new PriorityBlockingQueue<E>(); 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(queue, elements); 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return queue; 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // PriorityQueue 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code PriorityQueue} with the ordering given by its 2110888a09821a98ac0680fad765217302858e70fa4Paul Duffin * elements' natural ordering. 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 (requires that {@code E} be {@code Comparable} since 15.0). 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable> PriorityQueue<E> newPriorityQueue() { 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new PriorityQueue<E>(); 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code PriorityQueue} containing the given elements. 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <b>Note:</b> If the specified iterable is a {@code SortedSet} or a {@code PriorityQueue}, 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * this priority queue will be ordered according to the same ordering. 2240888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @since 11.0 (requires that {@code E} be {@code Comparable} since 15.0). 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E extends Comparable> PriorityQueue<E> newPriorityQueue( 2280888a09821a98ac0680fad765217302858e70fa4Paul Duffin Iterable<? extends E> elements) { 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Collection) { 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new PriorityQueue<E>(Collections2.cast(elements)); 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert PriorityQueue<E> queue = new PriorityQueue<E>(); 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterables.addAll(queue, elements); 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return queue; 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // SynchronousQueue 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates an empty {@code SynchronousQueue} with nonfair access policy. 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> SynchronousQueue<E> newSynchronousQueue() { 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new SynchronousQueue<E>(); 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 245dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Drains the queue as {@link BlockingQueue#drainTo(Collection, int)}, but if the requested 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code numElements} elements are not available, it will wait for them up to the specified 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * timeout. 2500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param q the blocking queue to be drained 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param buffer where to add the transferred elements 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param numElements the number of elements to be waited for 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param timeout how long to wait before giving up, in units of {@code unit} 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param unit a {@code TimeUnit} determining how to interpret the timeout parameter 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the number of elements transferred 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws InterruptedException if interrupted while waiting 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> int drain(BlockingQueue<E> q, Collection<? super E> buffer, int numElements, 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long timeout, TimeUnit unit) throws InterruptedException { 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkNotNull(buffer); 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This code performs one System.nanoTime() more than necessary, and in return, the time to 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * execute Queue#drainTo is not added *on top* of waiting for the timeout (which could make 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the timeout arbitrarily inaccurate, given a queue that is slow to drain). 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long deadline = System.nanoTime() + unit.toNanos(timeout); 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int added = 0; 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (added < numElements) { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // we could rely solely on #poll, but #drainTo might be more efficient when there are multiple 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // elements already available (e.g. LinkedBlockingQueue#drainTo locks only once) 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert added += q.drainTo(buffer, numElements - added); 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (added < numElements) { // not enough elements immediately available; will have to poll 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E e = q.poll(deadline - System.nanoTime(), TimeUnit.NANOSECONDS); 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (e == null) { 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; // we already waited enough, and there are no more elements in sight 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert buffer.add(e); 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert added++; 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return added; 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2850888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin * Drains the queue as {@linkplain #drain(BlockingQueue, Collection, int, long, TimeUnit)}, 2887dd252788645e940eada959bdde927426e2531c9Paul Duffin * but with a different behavior in case it is interrupted while waiting. In that case, the 2897dd252788645e940eada959bdde927426e2531c9Paul Duffin * operation will continue as usual, and in the end the thread's interruption status will be set 2907dd252788645e940eada959bdde927426e2531c9Paul Duffin * (no {@code InterruptedException} is thrown). 2917dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param q the blocking queue to be drained 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param buffer where to add the transferred elements 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param numElements the number of elements to be waited for 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param timeout how long to wait before giving up, in units of {@code unit} 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param unit a {@code TimeUnit} determining how to interpret the timeout parameter 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the number of elements transferred 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2997dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> int drainUninterruptibly(BlockingQueue<E> q, Collection<? super E> buffer, 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int numElements, long timeout, TimeUnit unit) { 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkNotNull(buffer); 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long deadline = System.nanoTime() + unit.toNanos(timeout); 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int added = 0; 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean interrupted = false; 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (added < numElements) { 3087dd252788645e940eada959bdde927426e2531c9Paul Duffin // we could rely solely on #poll, but #drainTo might be more efficient when there are 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // multiple elements already available (e.g. LinkedBlockingQueue#drainTo locks only once) 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert added += q.drainTo(buffer, numElements - added); 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (added < numElements) { // not enough elements immediately available; will have to poll 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E e; // written exactly once, by a successful (uninterrupted) invocation of #poll 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert e = q.poll(deadline - System.nanoTime(), TimeUnit.NANOSECONDS); 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (InterruptedException ex) { 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert interrupted = true; // note interruption and retry 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (e == null) { 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; // we already waited enough, and there are no more elements in sight 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert buffer.add(e); 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert added++; 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } finally { 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (interrupted) { 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Thread.currentThread().interrupt(); 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return added; 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3357dd252788645e940eada959bdde927426e2531c9Paul Duffin 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3377dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a synchronized (thread-safe) queue backed by the specified queue. In order to 3387dd252788645e940eada959bdde927426e2531c9Paul Duffin * guarantee serial access, it is critical that <b>all</b> access to the backing queue is 3397dd252788645e940eada959bdde927426e2531c9Paul Duffin * accomplished through the returned queue. 3407dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>It is imperative that the user manually synchronize on the returned queue when accessing 3427dd252788645e940eada959bdde927426e2531c9Paul Duffin * the queue's iterator: <pre> {@code 3437dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Queue<E> queue = Queues.synchronizedQueue(MinMaxPriorityQueue.<E>create()); 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin * ... 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin * queue.add(element); // Needn't be in synchronized block 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin * ... 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin * synchronized (queue) { // Must synchronize on queue! 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin * Iterator<E> i = queue.iterator(); // Must be in synchronized block 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin * while (i.hasNext()) { 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin * foo(i.next()); 3527dd252788645e940eada959bdde927426e2531c9Paul Duffin * } 3537dd252788645e940eada959bdde927426e2531c9Paul Duffin * }}</pre> 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>Failure to follow this advice may result in non-deterministic behavior. 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>The returned queue will be serializable if the specified queue is serializable. 3587dd252788645e940eada959bdde927426e2531c9Paul Duffin * 3597dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param queue the queue to be wrapped in a synchronized view 3607dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a synchronized view of the specified queue 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 14.0 3627dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3637dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <E> Queue<E> synchronizedQueue(Queue<E> queue) { 3647dd252788645e940eada959bdde927426e2531c9Paul Duffin return Synchronized.queue(queue, null); 3657dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3663ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 3673ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 3683ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Returns a synchronized (thread-safe) deque backed by the specified deque. In order to 3693ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * guarantee serial access, it is critical that <b>all</b> access to the backing deque is 3703ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * accomplished through the returned deque. 3713ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 3723ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>It is imperative that the user manually synchronize on the returned deque when accessing 3733ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * any of the deque's iterators: <pre> {@code 3743ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 3753ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Deque<E> deque = Queues.synchronizedDeque(Queues.<E>newArrayDeque()); 3763ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ... 3773ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * deque.add(element); // Needn't be in synchronized block 3783ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ... 3793ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * synchronized (deque) { // Must synchronize on deque! 3803ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Iterator<E> i = deque.iterator(); // Must be in synchronized block 3813ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * while (i.hasNext()) { 3823ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * foo(i.next()); 3833ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * } 3843ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * }}</pre> 3853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 3863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>Failure to follow this advice may result in non-deterministic behavior. 3873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 3883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * <p>The returned deque will be serializable if the specified deque is serializable. 3893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * 3903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @param deque the deque to be wrapped in a synchronized view 3913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @return a synchronized view of the specified deque 3923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * @since 15.0 3933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 3943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public static <E> Deque<E> synchronizedDeque(Deque<E> deque) { 3953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return Synchronized.deque(deque, null); 3963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 3971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 398