Add
Create a buffer of 3 elements.
UnboundedFifoBuffer buf = new UnboundedFifoBuffer(3);
Internally the implementation creates an extra element. Head and tail indices are equal to 0 as we have not added or removed any elements. As we add elements, tail index increases. When size of buffer equals the allocated buffer length, array is expanded so that size=size*2+1.
Remove
When we remove element, we get an extra vacant element. The head index points to 1. As we remove more elements, the head index increases further. When we add new elements, it will re-use the vacant elements.
Add again
In the above example, the tail index is pointing to the last element of the array. Since we have vacant elements due to the remove operation, instead of resizing the array, it will re-use the vacant elements. The tail index will point to 0 so that the next add will fill the 0 index element. As we add new elements, the tail index will increase. Since tail index is < head index, the size would be buffer length – head + tail.
Iterator
Iterator returns elements in the incremental order starting from head, till it reaches tail. If tail < head, element order will be from head to array’s last element and then 0 to tail index. In the example, iterator will return 5, 6, 7 (last element of array), 8 (index=0), 9, 10(index=tail)
Remove during iteration
If it is the first element, it can be removed quickly else we will have to left shift elements. In the below example, iterator returns first element 5. We do next() to get 6, and then call remove.
Re-sizing
Since size equals buffer length, adding a new element will expand the array. The elements will be re-positioned in the new array in the order from head->tail.
Unit test
public void testBuffLen() {
//Create a buffer of 3 elements
UnboundedFifoBuffer buf = new UnboundedFifoBuffer(3);
//Internally the implementation creates an extra element, not sure why?
assertEquals(4, buf.buffer.length);
//Head and tail indexes are equal to 0 as we have not added or removed any elements
assertEquals(0, buf.head);
assertEquals(0, buf.tail);
//As we add elements, tail index is incremented
buf.add(1);
assertEquals(0, buf.head);
assertEquals(1, buf.tail);
assertEquals(1, buf.size());
buf.add(2);
assertEquals(2, buf.size());
buf.add(3);
assertEquals(3, buf.size());
assertEquals(4, buf.buffer.length);
//When size of buffer equals the allocated buffer length, array is expanded so that size=size*2+1
buf.add(4);
assertEquals(4, buf.size());
assertEquals(7, buf.buffer.length);
buf.add(5);
buf.add(6);
assertEquals(6, buf.size());
assertEquals(7, buf.buffer.length);
//When we remove element, we get an extra vacant element.
buf.remove();
//Since the first element is removed, head index is incremented to 1
//When we add new elements, instead of re-sizing, it will re-use the vacant elements
assertEquals(5, buf.size());
assertEquals(1, buf.head);
assertEquals(6, buf.tail);
//As we remove more elements, the head index is incremented further
buf.remove();
buf.remove();
buf.remove();
assertEquals(2, buf.size());
assertEquals(4, buf.head);
assertEquals(6, buf.tail);
//Tail index is pointing to the end element in buffer. Since we have vacant elements due to the remove operation,
//instead of resizing the array, it will re-use the vacant elements.
buf.add(7);
//Tail index now points to 0 to reuse the vacant elements
assertEquals(3, buf.size());
assertEquals(4, buf.head);
assertEquals(0, buf.tail);
assertEquals(7, buf.buffer.length);
//Get method returns element pointing by the head index
assertEquals(5, buf.get());
assertEquals(5, buf.get());
//Add new elements, tail index is incremented
buf.add(8);
buf.add(9);
//Tail index is < head index so size = buffer length - head + tail
assertEquals(4, buf.head);
assertEquals(2, buf.tail);
assertEquals(5, buf.size());
assertEquals(7, buf.buffer.length);
buf.add(10);
assertEquals(4, buf.head);
assertEquals(3, buf.tail);
assertEquals(6, buf.size());
//Size equals buffer length so adding new element will expand the array
buf.add(11);
assertEquals(0, buf.head);
assertEquals(7, buf.tail);
assertEquals(13, buf.buffer.length);
}
