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

Could you please elaborate a bit more on the requirement. I was unable to understand what should rewind do. Should it add all elements which were added since mark()?

Answer 2

Have you tried wrapping one of the Java Collection types with a few additional parameters.

For example, create a new class that wraps an ArrayList. In addition to the array list, keep private member variables

• mark - the last index that was marked for a rewind
• current - the next index to retreive on get()

You would also add the following methods

• get() - Returns the object in the array list at index current and increments current
• mark() - sets mark to the value of current
• rewind() - sets current to the value of mark

There are still some details to work out (how are invalid indexes handled, what is mark set to initially, etc.) but that might give you a good start.

Answer 3

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.