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.Arrays; 021 import java.util.Collection; 022 import java.util.Iterator; 023 import java.util.NoSuchElementException; 024 025 /** 026 * The BoundedFifoBuffer is a very efficient implementation of 027 * Buffer that does not alter the size of the buffer at runtime. 028 * <p> 029 * The removal order of a <code>BoundedFifoBuffer</code> is based on the 030 * insertion order; elements are removed in the same order in which they 031 * were added. The iteration order is the same as the removal order. 032 * <p> 033 * The {@link #add(Object)}, {@link #remove()} and {@link #get()} operations 034 * all perform in constant time. All other operations perform in linear 035 * time or worse. 036 * <p> 037 * Note that this implementation is not synchronized. The following can be 038 * used to provide synchronized access to your <code>BoundedFifoBuffer</code>: 039 * <pre> 040 * Buffer fifo = BufferUtils.synchronizedBuffer(new BoundedFifoBuffer()); 041 * </pre> 042 * <p> 043 * This buffer prevents null objects from being added. 044 * 045 * @deprecated Moved to buffer subpackage. Due to be removed in v4.0. 046 * @since 2.1 047 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $ 048 * 049 * @author Avalon 050 * @author Berin Loritsch 051 * @author Paul Jack 052 * @author Stephen Colebourne 053 * @author Herve Quiroz 054 */ 055 public class BoundedFifoBuffer extends AbstractCollection 056 implements Buffer, BoundedCollection { 057 058 private final Object[] m_elements; 059 private int m_start = 0; 060 private int m_end = 0; 061 private boolean m_full = false; 062 private final int maxElements; 063 064 /** 065 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold 066 * 32 elements. 067 */ 068 public BoundedFifoBuffer() { 069 this(32); 070 } 071 072 /** 073 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold 074 * the specified number of elements. 075 * 076 * @param size the maximum number of elements for this fifo 077 * @throws IllegalArgumentException if the size is less than 1 078 */ 079 public BoundedFifoBuffer(int size) { 080 if (size <= 0) { 081 throw new IllegalArgumentException("The size must be greater than 0"); 082 } 083 m_elements = new Object[size]; 084 maxElements = m_elements.length; 085 } 086 087 /** 088 * Constructs a new <code>BoundedFifoBuffer</code> big enough to hold all 089 * of the elements in the specified collection. That collection's 090 * elements will also be added to the buffer. 091 * 092 * @param coll the collection whose elements to add, may not be null 093 * @throws NullPointerException if the collection is null 094 */ 095 public BoundedFifoBuffer(Collection coll) { 096 this(coll.size()); 097 addAll(coll); 098 } 099 100 /** 101 * Returns the number of elements stored in the buffer. 102 * 103 * @return this buffer's size 104 */ 105 public int size() { 106 int size = 0; 107 108 if (m_end < m_start) { 109 size = maxElements - m_start + m_end; 110 } else if (m_end == m_start) { 111 size = (m_full ? maxElements : 0); 112 } else { 113 size = m_end - m_start; 114 } 115 116 return size; 117 } 118 119 /** 120 * Returns true if this buffer is empty; false otherwise. 121 * 122 * @return true if this buffer is empty 123 */ 124 public boolean isEmpty() { 125 return size() == 0; 126 } 127 128 /** 129 * Returns true if this collection is full and no new elements can be added. 130 * 131 * @return <code>true</code> if the collection is full 132 */ 133 public boolean isFull() { 134 return size() == maxElements; 135 } 136 137 /** 138 * Gets the maximum size of the collection (the bound). 139 * 140 * @return the maximum number of elements the collection can hold 141 */ 142 public int maxSize() { 143 return maxElements; 144 } 145 146 /** 147 * Clears this buffer. 148 */ 149 public void clear() { 150 m_full = false; 151 m_start = 0; 152 m_end = 0; 153 Arrays.fill(m_elements, null); 154 } 155 156 /** 157 * Adds the given element to this buffer. 158 * 159 * @param element the element to add 160 * @return true, always 161 * @throws NullPointerException if the given element is null 162 * @throws BufferOverflowException if this buffer is full 163 */ 164 public boolean add(Object element) { 165 if (null == element) { 166 throw new NullPointerException("Attempted to add null object to buffer"); 167 } 168 169 if (m_full) { 170 throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects."); 171 } 172 173 m_elements[m_end++] = element; 174 175 if (m_end >= maxElements) { 176 m_end = 0; 177 } 178 179 if (m_end == m_start) { 180 m_full = true; 181 } 182 183 return true; 184 } 185 186 /** 187 * Returns the least recently inserted element in this buffer. 188 * 189 * @return the least recently inserted element 190 * @throws BufferUnderflowException if the buffer is empty 191 */ 192 public Object get() { 193 if (isEmpty()) { 194 throw new BufferUnderflowException("The buffer is already empty"); 195 } 196 197 return m_elements[m_start]; 198 } 199 200 /** 201 * Removes the least recently inserted element from this buffer. 202 * 203 * @return the least recently inserted element 204 * @throws BufferUnderflowException if the buffer is empty 205 */ 206 public Object remove() { 207 if (isEmpty()) { 208 throw new BufferUnderflowException("The buffer is already empty"); 209 } 210 211 Object element = m_elements[m_start]; 212 213 if (null != element) { 214 m_elements[m_start++] = null; 215 216 if (m_start >= maxElements) { 217 m_start = 0; 218 } 219 220 m_full = false; 221 } 222 223 return element; 224 } 225 226 /** 227 * Increments the internal index. 228 * 229 * @param index the index to increment 230 * @return the updated index 231 */ 232 private int increment(int index) { 233 index++; 234 if (index >= maxElements) { 235 index = 0; 236 } 237 return index; 238 } 239 240 /** 241 * Decrements the internal index. 242 * 243 * @param index the index to decrement 244 * @return the updated index 245 */ 246 private int decrement(int index) { 247 index--; 248 if (index < 0) { 249 index = maxElements - 1; 250 } 251 return index; 252 } 253 254 /** 255 * Returns an iterator over this buffer's elements. 256 * 257 * @return an iterator over this buffer's elements 258 */ 259 public Iterator iterator() { 260 return new Iterator() { 261 262 private int index = m_start; 263 private int lastReturnedIndex = -1; 264 private boolean isFirst = m_full; 265 266 public boolean hasNext() { 267 return isFirst || (index != m_end); 268 269 } 270 271 public Object next() { 272 if (!hasNext()) throw new NoSuchElementException(); 273 isFirst = false; 274 lastReturnedIndex = index; 275 index = increment(index); 276 return m_elements[lastReturnedIndex]; 277 } 278 279 public void remove() { 280 if (lastReturnedIndex == -1) throw new IllegalStateException(); 281 282 // First element can be removed quickly 283 if (lastReturnedIndex == m_start) { 284 BoundedFifoBuffer.this.remove(); 285 lastReturnedIndex = -1; 286 return; 287 } 288 289 // Other elements require us to shift the subsequent elements 290 int i = lastReturnedIndex + 1; 291 while (i != m_end) { 292 if (i >= maxElements) { 293 m_elements[i - 1] = m_elements[0]; 294 i = 0; 295 } else { 296 m_elements[i - 1] = m_elements[i]; 297 i++; 298 } 299 } 300 301 lastReturnedIndex = -1; 302 m_end = decrement(m_end); 303 m_elements[m_end] = null; 304 m_full = false; 305 index = decrement(index); 306 } 307 308 }; 309 } 310 311 }