001/* 002Copyright (c) 2022-2023 Steve Shering 003 004All rights reserved. 005 006As a special exception, the copyright holder of this software gives you permission 007to use this software for personal, not-for-profit purposes. 008 009For any other purpose, a license must be obtained from the copyright holder. 010 011This copyright notice and this permission notice must be included in all copies 012of this software, including copies of parts of this software. 013 014THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 015IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 016FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 017AUTHOR OR COPYRIGHT HOLDER BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 018LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 019OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 020THE SOFTWARE. 021*/ 022package net.sherst.util; 023 024import java.io.Reader; 025import java.lang.reflect.Array; 026import java.util.ArrayList; 027import java.util.Collection; 028import java.util.List; 029import java.util.Objects; 030 031/** 032 * A simple fast ring buffer (circular buffer) implementation for Java. 033 * <p> 034 * A ring buffer is a fixed-size first in - first out buffer 035 * typically backed by an array with head and tail pointers. 036 * Elements are added to the tail of the buffer and removed from the head. 037 * When the end of the array is reached, the pointers wrap around to the beginning. 038 * When the buffer is full, adding new elements overwrites the oldest elements 039 * (but see the {@link offer(E)} and {@link offer(E[])} methods in this implementation). 040 * <p> 041 * Pros: Fast, simple. 042 * <p> 043 * Cons: Size fixed at creation time, 044 * adding new elements overwrites the oldest ones if the buffer is full, 045 * elements can only be added or removed in FIFO order. 046 * <p> 047 * There are some useful look-ahead methods, {@link #peek()}, {@link #peek(int)}, {@link #at(E)}, 048 * {@link #at(E[])}, {@link #atSkip(E)} 049 * and {@link #atSkip(E[])}. 050 * <p> 051 * These are simple, hopefully fast, implementations. 052 * They deliberately do not implement Java's {@link java.util.Collection} or {@link java.util.Queue} interfaces, 053 * although the API is similar. 054 * <p> 055 * Variants:<ul> 056 * <li>{@link FastRingBuffer}: Simplest, fastest, not thread safe. 057 * <li>{@link SafeRingBuffer}: Thread safe. 058 * <li>{@link BlockingRingBuffer}: add and remove methods block if necessary; offer and poll methods are non-blocking. 059 * </ul> 060 * <p> 061 * {@link #remove()} sets the underlying array slot to {@code null} to avoid memory leaks. 062 * All other {@code remove} and {@code poll} methods call {@link #remove()}. 063 * <p> 064 * {@link #clear()} discards the underlying array to avoid memory leaks. 065 * {@link #removeAll()} calls {@link #clear()}. 066 * <p> 067 * Elements can be {@code null}, but this means that, 068 * if {@link #peek()}, {@link #poll()} or {@link #remove()} return null, 069 * this could be because an element was {@code null} or because the buffer was empty. 070 * Consider using {@link #isEmpty()} or {@link #size()} to disambiguate. 071 * <p> 072 * {@link #poll()} might seem redundant, but is overridden in {@link BlockingRingBuffer}. 073 * 074 * @param <E> the type of elements in the buffer 075 * @author sherstDotNet@yahoo.com 076 */ 077public class FastRingBuffer<E> { 078 private E[] arr; 079 protected int capacity=0; 080 protected int count=0; 081 private int head=0; 082 private int tail=0; 083 084 /** 085 * Creates a new buffer. 086 * 087 * @param capacity Maximum capacity of the buffer 088 */ 089 public FastRingBuffer(int capacity) { 090 this.capacity=capacity; 091 clear(); 092 } 093 094 /** 095 * Adds an element to the buffer. 096 * If the buffer is full, silently overwrites the oldest element. 097 * 098 * @param e the element to add 099 * @return {@code true} 100 */ 101 public boolean add(E e) { 102 arr[tail]=e; 103 if (count<capacity) 104 count++; 105 else { 106 head++; 107 if (head==capacity) 108 head=0; 109 } 110 tail++; 111 if (tail==capacity) 112 tail=0; 113 return true; 114 } 115 116 /** 117 * Adds elements to the buffer, preserving their ordering in the array. 118 * If the buffer is full, silently overwrites the oldest elements. 119 * 120 * @param a the elements to add 121 * @return {@code true} 122 */ 123 public boolean addAll(E[] a) { 124 for (E e : a) 125 add(e); 126 return true; 127 } 128 129 /** 130 * Adds elements to the buffer, preserving their ordering in the collection. 131 * If the buffer is full, silently overwrites the oldest elements. 132 * 133 * @param c the elements to add 134 * @return {@code true} 135 */ 136 public boolean addAll(Collection<E> c) { 137 for (E e : c) 138 add(e); 139 return true; 140 } 141 142 /** 143 * Returns {@code true} if the head of the buffer (the next element that will be removed) 144 * is equal to {@code o}, 145 * compared using {@link java.util.Objects#equals}. 146 * 147 * @param o the value to be compared 148 * @return {@code true} if the head of the buffer equals {@code o}; 149 * {@code false} if the buffer is empty 150 */ 151 public boolean at(E o) { 152 if (count==0) 153 return false; 154 return Objects.equals(arr[head], o); 155 } 156 157 /** 158 * Returns {@code true} if the elements at the head of the buffer (the next elements that will be removed) 159 * are equal to the contents of {@code a}, 160 * compared using {@link java.util.Objects#equals}. 161 * 162 * @param a the values to be compared 163 * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 164 * {@code false} if the buffer doesn't contain enough elements to match. 165 */ 166 public boolean at(E[] a) { 167 if (count<a.length) 168 return false; 169 for (int i=0; i<a.length; i++) { 170 if (!Objects.equals(peek(i), a[i])) 171 return false; 172 } 173 return true; 174 } 175 176 /** 177 * Compares the head of the buffer (the next element that will be removed) to {@code o} 178 * using {@link java.util.Objects#equals} 179 * and removes it from the buffer if there is a match. 180 * 181 * @param o the value to be compared 182 * @return {@code true} if the head of the buffer equals {@code o} and is removed; 183 * {@code false} if the buffer is empty 184 */ 185 public boolean atSkip(E o) { 186 if (count==0) 187 return false; 188 if (arr[head]!=o) 189 return false; 190 remove(); 191 return true; 192 } 193 194 /** 195 * Compares the head of the buffer (the next elements that will be removed) to {@code a} 196 * using {@link java.util.Objects#equals} 197 * and removes them from the buffer if there is a match. 198 * 199 * @param a the values to be compared 200 * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 201 * {@code false} if the buffer doesn't contain enough elements to match. 202 */ 203 public boolean atSkip(E[] a) { 204 if (!at(a)) 205 return false; 206 skip(a.length); 207 return true; 208 } 209 210 /** 211 * Empties the buffer. 212 */ 213 public void clear() { 214 arr=(E[]) new Object[capacity]; 215 head=0; 216 tail=0; 217 count=0; 218 } 219 220 /** 221 * Returns {@code true} if the buffer contains {@code e}, tested using {@link java.util.Objects#equals}. 222 * 223 * @param {@code e} the value to be tested 224 * @return {@code true} if the buffer contains {@code e}; 225 * {@code false} if not. 226 */ 227 public boolean contains(E e) { 228 for (int i=0; i<count; i++) 229 if (Objects.equals(e, arr[(i+head)%capacity])) 230 return true; 231 return false; 232 } 233 234 /** 235 * Returns the maximum capacity of this buffer. 236 * 237 * @return the maximum capacity of this buffer 238 */ 239 public int getCapacity() { 240 return capacity; 241 } 242 243 /** 244 * Returns {@code true} if the buffer is empty. 245 * 246 * @return {@code true} if the buffer is empty 247 */ 248 public boolean isEmpty() { 249 return count==0; 250 } 251 252 /** 253 * Adds an element to the buffer if there is space for it. 254 * 255 * @param e the element to add. 256 * @return {@code true} if there was space in the buffer and the element was added 257 */ 258 public boolean offer(E e) { 259 if (count>=capacity) 260 return false; 261 add(e); 262 return true; 263 } 264 265 /** 266 * Adds elements to the buffer if there is space for them. 267 * 268 * @param e the element to add. 269 * @return {@code true} if there was space in the buffer and the elements were added 270 */ 271 public boolean offer(E[] a) { 272 if (count+a.length>capacity) 273 return false; 274 for (E e : a) 275 add(e); 276 return true; 277 } 278 279 /** 280 * Adds elements to the buffer if there is space for them. 281 * 282 * @param e the element to add. 283 * @return {@code true} if there was space in the buffer and the elements were added 284 */ 285 public boolean offer(Collection<E> c) { 286 if (count+c.size()>capacity) 287 return false; 288 for (E e : c) 289 add(e); 290 return true; 291 } 292 293 /** 294 * Returns the head of the buffer (the next element that will be removed) without actually removing it. 295 * 296 * @return the element at the head of the buffer or {@code null} if the buffer is empty 297 */ 298 public E peek() { 299 if (count==0) 300 return null; 301 return arr[head]; 302 } 303 304 /** 305 * Returns the {@code n}<i>th</i> element that will be removed from the buffer, 306 * counting from 0 ({@code peek(0)} returns the first element that will be removed), 307 * or {@code null} if the buffer does not contain that many elements. 308 * 309 * @param n 310 * @return the {@code n}<i>th</i> element that will be removed from the buffer 311 * or {@code null} if the buffer does not contain that many elements 312 */ 313 public E peek(int n) { 314 if (n>count) 315 return null; 316 n+=head; 317 if (n>=capacity) 318 n-=capacity; 319 return arr[n]; 320 } 321 322 /** 323 * Removes and returns the element at the head of the buffer, 324 * or {@code null} if the buffer is empty. 325 * 326 * @return the element that was at the head of the buffer which was removed, 327 * or {@code null} if the buffer is empty 328 */ 329 public E poll() { 330 if (count<1) 331 return null; 332 return remove(); 333 } 334 335 /** 336 * Removes and returns {@code n} consecutive elements from the head of the buffer 337 * in the order they were added, or {@code null} if the buffer does not contain {@code n} elements. 338 * 339 * @param n the number of elements to remove 340 * @param cls the {@code Class} of the elements in the buffer (needed to create the array) 341 * @return the elements that were at the head of the buffer which were removed, 342 * or {@code null} if the buffer does not contain {@code n} elements 343 */ 344 public E[] poll(int n, Class<E> cls) { 345 if (count<n) 346 return null; 347 return remove(n, cls); 348 } 349 350 /** 351 * Removes and returns the element at the head of the buffer, 352 * or {@code null} if the buffer is empty. 353 * 354 * @return the element that was at the head of the buffer which was removed, 355 * or {@code null} if the buffer is empty 356 */ 357 public E remove() { 358 if (count==0) 359 return null; 360 E r=arr[head]; 361 arr[head]=null; 362 head++; 363 if (head==capacity) 364 head=0; 365 count--; 366 return r; 367 } 368 369 /** 370 * Removes and returns up to {@code n} consecutive elements from the head of the buffer 371 * in the order they were added. 372 * 373 * @param n the number of elements to remove 374 * @param cls the {@code Class} of the elements in the buffer (needed to create the array) 375 * @return the elements that were at the head of the buffer which were removed; 376 * the length of the array reflects the number of elements that were available 377 */ 378 public E[] remove(int n, Class<E> cls) { 379 n=Math.min(n, count); 380 E[] r=(E[]) Array.newInstance(cls, n); 381 for (int i=0; i<n; i++) 382 r[i]=remove(); 383 return r; 384 } 385 386 /** 387 * Empties the buffer. 388 * 389 * @return {@code true} 390 */ 391 public boolean removeAll() { 392 clear(); 393 return true; 394 } 395 396 /** 397 * Returns the number of elements in the buffer. 398 * 399 * @return the number of elements in the buffer 400 */ 401 public int size() { 402 return count; 403 } 404 405 /** 406 * Removes {@code n} elements from the head of the buffer (and discards them). 407 * If {@code n}>{@link size()}, only {@link size()} elements are removed. 408 * Inspired by and named after similar methods in 409 * {@link java.io.InputStream}s and {@link Reader}s. 410 * 411 * @param n the number of elements to remove 412 * @return the number of elements actually removed 413 */ 414 public int skip(int n) { 415 if (n<0) 416 throw new IllegalArgumentException("n<0"); 417 if (n>count) 418 n=count; 419 //this probably needs a loop to do arr[i]=null 420 for (int i=0; i<n; i++) 421 remove(); 422 return n; 423 } 424 425 public List<E> toList() { 426 var list=new ArrayList<E>(); 427 for (int i=0; i<count; i++) 428 list.add(arr[(i+head)%capacity]); 429 return list; 430 } 431 }