noncom - 1 year ago 67
Scala Question

# 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
``````

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!!!

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)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download