1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.buffer;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.util.AbstractCollection;
24 import java.util.Iterator;
25 import java.util.NoSuchElementException;
26
27 import org.apache.commons.collections.Buffer;
28 import org.apache.commons.collections.BufferUnderflowException;
29
30 /**
31 * UnboundedFifoBuffer is a very efficient implementation of
32 * {@link Buffer} that can grow to any size.
33 * According to performance testing, it exhibits a constant access time, but it
34 * also outperforms ArrayList when used for the same purpose.
35 * <p>
36 * The removal order of an {@link UnboundedFifoBuffer} is based on the insertion
37 * order; elements are removed in the same order in which they were added.
38 * The iteration order is the same as the removal order.
39 * <p>
40 * The {@link #remove()} and {@link #get()} operations perform in constant time.
41 * The {@link #add(Object)} operation performs in amortized constant time. All
42 * other operations perform in linear time or worse.
43 * <p>
44 * Note that this implementation is not synchronized. The following can be
45 * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
46 * <pre>
47 * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
48 * </pre>
49 * <p>
50 * This buffer prevents null objects from being added.
51 * <p>
52 * This class is Serializable from Commons Collections 3.1.
53 *
54 * @since 3.0 (previously in main package v2.1)
55 * @version $Id: UnboundedFifoBuffer.java 1429905 2013-01-07 17:15:14Z ggregory $
56 */
57 public class UnboundedFifoBuffer<E> extends AbstractCollection<E> implements Buffer<E>, Serializable {
58 // invariant: buffer.length > size()
59 // ie.buffer always has at least one empty entry
60
61 /** Serialization version */
62 private static final long serialVersionUID = -3482960336579541419L;
63
64 /** The array of objects in the buffer. */
65 protected transient E[] buffer;
66
67 /** The current head index. */
68 protected transient int head;
69
70 /** The current tail index. */
71 protected transient int tail;
72
73 /**
74 * Constructs an UnboundedFifoBuffer with the default number of elements.
75 * It is exactly the same as performing the following:
76 *
77 * <pre>
78 * new UnboundedFifoBuffer(32);
79 * </pre>
80 */
81 public UnboundedFifoBuffer() {
82 this(32);
83 }
84
85 /**
86 * Constructs an UnboundedFifoBuffer with the specified number of elements.
87 * The integer must be a positive integer.
88 *
89 * @param initialSize the initial size of the buffer
90 * @throws IllegalArgumentException if the size is less than 1
91 */
92 @SuppressWarnings("unchecked")
93 public UnboundedFifoBuffer(final int initialSize) {
94 if (initialSize <= 0) {
95 throw new IllegalArgumentException("The size must be greater than 0");
96 }
97 buffer = (E[]) new Object[initialSize + 1];
98 head = 0;
99 tail = 0;
100 }
101
102 //-----------------------------------------------------------------------
103 /**
104 * Write the buffer out using a custom routine.
105 *
106 * @param out the output stream
107 * @throws IOException if an I/O error occurs while writing to the output stream
108 */
109 private void writeObject(final ObjectOutputStream out) throws IOException {
110 out.defaultWriteObject();
111 out.writeInt(size());
112 out.writeInt(buffer.length);
113 for (final E e : this) {
114 out.writeObject(e);
115 }
116 }
117
118 /**
119 * Read the buffer in using a custom routine.
120 *
121 * @param in the input stream
122 * @throws IOException if an I/O error occurs while reading from the input stream
123 * @throws ClassNotFoundException if the class of a serialized object can not be found
124 */
125 @SuppressWarnings("unchecked")
126 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
127 in.defaultReadObject();
128 final int size = in.readInt();
129 final int length = in.readInt();
130 buffer = (E[]) new Object[length];
131 for (int i = 0; i < size; i++) {
132 buffer[i] = (E) in.readObject();
133 }
134 head = 0;
135 tail = size;
136 }
137
138 //-----------------------------------------------------------------------
139 /**
140 * Returns the number of elements stored in the buffer.
141 *
142 * @return this buffer's size
143 */
144 @Override
145 public int size() {
146 int size = 0;
147
148 if (tail < head) {
149 size = buffer.length - head + tail;
150 } else {
151 size = tail - head;
152 }
153
154 return size;
155 }
156
157 /**
158 * Returns true if this buffer is empty; false otherwise.
159 *
160 * @return true if this buffer is empty
161 */
162 @Override
163 public boolean isEmpty() {
164 return size() == 0;
165 }
166
167 /**
168 * Adds the given element to this buffer.
169 *
170 * @param obj the element to add
171 * @return true, always
172 * @throws NullPointerException if the given element is null
173 */
174 @Override
175 @SuppressWarnings("unchecked")
176 public boolean add(final E obj) {
177 if (obj == null) {
178 throw new NullPointerException("Attempted to add null object to buffer");
179 }
180
181 if (size() + 1 >= buffer.length) {
182 // copy contents to a new buffer array
183 final E[] tmp = (E[]) new Object[(buffer.length - 1) * 2 + 1];
184 int j = 0;
185 // move head to element zero in the new array
186 for (int i = head; i != tail;) {
187 tmp[j] = buffer[i];
188 buffer[i] = null;
189
190 j++;
191 i = increment(i);
192 }
193 buffer = tmp;
194 head = 0;
195 tail = j;
196 }
197
198 buffer[tail] = obj;
199 tail = increment(tail);
200 return true;
201 }
202
203 /**
204 * Returns the next object in the buffer.
205 *
206 * @return the next object in the buffer
207 * @throws BufferUnderflowException if this buffer is empty
208 */
209 public E get() {
210 if (isEmpty()) {
211 throw new BufferUnderflowException("The buffer is already empty");
212 }
213
214 return buffer[head];
215 }
216
217 /**
218 * Removes the next object from the buffer
219 *
220 * @return the removed object
221 * @throws BufferUnderflowException if this buffer is empty
222 */
223 public E remove() {
224 if (isEmpty()) {
225 throw new BufferUnderflowException("The buffer is already empty");
226 }
227
228 final E element = buffer[head];
229 if (element != null) {
230 buffer[head] = null;
231 head = increment(head);
232 }
233 return element;
234 }
235
236 /**
237 * Increments the internal index.
238 *
239 * @param index the index to increment
240 * @return the updated index
241 */
242 private int increment(int index) {
243 index++;
244 if (index >= buffer.length) {
245 index = 0;
246 }
247 return index;
248 }
249
250 /**
251 * Decrements the internal index.
252 *
253 * @param index the index to decrement
254 * @return the updated index
255 */
256 private int decrement(int index) {
257 index--;
258 if (index < 0) {
259 index = buffer.length - 1;
260 }
261 return index;
262 }
263
264 /**
265 * Returns an iterator over this buffer's elements.
266 *
267 * @return an iterator over this buffer's elements
268 */
269 @Override
270 public Iterator<E> iterator() {
271 return new Iterator<E>() {
272
273 private int index = head;
274 private int lastReturnedIndex = -1;
275
276 public boolean hasNext() {
277 return index != tail;
278
279 }
280
281 public E next() {
282 if (!hasNext()) {
283 throw new NoSuchElementException();
284 }
285 lastReturnedIndex = index;
286 index = increment(index);
287 return buffer[lastReturnedIndex];
288 }
289
290 public void remove() {
291 if (lastReturnedIndex == -1) {
292 throw new IllegalStateException();
293 }
294
295 // First element can be removed quickly
296 if (lastReturnedIndex == head) {
297 UnboundedFifoBuffer.this.remove();
298 lastReturnedIndex = -1;
299 return;
300 }
301
302 // Other elements require us to shift the subsequent elements
303 int i = increment(lastReturnedIndex);
304 while (i != tail) {
305 buffer[decrement(i)] = buffer[i];
306 i = increment(i);
307 }
308
309 lastReturnedIndex = -1;
310 tail = decrement(tail);
311 buffer[tail] = null;
312 index = decrement(index);
313 }
314
315 };
316 }
317
318 }