rotate.c

//
//  main.c
//  rotate
//
//  Created by Dave Kennedy on 30/11/2016.
//  Copyright © 2016 Dave Kennedy. All rights reserved.
//

#include <stdio.h>
#include <string.h>

/*
 Now we're going to rotate in-place and at low level
 Nothing is hidden - we're at the lowest memory abstraction of the languages
 
 Given:  "abcdefgh" <- 3
 We want "defghabc"
 
 How to get the first 3 characters at the back quickly?
 Reverse the array
 h g f e d c b a
          |-----
          |These are the characters I want at the back
 |--------
 | These are the characters I want at the front
 
 Three reversal operations are required
 1) Flip the whole array
 2) Reverse from 0 to (n - i)
 3) Reverse from (n-i) to n
 
 Total extra space required: 1 char
 
 Can it be done without flipping?
 Possibly, with a complicated algorithm. Lack of care leads to "defghcab" which is wrong
 
*/

#define SWAP(a,b) { \
    char t; \
    t = a; \
    a = b; \
    b = t;\
}

void reverse (char* chars, size_t start, size_t end) {
    char* left = chars+start;
    char* right = chars+end;
    while (left < right) {
        SWAP(*left,*right);
        
        left++;
        right--;
    }
}
void rotate (char* chars, int amount) {
    size_t length = strlen (chars);
    reverse (chars, 0, length);
    reverse (chars, 0, length-amount);
    reverse (chars, length-amount, length);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    char set [] = "abcdefgh";
    printf("%s\n", set);
    rotate(set, 3);
    printf("%s\n", set);
    
    return 0;
}