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    }