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.buffer;
17  
18  import java.io.IOException  ;
19  import java.io.ObjectInputStream  ;
20  import java.io.ObjectOutputStream  ;
21  import java.io.Serializable  ;
22  import java.util.AbstractCollection  ;
23  import java.util.Iterator  ;
24  import java.util.NoSuchElementException  ;
25  
26  import org.apache.commons.collections.Buffer;
27  import org.apache.commons.collections.BufferUnderflowException;
28  
29  /**
30   * UnboundedFifoBuffer is a very efficient buffer implementation.
31   * According to performance testing, it exhibits a constant access time, but it
32   * also outperforms ArrayList when used for the same purpose.
33   * <p>
34   * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion
35   * order; elements are removed in the same order in which they were added.
36   * The iteration order is the same as the removal order.
37   * <p>
38   * The {@link #remove()} and {@link #get()} operations perform in constant time.
39   * The {@link #add(Object)} operation performs in amortized constant time.  All
40   * other operations perform in linear time or worse.
41   * <p>
42   * Note that this implementation is not synchronized.  The following can be
43   * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>:
44   * <pre>
45   *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer());
46   * </pre>
47   * <p>
48   * This buffer prevents null objects from being added.
49   * <p>
50   * This class is Serializable from Commons Collections 3.1.
51   * 
52   * @since Commons Collections 3.0 (previously in main package v2.1)
53   * @version $Revision: 1.9 $ $Date: 2004/06/01 22:57:18 $
54   *
55   * @author Avalon
56   * @author Federico Barbieri
57   * @author Berin Loritsch
58   * @author Paul Jack
59   * @author Stephen Colebourne
60   */
61  public class UnboundedFifoBuffer extends AbstractCollection   implements Buffer, Serializable   {
62  
63      /** Serialization vesrion */
64      private static final long serialVersionUID = -3482960336579541419L;
65  
66      /** The array of objects in the buffer. */
67      protected transient Object  [] buffer;
68      /** The current head index. */
69      protected transient int head;
70      /** The current tail index. */
71      protected transient int tail;
72  
73      /**
74       * Constructs an UnboundedFifoBuffer with the default number of elements.
75       * It is exactly the same as performing the following:
76       *
77       * <pre>
78       *   new UnboundedFifoBuffer(32);
79       * </pre>
80       */
81      public UnboundedFifoBuffer() {
82          this(32);
83      }
84  
85      /**
86       * Constructs an UnboundedFifoBuffer with the specified number of elements.
87       * The integer must be a positive integer.
88       * 
89       * @param initialSize  the initial size of the buffer
90       * @throws IllegalArgumentException  if the size is less than 1
91       */
92      public UnboundedFifoBuffer(int initialSize) {
93          if (initialSize <= 0) {
94              throw new IllegalArgumentException  ("The size must be greater than 0");
95          }
96          buffer = new Object  [initialSize + 1];
97          head = 0;
98          tail = 0;
99      }
100 
101     //-----------------------------------------------------------------------
102     /**
103      * Write the buffer out using a custom routine.
104      * 
105      * @param out  the output stream
106      * @throws IOException
107      */
108     private void writeObject(ObjectOutputStream   out) throws IOException   {
109         out.defaultWriteObject();
110         out.writeInt(size());
111         for (Iterator   it = iterator(); it.hasNext();) {
112             out.writeObject(it.next());
113         }
114     }
115 
116     /**
117      * Read the buffer in using a custom routine.
118      * 
119      * @param in  the input stream
120      * @throws IOException
121      * @throws ClassNotFoundException
122      */
123     private void readObject(ObjectInputStream   in) throws IOException  , ClassNotFoundException   {
124         in.defaultReadObject();
125         int size = in.readInt();
126         buffer = new Object  [size];
127         for (int i = 0; i < size; i++) {
128             buffer[i] = in.readObject();
129         }
130         head = 0;
131         tail = size;
132     }
133 
134     //-----------------------------------------------------------------------
135     /**
136      * Returns the number of elements stored in the buffer.
137      *
138      * @return this buffer's size
139      */
140     public int size() {
141         int size = 0;
142 
143         if (tail < head) {
144             size = buffer.length - head + tail;
145         } else {
146             size = tail - head;
147         }
148 
149         return size;
150     }
151 
152     /**
153      * Returns true if this buffer is empty; false otherwise.
154      *
155      * @return true if this buffer is empty
156      */
157     public boolean isEmpty() {
158         return (size() == 0);
159     }
160 
161     /**
162      * Adds the given element to this buffer.
163      *
164      * @param obj  the element to add
165      * @return true, always
166      * @throws NullPointerException  if the given element is null
167      */
168     public boolean add(final Object   obj) {
169         if (obj == null) {
170             throw new NullPointerException  ("Attempted to add null object to buffer");
171         }
172 
173         if (size() + 1 >= buffer.length) {
174             Object  [] tmp = new Object  [((buffer.length - 1) * 2) + 1];
175 
176             int j = 0;
177             for (int i = head; i != tail;) {
178                 tmp[j] = buffer[i];
179                 buffer[i] = null;
180 
181                 j++;
182                 i++;
183                 if (i == buffer.length) {
184                     i = 0;
185                 }
186             }
187 
188             buffer = tmp;
189             head = 0;
190             tail = j;
191         }
192 
193         buffer[tail] = obj;
194         tail++;
195         if (tail >= buffer.length) {
196             tail = 0;
197         }
198         return true;
199     }
200 
201     /**
202      * Returns the next object in the buffer.
203      *
204      * @return the next object in the buffer
205      * @throws BufferUnderflowException  if this buffer is empty
206      */
207     public Object   get() {
208         if (isEmpty()) {
209             throw new BufferUnderflowException("The buffer is already empty");
210         }
211 
212         return buffer[head];
213     }
214 
215     /**
216      * Removes the next object from the buffer
217      *
218      * @return the removed object
219      * @throws BufferUnderflowException  if this buffer is empty
220      */
221     public Object   remove() {
222         if (isEmpty()) {
223             throw new BufferUnderflowException("The buffer is already empty");
224         }
225 
226         Object   element = buffer[head];
227 
228         if (null != element) {
229             buffer[head] = null;
230 
231             head++;
232             if (head >= buffer.length) {
233                 head = 0;
234             }
235         }
236 
237         return element;
238     }
239 
240     /**
241      * Increments the internal index.
242      * 
243      * @param index  the index to increment
244      * @return the updated index
245      */
246     private int increment(int index) {
247         index++;
248         if (index >= buffer.length) {
249             index = 0;
250         }
251         return index;
252     }
253 
254     /**
255      * Decrements the internal index.
256      * 
257      * @param index  the index to decrement
258      * @return the updated index
259      */
260     private int decrement(int index) {
261         index--;
262         if (index < 0) {
263             index = buffer.length - 1;
264         }
265         return index;
266     }
267 
268     /**
269      * Returns an iterator over this buffer's elements.
270      *
271      * @return an iterator over this buffer's elements
272      */
273     public Iterator   iterator() {
274         return new Iterator  () {
275 
276             private int index = head;
277             private int lastReturnedIndex = -1;
278 
279             public boolean hasNext() {
280                 return index != tail;
281 
282             }
283 
284             public Object   next() {
285                 if (!hasNext()) {
286                     throw new NoSuchElementException  ();
287                 }
288                 lastReturnedIndex = index;
289                 index = increment(index);
290                 return buffer[lastReturnedIndex];
291             }
292 
293             public void remove() {
294                 if (lastReturnedIndex == -1) {
295                     throw new IllegalStateException  ();
296                 }
297 
298                 // First element can be removed quickly
299                 if (lastReturnedIndex == head) {
300                     UnboundedFifoBuffer.this.remove();
301                     lastReturnedIndex = -1;
302                     return;
303                 }
304 
305                 // Other elements require us to shift the subsequent elements
306                 int i = lastReturnedIndex + 1;
307                 while (i != tail) {
308                     if (i >= buffer.length) {
309                         buffer[i - 1] = buffer[0];
310                         i = 0;
311                     } else {
312                         buffer[i - 1] = buffer[i];
313                         i++;
314                     }
315                 }
316 
317                 lastReturnedIndex = -1;
318                 tail = decrement(tail);
319                 buffer[tail] = null;
320                 index = decrement(index);
321             }
322 
323         };
324     }
325     
326 }
327
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags