Unbounded FIFO Buffer

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.

Unbounded FIFO Buffer

 

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.

Unbounded FIFO Buffer

 

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.

Unbounded FIFO Buffer

 

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)

Unbounded FIFO Buffer

 

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.

Unbounded FIFO Buffer

 

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.

Unbounded FIFO Buffer

 

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);
    }

Home