001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.buffer;
018
019 import java.io.IOException;
020 import java.io.ObjectInputStream;
021 import java.io.ObjectOutputStream;
022 import java.io.Serializable;
023 import java.util.AbstractCollection;
024 import java.util.Iterator;
025 import java.util.NoSuchElementException;
026
027 import org.apache.commons.collections.Buffer;
028 import org.apache.commons.collections.BufferUnderflowException;
029
030 /**
031 * UnboundedFifoBuffer is a very efficient implementation of
032 * <code>Buffer</code> that can grow to any size.
033 * According to performance testing, it exhibits a constant access time, but it
034 * also outperforms ArrayList when used for the same purpose.
035 * <p>
036 * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
037 * order; elements are removed in the same order in which they were added.
038 * The iteration order is the same as the removal order.
039 * <p>
040 * The {@link #remove()} and {@link #get()} operations perform in constant time.
041 * The {@link #add(Object)} operation performs in amortized constant time. All
042 * other operations perform in linear time or worse.
043 * <p>
044 * Note that this implementation is not synchronized. The following can be
045 * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
046 * <pre>
047 * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
048 * </pre>
049 * <p>
050 * This buffer prevents null objects from being added.
051 * <p>
052 * This class is Serializable from Commons Collections 3.1.
053 *
054 * @since Commons Collections 3.0 (previously in main package v2.1)
055 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
056 *
057 * @author Avalon
058 * @author Federico Barbieri
059 * @author Berin Loritsch
060 * @author Paul Jack
061 * @author Stephen Colebourne
062 * @author Andreas Schlosser
063 * @author Thomas Knych
064 * @author Jordan Krey
065 */
066 public class UnboundedFifoBuffer extends AbstractCollection implements Buffer, Serializable {
067 // invariant: buffer.length > size()
068 // ie.buffer always has at least one empty entry
069
070 /** Serialization vesrion */
071 private static final long serialVersionUID = -3482960336579541419L;
072
073 /** The array of objects in the buffer. */
074 protected transient Object[] buffer;
075 /** The current head index. */
076 protected transient int head;
077 /** The current tail index. */
078 protected transient int tail;
079
080 /**
081 * Constructs an UnboundedFifoBuffer with the default number of elements.
082 * It is exactly the same as performing the following:
083 *
084 * <pre>
085 * new UnboundedFifoBuffer(32);
086 * </pre>
087 */
088 public UnboundedFifoBuffer() {
089 this(32);
090 }
091
092 /**
093 * Constructs an UnboundedFifoBuffer with the specified number of elements.
094 * The integer must be a positive integer.
095 *
096 * @param initialSize the initial size of the buffer
097 * @throws IllegalArgumentException if the size is less than 1
098 */
099 public UnboundedFifoBuffer(int initialSize) {
100 if (initialSize <= 0) {
101 throw new IllegalArgumentException("The size must be greater than 0");
102 }
103 buffer = new Object[initialSize + 1];
104 head = 0;
105 tail = 0;
106 }
107
108 //-----------------------------------------------------------------------
109 /**
110 * Write the buffer out using a custom routine.
111 *
112 * @param out the output stream
113 * @throws IOException
114 */
115 private void writeObject(ObjectOutputStream out) throws IOException {
116 out.defaultWriteObject();
117 out.writeInt(size());
118 for (Iterator it = iterator(); it.hasNext();) {
119 out.writeObject(it.next());
120 }
121 }
122
123 /**
124 * Read the buffer in using a custom routine.
125 *
126 * @param in the input stream
127 * @throws IOException
128 * @throws ClassNotFoundException
129 */
130 private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
131 in.defaultReadObject();
132 int size = in.readInt();
133 buffer = new Object[size + 1];
134 for (int i = 0; i < size; i++) {
135 buffer[i] = in.readObject();
136 }
137 head = 0;
138 tail = size;
139 }
140
141 //-----------------------------------------------------------------------
142 /**
143 * Returns the number of elements stored in the buffer.
144 *
145 * @return this buffer's size
146 */
147 public int size() {
148 int size = 0;
149
150 if (tail < head) {
151 size = buffer.length - head + tail;
152 } else {
153 size = tail - head;
154 }
155
156 return size;
157 }
158
159 /**
160 * Returns true if this buffer is empty; false otherwise.
161 *
162 * @return true if this buffer is empty
163 */
164 public boolean isEmpty() {
165 return (size() == 0);
166 }
167
168 /**
169 * Adds the given element to this buffer.
170 *
171 * @param obj the element to add
172 * @return true, always
173 * @throws NullPointerException if the given element is null
174 */
175 public boolean add(final Object obj) {
176 if (obj == null) {
177 throw new NullPointerException("Attempted to add null object to buffer");
178 }
179
180 if (size() + 1 >= buffer.length) {
181 // copy contents to a new buffer array
182 Object[] tmp = new Object[((buffer.length - 1) * 2) + 1];
183 int j = 0;
184 // move head to element zero in the new array
185 for (int i = head; i != tail;) {
186 tmp[j] = buffer[i];
187 buffer[i] = null;
188
189 j++;
190 i = increment(i);
191 }
192 buffer = tmp;
193 head = 0;
194 tail = j;
195 }
196
197 buffer[tail] = obj;
198 tail = increment(tail);
199 return true;
200 }
201
202 /**
203 * Returns the next object in the buffer.
204 *
205 * @return the next object in the buffer
206 * @throws BufferUnderflowException if this buffer is empty
207 */
208 public Object get() {
209 if (isEmpty()) {
210 throw new BufferUnderflowException("The buffer is already empty");
211 }
212
213 return buffer[head];
214 }
215
216 /**
217 * Removes the next object from the buffer
218 *
219 * @return the removed object
220 * @throws BufferUnderflowException if this buffer is empty
221 */
222 public Object remove() {
223 if (isEmpty()) {
224 throw new BufferUnderflowException("The buffer is already empty");
225 }
226
227 Object element = buffer[head];
228 if (element != null) {
229 buffer[head] = null;
230 head = increment(head);
231 }
232 return element;
233 }
234
235 /**
236 * Increments the internal index.
237 *
238 * @param index the index to increment
239 * @return the updated index
240 */
241 private int increment(int index) {
242 index++;
243 if (index >= buffer.length) {
244 index = 0;
245 }
246 return index;
247 }
248
249 /**
250 * Decrements the internal index.
251 *
252 * @param index the index to decrement
253 * @return the updated index
254 */
255 private int decrement(int index) {
256 index--;
257 if (index < 0) {
258 index = buffer.length - 1;
259 }
260 return index;
261 }
262
263 /**
264 * Returns an iterator over this buffer's elements.
265 *
266 * @return an iterator over this buffer's elements
267 */
268 public Iterator iterator() {
269 return new Iterator() {
270
271 private int index = head;
272 private int lastReturnedIndex = -1;
273
274 public boolean hasNext() {
275 return index != tail;
276
277 }
278
279 public Object next() {
280 if (!hasNext()) {
281 throw new NoSuchElementException();
282 }
283 lastReturnedIndex = index;
284 index = increment(index);
285 return buffer[lastReturnedIndex];
286 }
287
288 public void remove() {
289 if (lastReturnedIndex == -1) {
290 throw new IllegalStateException();
291 }
292
293 // First element can be removed quickly
294 if (lastReturnedIndex == head) {
295 UnboundedFifoBuffer.this.remove();
296 lastReturnedIndex = -1;
297 return;
298 }
299
300 // Other elements require us to shift the subsequent elements
301 int i = increment(lastReturnedIndex);
302 while (i != tail) {
303 buffer[decrement(i)] = buffer[i];
304 i = increment(i);
305 }
306
307 lastReturnedIndex = -1;
308 tail = decrement(tail);
309 buffer[tail] = null;
310 index = decrement(index);
311 }
312
313 };
314 }
315
316 }