arrays - Best practice for shifting a sequence in a circular manner

Question

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

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.

UPDATE:

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

Answer 1

Immutable implementation

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.

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

Example code

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)

Output

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

Performance comparison to mutable implementations

The OP mentions that you should look at the mutable implementations (e.g. this answer), if you need performance. This is not true in general. As always: It depends.

Immutable

• update: O(log n), which is basically the update complexity of the underlying IndexedSeq;
• shifting: O(1), also involves creating a new object which may cost some cycles

Mutable

• update: O(1), array update, as fast as it gets
• shifting: O(n), you have to touch every element once; fast implementations on primitive arrays might still win against the immutable version for small arrays, because of constant factor