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