001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.collections; 018 019 import java.util.AbstractCollection; 020 import java.util.Iterator; 021 import java.util.NoSuchElementException; 022 023 /** 024 * UnboundedFifoBuffer is a very efficient buffer implementation. 025 * According to performance testing, it exhibits a constant access time, but it 026 * also outperforms ArrayList when used for the same purpose. 027 * <p> 028 * The removal order of an <code>UnboundedFifoBuffer</code> is based on the insertion 029 * order; elements are removed in the same order in which they were added. 030 * The iteration order is the same as the removal order. 031 * <p> 032 * The {@link #remove()} and {@link #get()} operations perform in constant time. 033 * The {@link #add(Object)} operation performs in amortized constant time. All 034 * other operations perform in linear time or worse. 035 * <p> 036 * Note that this implementation is not synchronized. The following can be 037 * used to provide synchronized access to your <code>UnboundedFifoBuffer</code>: 038 * <pre> 039 * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoBuffer()); 040 * </pre> 041 * <p> 042 * This buffer prevents null objects from being added. 043 * 044 * @deprecated Moved to buffer subpackage. Due to be removed in v4.0. 045 * @since Commons Collections 2.1 046 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 047 * 048 * @author Avalon 049 * @author Federico Barbieri 050 * @author Berin Loritsch 051 * @author Paul Jack 052 * @author Stephen Colebourne 053 * @author Andreas Schlosser 054 */ 055 public class UnboundedFifoBuffer extends AbstractCollection implements Buffer { 056 057 protected Object[] m_buffer; 058 protected int m_head; 059 protected int m_tail; 060 061 /** 062 * Constructs an UnboundedFifoBuffer with the default number of elements. 063 * It is exactly the same as performing the following: 064 * 065 * <pre> 066 * new UnboundedFifoBuffer(32); 067 * </pre> 068 */ 069 public UnboundedFifoBuffer() { 070 this(32); 071 } 072 073 /** 074 * Constructs an UnboundedFifoBuffer with the specified number of elements. 075 * The integer must be a positive integer. 076 * 077 * @param initialSize the initial size of the buffer 078 * @throws IllegalArgumentException if the size is less than 1 079 */ 080 public UnboundedFifoBuffer(int initialSize) { 081 if (initialSize <= 0) { 082 throw new IllegalArgumentException("The size must be greater than 0"); 083 } 084 m_buffer = new Object[initialSize + 1]; 085 m_head = 0; 086 m_tail = 0; 087 } 088 089 /** 090 * Returns the number of elements stored in the buffer. 091 * 092 * @return this buffer's size 093 */ 094 public int size() { 095 int size = 0; 096 097 if (m_tail < m_head) { 098 size = m_buffer.length - m_head + m_tail; 099 } else { 100 size = m_tail - m_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 obj the element to add 119 * @return true, always 120 * @throws NullPointerException if the given element is null 121 * @throws BufferOverflowException if this buffer is full 122 */ 123 public boolean add(final Object obj) { 124 if (obj == null) { 125 throw new NullPointerException("Attempted to add null object to buffer"); 126 } 127 128 if (size() + 1 >= m_buffer.length) { 129 Object[] tmp = new Object[((m_buffer.length - 1) * 2) + 1]; 130 131 int j = 0; 132 for (int i = m_head; i != m_tail;) { 133 tmp[j] = m_buffer[i]; 134 m_buffer[i] = null; 135 136 j++; 137 i++; 138 if (i == m_buffer.length) { 139 i = 0; 140 } 141 } 142 143 m_buffer = tmp; 144 m_head = 0; 145 m_tail = j; 146 } 147 148 m_buffer[m_tail] = obj; 149 m_tail++; 150 if (m_tail >= m_buffer.length) { 151 m_tail = 0; 152 } 153 return true; 154 } 155 156 /** 157 * Returns the next object in the buffer. 158 * 159 * @return the next object in the buffer 160 * @throws BufferUnderflowException if this buffer is empty 161 */ 162 public Object get() { 163 if (isEmpty()) { 164 throw new BufferUnderflowException("The buffer is already empty"); 165 } 166 167 return m_buffer[m_head]; 168 } 169 170 /** 171 * Removes the next object from the buffer 172 * 173 * @return the removed object 174 * @throws BufferUnderflowException if this buffer is empty 175 */ 176 public Object remove() { 177 if (isEmpty()) { 178 throw new BufferUnderflowException("The buffer is already empty"); 179 } 180 181 Object element = m_buffer[m_head]; 182 183 if (null != element) { 184 m_buffer[m_head] = null; 185 186 m_head++; 187 if (m_head >= m_buffer.length) { 188 m_head = 0; 189 } 190 } 191 192 return element; 193 } 194 195 /** 196 * Increments the internal index. 197 * 198 * @param index the index to increment 199 * @return the updated index 200 */ 201 private int increment(int index) { 202 index++; 203 if (index >= m_buffer.length) { 204 index = 0; 205 } 206 return index; 207 } 208 209 /** 210 * Decrements the internal index. 211 * 212 * @param index the index to decrement 213 * @return the updated index 214 */ 215 private int decrement(int index) { 216 index--; 217 if (index < 0) { 218 index = m_buffer.length - 1; 219 } 220 return index; 221 } 222 223 /** 224 * Returns an iterator over this buffer's elements. 225 * 226 * @return an iterator over this buffer's elements 227 */ 228 public Iterator iterator() { 229 return new Iterator() { 230 231 private int index = m_head; 232 private int lastReturnedIndex = -1; 233 234 public boolean hasNext() { 235 return index != m_tail; 236 237 } 238 239 public Object next() { 240 if (!hasNext()) 241 throw new NoSuchElementException(); 242 lastReturnedIndex = index; 243 index = increment(index); 244 return m_buffer[lastReturnedIndex]; 245 } 246 247 public void remove() { 248 if (lastReturnedIndex == -1) 249 throw new IllegalStateException(); 250 251 // First element can be removed quickly 252 if (lastReturnedIndex == m_head) { 253 UnboundedFifoBuffer.this.remove(); 254 lastReturnedIndex = -1; 255 return; 256 } 257 258 // Other elements require us to shift the subsequent elements 259 int i = increment(lastReturnedIndex); 260 while (i != m_tail) { 261 m_buffer[decrement(i)] = m_buffer[i]; 262 i = increment(i); 263 } 264 265 lastReturnedIndex = -1; 266 m_tail = decrement(m_tail); 267 m_buffer[m_tail] = null; 268 index = decrement(index); 269 } 270 271 }; 272 } 273 274 }