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.Arrays;
025    import java.util.Collection;
026    import java.util.Iterator;
027    import java.util.NoSuchElementException;
028    
029    import org.apache.commons.collections.BoundedCollection;
030    import org.apache.commons.collections.Buffer;
031    import org.apache.commons.collections.BufferOverflowException;
032    import org.apache.commons.collections.BufferUnderflowException;
033    
034    /**
035     * The BoundedFifoBuffer is a very efficient implementation of
036     * <code>Buffer</code> that is of a fixed size.
037     * <p>
038     * The removal order of a <code>BoundedFifoBuffer</code> is based on the 
039     * insertion order; elements are removed in the same order in which they
040     * were added.  The iteration order is the same as the removal order.
041     * <p>
042     * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
043     * all perform in constant time.  All other operations perform in linear
044     * time or worse.
045     * <p>
046     * Note that this implementation is not synchronized.  The following can be
047     * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
048     * <pre>
049     *   Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
050     * </pre>
051     * <p>
052     * This buffer prevents null objects from being added.
053     * <p>
054     * This class is Serializable from Commons Collections 3.1.
055     *
056     * @since Commons Collections 3.0 (previously in main package v2.1)
057     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
058     * 
059     * @author Avalon
060     * @author Berin Loritsch
061     * @author Paul Jack
062     * @author Stephen Colebourne
063     * @author Herve Quiroz
064     */
065    public class BoundedFifoBuffer extends AbstractCollection
066            implements Buffer, BoundedCollection, Serializable {
067    
068        /** Serialization version */
069        private static final long serialVersionUID = 5603722811189451017L;
070    
071        /** Underlying storage array */
072        private transient Object[] elements;
073        
074        /** Array index of first (oldest) buffer element */
075        private transient int start = 0;
076        
077        /** 
078         * Index mod maxElements of the array position following the last buffer
079         * element.  Buffer elements start at elements[start] and "wrap around"
080         * elements[maxElements-1], ending at elements[decrement(end)].  
081         * For example, elements = {c,a,b}, start=1, end=1 corresponds to 
082         * the buffer [a,b,c].
083         */
084        private transient int end = 0;
085        
086        /** Flag to indicate if the buffer is currently full. */
087        private transient boolean full = false;
088        
089        /** Capacity of the buffer */
090        private final int maxElements;
091    
092        /**
093         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
094         * 32 elements.
095         */
096        public BoundedFifoBuffer() {
097            this(32);
098        }
099    
100        /**
101         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
102         * the specified number of elements.
103         *
104         * @param size  the maximum number of elements for this fifo
105         * @throws IllegalArgumentException  if the size is less than 1
106         */
107        public BoundedFifoBuffer(int size) {
108            if (size <= 0) {
109                throw new IllegalArgumentException("The size must be greater than 0");
110            }
111            elements = new Object[size];
112            maxElements = elements.length;
113        }
114    
115        /**
116         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
117         * of the elements in the specified collection. That collection's
118         * elements will also be added to the buffer.
119         *
120         * @param coll  the collection whose elements to add, may not be null
121         * @throws NullPointerException if the collection is null
122         */
123        public BoundedFifoBuffer(Collection coll) {
124            this(coll.size());
125            addAll(coll);
126        }
127    
128        //-----------------------------------------------------------------------
129        /**
130         * Write the buffer out using a custom routine.
131         * 
132         * @param out  the output stream
133         * @throws IOException
134         */
135        private void writeObject(ObjectOutputStream out) throws IOException {
136            out.defaultWriteObject();
137            out.writeInt(size());
138            for (Iterator it = iterator(); it.hasNext();) {
139                out.writeObject(it.next());
140            }
141        }
142    
143        /**
144         * Read the buffer in using a custom routine.
145         * 
146         * @param in  the input stream
147         * @throws IOException
148         * @throws ClassNotFoundException
149         */
150        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
151            in.defaultReadObject();
152            elements = new Object[maxElements];
153            int size = in.readInt();
154            for (int i = 0; i < size; i++) {
155                elements[i] = in.readObject();
156            }
157            start = 0;
158            full = (size == maxElements);
159            if (full) {
160                end = 0;
161            } else {
162                end = size;
163            }
164        }
165    
166        //-----------------------------------------------------------------------
167        /**
168         * Returns the number of elements stored in the buffer.
169         *
170         * @return this buffer's size
171         */
172        public int size() {
173            int size = 0;
174    
175            if (end < start) {
176                size = maxElements - start + end;
177            } else if (end == start) {
178                size = (full ? maxElements : 0);
179            } else {
180                size = end - start;
181            }
182    
183            return size;
184        }
185    
186        /**
187         * Returns true if this buffer is empty; false otherwise.
188         *
189         * @return true if this buffer is empty
190         */
191        public boolean isEmpty() {
192            return size() == 0;
193        }
194    
195        /**
196         * Returns true if this collection is full and no new elements can be added.
197         *
198         * @return <code>true</code> if the collection is full
199         */
200        public boolean isFull() {
201            return size() == maxElements;
202        }
203        
204        /**
205         * Gets the maximum size of the collection (the bound).
206         *
207         * @return the maximum number of elements the collection can hold
208         */
209        public int maxSize() {
210            return maxElements;
211        }
212        
213        /**
214         * Clears this buffer.
215         */
216        public void clear() {
217            full = false;
218            start = 0;
219            end = 0;
220            Arrays.fill(elements, null);
221        }
222    
223        /**
224         * Adds the given element to this buffer.
225         *
226         * @param element  the element to add
227         * @return true, always
228         * @throws NullPointerException  if the given element is null
229         * @throws BufferOverflowException  if this buffer is full
230         */
231        public boolean add(Object element) {
232            if (null == element) {
233                throw new NullPointerException("Attempted to add null object to buffer");
234            }
235    
236            if (full) {
237                throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
238            }
239    
240            elements[end++] = element;
241    
242            if (end >= maxElements) {
243                end = 0;
244            }
245    
246            if (end == start) {
247                full = true;
248            }
249    
250            return true;
251        }
252    
253        /**
254         * Returns the least recently inserted element in this buffer.
255         *
256         * @return the least recently inserted element
257         * @throws BufferUnderflowException  if the buffer is empty
258         */
259        public Object get() {
260            if (isEmpty()) {
261                throw new BufferUnderflowException("The buffer is already empty");
262            }
263    
264            return elements[start];
265        }
266    
267        /**
268         * Removes the least recently inserted element from this buffer.
269         *
270         * @return the least recently inserted element
271         * @throws BufferUnderflowException  if the buffer is empty
272         */
273        public Object remove() {
274            if (isEmpty()) {
275                throw new BufferUnderflowException("The buffer is already empty");
276            }
277    
278            Object element = elements[start];
279    
280            if (null != element) {
281                elements[start++] = null;
282    
283                if (start >= maxElements) {
284                    start = 0;
285                }
286    
287                full = false;
288            }
289    
290            return element;
291        }
292    
293        /**
294         * Increments the internal index.
295         * 
296         * @param index  the index to increment
297         * @return the updated index
298         */
299        private int increment(int index) {
300            index++; 
301            if (index >= maxElements) {
302                index = 0;
303            }
304            return index;
305        }
306    
307        /**
308         * Decrements the internal index.
309         * 
310         * @param index  the index to decrement
311         * @return the updated index
312         */
313        private int decrement(int index) {
314            index--;
315            if (index < 0) {
316                index = maxElements - 1;
317            }
318            return index;
319        }
320    
321        /**
322         * Returns an iterator over this buffer's elements.
323         *
324         * @return an iterator over this buffer's elements
325         */
326        public Iterator iterator() {
327            return new Iterator() {
328    
329                private int index = start;
330                private int lastReturnedIndex = -1;
331                private boolean isFirst = full;
332    
333                public boolean hasNext() {
334                    return isFirst || (index != end);
335                    
336                }
337    
338                public Object next() {
339                    if (!hasNext()) {
340                        throw new NoSuchElementException();
341                    }
342                    isFirst = false;
343                    lastReturnedIndex = index;
344                    index = increment(index);
345                    return elements[lastReturnedIndex];
346                }
347    
348                public void remove() {
349                    if (lastReturnedIndex == -1) {
350                        throw new IllegalStateException();
351                    }
352    
353                    // First element can be removed quickly
354                    if (lastReturnedIndex == start) {
355                        BoundedFifoBuffer.this.remove();
356                        lastReturnedIndex = -1;
357                        return;
358                    }
359    
360                    int pos = lastReturnedIndex + 1;
361                    if (start < lastReturnedIndex && pos < end) {
362                        // shift in one part
363                        System.arraycopy(elements, pos, elements,
364                                lastReturnedIndex, end - pos);
365                    } else {
366                        // Other elements require us to shift the subsequent elements
367                        while (pos != end) {
368                            if (pos >= maxElements) {
369                                elements[pos - 1] = elements[0];
370                                pos = 0;
371                            } else {
372                                elements[decrement(pos)] = elements[pos];
373                                pos = increment(pos);
374                            }
375                        }
376                    }
377    
378                    lastReturnedIndex = -1;
379                    end = decrement(end);
380                    elements[end] = null;
381                    full = false;
382                    index = decrement(index);
383                }
384    
385            };
386        }
387    
388    }