Generalized range check for cyclic array (using modulo)

Question

I'm currently dealing with cyclic arrays in Algorithms & Data Structures and wanted to find a "clean" way using the modulo function to express whether an index is within a certain range of limits in a cyclic array.

$A = [a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7]$

$i_F:$ index of front element (first element)

$i_B:$ index of back element (last element)

Non-cyclic array

To check if an index is within the range given we use the simple inequality: $i_F \leq i \leq i_B$

Example:

$i_F = 2$

$i_B = 5$

We want to know if index $i=4$ is within that range. For that we use the following:

$i_F \leq i \leq i_B \Rightarrow$ $i$ is within the index range

Cyclic Array

What is the generalised inequality to check whether an index $i$ is within the range of $i_F$ and $i_B$ using the modulo function?

Example (first element is at index 6 and ends at index 4 (cyclically):

$i_F = 6$

$i_B = 3$

$i=2$ is clearly within the bounds, but $i=4$ is not.

Is it possible to express the inequality like before: $... \leq i \leq ...$?

Thank you

Answer 1

How about this: let $k$ be the length of cycle, say for you, above, $k=8$. Then "rotate" everything by subtracting $i_F$ modulo $k$ (i.e. subtracting $i_F$ and then reducing to the range $[0,k)$ modulo $k$). This gives you three new indices:

• $i_F'=i_F-i_F\pmod k=6-6\pmod 8=0$ of course,
• $i_B'=i_B-i_F\pmod k=3-6\pmod 8=-3\pmod 8=5$, and
• $i'=i-i_F\pmod k=4-6\pmod 8=-2\pmod 8=6$.

Then just check if $i_F'\le i'\le i_B'$, i.e. $0\le 6\le 5$ (here it is false).

In fact, check only whether $i'\le i_B'$ as the other inequality is always true as $i_F'=0$ at all times.

If in your favourite programming language, say, mod is the "remainder in integral division" operator, your check should look somewhat like ((i - i_F) mod k) <= ((i_B - i_F) mod k) (but beware how that language deals with negative numbers, it must still reduce them $\pmod k$).