为以循环的方式移动的序列的最佳实践 [英] Best practice for shifting a sequence in a circular manner

问题描述

我要实现一种数组或序列或列表，支持转发传阅的最便宜的方式和背部缠绕元素组成。见这个例子：

I have to implement a kind of an array or sequence or list, which supports the cheapest way of circulated forwarding and back winding of elements. See this example:

Original sequence: 1 2 3 4 5

Forwarded once: 5 1 2 3 4
Forwarded twice: 4 5 1 2 3

相同的，但相反的是为后面绕组。什么是执行这一最便宜，最斯卡拉式的方式吗？在Java中，我可以使用LinkedList的，它会做伟大的...但是，我无法找到斯卡拉任何明确的答案。

Same but opposite is for the back winding. What would be the cheapest and most Scala-style way of implementing this? In Java I could use LinkedList and it would do great... However, I could not find any definite answer for Scala.

此外，它也有容易更换由索引任何给定的元件，如在链表

Also, it also has to be easy to replace any given element by index, as in LinkedList.

更新：

有关最快的，但算法不那么地道的变种（你知道，当你需要它），是指切赫Pudlák的答案！

For the fastest, but not-so-idiomatic variant of algorithm (you know when you need it), refer to the answer of Petr Pudlák!!!

推荐答案

一个环形缓冲区是一对的 IndexedSeq 和内部指针到这个序列。我公司提供code为不可变的版本。请注意，并非所有可能有用所有的方法都是执行;这样的改变内容的存取器的 IndexedSeq 。

A ring buffer is a pair of an IndexedSeq and an Int pointer into this sequence. I provide code for a immutable version. Note that not all methods that might be useful are implemented; like the mutators that change the content of the IndexedSeq.

通过此实现，换挡只是制作一个新的对象。所以这是pretty效率。

With this implementation, shifting is just creating one new object. So it's pretty efficient.

class RingBuffer[A](val index: Int, val data: IndexedSeq[A]) extends IndexedSeq[A] {
  def shiftLeft = new RingBuffer((index + 1) % data.size, data)
  def shiftRight = new RingBuffer((index + data.size - 1) % data.size, data)
  def length = data.length
  def apply(i: Int) = data((index + i) % data.size)
}

val rb = new RingBuffer(0, IndexedSeq(2,3,5,7,11))

println("plain: " + rb)
println("sl: " + rb.shiftLeft)
println("sr: " + rb.shiftRight)

输出

plain: Main(2, 3, 5, 7, 11)
sl: Main(3, 5, 7, 11, 2)
sr: Main(11, 2, 3, 5, 7)

这篇关于为以循环的方式移动的序列的最佳实践的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！