Efficiently rotating a 2D array up by treating it as a "ring buffer" or "circular buffer"
Let's not copy or move the data in the 2D array. That's not efficient. Instead, let's rotate this 2D array by moving an i_start row index around, treating the whole thing like a "ring buffer" or "circular buffer", which is a common architectural style for an efficient FIFO buffer, especially in embedded systems.
@Dave mentions this concept in his answer here.
The time complexity of copying and/or rewriting the array to rotate it is equal to O(n), where n is the number of rows in this case. The time complexity of my approach below is a very short O(1), regardless of how big the array is or how many rows it has, since all we are doing to "rotate" it up is array2d->i_start = (array2d->i_start + 1) % NUM_ROWS;, which is very efficient!
Here is a full demonstration of this concept, using C-style arrays in C++. Note that if you just got rid of the = 0; part of the struct below, and also typedefed it (my preference) or added the word struct in a few more places where needed, this would also be a perfectly-valid C program.
cpp/ring_buffer_rotate_2d_array_up.cpp from my eRCaGuy_hello_world repo:
///usr/bin/env ccache g++ -Wall -Wextra -Werror -O3 -std=gnu++17 "$0" -o /tmp/a && /tmp/a "$@"; exit
// For the line just above, see my answer here: https://stackoverflow.com/a/75491834/4561887
// C++ (incl. C) includes
#include <cstdio> // For `printf()`
#include <iostream> // For `std::cin`, `std::cout`, `std::endl`, etc.
// Get the number of elements in any C array
// - from my repo here:
// https://github.com/ElectricRCAircraftGuy/eRCaGuy_hello_world/blob/master/c/utilities.h#L42
#define ARRAY_LEN(array) (sizeof(array) / sizeof((array)[0]))
/// Definitions: `rows` = "rows"; `cols` = "columns"
/// Get number of rows in a 2D array
#define NUM_ROWS(array_2d) ARRAY_LEN(array_2d)
/// Get number of columns in a 2D array
#define NUM_COLS(array_2d) ARRAY_LEN((array_2d)[0])
struct Array2d
{
// the actual C-style 2D array of data
int array[4][4];
// the starting index for the array, which represents the "first row"
size_t i_start = 0;
};
// Print the 2D array.
// - Note: pass by const reference since we won't change the array while
// printing.
void array2d_print(const Array2d& array2d)
{
const size_t NUM_ROWS = NUM_ROWS(array2d.array);
const size_t NUM_COLS = NUM_COLS(array2d.array);
size_t i_row = array2d.i_start;
for (size_t row = 0; row < NUM_ROWS; row++)
{
for (size_t i_col = 0; i_col < NUM_COLS; i_col++)
{
printf("%3i", (array2d.array)[i_row][i_col]);
if (i_col < NUM_COLS - 1)
{
printf(",");
}
else
{
printf("\n");
}
}
// increment our "ring-buffer-style" row index
i_row = (i_row + 1) % NUM_ROWS;
}
printf("\n");
}
// Rotate the 2D array up.
// - Note: pass by ptr since we **will** change the array (the `i_start` index
// in this case), and we want this fact to be obvious when the user calls
// this function.
void array2d_rotateup(Array2d* array2d)
{
const size_t NUM_ROWS = NUM_ROWS(array2d->array);
// Note: since the `i_start` index is an **unsigned** integer `size_t` type,
// this approach works perfectly fine even if the integer value overflows
// upward and rolls over, so there is never a need to check for overflow.
// This works fine and is well-defined behavior as-is. **Signed** integers,
// however, have technically **undefined** behavior during overflow and
// underflow.
array2d->i_start = (array2d->i_start + 1) % NUM_ROWS;
}
int main()
{
Array2d array2d =
{
.array =
{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16},
}
};
// print the starting array
array2d_print(array2d);
// now rotate and print the array NUM_ROWS times
for (size_t i = 0; i < NUM_ROWS(array2d.array); i++)
{
array2d_rotateup(&array2d);
array2d_print(array2d);
}
return 0;
}
Run command and output:
eRCaGuy_hello_world$ cpp/ring_buffer_rotate_2d_array_up.cpp
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16
1, 2, 3, 4
9, 10, 11, 12
13, 14, 15, 16
1, 2, 3, 4
5, 6, 7, 8
13, 14, 15, 16
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
1, 2, 3, 4
5, 6, 7, 8
9, 10, 11, 12
13, 14, 15, 16
References
- [my answer on 2D arrays] How to use multidimensional (ex: 2D) arrays, and pointers to them, as function parameters in C and C++
See also
- For more on ring (circular) buffers, including a full demo/library module, see my containers_ring_buffer_FIFO.c file in my eRCaGuy_hello_world repo.
