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.Arrays;
  23. import java.util.Collection;
  24. import java.util.Iterator;
  25. import java.util.NoSuchElementException;
  26. import org.apache.commons.collections.BoundedCollection;
  27. import org.apache.commons.collections.Buffer;
  28. import org.apache.commons.collections.BufferOverflowException;
  29. import org.apache.commons.collections.BufferUnderflowException;
  30. /**
  31. * The BoundedFifoBuffer is a very efficient implementation of
  32. * Buffer that does not alter the size of the buffer at runtime.
  33. * <p>
  34. * The removal order of a <code>BoundedFifoBuffer</code> is based on the
  35. * insertion order; elements are removed in the same order in which they
  36. * were added. The iteration order is the same as the removal order.
  37. * <p>
  38. * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations
  39. * all perform in constant time. All other operations perform in linear
  40. * 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>BoundedFifoBuffer</code>:
  44. * <pre>
  45. * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer());
  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.8 $ $Date: 2004/06/02 23:12:44 $
  54. *
  55. * @author Avalon
  56. * @author Berin Loritsch
  57. * @author Paul Jack
  58. * @author Stephen Colebourne
  59. * @author Herve Quiroz
  60. */
  61. public class BoundedFifoBuffer extends AbstractCollection
  62. implements Buffer, BoundedCollection, Serializable {
  63. /** Serialization version */
  64. private static final long serialVersionUID = 5603722811189451017L;
  65. private transient Object[] elements;
  66. private transient int start = 0;
  67. private transient int end = 0;
  68. private transient boolean full = false;
  69. private final int maxElements;
  70. /**
  71. * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
  72. * 32 elements.
  73. */
  74. public BoundedFifoBuffer() {
  75. this(32);
  76. }
  77. /**
  78. * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold
  79. * the specified number of elements.
  80. *
  81. * @param size the maximum number of elements for this fifo
  82. * @throws IllegalArgumentException if the size is less than 1
  83. */
  84. public BoundedFifoBuffer(int size) {
  85. if (size <= 0) {
  86. throw new IllegalArgumentException("The size must be greater than 0");
  87. }
  88. elements = new Object[size];
  89. maxElements = elements.length;
  90. }
  91. /**
  92. * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all
  93. * of the elements in the specified collection. That collection's
  94. * elements will also be added to the buffer.
  95. *
  96. * @param coll the collection whose elements to add, may not be null
  97. * @throws NullPointerException if the collection is null
  98. */
  99. public BoundedFifoBuffer(Collection coll) {
  100. this(coll.size());
  101. addAll(coll);
  102. }
  103. //-----------------------------------------------------------------------
  104. /**
  105. * Write the buffer out using a custom routine.
  106. *
  107. * @param out the output stream
  108. * @throws IOException
  109. */
  110. private void writeObject(ObjectOutputStream out) throws IOException {
  111. out.defaultWriteObject();
  112. out.writeInt(size());
  113. for (Iterator it = iterator(); it.hasNext();) {
  114. out.writeObject(it.next());
  115. }
  116. }
  117. /**
  118. * Read the buffer in using a custom routine.
  119. *
  120. * @param in the input stream
  121. * @throws IOException
  122. * @throws ClassNotFoundException
  123. */
  124. private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
  125. in.defaultReadObject();
  126. elements = new Object[maxElements];
  127. int size = in.readInt();
  128. for (int i = 0; i < size; i++) {
  129. elements[i] = in.readObject();
  130. }
  131. start = 0;
  132. end = size;
  133. full = (size == maxElements);
  134. }
  135. //-----------------------------------------------------------------------
  136. /**
  137. * Returns the number of elements stored in the buffer.
  138. *
  139. * @return this buffer's size
  140. */
  141. public int size() {
  142. int size = 0;
  143. if (end < start) {
  144. size = maxElements - start + end;
  145. } else if (end == start) {
  146. size = (full ? maxElements : 0);
  147. } else {
  148. size = end - start;
  149. }
  150. return size;
  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. * Returns true if this collection is full and no new elements can be added.
  162. *
  163. * @return <code>true</code> if the collection is full
  164. */
  165. public boolean isFull() {
  166. return size() == maxElements;
  167. }
  168. /**
  169. * Gets the maximum size of the collection (the bound).
  170. *
  171. * @return the maximum number of elements the collection can hold
  172. */
  173. public int maxSize() {
  174. return maxElements;
  175. }
  176. /**
  177. * Clears this buffer.
  178. */
  179. public void clear() {
  180. full = false;
  181. start = 0;
  182. end = 0;
  183. Arrays.fill(elements, null);
  184. }
  185. /**
  186. * Adds the given element to this buffer.
  187. *
  188. * @param element the element to add
  189. * @return true, always
  190. * @throws NullPointerException if the given element is null
  191. * @throws BufferOverflowException if this buffer is full
  192. */
  193. public boolean add(Object element) {
  194. if (null == element) {
  195. throw new NullPointerException("Attempted to add null object to buffer");
  196. }
  197. if (full) {
  198. throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
  199. }
  200. elements[end++] = element;
  201. if (end >= maxElements) {
  202. end = 0;
  203. }
  204. if (end == start) {
  205. full = true;
  206. }
  207. return true;
  208. }
  209. /**
  210. * Returns the least recently inserted element in this buffer.
  211. *
  212. * @return the least recently inserted element
  213. * @throws BufferUnderflowException if the buffer is empty
  214. */
  215. public Object get() {
  216. if (isEmpty()) {
  217. throw new BufferUnderflowException("The buffer is already empty");
  218. }
  219. return elements[start];
  220. }
  221. /**
  222. * Removes the least recently inserted element from this buffer.
  223. *
  224. * @return the least recently inserted element
  225. * @throws BufferUnderflowException if the buffer is empty
  226. */
  227. public Object remove() {
  228. if (isEmpty()) {
  229. throw new BufferUnderflowException("The buffer is already empty");
  230. }
  231. Object element = elements[start];
  232. if (null != element) {
  233. elements[start++] = null;
  234. if (start >= maxElements) {
  235. start = 0;
  236. }
  237. full = false;
  238. }
  239. return element;
  240. }
  241. /**
  242. * Increments the internal index.
  243. *
  244. * @param index the index to increment
  245. * @return the updated index
  246. */
  247. private int increment(int index) {
  248. index++;
  249. if (index >= maxElements) {
  250. index = 0;
  251. }
  252. return index;
  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 = maxElements - 1;
  264. }
  265. return index;
  266. }
  267. /**
  268. * Returns an iterator over this buffer's elements.
  269. *
  270. * @return an iterator over this buffer's elements
  271. */
  272. public Iterator iterator() {
  273. return new Iterator() {
  274. private int index = start;
  275. private int lastReturnedIndex = -1;
  276. private boolean isFirst = full;
  277. public boolean hasNext() {
  278. return isFirst || (index != end);
  279. }
  280. public Object next() {
  281. if (!hasNext()) {
  282. throw new NoSuchElementException();
  283. }
  284. isFirst = false;
  285. lastReturnedIndex = index;
  286. index = increment(index);
  287. return elements[lastReturnedIndex];
  288. }
  289. public void remove() {
  290. if (lastReturnedIndex == -1) {
  291. throw new IllegalStateException();
  292. }
  293. // First element can be removed quickly
  294. if (lastReturnedIndex == start) {
  295. BoundedFifoBuffer.this.remove();
  296. lastReturnedIndex = -1;
  297. return;
  298. }
  299. // Other elements require us to shift the subsequent elements
  300. int i = lastReturnedIndex + 1;
  301. while (i != end) {
  302. if (i >= maxElements) {
  303. elements[i - 1] = elements[0];
  304. i = 0;
  305. } else {
  306. elements[i - 1] = elements[i];
  307. i++;
  308. }
  309. }
  310. lastReturnedIndex = -1;
  311. end = decrement(end);
  312. elements[end] = null;
  313. full = false;
  314. index = decrement(index);
  315. }
  316. };
  317. }
  318. }