arraysalgorithmlistcircular-buffer
Shifting/aligning/rotating a circular buffer to zero in-place
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:
template <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;
}
}