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;
018    
019    import java.util.AbstractCollection;
020    import java.util.Arrays;
021    import java.util.Collection;
022    import java.util.Iterator;
023    import java.util.NoSuchElementException;
024    
025    /**
026     * The BoundedFifoBuffer is a very efficient implementation of
027     * Buffer that does not alter the size of the buffer at runtime.
028     * <p>
029     * The removal order of a <code>BoundedFifoBuffer</code> is based on the 
030     * insertion order; elements are removed in the same order in which they
031     * were added.  The iteration order is the same as the removal order.
032     * <p>
033     * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
034     * all perform in constant time.  All other operations perform in linear
035     * time or worse.
036     * <p>
037     * Note that this implementation is not synchronized.  The following can be
038     * used to provide synchronized access to your <code>BoundedFifoBuffer</code>:
039     * <pre>
040     *   Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
041     * </pre>
042     * <p>
043     * This buffer prevents null objects from being added.
044     *
045     * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
046     * @since 2.1
047     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
048     * 
049     * @author Avalon
050     * @author Berin Loritsch
051     * @author Paul Jack
052     * @author Stephen Colebourne
053     * @author Herve Quiroz
054     */
055    public class BoundedFifoBuffer extends AbstractCollection
056            implements Buffer, BoundedCollection {
057                
058        private final Object[] m_elements;
059        private int m_start = 0;
060        private int m_end = 0;
061        private boolean m_full = false;
062        private final int maxElements;
063    
064        /**
065         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
066         * 32 elements.
067         */
068        public BoundedFifoBuffer() {
069            this(32);
070        }
071    
072        /**
073         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
074         * the specified number of elements.
075         *
076         * @param size  the maximum number of elements for this fifo
077         * @throws IllegalArgumentException  if the size is less than 1
078         */
079        public BoundedFifoBuffer(int size) {
080            if (size <= 0) {
081                throw new IllegalArgumentException("The size must be greater than 0");
082            }
083            m_elements = new Object[size];
084            maxElements = m_elements.length;
085        }
086    
087        /**
088         * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
089         * of the elements in the specified collection. That collection's
090         * elements will also be added to the buffer.
091         *
092         * @param coll  the collection whose elements to add, may not be null
093         * @throws NullPointerException if the collection is null
094         */
095        public BoundedFifoBuffer(Collection coll) {
096            this(coll.size());
097            addAll(coll);
098        }
099    
100        /**
101         * Returns the number of elements stored in the buffer.
102         *
103         * @return this buffer's size
104         */
105        public int size() {
106            int size = 0;
107    
108            if (m_end < m_start) {
109                size = maxElements - m_start + m_end;
110            } else if (m_end == m_start) {
111                size = (m_full ? maxElements : 0);
112            } else {
113                size = m_end - m_start;
114            }
115    
116            return size;
117        }
118    
119        /**
120         * Returns true if this buffer is empty; false otherwise.
121         *
122         * @return true if this buffer is empty
123         */
124        public boolean isEmpty() {
125            return size() == 0;
126        }
127    
128        /**
129         * Returns true if this collection is full and no new elements can be added.
130         *
131         * @return <code>true</code> if the collection is full
132         */
133        public boolean isFull() {
134            return size() == maxElements;
135        }
136        
137        /**
138         * Gets the maximum size of the collection (the bound).
139         *
140         * @return the maximum number of elements the collection can hold
141         */
142        public int maxSize() {
143            return maxElements;
144        }
145        
146        /**
147         * Clears this buffer.
148         */
149        public void clear() {
150            m_full = false;
151            m_start = 0;
152            m_end = 0;
153            Arrays.fill(m_elements, null);
154        }
155    
156        /**
157         * Adds the given element to this buffer.
158         *
159         * @param element  the element to add
160         * @return true, always
161         * @throws NullPointerException  if the given element is null
162         * @throws BufferOverflowException  if this buffer is full
163         */
164        public boolean add(Object element) {
165            if (null == element) {
166                throw new NullPointerException("Attempted to add null object to buffer");
167            }
168    
169            if (m_full) {
170                throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
171            }
172    
173            m_elements[m_end++] = element;
174    
175            if (m_end >= maxElements) {
176                m_end = 0;
177            }
178    
179            if (m_end == m_start) {
180                m_full = true;
181            }
182    
183            return true;
184        }
185    
186        /**
187         * Returns the least recently inserted element in this buffer.
188         *
189         * @return the least recently inserted element
190         * @throws BufferUnderflowException  if the buffer is empty
191         */
192        public Object get() {
193            if (isEmpty()) {
194                throw new BufferUnderflowException("The buffer is already empty");
195            }
196    
197            return m_elements[m_start];
198        }
199    
200        /**
201         * Removes the least recently inserted element from this buffer.
202         *
203         * @return the least recently inserted element
204         * @throws BufferUnderflowException  if the buffer is empty
205         */
206        public Object remove() {
207            if (isEmpty()) {
208                throw new BufferUnderflowException("The buffer is already empty");
209            }
210    
211            Object element = m_elements[m_start];
212    
213            if (null != element) {
214                m_elements[m_start++] = null;
215    
216                if (m_start >= maxElements) {
217                    m_start = 0;
218                }
219    
220                m_full = false;
221            }
222    
223            return element;
224        }
225    
226        /**
227         * Increments the internal index.
228         * 
229         * @param index  the index to increment
230         * @return the updated index
231         */
232        private int increment(int index) {
233            index++; 
234            if (index >= maxElements) {
235                index = 0;
236            }
237            return index;
238        }
239    
240        /**
241         * Decrements the internal index.
242         * 
243         * @param index  the index to decrement
244         * @return the updated index
245         */
246        private int decrement(int index) {
247            index--;
248            if (index < 0) {
249                index = maxElements - 1;
250            }
251            return index;
252        }
253    
254        /**
255         * Returns an iterator over this buffer's elements.
256         *
257         * @return an iterator over this buffer's elements
258         */
259        public Iterator iterator() {
260            return new Iterator() {
261    
262                private int index = m_start;
263                private int lastReturnedIndex = -1;
264                private boolean isFirst = m_full;
265    
266                public boolean hasNext() {
267                    return isFirst || (index != m_end);
268                    
269                }
270    
271                public Object next() {
272                    if (!hasNext()) throw new NoSuchElementException();
273                    isFirst = false;
274                    lastReturnedIndex = index;
275                    index = increment(index);
276                    return m_elements[lastReturnedIndex];
277                }
278    
279                public void remove() {
280                    if (lastReturnedIndex == -1) throw new IllegalStateException();
281    
282                    // First element can be removed quickly
283                    if (lastReturnedIndex == m_start) {
284                        BoundedFifoBuffer.this.remove();
285                        lastReturnedIndex = -1;
286                        return;
287                    }
288    
289                    // Other elements require us to shift the subsequent elements
290                    int i = lastReturnedIndex + 1;
291                    while (i != m_end) {
292                        if (i >= maxElements) {
293                            m_elements[i - 1] = m_elements[0];
294                            i = 0;
295                        } else {
296                            m_elements[i - 1] = m_elements[i];
297                            i++;
298                        }
299                    }
300    
301                    lastReturnedIndex = -1;
302                    m_end = decrement(m_end);
303                    m_elements[m_end] = null;
304                    m_full = false;
305                    index = decrement(index);
306                }
307    
308            };
309        }
310    
311    }