帮我实现一个可回滚的缓冲区

Question

这就是我到目前为止的情况：

我有以下用例（作为公正的 jUnit 测试）来展示我想要实现的目标：

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

我尝试使用包装列表（几乎重新发明了轮子）、包装双队列来解决这个问题（这个完全是一团糟），我刚刚失败的第三次尝试是一个包装的 LinkedList，其中除了 rewind() 之外，其他所有东西都可以工作。我最近一次尝试的伪代码是这样的：

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

这根本不起作用，经过一些编辑后，我设法让阅读开始工作，直到调用 rewind() ，所以本质上我第三次编写了一堆冗余代码。在这一点上，我确实感到有点沮丧，因为我从来不擅长算法，这就是我现在来找你的原因：请帮助我实现这个和/或指出我纠正本机 Java API 解决方案，目前我只是感到很困惑，因为我无法让它发挥作用。

Answer 1

假设您有一个简单的 FIFO 对象，它实现了 add、get 和 size 操作，您可以用伪代码实现此扩展 FIFO，如下所示：

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

我认为这是一个相当干净的实现。

Answer 2

您是否尝试过使用一些附加参数来包装 Java Collection 类型之一。

例如，创建一个包装 ArrayList 的新类。除了数组列表之外，还保留私有成员变量

• mark - 标记为当前倒带的最后一个索引
• - get() 上要检索的下一个索引

您还可以添加以下方法

• get() - 返回数组中的对象列出当前索引并递增当前
• mark() - 将标记设置为当前的值
• rewind() - 将当前设置为标记的值

还有一些细节需要解决（如何处理无效索引、标记最初设置为什么）等）但这可能会给你一个好的开始。

Answer 3

您能详细说明一下要求吗？我无法理解应该倒带做什么。它应该添加自 mark() 之后添加的所有元素吗？