首页 > itarticle > circular buffer

circular buffer

admin 11月 12, 2020 0

When preparing for interviews, I was inspired by this post and wrote my own version of circular buffer.

Here’s some essense of circular buffer this data structure.

How many elements are in the buffer is calculated based on the write and read position.

How the calculation looks depends on whether the write position has flipped (wrapped around) or not.

If the write position has not wrapped around you can simply subtract the read position from the write position to know how many elements are in the buffer. If the write position has wrapped around (flipped) then the available space is equal to the capacity minus the read position plus the write position.

To keep track of whether the write position has flipped or not a special “flip marker” is used. That is where the name of the implementation comes from. Actually, in most cases you could just check if the write position is larger or smaller than the read position to detect if the write position has wrapped around. But, that doesn’t work when write position and read position are equal (the ring buffer is either completely full or completely empty).

Circular Buffer

public class  {
    Integer[] elements;
    int capacity;
    int writePtr = 0;
    int readPtr = 0;

    public (int capacity) {
        this.capacity = capacity;
        elements = new Integer[capacity];
    }

    public synchronized void put(Integer num) {
        
        if (elements[writePtr] != null) {
            throw new IllegalStateException();
        }
        
        // Put the element at the pointed position
        elements[writePtr] = num;

        // Move the pointer
        if (writePtr == capacity - 1) {
            writePtr = 0;
        } else {
            writePtr ++;
        }
    }

    public synchronized Integer take() {
        // If readPtr is pointing at a null position, meaning no element is in this circular buffer
        if (elements[readPtr] == null) {
            return null;
        }

        // Record the element, and remove it
        Integer result = elements[readPtr];
        elements[readPtr] = null;

        // Move the pointer
        if(readPtr == capacity - 1) {
            readPtr = 0;
        } else {
            readPtr ++;
        }

        // Return element
        return result;
    }

    public synchronized int occupiedSize() {
        // If writePtr is ahead of readPtr
        if(writePtr > readPtr) {
            return writePtr - readPtr;
        } else if(writePtr < readPtr) {
            // If readPtr is ahead of writePtr, meaning the writePtr has turned over
            return capacity - readPtr + writePtr;
        } else {
            // If writePtr == readPtr
            // If readPtr is pointing at an element
            if(elements[readPtr] != null) {
                return capacity;
            } else {
                // If readPtr is pointing no element
                return 0;
            }
        }
    }

    public synchronized int remainingCapacity() {
        return capacity - occupiedSize();
    }
    
    public synchronized void reset() {
        writePtr = 0;
        readPtr = 0;
        elements = new Integer[capacity];
    }

    public static void main(String[] args) {
        CircularBuffer cb = new CircularBuffer(3);

        System.out.println(cb.occupiedSize());

        cb.put(10);
        System.out.println(cb.occupiedSize());

        cb.put(20);
        System.out.println(cb.occupiedSize());

        System.out.println(cb.take2());
        System.out.println(cb.occupiedSize());

        cb.put(30);
        System.out.println(cb.occupiedSize());

        cb.put(40);
        System.out.println(cb.occupiedSize());

        System.out.println(cb.take2());
        System.out.println(cb.take2());
        System.out.println(cb.take2());
        System.out.println(cb.take2());
    }
}

Advanced Circular Buffer

Write a circular buffer that can override elements when it’s full

public class CircularBuffer2 {
    Integer[] elements;
    int rPtr;
    int wPtr;
    int capacity;

    CircularBuffer2(int capacity) {
        this.capacity = capacity;
        elements = new Integer[capacity];

        rPtr = 0;
        wPtr = 0;
    }

    public synchronized void put(Integer i) {
        // If there's alreay an element
        if(elements[wPtr] != null) {
            // Override it
            elements[wPtr] = i;

            // Move rPtr and wPtr together
            if(wPtr == capacity - 1) {
                wPtr = 0;
                rPtr = 0;
            } else {
                wPtr ++;
                rPtr ++;
            }
        } else {
            // If buffer is not full
            elements[wPtr] = i;

            // Only move wPtr
            if(wPtr == capacity - 1) {
                wPtr = 0;
            } else {
                wPtr ++;
            }
        }
    }

    public synchronized Integer get() {
        // If there's no element
        if(elements[rPtr] == null) {
            return null;
        }

        // Get the element
        Integer result = elements[rPtr];
        // Release resource
        elements[rPtr] = null;

        // Move rPtr
        if(rPtr == capacity - 1) {
            rPtr = 0;
        } else {
            rPtr++;
        }

        return result;
    }

    public static void main(String[] args) {
        CircularBuffer2 cb = new CircularBuffer2(3);

        cb.put(1);
        cb.put(2);
        cb.put(3);
        cb.put(4);
        System.out.println(cb.get());
        System.out.println(cb.get());
        System.out.println(cb.get());

        cb = new CircularBuffer2(3);

        cb.put(1);
        cb.put(2);
        cb.put(3);
        cb.put(4);
        cb.put(5);
        cb.put(6);
        System.out.println(cb.get());
        System.out.println(cb.get());
        System.out.println(cb.get());
    }
}