#include <cstddef>
#include <iostream>
#include <vector>
#include <algorithm>

typedef std::size_t index_t;
typedef double element_t;
typedef std::vector<element_t> row_t;
typedef std::vector<row_t> slice_t;
typedef std::vector<slice_t> array_3d_t;

// for one dimension
template<class T>
void fftshift_dimension(std::vector<T>& row)
{
  using std::swap;
  const index_t size = row.size();
  if(size <= 1)
    return;
  const index_t halved_size = size / 2;
  //swap the two halves
  for(index_t i = 0, j = size - halved_size ; i < halved_size ; ++i, ++j)
    swap(row[i], row[j]);
  // if the size is odd, rotate the right part
  if(size % 2)
  {
    swap(row[halved_size], row[size - 1]);
    const index_t n = size - 2;
    for(index_t i = halved_size ; i < n ; ++i)
      swap(row[i], row[i + 1]);
  }
}

// base case
template<class T>
void fftshift(std::vector<T>& array) {
  fftshift_dimension(array);
}

// reduce the problem for a dimension N+1 to a dimension N
template<class T>
void fftshift(std::vector<std::vector<T>>& array) {
  fftshift_dimension(array);
  for(auto& slice : array)
    fftshift(slice);
}

// overloads operator<< to print a 3-dimensional array
std::ostream& operator<<(std::ostream& output, const array_3d_t& input) {
  const index_t width = input.size();
  for(index_t i = 0; i < width ; i++)
  {
    const index_t height = input[i].size();
    for(index_t j = 0; j < height ; j++)
    {
      const index_t depth = input[i][j].size();
      for(index_t k = 0; k < depth; k++)
        output << input[i][j][k] << ' ';
      output << '\n';
    }
    output << '\n';
  }
  return output;
}

int main()
{
  constexpr index_t width = 3;
  constexpr index_t height = 4;
  constexpr index_t depth = 5;
  
  array_3d_t input(width, slice_t(height, row_t(depth)));
  
  // initialization
  for(index_t i = 0 ; i < width ; ++i)
    for(index_t j = 0 ; j < height ; ++j)
      for(index_t k = 0 ; k < depth ; ++k)
        input[i][j][k] = i + j + k;
  std::cout << input;
  
  // in place fftshift
  fftshift(input);
  
  std::cout << "and then" << '\n' << input;
}