CODEWITHSUNDEEP
javapointersqueuecircular-buffer
Nilnoc
Nilnoc

Reputation: 101

flush() and isEmpty() methods for a ring buffer without using .size() in Java

I am trying to implement a Ring (circular queue) of Chars in Java and I'm having a difficult time thinking through how to detect if the buffer isEmpty without using the .size() method on the array.

Because if the Ring Buffer is full read pointer == write pointer but also if the Ring Buffer is empty, read pointer == write pointer so I'm not sure how to check for isEmpty() correctly. I know that I can do it with .size() but I'm trying to figure out if it's possible to implement it without.

I know that I will need to waste a space at the end of the array but I'm not sure how to check it. Would the check be as simple as if (head != (tail - 1))?

Also, I am trying to write the flush() method and I think I can do so with a for each loop looking like this:

for(char c : items){
            c = (Character) null;
        }

But eclipse yells at me for null pointer access requiring auto boxing and unboxing.

Any help would be very much appreciated. The full class is below for reference:

public class RingBuffer {
    private char[] items;
    private int front;
    private int rear; 
    private int last;

    public RingBuffer(int capacity){
        items = new char[capacity +1];
        front = 0;
        rear = 0;
        last = capacity;

    }

    public void flush(){
        for(char c : items){
            c = (Character) null;
        }       
    }

    public boolean isEmpty(){
        return false;
    }

}

Upvotes: 0

Views: 2156

Answers (1)

vanekjar
vanekjar

Reputation: 2406

You can read more about Full/Empty Buffer Distinction on Wikipedia http://en.wikipedia.org/wiki/Circular_buffer#Full_.2F_Empty_Buffer_Distinction

There are multiple workarounds described. I would point out the one you mentioned and maybe the easiest one to understand.

Always keep one slot open

The buffer will never be full to the last item, but there will be always one slot empty. That means you can distinguish full from empty like this:

public boolean isEmpty() {
     return head == tail;
}

public boolean isFull() {
     // don't forget about the modulo here
     return head == ((tail - 1) % capacity);
}

When flushing (I would name it rather clear()) you don't have to overwrite the data in array or allocate a new one. You can just set pointers to the beginning of the array.

public void clear() {
     head = 0;
     tail = 0;
}

And that means the buffer will be considered empty. No matter what data are really written in memory they will be ignored and then overwritten.

If you liked this answer please mark it as accepted. Thank you.

Upvotes: 2

Related Questions