1/* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7package java.util.concurrent; 8 9import java.util.Deque; 10import java.util.Iterator; 11import java.util.NoSuchElementException; 12 13// BEGIN android-note 14// fixed framework docs link to "Collection#optional" 15// END android-note 16 17/** 18 * A {@link Deque} that additionally supports blocking operations that wait 19 * for the deque to become non-empty when retrieving an element, and wait for 20 * space to become available in the deque when storing an element. 21 * 22 * <p>{@code BlockingDeque} methods come in four forms, with different ways 23 * of handling operations that cannot be satisfied immediately, but may be 24 * satisfied at some point in the future: 25 * one throws an exception, the second returns a special value (either 26 * {@code null} or {@code false}, depending on the operation), the third 27 * blocks the current thread indefinitely until the operation can succeed, 28 * and the fourth blocks for only a given maximum time limit before giving 29 * up. These methods are summarized in the following table: 30 * 31 * <table BORDER CELLPADDING=3 CELLSPACING=1> 32 * <caption>Summary of BlockingDeque methods</caption> 33 * <tr> 34 * <td ALIGN=CENTER COLSPAN = 5> <b>First Element (Head)</b></td> 35 * </tr> 36 * <tr> 37 * <td></td> 38 * <td ALIGN=CENTER><em>Throws exception</em></td> 39 * <td ALIGN=CENTER><em>Special value</em></td> 40 * <td ALIGN=CENTER><em>Blocks</em></td> 41 * <td ALIGN=CENTER><em>Times out</em></td> 42 * </tr> 43 * <tr> 44 * <td><b>Insert</b></td> 45 * <td>{@link #addFirst addFirst(e)}</td> 46 * <td>{@link #offerFirst(Object) offerFirst(e)}</td> 47 * <td>{@link #putFirst putFirst(e)}</td> 48 * <td>{@link #offerFirst(Object, long, TimeUnit) offerFirst(e, time, unit)}</td> 49 * </tr> 50 * <tr> 51 * <td><b>Remove</b></td> 52 * <td>{@link #removeFirst removeFirst()}</td> 53 * <td>{@link #pollFirst pollFirst()}</td> 54 * <td>{@link #takeFirst takeFirst()}</td> 55 * <td>{@link #pollFirst(long, TimeUnit) pollFirst(time, unit)}</td> 56 * </tr> 57 * <tr> 58 * <td><b>Examine</b></td> 59 * <td>{@link #getFirst getFirst()}</td> 60 * <td>{@link #peekFirst peekFirst()}</td> 61 * <td><em>not applicable</em></td> 62 * <td><em>not applicable</em></td> 63 * </tr> 64 * <tr> 65 * <td ALIGN=CENTER COLSPAN = 5> <b>Last Element (Tail)</b></td> 66 * </tr> 67 * <tr> 68 * <td></td> 69 * <td ALIGN=CENTER><em>Throws exception</em></td> 70 * <td ALIGN=CENTER><em>Special value</em></td> 71 * <td ALIGN=CENTER><em>Blocks</em></td> 72 * <td ALIGN=CENTER><em>Times out</em></td> 73 * </tr> 74 * <tr> 75 * <td><b>Insert</b></td> 76 * <td>{@link #addLast addLast(e)}</td> 77 * <td>{@link #offerLast(Object) offerLast(e)}</td> 78 * <td>{@link #putLast putLast(e)}</td> 79 * <td>{@link #offerLast(Object, long, TimeUnit) offerLast(e, time, unit)}</td> 80 * </tr> 81 * <tr> 82 * <td><b>Remove</b></td> 83 * <td>{@link #removeLast() removeLast()}</td> 84 * <td>{@link #pollLast() pollLast()}</td> 85 * <td>{@link #takeLast takeLast()}</td> 86 * <td>{@link #pollLast(long, TimeUnit) pollLast(time, unit)}</td> 87 * </tr> 88 * <tr> 89 * <td><b>Examine</b></td> 90 * <td>{@link #getLast getLast()}</td> 91 * <td>{@link #peekLast peekLast()}</td> 92 * <td><em>not applicable</em></td> 93 * <td><em>not applicable</em></td> 94 * </tr> 95 * </table> 96 * 97 * <p>Like any {@link BlockingQueue}, a {@code BlockingDeque} is thread safe, 98 * does not permit null elements, and may (or may not) be 99 * capacity-constrained. 100 * 101 * <p>A {@code BlockingDeque} implementation may be used directly as a FIFO 102 * {@code BlockingQueue}. The methods inherited from the 103 * {@code BlockingQueue} interface are precisely equivalent to 104 * {@code BlockingDeque} methods as indicated in the following table: 105 * 106 * <table BORDER CELLPADDING=3 CELLSPACING=1> 107 * <caption>Comparison of BlockingQueue and BlockingDeque methods</caption> 108 * <tr> 109 * <td ALIGN=CENTER> <b>{@code BlockingQueue} Method</b></td> 110 * <td ALIGN=CENTER> <b>Equivalent {@code BlockingDeque} Method</b></td> 111 * </tr> 112 * <tr> 113 * <td ALIGN=CENTER COLSPAN = 2> <b>Insert</b></td> 114 * </tr> 115 * <tr> 116 * <td>{@link #add(Object) add(e)}</td> 117 * <td>{@link #addLast(Object) addLast(e)}</td> 118 * </tr> 119 * <tr> 120 * <td>{@link #offer(Object) offer(e)}</td> 121 * <td>{@link #offerLast(Object) offerLast(e)}</td> 122 * </tr> 123 * <tr> 124 * <td>{@link #put(Object) put(e)}</td> 125 * <td>{@link #putLast(Object) putLast(e)}</td> 126 * </tr> 127 * <tr> 128 * <td>{@link #offer(Object, long, TimeUnit) offer(e, time, unit)}</td> 129 * <td>{@link #offerLast(Object, long, TimeUnit) offerLast(e, time, unit)}</td> 130 * </tr> 131 * <tr> 132 * <td ALIGN=CENTER COLSPAN = 2> <b>Remove</b></td> 133 * </tr> 134 * <tr> 135 * <td>{@link #remove() remove()}</td> 136 * <td>{@link #removeFirst() removeFirst()}</td> 137 * </tr> 138 * <tr> 139 * <td>{@link #poll() poll()}</td> 140 * <td>{@link #pollFirst() pollFirst()}</td> 141 * </tr> 142 * <tr> 143 * <td>{@link #take() take()}</td> 144 * <td>{@link #takeFirst() takeFirst()}</td> 145 * </tr> 146 * <tr> 147 * <td>{@link #poll(long, TimeUnit) poll(time, unit)}</td> 148 * <td>{@link #pollFirst(long, TimeUnit) pollFirst(time, unit)}</td> 149 * </tr> 150 * <tr> 151 * <td ALIGN=CENTER COLSPAN = 2> <b>Examine</b></td> 152 * </tr> 153 * <tr> 154 * <td>{@link #element() element()}</td> 155 * <td>{@link #getFirst() getFirst()}</td> 156 * </tr> 157 * <tr> 158 * <td>{@link #peek() peek()}</td> 159 * <td>{@link #peekFirst() peekFirst()}</td> 160 * </tr> 161 * </table> 162 * 163 * <p>Memory consistency effects: As with other concurrent 164 * collections, actions in a thread prior to placing an object into a 165 * {@code BlockingDeque} 166 * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> 167 * actions subsequent to the access or removal of that element from 168 * the {@code BlockingDeque} in another thread. 169 * 170 * <p>This interface is a member of the 171 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 172 * Java Collections Framework</a>. 173 * 174 * @since 1.6 175 * @author Doug Lea 176 * @param <E> the type of elements held in this deque 177 */ 178public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> { 179 /* 180 * We have "diamond" multiple interface inheritance here, and that 181 * introduces ambiguities. Methods might end up with different 182 * specs depending on the branch chosen by javadoc. Thus a lot of 183 * methods specs here are copied from superinterfaces. 184 */ 185 186 /** 187 * Inserts the specified element at the front of this deque if it is 188 * possible to do so immediately without violating capacity restrictions, 189 * throwing an {@code IllegalStateException} if no space is currently 190 * available. When using a capacity-restricted deque, it is generally 191 * preferable to use {@link #offerFirst(Object) offerFirst}. 192 * 193 * @param e the element to add 194 * @throws IllegalStateException {@inheritDoc} 195 * @throws ClassCastException {@inheritDoc} 196 * @throws NullPointerException if the specified element is null 197 * @throws IllegalArgumentException {@inheritDoc} 198 */ 199 void addFirst(E e); 200 201 /** 202 * Inserts the specified element at the end of this deque if it is 203 * possible to do so immediately without violating capacity restrictions, 204 * throwing an {@code IllegalStateException} if no space is currently 205 * available. When using a capacity-restricted deque, it is generally 206 * preferable to use {@link #offerLast(Object) offerLast}. 207 * 208 * @param e the element to add 209 * @throws IllegalStateException {@inheritDoc} 210 * @throws ClassCastException {@inheritDoc} 211 * @throws NullPointerException if the specified element is null 212 * @throws IllegalArgumentException {@inheritDoc} 213 */ 214 void addLast(E e); 215 216 /** 217 * Inserts the specified element at the front of this deque if it is 218 * possible to do so immediately without violating capacity restrictions, 219 * returning {@code true} upon success and {@code false} if no space is 220 * currently available. 221 * When using a capacity-restricted deque, this method is generally 222 * preferable to the {@link #addFirst(Object) addFirst} method, which can 223 * fail to insert an element only by throwing an exception. 224 * 225 * @param e the element to add 226 * @throws ClassCastException {@inheritDoc} 227 * @throws NullPointerException if the specified element is null 228 * @throws IllegalArgumentException {@inheritDoc} 229 */ 230 boolean offerFirst(E e); 231 232 /** 233 * Inserts the specified element at the end of this deque if it is 234 * possible to do so immediately without violating capacity restrictions, 235 * returning {@code true} upon success and {@code false} if no space is 236 * currently available. 237 * When using a capacity-restricted deque, this method is generally 238 * preferable to the {@link #addLast(Object) addLast} method, which can 239 * fail to insert an element only by throwing an exception. 240 * 241 * @param e the element to add 242 * @throws ClassCastException {@inheritDoc} 243 * @throws NullPointerException if the specified element is null 244 * @throws IllegalArgumentException {@inheritDoc} 245 */ 246 boolean offerLast(E e); 247 248 /** 249 * Inserts the specified element at the front of this deque, 250 * waiting if necessary for space to become available. 251 * 252 * @param e the element to add 253 * @throws InterruptedException if interrupted while waiting 254 * @throws ClassCastException if the class of the specified element 255 * prevents it from being added to this deque 256 * @throws NullPointerException if the specified element is null 257 * @throws IllegalArgumentException if some property of the specified 258 * element prevents it from being added to this deque 259 */ 260 void putFirst(E e) throws InterruptedException; 261 262 /** 263 * Inserts the specified element at the end of this deque, 264 * waiting if necessary for space to become available. 265 * 266 * @param e the element to add 267 * @throws InterruptedException if interrupted while waiting 268 * @throws ClassCastException if the class of the specified element 269 * prevents it from being added to this deque 270 * @throws NullPointerException if the specified element is null 271 * @throws IllegalArgumentException if some property of the specified 272 * element prevents it from being added to this deque 273 */ 274 void putLast(E e) throws InterruptedException; 275 276 /** 277 * Inserts the specified element at the front of this deque, 278 * waiting up to the specified wait time if necessary for space to 279 * become available. 280 * 281 * @param e the element to add 282 * @param timeout how long to wait before giving up, in units of 283 * {@code unit} 284 * @param unit a {@code TimeUnit} determining how to interpret the 285 * {@code timeout} parameter 286 * @return {@code true} if successful, or {@code false} if 287 * the specified waiting time elapses before space is available 288 * @throws InterruptedException if interrupted while waiting 289 * @throws ClassCastException if the class of the specified element 290 * prevents it from being added to this deque 291 * @throws NullPointerException if the specified element is null 292 * @throws IllegalArgumentException if some property of the specified 293 * element prevents it from being added to this deque 294 */ 295 boolean offerFirst(E e, long timeout, TimeUnit unit) 296 throws InterruptedException; 297 298 /** 299 * Inserts the specified element at the end of this deque, 300 * waiting up to the specified wait time if necessary for space to 301 * become available. 302 * 303 * @param e the element to add 304 * @param timeout how long to wait before giving up, in units of 305 * {@code unit} 306 * @param unit a {@code TimeUnit} determining how to interpret the 307 * {@code timeout} parameter 308 * @return {@code true} if successful, or {@code false} if 309 * the specified waiting time elapses before space is available 310 * @throws InterruptedException if interrupted while waiting 311 * @throws ClassCastException if the class of the specified element 312 * prevents it from being added to this deque 313 * @throws NullPointerException if the specified element is null 314 * @throws IllegalArgumentException if some property of the specified 315 * element prevents it from being added to this deque 316 */ 317 boolean offerLast(E e, long timeout, TimeUnit unit) 318 throws InterruptedException; 319 320 /** 321 * Retrieves and removes the first element of this deque, waiting 322 * if necessary until an element becomes available. 323 * 324 * @return the head of this deque 325 * @throws InterruptedException if interrupted while waiting 326 */ 327 E takeFirst() throws InterruptedException; 328 329 /** 330 * Retrieves and removes the last element of this deque, waiting 331 * if necessary until an element becomes available. 332 * 333 * @return the tail of this deque 334 * @throws InterruptedException if interrupted while waiting 335 */ 336 E takeLast() throws InterruptedException; 337 338 /** 339 * Retrieves and removes the first element of this deque, waiting 340 * up to the specified wait time if necessary for an element to 341 * become available. 342 * 343 * @param timeout how long to wait before giving up, in units of 344 * {@code unit} 345 * @param unit a {@code TimeUnit} determining how to interpret the 346 * {@code timeout} parameter 347 * @return the head of this deque, or {@code null} if the specified 348 * waiting time elapses before an element is available 349 * @throws InterruptedException if interrupted while waiting 350 */ 351 E pollFirst(long timeout, TimeUnit unit) 352 throws InterruptedException; 353 354 /** 355 * Retrieves and removes the last element of this deque, waiting 356 * up to the specified wait time if necessary for an element to 357 * become available. 358 * 359 * @param timeout how long to wait before giving up, in units of 360 * {@code unit} 361 * @param unit a {@code TimeUnit} determining how to interpret the 362 * {@code timeout} parameter 363 * @return the tail of this deque, or {@code null} if the specified 364 * waiting time elapses before an element is available 365 * @throws InterruptedException if interrupted while waiting 366 */ 367 E pollLast(long timeout, TimeUnit unit) 368 throws InterruptedException; 369 370 /** 371 * Removes the first occurrence of the specified element from this deque. 372 * If the deque does not contain the element, it is unchanged. 373 * More formally, removes the first element {@code e} such that 374 * {@code o.equals(e)} (if such an element exists). 375 * Returns {@code true} if this deque contained the specified element 376 * (or equivalently, if this deque changed as a result of the call). 377 * 378 * @param o element to be removed from this deque, if present 379 * @return {@code true} if an element was removed as a result of this call 380 * @throws ClassCastException if the class of the specified element 381 * is incompatible with this deque 382 * (<a href="../Collection.html#optional-restrictions">optional</a>) 383 * @throws NullPointerException if the specified element is null 384 * (<a href="../Collection.html#optional-restrictions">optional</a>) 385 */ 386 boolean removeFirstOccurrence(Object o); 387 388 /** 389 * Removes the last occurrence of the specified element from this deque. 390 * If the deque does not contain the element, it is unchanged. 391 * More formally, removes the last element {@code e} such that 392 * {@code o.equals(e)} (if such an element exists). 393 * Returns {@code true} if this deque contained the specified element 394 * (or equivalently, if this deque changed as a result of the call). 395 * 396 * @param o element to be removed from this deque, if present 397 * @return {@code true} if an element was removed as a result of this call 398 * @throws ClassCastException if the class of the specified element 399 * is incompatible with this deque 400 * (<a href="../Collection.html#optional-restrictions">optional</a>) 401 * @throws NullPointerException if the specified element is null 402 * (<a href="../Collection.html#optional-restrictions">optional</a>) 403 */ 404 boolean removeLastOccurrence(Object o); 405 406 // *** BlockingQueue methods *** 407 408 /** 409 * Inserts the specified element into the queue represented by this deque 410 * (in other words, at the tail of this deque) if it is possible to do so 411 * immediately without violating capacity restrictions, returning 412 * {@code true} upon success and throwing an 413 * {@code IllegalStateException} if no space is currently available. 414 * When using a capacity-restricted deque, it is generally preferable to 415 * use {@link #offer(Object) offer}. 416 * 417 * <p>This method is equivalent to {@link #addLast(Object) addLast}. 418 * 419 * @param e the element to add 420 * @throws IllegalStateException {@inheritDoc} 421 * @throws ClassCastException if the class of the specified element 422 * prevents it from being added to this deque 423 * @throws NullPointerException if the specified element is null 424 * @throws IllegalArgumentException if some property of the specified 425 * element prevents it from being added to this deque 426 */ 427 boolean add(E e); 428 429 /** 430 * Inserts the specified element into the queue represented by this deque 431 * (in other words, at the tail of this deque) if it is possible to do so 432 * immediately without violating capacity restrictions, returning 433 * {@code true} upon success and {@code false} if no space is currently 434 * available. When using a capacity-restricted deque, this method is 435 * generally preferable to the {@link #add} method, which can fail to 436 * insert an element only by throwing an exception. 437 * 438 * <p>This method is equivalent to {@link #offerLast(Object) offerLast}. 439 * 440 * @param e the element to add 441 * @throws ClassCastException if the class of the specified element 442 * prevents it from being added to this deque 443 * @throws NullPointerException if the specified element is null 444 * @throws IllegalArgumentException if some property of the specified 445 * element prevents it from being added to this deque 446 */ 447 boolean offer(E e); 448 449 /** 450 * Inserts the specified element into the queue represented by this deque 451 * (in other words, at the tail of this deque), waiting if necessary for 452 * space to become available. 453 * 454 * <p>This method is equivalent to {@link #putLast(Object) putLast}. 455 * 456 * @param e the element to add 457 * @throws InterruptedException {@inheritDoc} 458 * @throws ClassCastException if the class of the specified element 459 * prevents it from being added to this deque 460 * @throws NullPointerException if the specified element is null 461 * @throws IllegalArgumentException if some property of the specified 462 * element prevents it from being added to this deque 463 */ 464 void put(E e) throws InterruptedException; 465 466 /** 467 * Inserts the specified element into the queue represented by this deque 468 * (in other words, at the tail of this deque), waiting up to the 469 * specified wait time if necessary for space to become available. 470 * 471 * <p>This method is equivalent to 472 * {@link #offerLast(Object,long,TimeUnit) offerLast}. 473 * 474 * @param e the element to add 475 * @return {@code true} if the element was added to this deque, else 476 * {@code false} 477 * @throws InterruptedException {@inheritDoc} 478 * @throws ClassCastException if the class of the specified element 479 * prevents it from being added to this deque 480 * @throws NullPointerException if the specified element is null 481 * @throws IllegalArgumentException if some property of the specified 482 * element prevents it from being added to this deque 483 */ 484 boolean offer(E e, long timeout, TimeUnit unit) 485 throws InterruptedException; 486 487 /** 488 * Retrieves and removes the head of the queue represented by this deque 489 * (in other words, the first element of this deque). 490 * This method differs from {@link #poll poll} only in that it 491 * throws an exception if this deque is empty. 492 * 493 * <p>This method is equivalent to {@link #removeFirst() removeFirst}. 494 * 495 * @return the head of the queue represented by this deque 496 * @throws NoSuchElementException if this deque is empty 497 */ 498 E remove(); 499 500 /** 501 * Retrieves and removes the head of the queue represented by this deque 502 * (in other words, the first element of this deque), or returns 503 * {@code null} if this deque is empty. 504 * 505 * <p>This method is equivalent to {@link #pollFirst()}. 506 * 507 * @return the head of this deque, or {@code null} if this deque is empty 508 */ 509 E poll(); 510 511 /** 512 * Retrieves and removes the head of the queue represented by this deque 513 * (in other words, the first element of this deque), waiting if 514 * necessary until an element becomes available. 515 * 516 * <p>This method is equivalent to {@link #takeFirst() takeFirst}. 517 * 518 * @return the head of this deque 519 * @throws InterruptedException if interrupted while waiting 520 */ 521 E take() throws InterruptedException; 522 523 /** 524 * Retrieves and removes the head of the queue represented by this deque 525 * (in other words, the first element of this deque), waiting up to the 526 * specified wait time if necessary for an element to become available. 527 * 528 * <p>This method is equivalent to 529 * {@link #pollFirst(long,TimeUnit) pollFirst}. 530 * 531 * @return the head of this deque, or {@code null} if the 532 * specified waiting time elapses before an element is available 533 * @throws InterruptedException if interrupted while waiting 534 */ 535 E poll(long timeout, TimeUnit unit) 536 throws InterruptedException; 537 538 /** 539 * Retrieves, but does not remove, the head of the queue represented by 540 * this deque (in other words, the first element of this deque). 541 * This method differs from {@link #peek peek} only in that it throws an 542 * exception if this deque is empty. 543 * 544 * <p>This method is equivalent to {@link #getFirst() getFirst}. 545 * 546 * @return the head of this deque 547 * @throws NoSuchElementException if this deque is empty 548 */ 549 E element(); 550 551 /** 552 * Retrieves, but does not remove, the head of the queue represented by 553 * this deque (in other words, the first element of this deque), or 554 * returns {@code null} if this deque is empty. 555 * 556 * <p>This method is equivalent to {@link #peekFirst() peekFirst}. 557 * 558 * @return the head of this deque, or {@code null} if this deque is empty 559 */ 560 E peek(); 561 562 /** 563 * Removes the first occurrence of the specified element from this deque. 564 * If the deque does not contain the element, it is unchanged. 565 * More formally, removes the first element {@code e} such that 566 * {@code o.equals(e)} (if such an element exists). 567 * Returns {@code true} if this deque contained the specified element 568 * (or equivalently, if this deque changed as a result of the call). 569 * 570 * <p>This method is equivalent to 571 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. 572 * 573 * @param o element to be removed from this deque, if present 574 * @return {@code true} if this deque changed as a result of the call 575 * @throws ClassCastException if the class of the specified element 576 * is incompatible with this deque 577 * (<a href="../Collection.html#optional-restrictions">optional</a>) 578 * @throws NullPointerException if the specified element is null 579 * (<a href="../Collection.html#optional-restrictions">optional</a>) 580 */ 581 boolean remove(Object o); 582 583 /** 584 * Returns {@code true} if this deque contains the specified element. 585 * More formally, returns {@code true} if and only if this deque contains 586 * at least one element {@code e} such that {@code o.equals(e)}. 587 * 588 * @param o object to be checked for containment in this deque 589 * @return {@code true} if this deque contains the specified element 590 * @throws ClassCastException if the class of the specified element 591 * is incompatible with this deque 592 * (<a href="../Collection.html#optional-restrictions">optional</a>) 593 * @throws NullPointerException if the specified element is null 594 * (<a href="../Collection.html#optional-restrictions">optional</a>) 595 */ 596 boolean contains(Object o); 597 598 /** 599 * Returns the number of elements in this deque. 600 * 601 * @return the number of elements in this deque 602 */ 603 int size(); 604 605 /** 606 * Returns an iterator over the elements in this deque in proper sequence. 607 * The elements will be returned in order from first (head) to last (tail). 608 * 609 * @return an iterator over the elements in this deque in proper sequence 610 */ 611 Iterator<E> iterator(); 612 613 // *** Stack methods *** 614 615 /** 616 * Pushes an element onto the stack represented by this deque (in other 617 * words, at the head of this deque) if it is possible to do so 618 * immediately without violating capacity restrictions, throwing an 619 * {@code IllegalStateException} if no space is currently available. 620 * 621 * <p>This method is equivalent to {@link #addFirst(Object) addFirst}. 622 * 623 * @throws IllegalStateException {@inheritDoc} 624 * @throws ClassCastException {@inheritDoc} 625 * @throws NullPointerException if the specified element is null 626 * @throws IllegalArgumentException {@inheritDoc} 627 */ 628 void push(E e); 629} 630