旋转 Scala 集合

1. Introduction

When dealing with an ordered collection, we sometimes need to perform rotations over its elements. This means that we can think of the collection as if it was a ring, connecting its last element to the first, and then we can take a view of the collection, starting from any element.

We can also think of this as shifting the elements of the collection left or right, and the elements that exit the collection through one of the extremes enter it again through the other one.

The problem we’ll tackle in this tutorial is creating a rotated view of a sequential collection at any arbitrary index.

2. Solution

Many approaches exist to solve this problem, but if we want to be idiomatic and efficient, we should leverage the immutability of collections and their extremely rich API.

Let’s start by creating an implicit value class to add a method rotatedView() to all sequences:

object Rotator {
  implicit class Wrapper[T](val sequence: Seq[T]) extends AnyVal {
    def rotatedView(index: Int): Seq[T] = ???
  }
}

This isn’t strictly necessary, but it’s useful here and a pattern we should try to master.

Now, we can focus on the implementation of the method:

def rotatedView(index: Int): Seq[T] = {
  val length = sequence.length
  if (length == 0) sequence
  else {
    val normalisedIndex = (index % length + length) % length
    val (left, right) = sequence.splitAt(normalisedIndex)
    right ++ left
  }
}

First, we find the sequence length, and if it’s zero, we do nothing.

Otherwise, the algorithm takes the passed rotation index and uses it to split the collection into two parts. Then it simply swaps the two parts and joins them back again.

Perhaps the most interesting part of this solution is calculating the index at which the splitting happens. Why is that? It’s because there’s no guarantee that the passed index will be between zero and the collection size!

On the one hand, it’s possible that a positive index is larger than the size of the collection, in which case it’ll be treated as if several whole rotations happen.

On the other hand, it’s possible that a negative index is handed, which means we need to rotate the collection in the other direction. Once again, it’s completely possible that the value of the negative index is larger than the size of the collection, so we need to cater to that, too.

3. Testing

Let’s test our solution using ScalaTest. First, let’s create the scaffolding:

class RotatorSpec extends AnyWordSpec {
  import Rotator._

  "A rotator of collections" should {
    // add tests here
  }
}

Note how we import the elements of the object Rotator, including our implicit value class.

Now, it’s time for some tests. First, we want to validate that an empty collection won’t break things:

"do nothing to an empty list" in {
  val sequence = Vector.empty[Char]
  assert(sequence.rotatedView(8).isEmpty)
}

If the rotation is zero, the collection is not touched:

"do nothing when the rotation is zero" in {
  val sequence = Vector('a', 'b', 'c', 'd', 'e')
  assertResult(sequence)(sequence.rotatedView(0))
}

Next, let’s test the positive rotations, including the possibility that the rotation is larger than the collection size:

"handle positive rotations" in {
  val sequence = Vector('a', 'b', 'c', 'd', 'e')
  assertResult(Vector('b', 'c', 'd', 'e', 'a'))(sequence.rotatedView(1))
  assertResult(Vector('e', 'a', 'b', 'c', 'd'))(sequence.rotatedView(4))
  assertResult(Vector('b', 'c', 'd', 'e', 'a'))(sequence.rotatedView(6))
}

Next, we do something equivalent but for negative rotations:

"handle negative rotations" in {
  val sequence = Vector('a', 'b', 'c', 'd', 'e')
  assertResult(Vector('b', 'c', 'd', 'e', 'a'))(sequence.rotatedView(-4))
  assertResult(Vector('e', 'a', 'b', 'c', 'd'))(sequence.rotatedView(-1))
  assertResult(Vector('a', 'b', 'c', 'd', 'e'))(sequence.rotatedView(-10))
}

Finally, we want to guarantee that the resulting sequences can be further used in functional operations like foldLeft():

"support folding" in {
  val sequence = Vector('u', 'n', 'g', 'b', 'a', 'e', 'l', 'd')
  val rotatedAndFolded =
    sequence
      .rotatedView(3)
      .foldLeft("")((str, char) => str :+ char)
  assertResult("baeldung")(rotatedAndFolded)
}

4. Conclusion

In this article, we’ve examined an efficient and idiomatic way to rotate a finite, ordered collection.

As usual, the full code for this article is available over on GitHub.