1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19 package org.apache.syncope.common.lib.collections;
20
21 import java.io.IOException;
22 import java.io.ObjectInputStream;
23 import java.io.ObjectOutputStream;
24 import java.io.Serializable;
25 import java.util.AbstractCollection;
26 import java.util.Arrays;
27 import java.util.Collection;
28 import java.util.Iterator;
29 import java.util.NoSuchElementException;
30 import java.util.Queue;
31
32 /**
33 * CircularFifoQueue is a first-in first-out queue with a fixed size that
34 * replaces its oldest element if full.
35 *
36 * The removal order of a {@link CircularFifoQueue} is based on the
37 * insertion order; elements are removed in the same order in which they
38 * were added. The iteration order is the same as the removal order.
39 *
40 * The {@link #add(Object)}, {@link #remove()}, {@link #peek()}, {@link #poll},
41 * {@link #offer(Object)} operations all perform in constant time.
42 * All other operations perform in linear time or worse.
43 *
44 * This queue prevents null objects from being added.
45 *
46 * @param <E> the type of elements held in this collection
47 */
48 public class CircularFifoQueue<E> extends AbstractCollection<E> implements Queue<E>, Serializable {
49
50 private static final long serialVersionUID = -8423413834657610406L;
51
52 /** Underlying storage array. */
53 private transient E[] elements;
54
55 /** Array index of first (oldest) queue element. */
56 private transient int start = 0;
57
58 /**
59 * Index mod maxElements of the array position following the last queue
60 * element. Queue elements start at elements[start] and "wrap around"
61 * elements[maxElements-1], ending at elements[decrement(end)].
62 * For example, elements = {c,a,b}, start=1, end=1 corresponds to
63 * the queue [a,b,c].
64 */
65 private transient int end = 0;
66
67 /** Flag to indicate if the queue is currently full. */
68 private transient boolean full = false;
69
70 /** Capacity of the queue. */
71 private final int maxElements;
72
73 /**
74 * Constructor that creates a queue with the default size of 32.
75 */
76 public CircularFifoQueue() {
77 this(32);
78 }
79
80 /**
81 * Constructor that creates a queue with the specified size.
82 *
83 * @param size the size of the queue (cannot be changed)
84 * @throws IllegalArgumentException if the size is < 1
85 */
86 @SuppressWarnings("unchecked")
87 public CircularFifoQueue(final int size) {
88 if (size <= 0) {
89 throw new IllegalArgumentException("The size must be greater than 0");
90 }
91 elements = (E[]) new Object[size];
92 maxElements = elements.length;
93 }
94
95 /**
96 * Constructor that creates a queue from the specified collection.
97 * The collection size also sets the queue size.
98 *
99 * @param coll the collection to copy into the queue, may not be null
100 * @throws NullPointerException if the collection is null
101 */
102 public CircularFifoQueue(final Collection<? extends E> coll) {
103 this(coll.size());
104 addAll(coll);
105 }
106
107 //-----------------------------------------------------------------------
108 /**
109 * Write the queue out using a custom routine.
110 *
111 * @param out the output stream
112 * @throws IOException if an I/O error occurs while writing to the output stream
113 */
114 private void writeObject(final ObjectOutputStream out) throws IOException {
115 out.defaultWriteObject();
116 out.writeInt(size());
117 for (final E e : this) {
118 out.writeObject(e);
119 }
120 }
121
122 /**
123 * Read the queue in using a custom routine.
124 *
125 * @param in the input stream
126 * @throws IOException if an I/O error occurs while writing to the output stream
127 * @throws ClassNotFoundException if the class of a serialized object can not be found
128 */
129 @SuppressWarnings("unchecked")
130 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
131 in.defaultReadObject();
132 elements = (E[]) new Object[maxElements];
133 final int size = in.readInt();
134 for (int i = 0; i < size; i++) {
135 elements[i] = (E) in.readObject();
136 }
137 start = 0;
138 full = size == maxElements;
139 if (full) {
140 end = 0;
141 } else {
142 end = size;
143 }
144 }
145
146 //-----------------------------------------------------------------------
147 /**
148 * Returns the number of elements stored in the queue.
149 *
150 * @return this queue's size
151 */
152 @Override
153 public int size() {
154 int size;
155
156 if (end < start) {
157 size = maxElements - start + end;
158 } else if (end == start) {
159 size = full ? maxElements : 0;
160 } else {
161 size = end - start;
162 }
163
164 return size;
165 }
166
167 /**
168 * Returns true if this queue is empty; false otherwise.
169 *
170 * @return true if this queue is empty
171 */
172 @Override
173 public boolean isEmpty() {
174 return size() == 0;
175 }
176
177 /**
178 *
179 * <p>
180 * A {@code CircularFifoQueue} can never be full, thus this returns always
181 * {@code false}.
182 *
183 * @return always returns {@code false}
184 */
185 public static boolean isFull() {
186 return false;
187 }
188
189 /**
190 * Returns {@code true} if the capacity limit of this queue has been reached,
191 * i.e. the number of elements stored in the queue equals its maximum size.
192 *
193 * @return {@code true} if the capacity limit has been reached, {@code false} otherwise
194 * @since 4.1
195 */
196 public boolean isAtFullCapacity() {
197 return size() == maxElements;
198 }
199
200 /**
201 * Gets the maximum size of the collection (the bound).
202 *
203 * @return the maximum number of elements the collection can hold
204 */
205 public int maxSize() {
206 return maxElements;
207 }
208
209 /**
210 * Clears this queue.
211 */
212 @Override
213 public void clear() {
214 full = false;
215 start = 0;
216 end = 0;
217 Arrays.fill(elements, null);
218 }
219
220 /**
221 * Adds the given element to this queue. If the queue is full, the least recently added
222 * element is discarded so that a new element can be inserted.
223 *
224 * @param element the element to add
225 * @return true, always
226 * @throws NullPointerException if the given element is null
227 */
228 @Override
229 public boolean add(final E element) {
230 if (null == element) {
231 throw new NullPointerException("Attempted to add null object to queue");
232 }
233
234 if (isAtFullCapacity()) {
235 remove();
236 }
237
238 elements[end++] = element;
239
240 if (end >= maxElements) {
241 end = 0;
242 }
243
244 if (end == start) {
245 full = true;
246 }
247
248 return true;
249 }
250
251 /**
252 * Returns the element at the specified position in this queue.
253 *
254 * @param index the position of the element in the queue
255 * @return the element at position {@code index}
256 * @throws NoSuchElementException if the requested position is outside the range [0, size)
257 */
258 public E get(final int index) {
259 final int sz = size();
260 if (index < 0 || index >= sz) {
261 throw new NoSuchElementException(
262 String.format("The specified index (%1$d) is outside the available range [0, %2$d)",
263 index, Integer.valueOf(sz)));
264 }
265
266 final int idx = (start + index) % maxElements;
267 return elements[idx];
268 }
269
270 //-----------------------------------------------------------------------
271 /**
272 * Adds the given element to this queue. If the queue is full, the least recently added
273 * element is discarded so that a new element can be inserted.
274 *
275 * @param element the element to add
276 * @return true, always
277 * @throws NullPointerException if the given element is null
278 */
279 @Override
280 public boolean offer(final E element) {
281 return add(element);
282 }
283
284 @Override
285 public E poll() {
286 if (isEmpty()) {
287 return null;
288 }
289 return remove();
290 }
291
292 @Override
293 public E element() {
294 if (isEmpty()) {
295 throw new NoSuchElementException("queue is empty");
296 }
297 return peek();
298 }
299
300 @Override
301 public E peek() {
302 if (isEmpty()) {
303 return null;
304 }
305 return elements[start];
306 }
307
308 @Override
309 public E remove() {
310 if (isEmpty()) {
311 throw new NoSuchElementException("queue is empty");
312 }
313
314 final E element = elements[start];
315 if (null != element) {
316 elements[start++] = null;
317
318 if (start >= maxElements) {
319 start = 0;
320 }
321 full = false;
322 }
323 return element;
324 }
325
326 //-----------------------------------------------------------------------
327 /**
328 * Increments the internal index.
329 *
330 * @param index the index to increment
331 * @return the updated index
332 */
333 private int increment(final int index) {
334 int result = index;
335 result++;
336 if (result >= maxElements) {
337 result = 0;
338 }
339 return result;
340 }
341
342 /**
343 * Decrements the internal index.
344 *
345 * @param index the index to decrement
346 * @return the updated index
347 */
348 private int decrement(final int index) {
349 int result = index;
350 result--;
351 if (result < 0) {
352 result = maxElements - 1;
353 }
354 return result;
355 }
356
357 /**
358 * Returns an iterator over this queue's elements.
359 *
360 * @return an iterator over this queue's elements
361 */
362 @Override
363 public Iterator<E> iterator() {
364 return new Iterator<>() {
365
366 private int index = start;
367
368 private int lastReturnedIndex = -1;
369
370 private boolean isFirst = full;
371
372 @Override
373 public boolean hasNext() {
374 return isFirst || index != end;
375 }
376
377 @Override
378 public E next() {
379 if (!hasNext()) {
380 throw new NoSuchElementException();
381 }
382 isFirst = false;
383 lastReturnedIndex = index;
384 index = increment(index);
385 return elements[lastReturnedIndex];
386 }
387
388 @Override
389 public void remove() {
390 if (lastReturnedIndex == -1) {
391 throw new IllegalStateException();
392 }
393
394 // First element can be removed quickly
395 if (lastReturnedIndex == start) {
396 CircularFifoQueue.this.remove();
397 lastReturnedIndex = -1;
398 return;
399 }
400
401 int pos = lastReturnedIndex + 1;
402 if (start < lastReturnedIndex && pos < end) {
403 // shift in one part
404 System.arraycopy(elements, pos, elements, lastReturnedIndex, end - pos);
405 } else {
406 // Other elements require us to shift the subsequent elements
407 while (pos != end) {
408 if (pos >= maxElements) {
409 elements[pos - 1] = elements[0];
410 pos = 0;
411 } else {
412 elements[decrement(pos)] = elements[pos];
413 pos = increment(pos);
414 }
415 }
416 }
417
418 lastReturnedIndex = -1;
419 end = decrement(end);
420 elements[end] = null;
421 full = false;
422 index = decrement(index);
423 }
424
425 };
426 }
427 }