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.Iterator;
021    import java.util.NoSuchElementException;
022    
023    /**
024     * UnboundedFifoBuffer is a very efficient buffer implementation.
025     * According to performance testing, it exhibits a constant access time, but it
026     * also outperforms ArrayList when used for the same purpose.
027     * <p>
028     * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
029     * order; elements are removed in the same order in which they were added.
030     * The iteration order is the same as the removal order.
031     * <p>
032     * The {@link #remove()} and {@link #get()} operations perform in constant time.
033     * The {@link #add(Object)} operation performs in amortized constant time.  All
034     * other operations perform in linear time or worse.
035     * <p>
036     * Note that this implementation is not synchronized.  The following can be
037     * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
038     * <pre>
039     *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
040     * </pre>
041     * <p>
042     * This buffer prevents null objects from being added.
043     * 
044     * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
045     * @since Commons Collections 2.1
046     * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
047     *
048     * @author Avalon
049     * @author Federico Barbieri
050     * @author Berin Loritsch
051     * @author Paul Jack
052     * @author Stephen Colebourne
053     * @author Andreas Schlosser
054     */
055    public class UnboundedFifoBuffer extends AbstractCollection implements Buffer {
056        
057        protected Object[] m_buffer;
058        protected int m_head;
059        protected int m_tail;
060    
061        /**
062         * Constructs an UnboundedFifoBuffer with the default number of elements.
063         * It is exactly the same as performing the following:
064         *
065         * <pre>
066         *   new UnboundedFifoBuffer(32);
067         * </pre>
068         */
069        public UnboundedFifoBuffer() {
070            this(32);
071        }
072    
073        /**
074         * Constructs an UnboundedFifoBuffer with the specified number of elements.
075         * The integer must be a positive integer.
076         * 
077         * @param initialSize  the initial size of the buffer
078         * @throws IllegalArgumentException  if the size is less than 1
079         */
080        public UnboundedFifoBuffer(int initialSize) {
081            if (initialSize <= 0) {
082                throw new IllegalArgumentException("The size must be greater than 0");
083            }
084            m_buffer = new Object[initialSize + 1];
085            m_head = 0;
086            m_tail = 0;
087        }
088    
089        /**
090         * Returns the number of elements stored in the buffer.
091         *
092         * @return this buffer's size
093         */
094        public int size() {
095            int size = 0;
096    
097            if (m_tail < m_head) {
098                size = m_buffer.length - m_head + m_tail;
099            } else {
100                size = m_tail - m_head;
101            }
102    
103            return size;
104        }
105    
106        /**
107         * Returns true if this buffer is empty; false otherwise.
108         *
109         * @return true if this buffer is empty
110         */
111        public boolean isEmpty() {
112            return (size() == 0);
113        }
114    
115        /**
116         * Adds the given element to this buffer.
117         *
118         * @param obj  the element to add
119         * @return true, always
120         * @throws NullPointerException  if the given element is null
121         * @throws BufferOverflowException  if this buffer is full
122         */
123        public boolean add(final Object obj) {
124            if (obj == null) {
125                throw new NullPointerException("Attempted to add null object to buffer");
126            }
127    
128            if (size() + 1 >= m_buffer.length) {
129                Object[] tmp = new Object[((m_buffer.length - 1) * 2) + 1];
130    
131                int j = 0;
132                for (int i = m_head; i != m_tail;) {
133                    tmp[j] = m_buffer[i];
134                    m_buffer[i] = null;
135    
136                    j++;
137                    i++;
138                    if (i == m_buffer.length) {
139                        i = 0;
140                    }
141                }
142    
143                m_buffer = tmp;
144                m_head = 0;
145                m_tail = j;
146            }
147    
148            m_buffer[m_tail] = obj;
149            m_tail++;
150            if (m_tail >= m_buffer.length) {
151                m_tail = 0;
152            }
153            return true;
154        }
155    
156        /**
157         * Returns the next object in the buffer.
158         *
159         * @return the next object in the buffer
160         * @throws BufferUnderflowException  if this buffer is empty
161         */
162        public Object get() {
163            if (isEmpty()) {
164                throw new BufferUnderflowException("The buffer is already empty");
165            }
166    
167            return m_buffer[m_head];
168        }
169    
170        /**
171         * Removes the next object from the buffer
172         *
173         * @return the removed object
174         * @throws BufferUnderflowException  if this buffer is empty
175         */
176        public Object remove() {
177            if (isEmpty()) {
178                throw new BufferUnderflowException("The buffer is already empty");
179            }
180    
181            Object element = m_buffer[m_head];
182    
183            if (null != element) {
184                m_buffer[m_head] = null;
185    
186                m_head++;
187                if (m_head >= m_buffer.length) {
188                    m_head = 0;
189                }
190            }
191    
192            return element;
193        }
194    
195        /**
196         * Increments the internal index.
197         * 
198         * @param index  the index to increment
199         * @return the updated index
200         */
201        private int increment(int index) {
202            index++;
203            if (index >= m_buffer.length) {
204                index = 0;
205            }
206            return index;
207        }
208    
209        /**
210         * Decrements the internal index.
211         * 
212         * @param index  the index to decrement
213         * @return the updated index
214         */
215        private int decrement(int index) {
216            index--;
217            if (index < 0) {
218                index = m_buffer.length - 1;
219            }
220            return index;
221        }
222    
223        /**
224         * Returns an iterator over this buffer's elements.
225         *
226         * @return an iterator over this buffer's elements
227         */
228        public Iterator iterator() {
229            return new Iterator() {
230    
231                private int index = m_head;
232                private int lastReturnedIndex = -1;
233    
234                public boolean hasNext() {
235                    return index != m_tail;
236    
237                }
238    
239                public Object next() {
240                    if (!hasNext())
241                        throw new NoSuchElementException();
242                    lastReturnedIndex = index;
243                    index = increment(index);
244                    return m_buffer[lastReturnedIndex];
245                }
246    
247                public void remove() {
248                    if (lastReturnedIndex == -1)
249                        throw new IllegalStateException();
250    
251                    // First element can be removed quickly
252                    if (lastReturnedIndex == m_head) {
253                        UnboundedFifoBuffer.this.remove();
254                        lastReturnedIndex = -1;
255                        return;
256                    }
257    
258                    // Other elements require us to shift the subsequent elements
259                    int i = increment(lastReturnedIndex);
260                    while (i != m_tail) {
261                        m_buffer[decrement(i)] = m_buffer[i];
262                        i = increment(i);
263                    }
264    
265                    lastReturnedIndex = -1;
266                    m_tail = decrement(m_tail);
267                    m_buffer[m_tail] = null;
268                    index = decrement(index);
269                }
270    
271            };
272        }
273        
274    }