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}&gt;{@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  }