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.util.Collection;
026
027/**
028 * A thread-safe ring buffer (circular buffer) implementation for Java.
029 * <p>
030 * A ring buffer is a fixed-size first in - first out buffer
031 * typically backed by an array with head and tail pointers.
032 * Elements are added to the tail of the buffer and removed from the head.
033 * When the end of the array is reached, the pointers wrap around to the beginning.
034 * When the buffer is full, adding new elements overwrites the oldest elements
035 * (but see the {@link offer(E)} and {@link offer(E[])} methods in this implementation).
036 * <p>
037 * Pros: Fast, simple. 
038 * <p>
039 * Cons: Size fixed at creation time, 
040 * adding new elements overwrites the oldest ones if the buffer is full,
041 * elements can only be added or removed in FIFO order.
042 * <p>
043 * There are some useful look-ahead methods, {@link #peek()}, {@link #peek(int)}, {@link #at(E)},
044 * {@link #at(E[])}, {@link #atSkip(E)} 
045 * and {@link #atSkip(E[])}.
046 * <p>
047 * These are simple, hopefully fast, implementations. 
048 * They deliberately do not implement Java's {@link java.util.Collection} or {@link java.util.Queue} interfaces,
049 * although the API is similar.
050 * <p>
051 * Variants:<ul>
052 * <li>{@link FastRingBuffer}: Simplest, fastest, not thread safe.
053 * <li>{@link SafeRingBuffer}: Thread safe.
054 * <li>{@link BlockingRingBuffer}: add and remove methods block if necessary; offer and poll methods are non-blocking.
055 * </ul>
056 * <p>
057 * {@link #remove()} sets the underlying array slot to {@code null} to avoid memory leaks.
058 * All other {@code remove} and {@code poll} methods call {@link #remove()}. 
059 * <p>
060 * {@link #clear()} discards the underlying array to avoid memory leaks. 
061 * {@link #removeAll()} calls {@link #clear()}. 
062 * <p>
063 * Elements can be {@code null}, but this means that,
064 * if {@link #peek()}, {@link #poll()} or {@link #remove()} return null,
065 * this could be because an element was {@code null} or because the buffer was empty.
066 * Consider using {@link #isEmpty()} or {@link #size()} to disambiguate.
067 * <p>
068 * {@link #poll()} might seem redundant, but is overridden in {@link BlockingRingBuffer}.
069 * 
070 * @param <E> the type of elements in the buffer
071 * @author sherstDotNet@yahoo.com
072 */
073public class SafeRingBuffer<E> extends net.sherst.util.FastRingBuffer<E> {
074 
075 /**
076  * Creates a new buffer.
077  * 
078  * @param capacity Maximum capacity of the buffer
079  */
080 public SafeRingBuffer(int capacity) {
081  super(capacity);
082   }
083 
084 /**
085  * Adds an element to the buffer.
086  * If the buffer is full, silently overwrites the oldest element.
087  * 
088  * @param e the element to add
089  */
090 @Override
091 public synchronized boolean add(E e) {
092    return super.add(e);
093    }
094 
095 /**
096  * Adds elements to the buffer, preserving their ordering in the array.
097  * If the buffer is full, silently overwrites the oldest elements.
098  * 
099  * @param a the elements to add
100  * @return <b>true</b>
101  */
102 @Override
103 public synchronized boolean addAll(E[] a) {
104    return super.addAll(a);
105    }
106 
107 /**
108  * Adds elements to the buffer, preserving their ordering in the collection.
109  * If the buffer is full, silently overwrites the oldest elements.
110  * 
111  * @param c the elements to add
112  * @return <b>true</b>
113  */
114 @Override
115 public synchronized boolean addAll(Collection<E> c) {
116    return super.addAll(c);
117    }
118 
119 /**
120  * Returns {@code true} if the head of the buffer (the next element that will be removed) 
121  * is equal to {@code o},
122  * compared using {@link java.util.Objects#equals}.
123  * 
124  * @param o the value to be compared
125  * @return {@code true} if the head of the buffer equals {@code o}; 
126  * {@code false} if the buffer is empty
127  */
128 @Override
129 public synchronized boolean at(E o) {
130  return super.at(o);
131  }
132 
133 /**
134  * Returns {@code true} if the elements at the head of the buffer (the next elements that will be removed)
135  * are equal to the contents of {@code a},
136  * compared using {@link java.util.Objects#equals}.
137  * 
138  * @param a the values to be compared
139  * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 
140  * {@code false} if the buffer doesn't contain enough elements to match.
141  */
142 @Override
143 public synchronized boolean at(E[] a) {
144  return super.at(a);
145  }
146 
147 /**
148  * Compares the head of the buffer (the next element that will be removed) to {@code o} 
149  * using {@link java.util.Objects#equals} 
150  * and removes it from the buffer if there is a match.
151  * 
152  * @param o the value to be compared
153  * @return {@code true} if the head of the buffer equals {@code o} and is removed; 
154  * {@code false} if the buffer is empty
155  */
156 @Override
157 public synchronized boolean atSkip(E o) {
158  return super.atSkip(o);
159  }
160 
161 /**
162  * Compares the head of the buffer (the next elements that will be removed) to {@code a}
163  * using {@link java.util.Objects#equals}
164  * and removes them from the buffer if there is a match.
165  * 
166  * @param a the values to be compared
167  * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 
168  * {@code false} if the buffer doesn't contain enough elements to match.
169  */
170 @Override
171 public synchronized boolean atSkip(E[] a) {
172  return super.atSkip(a);
173  }
174 
175 /**
176  * Empties the buffer.
177  */
178 @Override
179 public synchronized void clear() {
180  super.clear();
181  notifyAll();
182  }
183 
184 /**
185  * Returns the maximum capacity of this buffer.
186  * 
187  * @return the maximum capacity of this buffer
188  */
189 @Override
190 public int getCapacity() {
191  return super.getCapacity();
192  }
193 
194 /**
195  * Returns {@code true} if the buffer is empty.
196  * 
197  * @return {@code true} if the buffer is empty
198  */
199 @Override
200 public synchronized boolean isEmpty() {
201   return super.isEmpty();
202    }
203 
204 /**
205  * Adds an element to the buffer if there is space for it.
206  * 
207  * @param e the element to add.
208  * @return {@code true} if there was space in the buffer and the element was added
209  */
210 @Override
211 public synchronized boolean offer(E e) {
212   return super.offer(e);
213   }
214 
215 /**
216  * Adds elements to the buffer if there is space for them.
217  * 
218  * @param e the element to add.
219  * @return {@code true} if there was space in the buffer and the elements were added
220  */
221 @Override
222 public synchronized boolean offer(E[] a) {
223   return super.offer(a);
224   }
225 
226 /**
227  * Adds elements to the buffer if there is space for them.
228  * 
229  * @param e the element to add.
230  * @return {@code true} if there was space in the buffer and the elements were added
231  */
232 @Override
233 public synchronized boolean offer(Collection<E> c) {
234   return super.offer(c);
235   }
236 
237 /**
238  * Returns the head of the buffer (the next element that will be removed) without actually removing it.
239  * 
240  * @return the element at the head of the buffer or {@code null} if the buffer is empty
241  */
242 @Override
243 public synchronized E peek() {
244  return super.peek();
245   }
246 
247 /**
248  * Returns the {@code n}<i>th</i> element that will be removed from the buffer, 
249  * counting from 0 ({@code peek(0)} returns the first element that will be removed), 
250  * or {@code null} if the buffer does not contain that many elements.
251  * 
252  * @param n
253  * @return the {@code n}<i>th</i> element that will be removed from the buffer 
254  * or {@code null} if the buffer does not contain that many elements
255  */
256 @Override
257 public synchronized E peek(int n) {
258  return super.peek(n);
259   }
260 
261 /**
262  * Removes and returns the element at the head of the buffer, 
263  * or {@code null} if the buffer is empty.  
264  * 
265  * @return the element that was at the head of the buffer which was removed, 
266  * or {@code null} if the buffer is empty
267  */
268 @Override
269 public synchronized E poll() {
270  return super.poll();
271   }
272 
273 /**
274  * Removes and returns {@code n} consecutive elements from the head of the buffer 
275  * in the order they were added, or {@code null} if the buffer does not contain {@code n} elements. 
276  * 
277  * @param n the number of elements to remove
278  * @param cls the {@code Class} of the elements in the buffer (needed to create the array)
279  * @return the elements that were at the head of the buffer which were removed, 
280  * or {@code null} if the buffer does not contain {@code n} elements
281  */
282 @Override
283 public synchronized E[] poll(int n, Class<E> cls) {
284  return super.poll(n, cls);
285   }
286 
287 /**
288  * Removes and returns the element at the head of the buffer, 
289  * or {@code null} if the buffer is empty.  
290  * 
291  * @return the element that was at the head of the buffer which was removed, 
292  * or {@code null} if the buffer is empty
293  */
294 @Override
295 public synchronized E remove() {
296  return super.remove();
297   }
298 
299 /**
300  * Removes and returns up to {@code n} consecutive elements from the head of the buffer 
301  * in the order they were added.
302  * 
303  * @param n the number of elements to remove
304  * @param cls the {@code Class} of the elements in the buffer (needed to create the array)
305  * @return the elements that were at the head of the buffer which were removed; 
306  * the length of the array reflects the number of elements that were available 
307  */
308 @Override
309 public synchronized E[] remove(int n, Class<E> cls) {
310  return super.remove(n, cls);
311   }
312
313/**
314* Empties the buffer.
315* 
316* @return {@code true}  
317*/
318 @Override
319 public synchronized boolean removeAll() {
320   return super.removeAll();
321   }
322 
323 /**
324  * Returns the number of elements in the buffer.
325  * 
326  * @return the number of elements in the buffer
327  */
328 @Override
329 public synchronized int size() {
330  return super.size();
331  }
332 
333 /**
334  * Removes {@code n} elements from the head of the buffer (and discards them). 
335  * If {@code n}&gt;{@link size()}, only {@link size()} elements are removed. 
336  * Does not block if the buffer is empty.
337  * Inspired by and named after similar methods in 
338  * {@link java.io.InputStream}s and {@link Reader}s. 
339  * 
340  * @param n the number of elements to remove
341  * @return the number of elements actually removed
342  */
343 @Override
344 public synchronized int skip(int n) {
345    return super.skip(n);
346    }
347  }