Circular Buffer

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class CircularBuffer {
Integer[] elements;
int capacity;
int writePtr = 0;
int readPtr = 0;

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

public synchronized void put(Integer num) {
// If writePtr is pointing at a filled position, meaning all positions having been taken
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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());
}
}