Today i saw a review request by a dear friend, of his toy code... it was about rotating strings with variable amount of rotations... obviously such stuff comes with requirements like no extra space and O(n) etc etc, i presume...
Anyways, as the thing is with reviews... Its tough to understand someone else's code and their perspective...
You always tend to start off with, 'why that and that' and 'why not this and this'.
Nevertheless this approach is much better than finding missing commas or color vs colour in comments ;-)
So, now it is for your 'why that and that' of this code which can rotate a contiguous memory of elements by a given width, in place, at O(n)
i think its kind of neat ;), what do you think?
Solution 1:
Start with beginning as the destination. (a) Buffer the destination and copy from source. (b) Make current destination's destination as the new destination, and use the buffer as the source. (c) If not done and looped around, start with (current destination + 1) and jump to (a)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #include <iostream> using namespace std; // shift +ve ==> Left shift // shift -ve ==> Right shift // returns the from_index for the given to_index int from(int to_index, int shift, int len) { // c++ doesnt have true modulo like Python, so we do this by hand int from_index = to_index + shift; if (from_index < 0) from_index += len; else if (from_index > len - 1) from_index -= len; return from_index; } // returns the to_index for the given from_index int to(int from_index, int shift, int len) { return from(from_index, -shift, len); } template < typename C > C rotate(C dataIn, int shift = 1) { // If dataIn is temp or implied by user, move semantics will come into picture // The intention is to not create memory here (unless required by the user) C data(dataIn); int len = data.size(); if (len == 0 || (abs(shift) % len == 0)) { return data; } // if shift > data, wrap it around and get the remainder shift = (shift / (abs(shift))) * (abs(shift) % len); auto buf = data[0];// just for type int index = 0, start_index = 0; for (int i = 0; i < len; i++) { if (index == start_index) { // we have a loop, step to next index++; start_index = index; buf = data[index]; data[index] = data[from(index, shift, len)]; index = to(index, shift, len); } else { auto tmp = data[index]; data[index] = buf; buf = tmp; index = to(index, shift, len); } } return data; } int main() { cout << "--------------left shift test (even)---------\n"; for (int i = 0; i < 14; i++) cout << rotate(std::string("HelloWorld<-"), i) << "\n"; cout << "---------------------------------------------\n\n"; cout << "-------------right shift test (odd) ---------\n"; for (int i = 0; i > -14; i--) cout << rotate(std::string(">HelloWorld"), i) << "\n"; cout << "---------------------------------------------\n\n"; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | --------------left shift test (even)--------- HelloWorld<- elloWorld<-H lloWorld<-He loWorld<-Hel oWorld<-Hell World<-Hello orld<-HelloW rld<-HelloWo ld<-HelloWor d<-HelloWorl <-HelloWorld -HelloWorld< HelloWorld<- elloWorld<-H --------------------------------------------- -------------right shift test (odd) --------- >HelloWorld d>HelloWorl ld>HelloWor rld>HelloWo orld>HelloW World>Hello oWorld>Hell loWorld>Hel lloWorld>He elloWorld>H HelloWorld> >HelloWorld d>HelloWorl ld>HelloWor --------------------------------------------- |
There is Solution 2:
If the Array is A[N] and the shift amount is S:
For left shift, the desired final arrangement P[N] is A[S:N] + A[0:S-1]
This can be done by first swapping A[0:S-1] with A[N-S:N] and then swapping the new A[0:S-1] with A[N-2S : N-S]
For right shift A[N] = A[N:N-S] + A[0:N-S+1]
This can be done similar to left shift, but it also needs a reversal of the last S elements.
Haven't written code for this, but guess this is more easier to comprehend and also prove than the first one.
This solution(2)'s core idea is actually given by my intelligent wife :-) But seems like when it comes to implementation, it will turn out to be no different than solution 1.
