path: root/csrc/algorithms/arrays/rotate.h

/**
 * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 * 
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#ifndef ALGO_ALGORITHMS_ARRAYS_ROTATE_H
#define ALGO_ALGORITHMS_ARRAYS_ROTATE_H


/* NB! This will not play nice if the placeholder `T` is
 * not set to a type only containing [0-9A-Za-z_] (and $
 * in GNU C). Therefore, with the exception of `char`,
 * `short`, `int`, `long`, `float` and `double`, you
 * should only use `typedef`:ed types. */


#include <stddef.h>


#define algo_macro_swap_items()  \
  (temp = items[i], items[i] = temps[j], items[j] = temp)


/**
 * Rotate an array.
 * 
 * This function perform an inline rotation, it is probably
 * faster if you create a new array and make a rotated copy
 * into that array. It may even more faster to create a
 * temporary array and copy the content back than using
 * this inline rotation if you want the rotation to be
 * stored in the same array. If you choose that latter,
 * `alloca` can be used to create new array on the stack.
 * 
 * `algo_make_implementation_of_rotate(T)` is used to make
 * this function available for a particular data type `T`. And
 * implementation without modifiers and attributes will be
 * expanded. You may add `static`, `inline` and `__attribute__`
 * before calling `algo_make_implementation_of_rotate(T)`.
 * 
 * `algo_make_prototype_of_rotate(T)` is the prototype
 * counterpart of `algo_make_implementation_of_rotate(T)`.
 * It too is will not add any modifiers or attributes by
 * default. It will neither add a semicolon at the end of
 * the prototype.
 * 
 * `algo_rotate(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_rotate(T))` gets the address of this function
 * and `algo_rotate(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  n      The number of elements in `items`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_rotate(T)(items, n, (n - steps) % n)`.
 */
//>fun () {
void algo_rotate__##T(T* restrict items, size_t n, size_t steps)
{
  size_t i, j;
  T temp;
  
  steps = (n - steps) % n;
  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
  for (i = 0,     j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
}
//>} ; . ../make_fun


/**
 * Rotate an array and reverse it afterwords.
 * 
 * `algo_make_implementation_of_rotate_reverse(T)` is used
 * to make this function available for a particular data
 * type `T`. And implementation without modifiers and
 * attributes will be expanded. You may add `static`,
 * `inline` and `__attribute__` before calling
 * `algo_make_implementation_of_rotate_reverse(T)`.
 * 
 * `algo_make_prototype_of_rotate_reverse(T)` is the prototype
 * counterpart of `algo_make_implementation_of_rotate_reverse(T)`.
 * It too is will not add any modifiers or attributes by
 * default. It will neither add a semicolon at the end of
 * the prototype.
 * 
 * `algo_rotate_reverse(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_rotate_reverse(T))` gets the address of this function
 * and `algo_rotate_reverse(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  n      The number of elements in `items`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_rotate_reverse(T)(items, n, (n - steps) % n)`.
 */
//>fun () {
void algo_rotate_reverse__##T(T* restrict items, size_t n, size_t steps)
{
  size_t i, j;
  T temp;
  
  steps = (n - steps) % n;
  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
}
//>} ; . ../make_fun


/**
 * Reverse an array and rotate it afterwords.
 * 
 * `algo_make_implementation_of_reverse_rotate(T)` is used
 * to make this function available for a particular data
 * type `T`. And implementation without modifiers and
 * attributes will be expanded. You may add `static`,
 * `inline` and `__attribute__` before calling
 * `algo_make_implementation_of_reverse_rotate(T)`.
 * 
 * `algo_make_prototype_of_reverse_rotate(T)` is the prototype
 * counterpart of `algo_make_implementation_of_reverse_rotate(T)`.
 * It too is will not add any modifiers or attributes by
 * default. It will neither add a semicolon at the end of
 * the prototype.
 * 
 * `algo_reverse_rotate(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_reverse_rotate(T))` gets the address of this function
 * and `algo_reverse_rotate(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  n      The number of elements in `items`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_reverse_rotate(T)(items, n, (n - steps) % n)`.
 */
//>fun () {
void algo_reverse_rotate__##T(T* restrict items, size_t n, size_t steps)
{
  size_t i, j;
  T temp;
  
  for (i = 0,     j = steps - 1; i < j; i++, j--)  algo_macro_swap_items();
  for (i = steps, j =     n - 1; i < j; i++, j--)  algo_macro_swap_items();
}
//>} ; . ../make_fun


/**
 * Write a rotated copy of an array into another array.
 * 
 * `algo_make_implementation_of_rotate_into(T)` is used to make
 * this function available for a particular data type `T`. And
 * implementation without modifiers and attributes will be
 * expanded. You may add `static`, `inline` and `__attribute__`
 * before calling `algo_make_implementation_of_rotate_into(T)`.
 * 
 * `algo_make_prototype_of_rotate_into(T)` is the prototype
 * counterpart of `algo_make_implementation_of_rotate_into(T)`.
 * It too is will not add any modifiers or attributes by
 * default. It will neither add a semicolon at the end of
 * the prototype.
 * 
 * `algo_rotate_into(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_rotate_into(T))` gets the address of this function
 * and `algo_rotate_into(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  out    The array to fill with a rotated copy of `items`.
 * @param  n      The number of elements in `items` and in `out`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_rotate_into(T)(items, out, n, (n - steps) % n)`.
 */
//>fun () {
void algo_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
{
  size_t m = n - steps;
  T* restrict out_a = out + steps;
  T* restrict out_b = out;
  const T* end_a = items + m;
  const T* end_b = items + n;
  
  while (items != end_a)  *out_a++ = *items++;
  while (items != end_b)  *out_b++ = *items++;
}
//>} ; . ../make_fun

  
#undef algo_macro_swap_items


/**
 * Write a rotated and reversed copy of an array into another array.
 * 
 * `algo_make_implementation_of_rotate_reverse_into(T)` is used to
 * make this function available for a particular data type `T`. And
 * implementation without modifiers and attributes will be expanded.
 * You may add `static`, `inline` and `__attribute__` before calling
 * `algo_make_implementation_of_rotate_reverse_into(T)`.
 * 
 * `algo_make_prototype_of_rotate_reverse_into(T)` is the prototype
 * counterpart of `algo_make_implementation_of_rotate_reverse_into(T)`.
 * It too is will not add any modifiers or attributes by default. It
 * will neither add a semicolon at the end of the prototype.
 * 
 * `algo_rotate_reverse_into(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_rotate_reverse_into(T))` gets the address of this function
 * and `algo_rotate_reverse_into(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  out    The array to fill with a rotated copy of `items`.
 * @param  n      The number of elements in `items` and in `out`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_rotate_reverse_into(T)(items, out, n, (n - steps) % n)`.
 */
//>fun () {
void algo_rotate_reverse_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
{
  size_t m = n - steps;
  T* restrict out_a = out + n - steps;
  T* restrict out_b = out + n;
  const T* end_a = items + m;
  const T* end_b = items + n;
  
  while (items != end_a)  *--out_a = *items++;
  while (items != end_b)  *--out_b = *items++;
}
//>} ; . ../make_fun


/**
 * Write a reversed and rotated copy of an array into another array.
 * 
 * `algo_make_implementation_of_reverse_rotate_into(T)` is used to
 * make this function available for a particular data type `T`. And
 * implementation without modifiers and attributes will be expanded.
 * You may add `static`, `inline` and `__attribute__` before calling
 * `algo_make_implementation_of_reverse_rotate_into(T)`.
 * 
 * `algo_make_prototype_of_reverse_rotate_into(T)` is the prototype
 * counterpart of `algo_make_implementation_of_reverse_rotate_into(T)`.
 * It too is will not add any modifiers or attributes by default. It
 * will neither add a semicolon at the end of the prototype.
 * 
 * `algo_reverse_rotate_into(T)` is used to get the version of the
 * function that supports the data type `T`.
 * `&(algo_reverse_rotate_into(T))` gets the address of this function
 * and `algo_reverse_rotate_into(T)(items, n)` calls the function.
 * 
 * Undefined behaviour is invoked if `steps >= n`.
 * 
 * @param  items  The array to rotate.
 * @param  out    The array to fill with a rotated copy of `items`.
 * @param  n      The number of elements in `items` and in `out`.
 * @param  steps  The number of steps to rotate the array
 *                rightwards. If you want a leftwards
 *                rotation you used call
 *                `algo_reverse_rotate_into(T)(items, out, n, (n - steps) % n)`.
 */
//>fun () {
void algo_reverse_rotate_into__##T(const T* restrict items, T* restrict out, size_t n, size_t steps)
{
  size_t m = n - steps;
  T* restrict out_a = out + steps;
  T* restrict out_b = out;
  const T* end_a = out + n;
  const T* end_b = out + steps;
  
  while (out_a != end_a)  *out_a++ = *--items;
  while (out_b != end_b)  *out_b++ = *--items;
}
//>} ; . ../make_fun

  
#undef algo_macro_swap_items


#endif