How to implement carousel with an array

Question

I have an array of items representing a virtual carousel.

const carousel = ['a','b','c','d','e'];
let currentIndex = 0;

function move (amount) {
   const l = items.length;  // in case carousel size changes

   // need to update currentIndex

   return carousel[currentIndex];

}

What is a clean or clever way to handle moving left when currentIndex == 0 and moving right when currentIndex == length-1?

I have thought about this before and have never come with anything very clever or concise.

Answer 1

short answer

Implement a circular array via modular arithmetic. Given a distance to move, to calculate the appropriate index:

// put distance in the range {-len+1, -len+2, ..., -1, 0, 1, ..., len-2, len-1}
distance = distance % len
// add an extra len to ensure `distance+len` is non-negative
new_index = (index + distance + len) % len

long answer

Use modular arithmetic much like how you'd read a typical analog clock. The premise is to add two integers, divide by a integer, and keep the remainder. For example, 13 = 3 (mod 10) because 13 is 1*10 + 3 and 3 is 0*10 + 3.

But why did we choose to arrange 3 and 13 as we did? To answer that, we consider the Euclidean division algorithm (EDA). It says for two integers a and b there exists unique integers q and r such that

a = b*q + r

with 0 ≤ r < b. This is more powerful than you'd think: it allows us to "work modulo n."

That is, we can say a = b (mod n) iff there are unique integers q1, r1, q2, and r2 such that

a = n * q1 + r1,   0 ≤ r1 < n
b = n * q2 + r2,   0 ≤ r2 < n

and r1 equals r2. We call r1 and r2 the "remainders."

To go back to the previous example, we now know why 13 = 3 (mod 10). The EDA says 13 = 1*10 + 3 and that 1 and 3 are the only q and r satisfying the necessary constraints; by similar logic, 3 = 0*10 + 3. Since the remainders are equal, we say that 13 and 3 are equal when "working mod 10."

Fortunately, JavaScript implements a modulo operator natively. Unfortunately, we need to watch out for a quirk, i.e., the modulo operator keeps the sign of its operands. This gives you some results like -6 % 5 == -1 and -20 % 7 == -6. While perfectly valid mathematical statements (check why), this doesn't help us when it comes to array indices.

Lemma 1: a + n = a (mod n)
Lemma 2: -1 = n-1 (mod n)
Lemma 3: -a = n-a (mod n)

The way to overcome this is to "trick" JavaScript into using the correct sign. Suppose we have an array with length len and current index index; we want to move the index by a distance d:

// put `d` within the range {-len+1, -len+2, ..., -2, -1, -0}
d = d % len
// add an extra len to ensure `d+len` is non-negative
new_index = (index + d + len) % len

We accomplish this by first putting d within the range {-len+1, -len+2, ..., -2, -1, -0}. Next, we add an extra len to make sure the distance we're moving is within the range {1, 2, ..., len-1, len}, thereby ensuring the result of the % operation has a positive sign. We know this works because (-a+b) + a = b (mod a). Then we just set the new index to index + d + len (mod len).

More detailed implementation:

class Carousel {
  // assumes `arr` is non-empty
  constructor (arr, index = 0) {
    this.arr = arr
    this.index = index % arr.length
  }
  // `distance` is an integer (...-2, -1, 0, 1, 2, ...)
  move (distance) {
    let len = this.arr.length
    distance = distance % len
    let new_index = (this.index + distance + len) % len
    this.index = new_index
    return this.arr[this.index]
  }
}

// usage:
let c = new Carousel(['a','b','c','d','e'], 1) // position pointer set at 'b'
c.move(-1)  // returns 'a' as (1 + -1 + 5) % 5 == 5 % 5 == 0
c.move(-1)  // returns 'e' as (0 + -1 + 5) % 5 == 4 % 5 == 4
c.move(21)  // returns 'a' as (4 + 21 + 5) % 5 == 30 % 5 == 0

Answer 2

I had implemented an Array.prototype.rotate() a while back. It might come very handy for this job. Here is the code;

Array.prototype.rotate = function(n) {
var len = this.length;
return !(n % len) ? this.slice()
                  : this.map((e,i,a) => a[(i + (len + n % len)) % len]);
};
var a = [1,2,3,4,5,6,7,8,9],
    b = a.rotate(10);
console.log(JSON.stringify(b));
    b = a.rotate(-10);
console.log(JSON.stringify(b));

Answer 3

currentIndex = currentIndex + change;
if (currentIndex >= l)  currentIndex = 0;
if (currentIndex < 0) currentIndex = l -  1;

This will modify the index, check if it's broken possible values and adjust to either 'side' of the carousel.