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 modulehunt.collection.Deque;
13 14 importhunt.collection.Queue;
15 importstd.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 interfaceDeque(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 voidaddFirst(Ee);
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 voidaddLast(Ee);
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 boolofferFirst(Ee);
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 boolofferLast(Ee);
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 EremoveFirst();
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 EremoveLast();
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 EpollFirst();
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 EpollLast();
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 EgetFirst();
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 EgetLast();
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 EpeekFirst();
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 EpeekLast();
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 boolremoveFirstOccurrence(Eo);
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 booladd(Ee);
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 booloffer(Ee);
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 Eremove();
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 Epoll();
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 Eelement();
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 Epeek();
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 voidpush(Ee);
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 Epop();
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 boolremove(Eo);
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 boolcontains(Eo);
536 537 /**
538 * Returns the number of elements in this deque.
539 *
540 * @return the number of elements in this deque
541 */542 intsize();
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!EdescendingIterator();
561 562 }