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.Queue; 13 14 import hunt.collection.Collection; 15 16 /** 17 * A collection designed for holding elements prior to processing. 18 * Besides basic {@link hunt.collection.Collection Collection} operations, 19 * queues provide additional insertion, extraction, and inspection 20 * operations. Each of these methods exists in two forms: one throws 21 * an exception if the operation fails, the other returns a special 22 * value (either {@code null} or {@code false}, depending on the 23 * operation). The latter form of the insert operation is designed 24 * specifically for use with capacity-restricted {@code Queue} 25 * implementations; in most implementations, insert operations cannot 26 * fail. 27 * 28 * <table BORDER CELLPADDING=3 CELLSPACING=1> 29 * <caption>Summary of Queue methods</caption> 30 * <tr> 31 * <td></td> 32 * <td ALIGN=CENTER><em>Throws exception</em></td> 33 * <td ALIGN=CENTER><em>Returns special value</em></td> 34 * </tr> 35 * <tr> 36 * <td><b>Insert</b></td> 37 * <td>{@link Queue#add add(e)}</td> 38 * <td>{@link Queue#offer offer(e)}</td> 39 * </tr> 40 * <tr> 41 * <td><b>Remove</b></td> 42 * <td>{@link Queue#remove remove()}</td> 43 * <td>{@link Queue#poll poll()}</td> 44 * </tr> 45 * <tr> 46 * <td><b>Examine</b></td> 47 * <td>{@link Queue#element element()}</td> 48 * <td>{@link Queue#peek peek()}</td> 49 * </tr> 50 * </table> 51 * 52 * <p>Queues typically, but do not necessarily, order elements in a 53 * FIFO (first-in-first-out) manner. Among the exceptions are 54 * priority queues, which order elements according to a supplied 55 * comparator, or the elements' natural ordering, and LIFO queues (or 56 * stacks) which order the elements LIFO (last-in-first-out). 57 * Whatever the ordering used, the <em>head</em> of the queue is that 58 * element which would be removed by a call to {@link #remove() } or 59 * {@link #poll()}. In a FIFO queue, all new elements are inserted at 60 * the <em>tail</em> of the queue. Other kinds of queues may use 61 * different placement rules. Every {@code Queue} implementation 62 * must specify its ordering properties. 63 * 64 * <p>The {@link #offer offer} method inserts an element if possible, 65 * otherwise returning {@code false}. This differs from the {@link 66 * hunt.collection.Collection#add Collection.add} method, which can fail to 67 * add an element only by throwing an unchecked exception. The 68 * {@code offer} method is designed for use when failure is a normal, 69 * rather than exceptional occurrence, for example, in fixed-capacity 70 * (or "bounded") queues. 71 * 72 * <p>The {@link #remove()} and {@link #poll()} methods remove and 73 * return the head of the queue. 74 * Exactly which element is removed from the queue is a 75 * function of the queue's ordering policy, which differs from 76 * implementation to implementation. The {@code remove()} and 77 * {@code poll()} methods differ only in their behavior when the 78 * queue is empty: the {@code remove()} method throws an exception, 79 * while the {@code poll()} method returns {@code null}. 80 * 81 * <p>The {@link #element()} and {@link #peek()} methods return, but do 82 * not remove, the head of the queue. 83 * 84 * <p>The {@code Queue} interface does not define the <i>blocking queue 85 * methods</i>, which are common in concurrent programming. These methods, 86 * which wait for elements to appear or for space to become available, are 87 * defined in the {@link hunt.concurrency.BlockingQueue} interface, which 88 * extends this interface. 89 * 90 * <p>{@code Queue} implementations generally do not allow insertion 91 * of {@code null} elements, although some implementations, such as 92 * {@link LinkedList}, do not prohibit insertion of {@code null}. 93 * Even in the implementations that permit it, {@code null} should 94 * not be inserted into a {@code Queue}, as {@code null} is also 95 * used as a special return value by the {@code poll} method to 96 * indicate that the queue contains no elements. 97 * 98 * <p>{@code Queue} implementations generally do not define 99 * element-based versions of methods {@code equals} and 100 * {@code hashCode} but instead inherit the identity based versions 101 * from class {@code Object}, because element-based equality is not 102 * always well-defined for queues with the same elements but different 103 * ordering properties. 104 * 105 * 106 * <p>This interface is a member of the 107 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 108 * Java Collections Framework</a>. 109 * 110 * @see hunt.collection.Collection 111 * @see LinkedList 112 * @see PriorityQueue 113 * @see hunt.concurrency.LinkedBlockingQueue 114 * @see hunt.concurrency.BlockingQueue 115 * @see hunt.concurrency.ArrayBlockingQueue 116 * @see hunt.concurrency.LinkedBlockingQueue 117 * @see hunt.concurrency.PriorityBlockingQueue 118 * @author Doug Lea 119 * @param !E the type of elements held in this collection 120 */ 121 interface Queue(E) : Collection!E { 122 /** 123 * Inserts the specified element into this queue if it is possible to do so 124 * immediately without violating capacity restrictions, returning 125 * {@code true} upon success and throwing an {@code IllegalStateException} 126 * if no space is currently available. 127 * 128 * @param e the element to add 129 * @return {@code true} (as specified by {@link Collection#add}) 130 * @throws IllegalStateException if the element cannot be added at this 131 * time due to capacity restrictions 132 * @throws ClassCastException if the class of the specified element 133 * prevents it from being added to this queue 134 * @throws NullPointerException if the specified element is null and 135 * this queue does not permit null elements 136 * @throws IllegalArgumentException if some property of this element 137 * prevents it from being added to this queue 138 */ 139 bool add(E e); 140 141 /** 142 * Inserts the specified element into this queue if it is possible to do 143 * so immediately without violating capacity restrictions. 144 * When using a capacity-restricted queue, this method is generally 145 * preferable to {@link #add}, which can fail to insert an element only 146 * by throwing an exception. 147 * 148 * @param e the element to add 149 * @return {@code true} if the element was added to this queue, else 150 * {@code false} 151 * @throws ClassCastException if the class of the specified element 152 * prevents it from being added to this queue 153 * @throws NullPointerException if the specified element is null and 154 * this queue does not permit null elements 155 * @throws IllegalArgumentException if some property of this element 156 * prevents it from being added to this queue 157 */ 158 bool offer(E e); 159 160 /** 161 * Retrieves and removes the head of this queue. This method differs 162 * from {@link #poll poll} only in that it throws an exception if this 163 * queue is empty. 164 * 165 * @return the head of this queue 166 * @throws NoSuchElementException if this queue is empty 167 */ 168 E remove(); 169 170 /** 171 * Retrieves and removes the head of this queue, 172 * or returns {@code null} if this queue is empty. 173 * 174 * @return the head of this queue, or {@code null} if this queue is empty 175 */ 176 E poll(); 177 178 /** 179 * Retrieves, but does not remove, the head of this queue. This method 180 * differs from {@link #peek peek} only in that it throws an exception 181 * if this queue is empty. 182 * 183 * @return the head of this queue 184 * @throws NoSuchElementException if this queue is empty 185 */ 186 E element(); 187 188 /** 189 * Retrieves, but does not remove, the head of this queue, 190 * or returns {@code null} if this queue is empty. 191 * 192 * @return the head of this queue, or {@code null} if this queue is empty 193 */ 194 E peek(); 195 }