TheAlgorithms · alxkm · Oct 15, 2024 · Oct 5, 2024 · Oct 7, 2024 · Oct 12, 2024
@@ -2,27 +2,62 @@
 
 import java.util.concurrent.atomic.AtomicInteger;
 
+/**
+ * The {@code CircularBuffer} class implements a generic circular (or ring) buffer.
+ * A circular buffer is a fixed-size data structure that operates in a FIFO (First In, First Out) manner.
+ * The buffer allows you to overwrite old data when the buffer is full and efficiently use limited memory.
+ * When the buffer is full, adding a new item will overwrite the oldest data.
+ *
+ * @param <Item> The type of elements stored in the circular buffer.
+ */
 public class CircularBuffer<Item> {
     private final Item[] buffer;
     private final CircularPointer putPointer;
     private final CircularPointer getPointer;
     private final AtomicInteger size = new AtomicInteger(0);
 
+    /**
+     * Constructor to initialize the circular buffer with a specified size.
+     *
+     * @param size The size of the circular buffer.
+     * @throws IllegalArgumentException if the size is zero or negative.
+     */
     public CircularBuffer(int size) {
+        if (size <= 0) {
+            throw new IllegalArgumentException("Buffer size must be positive");
+        }
         // noinspection unchecked
         this.buffer = (Item[]) new Object[size];
         this.putPointer = new CircularPointer(0, size);
         this.getPointer = new CircularPointer(0, size);
     }
 
+    /**
+     * Checks if the circular buffer is empty.
+     * This method is based on the current size of the buffer.
+     *
+     * @return {@code true} if the buffer is empty, {@code false} otherwise.
+     */
     public boolean isEmpty() {
         return size.get() == 0;
     }
 
+    /**
+     * Checks if the circular buffer is full.
+     * The buffer is considered full when its size equals its capacity.
+     *
+     * @return {@code true} if the buffer is full, {@code false} otherwise.
+     */
     public boolean isFull() {
         return size.get() == buffer.length;
     }
 
+    /**
+     * Retrieves and removes the item at the front of the buffer (FIFO).
+     * This operation will move the {@code getPointer} forward.
+     *
+     * @return The item at the front of the buffer, or {@code null} if the buffer is empty.
+     */
     public Item get() {
         if (isEmpty()) {
             return null;
@@ -33,31 +68,64 @@ public Item get() {
         return item;
     }
 
+    /**
+     * Adds an item to the end of the buffer (FIFO).
+     * If the buffer is full, this operation will overwrite the oldest data.
+     *
+     * @param item The item to be added.
+     * @throws IllegalArgumentException if the item is null.
+     * @return {@code true} if the item was successfully added, {@code false} if the buffer was full and the item overwrote existing data.
+     */
     public boolean put(Item item) {
+        if (item == null) {
+            throw new IllegalArgumentException("Null items are not allowed");
+        }
+
+        boolean wasEmpty = isEmpty();
         if (isFull()) {
-            return false;
+            getPointer.getAndIncrement(); // Move get pointer to discard oldest item
+        } else {
+            size.incrementAndGet();
         }
 
         buffer[putPointer.getAndIncrement()] = item;
-        size.incrementAndGet();
-        return true;
+        return wasEmpty;
     }
 
+    /**
+     * The {@code CircularPointer} class is a helper class used to track the current index (pointer)
+     * in the circular buffer.
+     * The max value represents the capacity of the buffer.
+     * The `CircularPointer` class ensures that the pointer automatically wraps around to 0
+     * when it reaches the maximum index.
+     * This is achieved in the `getAndIncrement` method, where the pointer
+     * is incremented and then taken modulo the maximum value (`max`).
+     * This operation ensures that the pointer always stays within the bounds of the buffer.
+     */
     private static class CircularPointer {
         private int pointer;
         private final int max;
 
+        /**
+         * Constructor to initialize the circular pointer.
+         *
+         * @param pointer The initial position of the pointer.
+         * @param max The maximum size (capacity) of the circular buffer.
+         */
         CircularPointer(int pointer, int max) {
             this.pointer = pointer;
             this.max = max;
         }
 
+        /**
+         * Increments the pointer by 1 and wraps it around to 0 if it reaches the maximum value.
+         * This ensures the pointer always stays within the buffer's bounds.
+         *
+         * @return The current pointer value before incrementing.
+         */
         public int getAndIncrement() {
-            if (pointer == max) {
-                pointer = 0;
-            }
             int tmp = pointer;
-            pointer++;
+            pointer = (pointer + 1) % max;
             return tmp;
         }
     }

@@ -1,143 +1,88 @@
 package com.thealgorithms.datastructures.buffers;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertFalse;
 import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.List;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Executors;
-import java.util.concurrent.ThreadLocalRandom;
-import java.util.concurrent.TimeUnit;
-import java.util.concurrent.atomic.AtomicIntegerArray;
-import org.junit.jupiter.api.BeforeEach;
-import org.junit.jupiter.api.RepeatedTest;
 import org.junit.jupiter.api.Test;
 
 class CircularBufferTest {
-    private static final int BUFFER_SIZE = 10;
-    private CircularBuffer<Integer> buffer;
-
-    @BeforeEach
-    void setUp() {
-        buffer = new CircularBuffer<>(BUFFER_SIZE);
-    }
 
     @Test
-    void isEmpty() {
+    void testInitialization() {
+        CircularBuffer<Integer> buffer = new CircularBuffer<>(5);
         assertTrue(buffer.isEmpty());
-        buffer.put(generateInt());
-        assertFalse(buffer.isEmpty());
+        assertEquals(Boolean.FALSE, buffer.isFull());
     }
 
     @Test
-    void isFull() {
-        assertFalse(buffer.isFull());
-        buffer.put(generateInt());
-        assertFalse(buffer.isFull());
+    void testPutAndGet() {
+        CircularBuffer<String> buffer = new CircularBuffer<>(3);
 
-        for (int i = 1; i < BUFFER_SIZE; i++) {
-            buffer.put(generateInt());
-        }
+        assertTrue(buffer.put("A"));
+        assertEquals(Boolean.FALSE, buffer.isEmpty());
+        assertEquals(Boolean.FALSE, buffer.isFull());
+
+        buffer.put("B");
+        buffer.put("C");
         assertTrue(buffer.isFull());
+
+        assertEquals("A", buffer.get());
+        assertEquals("B", buffer.get());
+        assertEquals("C", buffer.get());
+        assertTrue(buffer.isEmpty());
     }
 
     @Test
-    void get() {
-        assertNull(buffer.get());
-        for (int i = 0; i < 100; i++) {
-            buffer.put(i);
-        }
-        for (int i = 0; i < BUFFER_SIZE; i++) {
-            assertEquals(i, buffer.get());
-        }
+    void testOverwrite() {
+        CircularBuffer<Integer> buffer = new CircularBuffer<>(3);
+
+        buffer.put(1);
+        buffer.put(2);
+        buffer.put(3);
+        assertEquals(Boolean.FALSE, buffer.put(4)); // This should overwrite 1
+
+        assertEquals(2, buffer.get());
+        assertEquals(3, buffer.get());
+        assertEquals(4, buffer.get());
         assertNull(buffer.get());
     }
 
     @Test
-    void put() {
-        for (int i = 0; i < BUFFER_SIZE; i++) {
-            assertTrue(buffer.put(generateInt()));
-        }
-        assertFalse(buffer.put(generateInt()));
+    void testEmptyBuffer() {
+        CircularBuffer<Double> buffer = new CircularBuffer<>(2);
+        assertNull(buffer.get());
     }
 
-    @RepeatedTest(1000)
-    void concurrentTest() throws InterruptedException {
-        final int numberOfThreadsForProducers = 3;
-        final int numberOfThreadsForConsumers = 2;
-        final int numberOfItems = 300;
-        final CountDownLatch producerCountDownLatch = new CountDownLatch(numberOfItems);
-        final CountDownLatch consumerCountDownLatch = new CountDownLatch(numberOfItems);
-        final AtomicIntegerArray resultAtomicArray = new AtomicIntegerArray(numberOfItems);
-
-        // We are running 2 ExecutorService simultaneously 1 - producer, 2 - consumer
-        // Run producer threads to populate buffer.
-        ExecutorService putExecutors = Executors.newFixedThreadPool(numberOfThreadsForProducers);
-        putExecutors.execute(() -> {
-            while (producerCountDownLatch.getCount() > 0) {
-                int count = (int) producerCountDownLatch.getCount();
-                boolean put = buffer.put(count);
-                while (!put) {
-                    put = buffer.put(count);
-                }
-                producerCountDownLatch.countDown();
-            }
-        });
-
-        // Run consumer threads to retrieve the data from buffer.
-        ExecutorService getExecutors = Executors.newFixedThreadPool(numberOfThreadsForConsumers);
-        getExecutors.execute(() -> {
-            while (consumerCountDownLatch.getCount() > 0) {
-                int count = (int) consumerCountDownLatch.getCount();
-                Integer item = buffer.get();
-                while (item == null) {
-                    item = buffer.get();
-                }
-                resultAtomicArray.set(count - 1, item);
-                consumerCountDownLatch.countDown();
-            }
-        });
-
-        producerCountDownLatch.await();
-        consumerCountDownLatch.await();
-        putExecutors.shutdown();
-        getExecutors.shutdown();
-        shutDownExecutorSafely(putExecutors);
-        shutDownExecutorSafely(getExecutors);
-
-        List<Integer> resultArray = getSortedListFrom(resultAtomicArray);
-        for (int i = 0; i < numberOfItems; i++) {
-            int expectedItem = i + 1;
-            assertEquals(expectedItem, resultArray.get(i));
-        }
+    @Test
+    void testFullBuffer() {
+        CircularBuffer<Character> buffer = new CircularBuffer<>(2);
+        buffer.put('A');
+        buffer.put('B');
+        assertTrue(buffer.isFull());
+        assertEquals(Boolean.FALSE, buffer.put('C')); // This should overwrite 'A'
+        assertEquals('B', buffer.get());
+        assertEquals('C', buffer.get());
     }
 
-    private int generateInt() {
-        return ThreadLocalRandom.current().nextInt(0, 100);
-    }
+    @Test
+    void testIllegalArguments() {
+        assertThrows(IllegalArgumentException.class, () -> new CircularBuffer<>(0));
+        assertThrows(IllegalArgumentException.class, () -> new CircularBuffer<>(-1));
 
-    private void shutDownExecutorSafely(ExecutorService executorService) {
-        try {
-            if (!executorService.awaitTermination(1_000, TimeUnit.MILLISECONDS)) {
-                executorService.shutdownNow();
-            }
-        } catch (InterruptedException e) {
-            executorService.shutdownNow();
-        }
+        CircularBuffer<String> buffer = new CircularBuffer<>(1);
+        assertThrows(IllegalArgumentException.class, () -> buffer.put(null));
     }
 
-    public List<Integer> getSortedListFrom(AtomicIntegerArray atomicArray) {
-        int length = atomicArray.length();
-        ArrayList<Integer> result = new ArrayList<>(length);
-        for (int i = 0; i < length; i++) {
-            result.add(atomicArray.get(i));
+    @Test
+    void testLargeBuffer() {
+        CircularBuffer<Integer> buffer = new CircularBuffer<>(1000);
+        for (int i = 0; i < 1000; i++) {
+            buffer.put(i);
         }
-        result.sort(Comparator.comparingInt(o -> o));
-        return result;
+        assertTrue(buffer.isFull());
+        buffer.put(1000); // This should overwrite 0
+        assertEquals(1, buffer.get());
     }
 }