Circular buffer

The circular buffer is an array based queue implementation, widely used for buffering data flows.

Description

The circular buffer consists of one array of fixed length and two pointers. The first pointer points the first stored element, the second one points to the first empty position of the array. When the element is added to the structure, the second index is incremented. When the first element of the array is polled (removed), the first element is incremented and the position is nulled (and the element is destructed). Because both increment operations are performed in a modular fashion (when the last position of the array is occupied, the next element is added at the beginning of the array (if it is empty)), the structure itself forms a circle, hence it is called the circular buffer.

Complexity of operations

The asymptotic complexity of addLast and poll (getFirst) operations is constant – O(1) .

Java

/**
 * Circular buffer - array based queue
 * @author Pavel Micka
 */
public class CircularBuffer<ENTITY> {

    private int size;
    private Object[] array;
    private int pointer; //first empty position

    /**
     * Constructor
     * @param length size of the buffer
     */
    public CircularBuffer(int length) {
        this.array = new Object[length];
        this.size = 0;
        pointer = 0;
    }

    /**
     * Add an element at the end of the array
     * @param i element
     */
    public void addLast(ENTITY i) {
        if (this.size == array.length) {
            throw new IllegalStateException("Buffer is full");
        }
        array[pointer] = i;

        pointer = modulo((pointer + 1), array.length);
        size++;
    }

    /**
     * Return and delete the first element (poll)
     * @return first element
     */
    public ENTITY getFirst() {
        if (this.size == 0) {
            throw new IllegalStateException("Buffer is empty");
        }
        ENTITY value = (ENTITY) array[modulo((pointer - size), array.length)];
        
        array[modulo((pointer - size), array.length)] = null;
        size--;
        
        return value;
    }

    /**
     * Read the first element (peek)
     * @return first element
     */
    public ENTITY readFirst() {
        if (this.size == 0) {
            throw new IllegalStateException("Buffer is empty");
        }
        ENTITY value = (ENTITY) array[modulo((pointer - size), array.length)];
        return value;
    }

    /**
     * x ≡ number mod(modulo)
     * @param number number
     * @param modulo modulo
     * @return the least nonnegative residuum
     */
    private int modulo(int number, int modulo) {
        if (number >= 0) {
            return number % modulo;
        }
        int result = number % modulo;
        return result == 0 ? 0 : result + modulo;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Content: ");
        for (int i = 0; i < size; i++) {
            builder.append(array[modulo((pointer - size + i), array.length)]).append(" ");
        }
        builder.append("\\nfirst index: ").append(modulo((pointer - size), array.length)).append(", last index:").append(pointer - 1).append(", size: ").append(size);
        return builder.toString();
    }

    /**
     * Number of occupied positions
     * @return number of elements present in the buffer
     */
    public int getSize() {
        return this.size;
    }

    /**
     * Size of the buffer
     * @return maximal number of elements that could be stored in the buffer
     */
    public int getLength() {
        return array.length;
    }
}

Description

Complexity of operations

Doporučujeme