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