Path: csiph.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!feeder.erje.net!1.eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail
From: Melzzzzz <mel@zzzzz.com>
Newsgroups: comp.programming
Subject: Re: Rotation
Date: Tue, 5 Jan 2016 09:13:13 +0100
Organization: albasani.net
Lines: 52
Message-ID: <20160105091313.2ff01847@maxa-pc>
References: <f8f1edff-9175-4210-8877-fdd0ffa4f42c@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Trace: news.albasani.net lSVpPQZpt4z+6x59uRzkGdyjOk2mU8u4WggqWMHo+uhhNrSsYVks38SqRJ6Fc2iyXDoBtdhSbS6Ze5w+7tKbJg==
NNTP-Posting-Date: Tue, 5 Jan 2016 08:13:13 +0000 (UTC)
Injection-Info: news.albasani.net; logging-data="xGBQ6AvegXVRSaZifhY5/yPvYKC4qe2NmKMTxDIpHpYeBSBN0eeafDqdIHAEPUWOjUWVr4ONkAXD5BiFcmh6nhJrG7wU1NP7swjyiSHqjzEGwvpUYZ910BEYKArYEGvd"; mail-complaints-to="abuse@albasani.net"
X-Newsreader: Claws Mail 3.13.1 (GTK+ 2.24.29; x86_64-unknown-linux-gnu)
Cancel-Lock: sha1:GFsjZ8ZegS0U2IVTgI426+9MpnE=
Xref: csiph.com comp.programming:6199

On Mon, 4 Jan 2016 09:25:50 -0800 (PST)
Paul <pepstein5@gmail.com> wrote:

> Suppose we want to rotate the list of numbers [1, 2, 3, 4, ..., 10]
> so that it begins with a 4 and we end up with [4,...10, 1, 2, 3]. 
> 
> I was looking at the standard-library c++ way to do this from
> http://www.cplusplus.com/reference/algorithm/rotate/ 
> 
> There we get (as an example) the code below.  To rotate as above,
> middle would be the pointer to 4 which is indexed 3 in c++ which
> begins counting at zero. 
> 
> 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; 
>   } 
> } 
> 
> 
> I can verify that this code works for special cases but it's not
> intuitively clear that it should always work.  Basically, I don't
> understand why it should work as an algorithm for rotation, although
> I can verify it. 
> 
> What is a good intuitive way of seeing that this algorithm rotates a
> list, and what is a good way (or text) for improving intuition about
> thinking about these things so that I can come up with such
> algorithms by myself? 
> 
> Thank You 
> 
> Paul 
Well if this is not in place rather outputs to different list than it
is easy to understand.

next = middle;
while(next != last) {
	*out++=*next++;
}
next = first;
while(next != middle) {
	*out++=*next++;
}