1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.collection.Deque; 13 14 import hunt.collection.Queue; 15 import std.range; 16 17 /** 18 * A linear collection that supports element insertion and removal at 19 * both ends. The name <i>deque</i> is short for "double ended queue" 20 * and is usually pronounced "deck". Most {@code Deque} 21 * implementations place no fixed limits on the number of elements 22 * they may contain, but this interface supports capacity-restricted 23 * deques as well as those with no fixed size limit. 24 * 25 * <p>This interface defines methods to access the elements at both 26 * ends of the deque. Methods are provided to insert, remove, and 27 * examine the element. Each of these methods exists in two forms: 28 * one throws an exception if the operation fails, the other returns a 29 * special value (either {@code null} or {@code false}, depending on 30 * the operation). The latter form of the insert operation is 31 * designed specifically for use with capacity-restricted 32 * {@code Deque} implementations; in most implementations, insert 33 * operations cannot fail. 34 * 35 * <p>The twelve methods described above are summarized in the 36 * following table: 37 * 38 * <table BORDER CELLPADDING=3 CELLSPACING=1> 39 * <caption>Summary of Deque methods</caption> 40 * <tr> 41 * <td></td> 42 * <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td> 43 * <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td> 44 * </tr> 45 * <tr> 46 * <td></td> 47 * <td ALIGN=CENTER><em>Throws exception</em></td> 48 * <td ALIGN=CENTER><em>Special value</em></td> 49 * <td ALIGN=CENTER><em>Throws exception</em></td> 50 * <td ALIGN=CENTER><em>Special value</em></td> 51 * </tr> 52 * <tr> 53 * <td><b>Insert</b></td> 54 * <td>{@link Deque#addFirst addFirst(e)}</td> 55 * <td>{@link Deque#offerFirst offerFirst(e)}</td> 56 * <td>{@link Deque#addLast addLast(e)}</td> 57 * <td>{@link Deque#offerLast offerLast(e)}</td> 58 * </tr> 59 * <tr> 60 * <td><b>Remove</b></td> 61 * <td>{@link Deque#removeFirst removeFirst()}</td> 62 * <td>{@link Deque#pollFirst pollFirst()}</td> 63 * <td>{@link Deque#removeLast removeLast()}</td> 64 * <td>{@link Deque#pollLast pollLast()}</td> 65 * </tr> 66 * <tr> 67 * <td><b>Examine</b></td> 68 * <td>{@link Deque#getFirst getFirst()}</td> 69 * <td>{@link Deque#peekFirst peekFirst()}</td> 70 * <td>{@link Deque#getLast getLast()}</td> 71 * <td>{@link Deque#peekLast peekLast()}</td> 72 * </tr> 73 * </table> 74 * 75 * <p>This interface extends the {@link Queue} interface. When a deque is 76 * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are 77 * added at the end of the deque and removed from the beginning. The methods 78 * inherited from the {@code Queue} interface are precisely equivalent to 79 * {@code Deque} methods as indicated in the following table: 80 * 81 * <table BORDER CELLPADDING=3 CELLSPACING=1> 82 * <caption>Comparison of Queue and Deque methods</caption> 83 * <tr> 84 * <td ALIGN=CENTER> <b>{@code Queue} Method</b></td> 85 * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 86 * </tr> 87 * <tr> 88 * <td>{@link java.util.Queue#add add(e)}</td> 89 * <td>{@link #addLast addLast(e)}</td> 90 * </tr> 91 * <tr> 92 * <td>{@link java.util.Queue#offer offer(e)}</td> 93 * <td>{@link #offerLast offerLast(e)}</td> 94 * </tr> 95 * <tr> 96 * <td>{@link java.util.Queue#remove remove()}</td> 97 * <td>{@link #removeFirst removeFirst()}</td> 98 * </tr> 99 * <tr> 100 * <td>{@link java.util.Queue#poll poll()}</td> 101 * <td>{@link #pollFirst pollFirst()}</td> 102 * </tr> 103 * <tr> 104 * <td>{@link java.util.Queue#element element()}</td> 105 * <td>{@link #getFirst getFirst()}</td> 106 * </tr> 107 * <tr> 108 * <td>{@link java.util.Queue#peek peek()}</td> 109 * <td>{@link #peek peekFirst()}</td> 110 * </tr> 111 * </table> 112 * 113 * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks. This 114 * interface should be used in preference to the legacy {@link Stack} class. 115 * When a deque is used as a stack, elements are pushed and popped from the 116 * beginning of the deque. Stack methods are precisely equivalent to 117 * {@code Deque} methods as indicated in the table below: 118 * 119 * <table BORDER CELLPADDING=3 CELLSPACING=1> 120 * <caption>Comparison of Stack and Deque methods</caption> 121 * <tr> 122 * <td ALIGN=CENTER> <b>Stack Method</b></td> 123 * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 124 * </tr> 125 * <tr> 126 * <td>{@link #push push(e)}</td> 127 * <td>{@link #addFirst addFirst(e)}</td> 128 * </tr> 129 * <tr> 130 * <td>{@link #pop pop()}</td> 131 * <td>{@link #removeFirst removeFirst()}</td> 132 * </tr> 133 * <tr> 134 * <td>{@link #peek peek()}</td> 135 * <td>{@link #peekFirst peekFirst()}</td> 136 * </tr> 137 * </table> 138 * 139 * <p>Note that the {@link #peek peek} method works equally well when 140 * a deque is used as a queue or a stack; in either case, elements are 141 * drawn from the beginning of the deque. 142 * 143 * <p>This interface provides two methods to remove interior 144 * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and 145 * {@link #removeLastOccurrence removeLastOccurrence}. 146 * 147 * <p>Unlike the {@link List} interface, this interface does not 148 * provide support for indexed access to elements. 149 * 150 * <p>While {@code Deque} implementations are not strictly required 151 * to prohibit the insertion of null elements, they are strongly 152 * encouraged to do so. Users of any {@code Deque} implementations 153 * that do allow null elements are strongly encouraged <i>not</i> to 154 * take advantage of the ability to insert nulls. This is so because 155 * {@code null} is used as a special return value by various methods 156 * to indicated that the deque is empty. 157 * 158 * <p>{@code Deque} implementations generally do not define 159 * element-based versions of the {@code equals} and {@code hashCode} 160 * methods, but instead inherit the identity-based versions from class 161 * {@code Object}. 162 * 163 * <p>This interface is a member of the <a 164 * href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections 165 * Framework</a>. 166 * 167 * @author Doug Lea 168 * @author Josh Bloch 169 * @param !E the type of elements held in this collection 170 */ 171 interface Deque(E) : Queue!E { 172 /** 173 * Inserts the specified element at the front of this deque if it is 174 * possible to do so immediately without violating capacity restrictions, 175 * throwing an {@code IllegalStateException} if no space is currently 176 * available. When using a capacity-restricted deque, it is generally 177 * preferable to use method {@link #offerFirst}. 178 * 179 * @param e the element to add 180 * @throws IllegalStateException if the element cannot be added at this 181 * time due to capacity restrictions 182 * @throws ClassCastException if the class of the specified element 183 * prevents it from being added to this deque 184 * @throws NullPointerException if the specified element is null and this 185 * deque does not permit null elements 186 * @throws IllegalArgumentException if some property of the specified 187 * element prevents it from being added to this deque 188 */ 189 void addFirst(E e); 190 191 /** 192 * Inserts the specified element at the end of this deque if it is 193 * possible to do so immediately without violating capacity restrictions, 194 * throwing an {@code IllegalStateException} if no space is currently 195 * available. When using a capacity-restricted deque, it is generally 196 * preferable to use method {@link #offerLast}. 197 * 198 * <p>This method is equivalent to {@link #add}. 199 * 200 * @param e the element to add 201 * @throws IllegalStateException if the element cannot be added at this 202 * time due to capacity restrictions 203 * @throws ClassCastException if the class of the specified element 204 * prevents it from being added to this deque 205 * @throws NullPointerException if the specified element is null and this 206 * deque does not permit null elements 207 * @throws IllegalArgumentException if some property of the specified 208 * element prevents it from being added to this deque 209 */ 210 void addLast(E e); 211 212 /** 213 * Inserts the specified element at the front of this deque unless it would 214 * violate capacity restrictions. When using a capacity-restricted deque, 215 * this method is generally preferable to the {@link #addFirst} method, 216 * which can fail to insert an element only by throwing an exception. 217 * 218 * @param e the element to add 219 * @return {@code true} if the element was added to this deque, else 220 * {@code false} 221 * @throws ClassCastException if the class of the specified element 222 * prevents it from being added to this deque 223 * @throws NullPointerException if the specified element is null and this 224 * deque does not permit null elements 225 * @throws IllegalArgumentException if some property of the specified 226 * element prevents it from being added to this deque 227 */ 228 bool offerFirst(E e); 229 230 /** 231 * Inserts the specified element at the end of this deque unless it would 232 * violate capacity restrictions. When using a capacity-restricted deque, 233 * this method is generally preferable to the {@link #addLast} method, 234 * which can fail to insert an element only by throwing an exception. 235 * 236 * @param e the element to add 237 * @return {@code true} if the element was added to this deque, else 238 * {@code false} 239 * @throws ClassCastException if the class of the specified element 240 * prevents it from being added to this deque 241 * @throws NullPointerException if the specified element is null and this 242 * deque does not permit null elements 243 * @throws IllegalArgumentException if some property of the specified 244 * element prevents it from being added to this deque 245 */ 246 bool offerLast(E e); 247 248 /** 249 * Retrieves and removes the first element of this deque. This method 250 * differs from {@link #pollFirst pollFirst} only in that it throws an 251 * exception if this deque is empty. 252 * 253 * @return the head of this deque 254 * @throws NoSuchElementException if this deque is empty 255 */ 256 E removeFirst(); 257 258 /** 259 * Retrieves and removes the last element of this deque. This method 260 * differs from {@link #pollLast pollLast} only in that it throws an 261 * exception if this deque is empty. 262 * 263 * @return the tail of this deque 264 * @throws NoSuchElementException if this deque is empty 265 */ 266 E removeLast(); 267 268 /** 269 * Retrieves and removes the first element of this deque, 270 * or returns {@code null} if this deque is empty. 271 * 272 * @return the head of this deque, or {@code null} if this deque is empty 273 */ 274 E pollFirst(); 275 276 /** 277 * Retrieves and removes the last element of this deque, 278 * or returns {@code null} if this deque is empty. 279 * 280 * @return the tail of this deque, or {@code null} if this deque is empty 281 */ 282 E pollLast(); 283 284 /** 285 * Retrieves, but does not remove, the first element of this deque. 286 * 287 * This method differs from {@link #peekFirst peekFirst} only in that it 288 * throws an exception if this deque is empty. 289 * 290 * @return the head of this deque 291 * @throws NoSuchElementException if this deque is empty 292 */ 293 E getFirst(); 294 295 /** 296 * Retrieves, but does not remove, the last element of this deque. 297 * This method differs from {@link #peekLast peekLast} only in that it 298 * throws an exception if this deque is empty. 299 * 300 * @return the tail of this deque 301 * @throws NoSuchElementException if this deque is empty 302 */ 303 E getLast(); 304 305 /** 306 * Retrieves, but does not remove, the first element of this deque, 307 * or returns {@code null} if this deque is empty. 308 * 309 * @return the head of this deque, or {@code null} if this deque is empty 310 */ 311 E peekFirst(); 312 313 /** 314 * Retrieves, but does not remove, the last element of this deque, 315 * or returns {@code null} if this deque is empty. 316 * 317 * @return the tail of this deque, or {@code null} if this deque is empty 318 */ 319 E peekLast(); 320 321 /** 322 * Removes the first occurrence of the specified element from this deque. 323 * If the deque does not contain the element, it is unchanged. 324 * More formally, removes the first element {@code e} such that 325 * <tt>(o==null ? e==null : o.equals(e))</tt> 326 * (if such an element exists). 327 * Returns {@code true} if this deque contained the specified element 328 * (or equivalently, if this deque changed as a result of the call). 329 * 330 * @param o element to be removed from this deque, if present 331 * @return {@code true} if an element was removed as a result of this call 332 * @throws ClassCastException if the class of the specified element 333 * is incompatible with this deque 334 * (<a href="Collection.html#optional-restrictions">optional</a>) 335 * @throws NullPointerException if the specified element is null and this 336 * deque does not permit null elements 337 * (<a href="Collection.html#optional-restrictions">optional</a>) 338 */ 339 bool removeFirstOccurrence(E o); 340 341 /** 342 * Removes the last occurrence of the specified element from this deque. 343 * If the deque does not contain the element, it is unchanged. 344 * More formally, removes the last element {@code e} such that 345 * <tt>(o==null ? e==null : o.equals(e))</tt> 346 * (if such an element exists). 347 * Returns {@code true} if this deque contained the specified element 348 * (or equivalently, if this deque changed as a result of the call). 349 * 350 * @param o element to be removed from this deque, if present 351 * @return {@code true} if an element was removed as a result of this call 352 * @throws ClassCastException if the class of the specified element 353 * is incompatible with this deque 354 * (<a href="Collection.html#optional-restrictions">optional</a>) 355 * @throws NullPointerException if the specified element is null and this 356 * deque does not permit null elements 357 * (<a href="Collection.html#optional-restrictions">optional</a>) 358 */ 359 // bool removeLastOccurrence(E o); 360 361 // *** Queue methods *** 362 363 /** 364 * Inserts the specified element into the queue represented by this deque 365 * (in other words, at the tail of this deque) if it is possible to do so 366 * immediately without violating capacity restrictions, returning 367 * {@code true} upon success and throwing an 368 * {@code IllegalStateException} if no space is currently available. 369 * When using a capacity-restricted deque, it is generally preferable to 370 * use {@link #offer(Object) offer}. 371 * 372 * <p>This method is equivalent to {@link #addLast}. 373 * 374 * @param e the element to add 375 * @return {@code true} (as specified by {@link Collection#add}) 376 * @throws IllegalStateException if the element cannot be added at this 377 * time due to capacity restrictions 378 * @throws ClassCastException if the class of the specified element 379 * prevents it from being added to this deque 380 * @throws NullPointerException if the specified element is null and this 381 * deque does not permit null elements 382 * @throws IllegalArgumentException if some property of the specified 383 * element prevents it from being added to this deque 384 */ 385 bool add(E e); 386 387 /** 388 * Inserts the specified element into the queue represented by this deque 389 * (in other words, at the tail of this deque) if it is possible to do so 390 * immediately without violating capacity restrictions, returning 391 * {@code true} upon success and {@code false} if no space is currently 392 * available. When using a capacity-restricted deque, this method is 393 * generally preferable to the {@link #add} method, which can fail to 394 * insert an element only by throwing an exception. 395 * 396 * <p>This method is equivalent to {@link #offerLast}. 397 * 398 * @param e the element to add 399 * @return {@code true} if the element was added to this deque, else 400 * {@code false} 401 * @throws ClassCastException if the class of the specified element 402 * prevents it from being added to this deque 403 * @throws NullPointerException if the specified element is null and this 404 * deque does not permit null elements 405 * @throws IllegalArgumentException if some property of the specified 406 * element prevents it from being added to this deque 407 */ 408 bool offer(E e); 409 410 /** 411 * Retrieves and removes the head of the queue represented by this deque 412 * (in other words, the first element of this deque). 413 * This method differs from {@link #poll poll} only in that it throws an 414 * exception if this deque is empty. 415 * 416 * <p>This method is equivalent to {@link #removeFirst()}. 417 * 418 * @return the head of the queue represented by this deque 419 * @throws NoSuchElementException if this deque is empty 420 */ 421 E remove(); 422 423 /** 424 * Retrieves and removes the head of the queue represented by this deque 425 * (in other words, the first element of this deque), or returns 426 * {@code null} if this deque is empty. 427 * 428 * <p>This method is equivalent to {@link #pollFirst()}. 429 * 430 * @return the first element of this deque, or {@code null} if 431 * this deque is empty 432 */ 433 E poll(); 434 435 /** 436 * Retrieves, but does not remove, the head of the queue represented by 437 * this deque (in other words, the first element of this deque). 438 * This method differs from {@link #peek peek} only in that it throws an 439 * exception if this deque is empty. 440 * 441 * <p>This method is equivalent to {@link #getFirst()}. 442 * 443 * @return the head of the queue represented by this deque 444 * @throws NoSuchElementException if this deque is empty 445 */ 446 E element(); 447 448 /** 449 * Retrieves, but does not remove, the head of the queue represented by 450 * this deque (in other words, the first element of this deque), or 451 * returns {@code null} if this deque is empty. 452 * 453 * <p>This method is equivalent to {@link #peekFirst()}. 454 * 455 * @return the head of the queue represented by this deque, or 456 * {@code null} if this deque is empty 457 */ 458 E peek(); 459 460 461 // *** Stack methods *** 462 463 /** 464 * Pushes an element onto the stack represented by this deque (in other 465 * words, at the head of this deque) if it is possible to do so 466 * immediately without violating capacity restrictions, throwing an 467 * {@code IllegalStateException} if no space is currently available. 468 * 469 * <p>This method is equivalent to {@link #addFirst}. 470 * 471 * @param e the element to push 472 * @throws IllegalStateException if the element cannot be added at this 473 * time due to capacity restrictions 474 * @throws ClassCastException if the class of the specified element 475 * prevents it from being added to this deque 476 * @throws NullPointerException if the specified element is null and this 477 * deque does not permit null elements 478 * @throws IllegalArgumentException if some property of the specified 479 * element prevents it from being added to this deque 480 */ 481 void push(E e); 482 483 /** 484 * Pops an element from the stack represented by this deque. In other 485 * words, removes and returns the first element of this deque. 486 * 487 * <p>This method is equivalent to {@link #removeFirst()}. 488 * 489 * @return the element at the front of this deque (which is the top 490 * of the stack represented by this deque) 491 * @throws NoSuchElementException if this deque is empty 492 */ 493 E pop(); 494 495 496 // *** Collection methods *** 497 498 /** 499 * Removes the first occurrence of the specified element from this deque. 500 * If the deque does not contain the element, it is unchanged. 501 * More formally, removes the first element {@code e} such that 502 * <tt>(o==null ? e==null : o.equals(e))</tt> 503 * (if such an element exists). 504 * Returns {@code true} if this deque contained the specified element 505 * (or equivalently, if this deque changed as a result of the call). 506 * 507 * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}. 508 * 509 * @param o element to be removed from this deque, if present 510 * @return {@code true} if an element was removed as a result of this call 511 * @throws ClassCastException if the class of the specified element 512 * is incompatible with this deque 513 * (<a href="Collection.html#optional-restrictions">optional</a>) 514 * @throws NullPointerException if the specified element is null and this 515 * deque does not permit null elements 516 * (<a href="Collection.html#optional-restrictions">optional</a>) 517 */ 518 bool remove(E o); 519 520 /** 521 * Returns {@code true} if this deque contains the specified element. 522 * More formally, returns {@code true} if and only if this deque contains 523 * at least one element {@code e} such that 524 * <tt>(o==null ? e==null : o.equals(e))</tt>. 525 * 526 * @param o element whose presence in this deque is to be tested 527 * @return {@code true} if this deque contains the specified element 528 * @throws ClassCastException if the type of the specified element 529 * is incompatible with this deque 530 * (<a href="Collection.html#optional-restrictions">optional</a>) 531 * @throws NullPointerException if the specified element is null and this 532 * deque does not permit null elements 533 * (<a href="Collection.html#optional-restrictions">optional</a>) 534 */ 535 bool contains(E o); 536 537 /** 538 * Returns the number of elements in this deque. 539 * 540 * @return the number of elements in this deque 541 */ 542 int size(); 543 544 /** 545 * Returns an iterator over the elements in this deque in proper sequence. 546 * The elements will be returned in order from first (head) to last (tail). 547 * 548 * @return an iterator over the elements in this deque in proper sequence 549 */ 550 // Iterator!E iterator(); 551 552 /** 553 * Returns an iterator over the elements in this deque in reverse 554 * sequential order. The elements will be returned in order from 555 * last (tail) to first (head). 556 * 557 * @return an iterator over the elements in this deque in reverse 558 * sequence 559 */ 560 InputRange!E descendingIterator(); 561 562 }