Help me implement a rewindable buffer

Question

This is where I'm so far:

I have the following the following use case (as impartial jUnit test) to show what I want to achieve:

buffer.add(o1);
assertEquals(1, buffer.size());
buffer.mark();
buffer.add(o2);
assertEquals(2, buffer.size());
buffer.add(o3);
assertEquals(3, buffer.size());
assertSame(o1, buffer.get());
assertSame(o2, buffer.get());
assertSame(o3, buffer.get());
buffer.rewind();
// NOTE: It must be possible to enter the same object multiple times
//       into the buffer.
buffer.add(o2);
assertSame(o2, buffer.get());
assertSame(o3, buffer.get());
assertSame(o2, buffer.get());

I have tried solving this using a wrapped List (almost reinvented the wheel), wrapped twin queue (this one was a complete mess), and my third attempt I just failed with was a wrapped LinkedList in which I got everything else working except rewind(). The pseudocode for my latest attempt was something like this:

if [backBuffer is empty]
    [get latest object]
    increment currentIndex
    if [markIndex < currentIndex]
        [put object to backbuffer]
    return object
else
    [get object from backbuffer at index backBufferIndex]
    increment backBufferIndex
    return object

This didn't work at all and after some editing I managed to get reading to work until rewind() was called so essentially I made a bunch of redundant code for the third time. I do feel a bit frustrated at this point since I've never been good with algorithms and that's why I'm coming to you now: Please help me implement this and/or point to me to correct native Java API solution, currently I just feel stumped because I can't get this to work.

Answer 1

Assuming you have a simple FIFO object that implements add, get and size operations, you could implement this extended FIFO in pseudocode as follows:

constructor()
{
    FIFO current = new FIFO();
    FIFO alternate = new FIFO();
}

add(Object x)
{
    return current.add(x);
}

get()
{
    Object x = current.get();
    alternate.add(x);
    return x;
}

size()
{
    return current.size();
}

mark()
{
    alternate = new FIFO();
}

rewind()
{
    while (current.size > 0)
    {
        alternate.add(current.get());
    }
    current = alternate;
    alternate = new FIFO();
}

I think this is a fairly clean implementation.