Question
I'm using a circular buffer to push data onto either end of a list. After I'm done I want to align the buffer so the first element in the list is at position zero and can be used like a regular array without any fancy indexing overhead.
So I have my circular list with capacity N, it has n elements starting at arbitrary index f.
What's the fastest way to shift/rotate all the elements such that f = 0?
The catch is I want to do this in-place (though of course some registers/temporaries will be needed). The buffer may be full (n = N), [EDIT] but I'm also interested in efficiently handling the cases where it's nearly empty.
Solution
This algorithm taken from the std::rotate implementation on cplusplus.com is quite nice:
https://stackoverflow.com/questions/21479784
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russiantemplate <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last)
{
ForwardIterator next = middle;
while (first!=next)
{
swap (*first++,*next++);
if (next==last) next=middle;
else if (first==middle) middle=next;
}
}
OTHER TIPS
I will first assume that n=N. You can put the element f to 0, then 0 will go to n-f, n-f to n-2f, etc. You will, after a finite number of steps, go back to 0, thanks to group theory. You will have gone to all items at most 1 time (except of course f, which is the beginning and the end).
Will you have gone to all items at least 1? Well, it depends if l=pgcd(N, f)==0.
If l==1, you are done. If not, you have to do the same procedure l-1 times, starting from (f+1)...(f+l-1).
This procedure only use one variable and do it in-place. Each loop is runned on exacty n/f items.
The following figure illustrate the algorithm, with n=N=12 and f=3. We have l=3 so we have three loops : marron, blue, green. The initial numbers are in black, the final are colored.
If n<N the same algorihm still works, because the empty region before f in the circular array will be reported to the empty region at the end of the linear array. See the following schema for an illustration of this trick. We have N=12, n=10 and f=3, so 1 and 2 are missing (ie they are in the grey region or the ring). l=gcd(3, 12)=3 here.
For cache-friendlyness you may want to invert the two loops. You will need l variables in that case.
In pseudo-Python
from fractions import gcd
l = gcd(N, f)
niter = N//l # integer because l = gcd(N, f)
temp = t[f:(f+l-1)]
pos = f
for i=1 to niter
for j=0 to l-1
pos -= 1
pos = (pos + N) % N # in [0...N-1]
swap(temp[j], t[pos])
In the destination buffer after rotation buffer position n gets the contens of position (n + f) % N. The tricky part is the fact that all sorts of sequences of replacement can occur. This can be handled by traversing these sequences until the original position occurs. Keeping track of how many replacements have been done allows the algorithm to stop in time.
Following test method acts on a char array as that is easiest to setup:
private char[] rotate(char[] buf, int start) {
int len = buf.length;
int count = 0;
int offset = 0;
while (count < len) {
int index = offset;
char tmp = buf[index];
int index2 = (start + index) % len;
while (index2 != offset) {
buf[index] = buf[index2];
count++;
index = index2;
index2 = (start + index) % len;
}
buf[index] = tmp;
count++;
offset++;
}
return buf;
}
The following tests succeed:
public void testRotate() {
assertEquals("A", rotate("A", 0));
assertEquals("AB", rotate("AB", 0));
assertEquals("AB", rotate("BA", 1));
assertEquals("ABCD", rotate("DABC", 1));
assertEquals("ABCDE", rotate("DEABC", 2));
assertEquals("ABCDEF", rotate("DEFABC", 3));
assertEquals("ABCDEF1", rotate("DEF1ABC", 4));
assertEquals("ABCDEF12", rotate("DEF12ABC", 5));
assertEquals("ABCDEF123", rotate("DEF123ABC", 6));
}
private String rotate(String buf, int start) {
return new String(rotate(buf.toCharArray(), start));
}
Update:
The above algorithm rotates a full buffer, to optimise rotating buffers thats are not full you can pick out the quick wins and use a full rotation for what is left:
private char[] realign(char[] buf, int start, int items) {
int len = buf.length;
int offset = 0;
if (0 == start) {
// done
} else if (items <= len - start) {
// simply move to front
while (offset < items) {
buf[offset++] = buf[start++];
}
} else if (items * 2 <= len) {
// move lead out of the way first
int last = start;
int end = items - len + start;
while (0 < end) {
buf[--last] = buf[--end];
}
while (offset < items && start < len) {
buf[offset++] = buf[start++];
}
while (offset < items) {
buf[offset++] = buf[last++];
}
} else {
// use full rotate on the rest
buf = rotate(buf, start);
}
return buf;
}
This will take care of most of the situations, those where the buffer if more than half full and where it wraps over the end of the buffer are being rotated in full. The following tests succeed:
public void testRealign() {
assertEquals("A", realign("A", 0, 1));
assertEquals("AB", realign("BA", 1, 2));
assertEquals("ABCD", realign("DABC", 1, 4));
assertEquals("ABCDE", realign("DEABC", 2, 5));
assertEquals("ABCDEF", realign("DEF123ABC", 6, 6));
assertEquals("0123456789", realign("4567890123", 6, 10));
assertEquals("ABC", realign("ABC", 0, 3));
assertEquals("ABC", realign("012ABC3", 3, 3));
assertEquals("ABC", realign("01234ABC", 5, 3));
assertEquals("ABCD", realign("D1234ABC", 5, 4));
assertEquals("ABCD", realign("CD1234AB", 6, 4));
assertEquals("ABCD", realign("BCD1234A", 7, 4));
}
private String realign(String buf, int start, int items) {
return (new String(realign(buf.toCharArray(), start, items))).substring(0, items);
}
fn swapItems arr index_a index_b = (
local item_a = arr[index_a]
local item_b = arr[index_b]
arr[index_a] = item_b
arr[index_b] = item_a
),
fn rotateItems arr cnt way:#right = (
for i=1 to cnt do ( --how many times we shift
case way of (
#right:(
local next = 2
for j=1 to arr.count-1 do ( --shift each except last
swapItems arr 1 next --swap first with next
next+=1
)
)
#left:(
local prev = arr.count - 1
for j=arr.count to 2 by -1 do ( --shift each except first
swapItems arr arr.count prev --swap last with prev
prev-=1
)
)
)
)
)
ar = #(1, 2, 3, 4)
mcArray.rotateItems ar 1 > #(4, 1, 2, 3)
mcArray.rotateItems ar 2 > #(3, 4, 1, 2)
mcArray.rotateItems ar 1 way:#left > #(2, 3, 4, 1)
First of all you should not align the buffer. Looks like an unnecessary overhead.
The tastes way to implement this should be
1) Create a new array
2) Copy elements (std::copy) from n=0 to end of array
3) Copy begining of the array from f=0 to n=6
4) std::swap arrays
