UnboundedFifoBuffer


1   /*
2    *  Copyright 2002-2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.apache.commons.collections;
17  
18  import java.util.AbstractCollection  ;
19  import java.util.Iterator  ;
20  import java.util.NoSuchElementException  ;
21  
22  /**
23   * UnboundedFifoBuffer is a very efficient buffer implementation.
24   * According to performance testing, it exhibits a constant access time, but it
25   * also outperforms ArrayList when used for the same purpose.
26   * <p>
27   * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
28   * order; elements are removed in the same order in which they were added.
29   * The iteration order is the same as the removal order.
30   * <p>
31   * The {@link #remove()} and {@link #get()} operations perform in constant time.
32   * The {@link #add(Object)} operation performs in amortized constant time.  All
33   * other operations perform in linear time or worse.
34   * <p>
35   * Note that this implementation is not synchronized.  The following can be
36   * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
37   * <pre>
38   *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
39   * </pre>
40   * <p>
41   * This buffer prevents null objects from being added.
42   * 
43   * @deprecated Moved to buffer subpackage. Due to be removed in v4.0.
44   * @since Commons Collections 2.1
45   * @version $Revision: 1.15 $ $Date: 2004/02/18 01:15:42 $
46   *
47   * @author Avalon
48   * @author Federico Barbieri
49   * @author Berin Loritsch
50   * @author Paul Jack
51   * @author Stephen Colebourne
52   */
53  public class UnboundedFifoBuffer extends AbstractCollection   implements Buffer {
54      
55      protected Object  [] m_buffer;
56      protected int m_head;
57      protected int m_tail;
58  
59      /**
60       * Constructs an UnboundedFifoBuffer with the default number of elements.
61       * It is exactly the same as performing the following:
62       *
63       * <pre>
64       *   new UnboundedFifoBuffer(32);
65       * </pre>
66       */
67      public UnboundedFifoBuffer() {
68          this(32);
69      }
70  
71      /**
72       * Constructs an UnboundedFifoBuffer with the specified number of elements.
73       * The integer must be a positive integer.
74       * 
75       * @param initialSize  the initial size of the buffer
76       * @throws IllegalArgumentException  if the size is less than 1
77       */
78      public UnboundedFifoBuffer(int initialSize) {
79          if (initialSize <= 0) {
80              throw new IllegalArgumentException  ("The size must be greater than 0");
81          }
82          m_buffer = new Object  [initialSize + 1];
83          m_head = 0;
84          m_tail = 0;
85      }
86  
87      /**
88       * Returns the number of elements stored in the buffer.
89       *
90       * @return this buffer's size
91       */
92      public int size() {
93          int size = 0;
94  
95          if (m_tail < m_head) {
96              size = m_buffer.length - m_head + m_tail;
97          } else {
98              size = m_tail - m_head;
99          }
100 
101         return size;
102     }
103 
104     /**
105      * Returns true if this buffer is empty; false otherwise.
106      *
107      * @return true if this buffer is empty
108      */
109     public boolean isEmpty() {
110         return (size() == 0);
111     }
112 
113     /**
114      * Adds the given element to this buffer.
115      *
116      * @param obj  the element to add
117      * @return true, always
118      * @throws NullPointerException  if the given element is null
119      * @throws BufferOverflowException  if this buffer is full
120      */
121     public boolean add(final Object   obj) {
122         if (obj == null) {
123             throw new NullPointerException  ("Attempted to add null object to buffer");
124         }
125 
126         if (size() + 1 >= m_buffer.length) {
127             Object  [] tmp = new Object  [((m_buffer.length - 1) * 2) + 1];
128 
129             int j = 0;
130             for (int i = m_head; i != m_tail;) {
131                 tmp[j] = m_buffer[i];
132                 m_buffer[i] = null;
133 
134                 j++;
135                 i++;
136                 if (i == m_buffer.length) {
137                     i = 0;
138                 }
139             }
140 
141             m_buffer = tmp;
142             m_head = 0;
143             m_tail = j;
144         }
145 
146         m_buffer[m_tail] = obj;
147         m_tail++;
148         if (m_tail >= m_buffer.length) {
149             m_tail = 0;
150         }
151         return true;
152     }
153 
154     /**
155      * Returns the next object in the buffer.
156      *
157      * @return the next object in the buffer
158      * @throws BufferUnderflowException  if this buffer is empty
159      */
160     public Object   get() {
161         if (isEmpty()) {
162             throw new BufferUnderflowException("The buffer is already empty");
163         }
164 
165         return m_buffer[m_head];
166     }
167 
168     /**
169      * Removes the next object from the buffer
170      *
171      * @return the removed object
172      * @throws BufferUnderflowException  if this buffer is empty
173      */
174     public Object   remove() {
175         if (isEmpty()) {
176             throw new BufferUnderflowException("The buffer is already empty");
177         }
178 
179         Object   element = m_buffer[m_head];
180 
181         if (null != element) {
182             m_buffer[m_head] = null;
183 
184             m_head++;
185             if (m_head >= m_buffer.length) {
186                 m_head = 0;
187             }
188         }
189 
190         return element;
191     }
192 
193     /**
194      * Increments the internal index.
195      * 
196      * @param index  the index to increment
197      * @return the updated index
198      */
199     private int increment(int index) {
200         index++;
201         if (index >= m_buffer.length) {
202             index = 0;
203         }
204         return index;
205     }
206 
207     /**
208      * Decrements the internal index.
209      * 
210      * @param index  the index to decrement
211      * @return the updated index
212      */
213     private int decrement(int index) {
214         index--;
215         if (index < 0) {
216             index = m_buffer.length - 1;
217         }
218         return index;
219     }
220 
221     /**
222      * Returns an iterator over this buffer's elements.
223      *
224      * @return an iterator over this buffer's elements
225      */
226     public Iterator   iterator() {
227         return new Iterator  () {
228 
229             private int index = m_head;
230             private int lastReturnedIndex = -1;
231 
232             public boolean hasNext() {
233                 return index != m_tail;
234 
235             }
236 
237             public Object   next() {
238                 if (!hasNext())
239                     throw new NoSuchElementException  ();
240                 lastReturnedIndex = index;
241                 index = increment(index);
242                 return m_buffer[lastReturnedIndex];
243             }
244 
245             public void remove() {
246                 if (lastReturnedIndex == -1)
247                     throw new IllegalStateException  ();
248 
249                 // First element can be removed quickly
250                 if (lastReturnedIndex == m_head) {
251                     UnboundedFifoBuffer.this.remove();
252                     lastReturnedIndex = -1;
253                     return;
254                 }
255 
256                 // Other elements require us to shift the subsequent elements
257                 int i = lastReturnedIndex + 1;
258                 while (i != m_tail) {
259                     if (i >= m_buffer.length) {
260                         m_buffer[i - 1] = m_buffer[0];
261                         i = 0;
262                     } else {
263                         m_buffer[i - 1] = m_buffer[i];
264                         i++;
265                     }
266                 }
267 
268                 lastReturnedIndex = -1;
269                 m_tail = decrement(m_tail);
270                 m_buffer[m_tail] = null;
271                 index = decrement(index);
272             }
273 
274         };
275     }
276     
277 }
278
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags