I think the idea expressed in the first reply, involving enough temp storage to hold the difference in size between the two parts, will have the smallest footprint that can be implemented by simply incrementing (or decrementing) pointers.

But if you really want to pursue a single-temp-register solution, the basic idea for the pointer arithmetic would go like this:

1. Pick a starting point in the buffer and move its value into the temp register - for simplicity, let this initial "move-to" pointer (p1) be offset 0 from the start of the buffer.
2. What do you add to this address in order to point to the element that should be moved here? Let's call it D; set a "move-from" pointer (p2) equal to p1 + D.
3. Move the value from p2 to p1.
4. Now set p1 = p2 ("move-from" becomes "move-to") and add D to p2 (setting the next "move-from" value) and go back to step 3 - but here's the first arcane part: whenever this addition puts the pointer value past the end of the buffer, subtract the length of the buffer (i.e. allow the pointer to just wrap around).
5. The next arcane part: if D is an even number, then at some point you'll reach an iteration where p2 is set to the initial value of p1 (where the initial move was from p1 into the temp register), so move from the temp into this p1 location, then increment both pointers by 1, move the value from the new p1 into the temp register, and return to step 3.
6. Last arcane part: keep count of every move, including moves out of (not into) the temp register; when you've done buffer_count moves, you're done. (When D is odd, this will be the first iteration where p2 turns up to have the initial value of p1, so you'll move from temp on this iteration.)

I hope I've got that right (I suspect there may be a better way to describe it)... If it all sounds like a better idea than using more storage, then have fun with that.

(Update: Regarding the "completion condition" (item 6), there is a better (more correct) description: it will always happen on an iteration where a value is moved out of the temp register. When D is odd, this happens only once, and when it's even, it happens exactly twice - once for the even-numbered offsets, and once for the odd-numbered ones.)

(Another update -- sorry... The problem in steps 5 and 6 is not just an even/odd thing. It has to do with the largest common divisor of D and buffer_count; e.g. if D and buffer_count are both multiples of 4, then you'll need to move values out of the temp register a total of four times; you'll need to add 1 to the pointers after the first three of those, and the fourth one will be the final iteration.)

Can't... stop... updating... I improved the phrasing in step 3 (I hope it's clearer), and here is a diagram of the sequence (using a small buffer).

Do you know a priori when the second half is shorter than the first? The obvious thing to me is to have a third buffer equal in size to the difference between the two where you store the part that you're about to overwrite.

The clever way that struck me while trying to get around that is to reverse the whole thing, then reverse each of the sub-buffers. It takes more time but it does it in place.

edit: other than the triple reverse, I can't do it in place (i.e. without a third buffer equal to the difference) without putting in a bunch of rotations to get the ends of the longer buffer in the right place:

first, swap the ends of the longer one so you won't overwrite the trailing elements of the long one:

[X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7]
[download]

becomes

then to a straight swap

then you're stuck rotating the trailing elements of the longer one back into place

[Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X9 X2 X3 X4 X5 X6 X7 X8]
[Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X2 X3 X4 X5 X6 X7 X8 X9]
[download]

I can do it with just one temp and n+m+(m-n) swaps (on paper):

 0 1 2 3 4 5 6 7 8 
[a b c d e f 1 2 3] temp
      [d]>>>>>>>>>>>[d]             temp = *(p1+p1len+1)     // want t
+o move [0]->[3] so put [3]->temp  (1)
[a]>>>[d]                        *(p1+p1len+1) = *(p1+0)     // [0]->[
+3]                                (2)
[e]<<<<<[e]                      *(p1+0) = *(p1+p1len+2)     // want t
+o move [1]->[4] so put [4]->[0]   (3)
  [b]>>>[b]                      *(p1+p1len+2) = *(p1+1)     // [1]->[
+4]                                (4)
  [f]<<<<<[f]                    *(p1+1) = *(p1+p1len+3)     // want t
+o move [2]->[5] so put [5]->[1]   (5)
    [c]>>>[c]                    *(p1+p1len+3) = *(p1+2)     // [2]->[
+5] leaving [2] free so            (6)
    [3]<<<<<<<<<[3]              *(p1+2) = *(p2+p2len-1)     // [2]<-[
+8] leaving [8] free so            (7)
  [f]>>>>>>>>>>>[f]              *(p2+p2len-1) = *(p1+1)     // [1]->[
+8] leaving [1] free so            (8)
  [2]<<<<<<<<<[2]                *(p1+1) = *(p2+p2len-2)     // [1]<-[
+7] leaving [7] free so            (9)
[e]>>>>>>>>>>>[e]                *(p2+p2len-2) = *(p1+0)     // [0]->[
+7] leaving [0] free so           (10)
[1]<<<<<<<<<[1]                  *(p1+0) = *(p2+p2len-3)     // [0]<-[
+6] which leaves [6] free         (11)
            [d]<<<<<[d]          *(p2+p2len-3) = temp;       // for th
+e value in temp                  (12)
[1 2 3 a b c d e f]                                            m=6, n=
+3, moves= 6+3+(6-3) = 12
[download]

But I'm damned if I can see any pattern to the increments & decrements or steps; to capture that for a generic M+N?

the triple reverse (which really is only two passes through the whole thing).

That's really quite brilliant, I'd never have thought of that :), and it will certainly be what O shall fall back to if I can't get this working.

But as the left buffers are going to be 2GB or 4GB or 8GB or 16GB or 32GB (depending on physical memory in the machine)

and the right buffer could be anything from 16 bytes up to the (leftBufferSize)-16 (ie. whatever is left in the dataset modulus the leftBufferSize)

you can see why I'd rather avoid (M+N)*2 if I can get M+N+(M-N). (And also why a 3 buffer is impractical.)

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
m=6, n=3, moves= 6+3+(6-3) = 12

void swapBufferChunks( U8 *buf, U32 start1, U32 start2, U32 bufsize ) 
+{
    register U64 *p1 = (U64*)&buf[ start1 ];
    register U64 *p2 = (U64*)&buf[ start2 ];
    register U64 temp;

    shift_size = p2 - p1;
    end_buf = p1 + bufsize;   # assuming bufsize is byte count
    item_count = bufsize / 8; # assuming elements are 8-bytes each
    iter_count = 0;

    bgn_ofs = p1;
    temp = *p1;

    while ( iter_count < item_count ) {
        if ( p2 = bgn_ofs ) {
            *p1 = temp;
            iter_count++;
            last if ( iter_count == item_count ); # break out of while
+ loop as soon as this is true
            p1++;
            p2++;
            bgn_ofs = p1;
            temp = *p1;
        }
        *p1 = *p2;
        iter_count++;
        p1 = p2;
        p2 += shift_size;
        p2 -= bufsize if ( p2 >= end_buf );
    }
}
[download]

(Updating again to mention that my snippet is bound to have a problem when it hits the last iteration; I haven't tried to fix that in the snippet (left as an exercise for the reader) -- hint: must increment iter_count every time a value is assigned to *p1, and must exit the while loop as soon as iter_count reaches the value of item_count.

(final update: last line used to say ... if ( p2 > end_buf ) which was bound to be wrong. Hell, while I'm at. might as well fix the last-iteration problem too. Still, this sort of thing needs really careful testing, which I haven't done.)

Yes. I think you filled in the last piece o fthe puzzle for me...I'll get back once I've coded and tested it. Thank you!

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

I've (possibly as a consequence of reading graff's post, but I'm not sure), come up with two patterns that I think will solve all cases, but I'm still having the devil's own trouble translating them into code!

Here are the two graphically, with some (possible, but incomplete) pointer math attempting to describe the swaps.

An bigger even/smaller odd case:

p2+p2len            -3-2-1
p2                  +0+1+2
p1+p1len-6-5-4-3-2-1
p1      +0+1+2+3+4+5
         0 1 2 3 4 5 6 7 8 
        [a b c d e f 1 2 3] temp
                    [1]>>>>>>[1]       temp   = *(p2+0)
              [d]>>>[d]               *(p2+0) = *(p1+3)
        [a]>>>[a]                     *(p1+3) = *(p1+0)
        [1]<<<<<<<<<<<<<<<<<<[1]      *(p1+0) =  temp
                      [2]>>>>[2]       temp   = *(p2+1)
                [e]>>>[e]             *(p2+1) = *(p1+4)
          [b]>>>[b]                   *(p1+4) = *(p1+1)
          [2]<<<<<<<<<<<<<<<<[2]      *(p1+1) =  temp
                        [3]>>[3]       temp   = *(p2+2)
                  [f]>>>[f]           *(p2+2) = *(p1+5)
            [c]>>>[c]                 *(p1+5) = *(p1+2)
            [3]<<<<<<<<<<<<<<[3]      *(p1+2) =  temp    
        [1 2 3 a b c d e f]
[download]

The above looks like 3 reps of a loop. (But is that because 6-3 = 3 or just because The smaller is 3; or ... ). And code?

A bigger odd/smaller even case:

p2+p2len                  -4-3-2-1
p2                        +0+1+2+3
p1+p1len-9-8-7-6-5-4-3-2-1
p1      +0+1+2+3+4+5+6+7+8
         0 1 2 3 4 5 6 7 8 
        [a b c d e f g h i 1 2 3 4] temp  
                                [4]>>[4]      temp   = *(p2+3)
                        [i]>>>>>[i]          *(p2+3) = *(p1+8) 
                [e]>>>>>[e]                  *(p1+8) = *(p1+4)
        [a]>>>>>[a]                          *(p1+4) = *(p1+0)
        [1]<<<<<<<<<<<<<<<[1]                *(p1+0) = *(p2+0)
                  [f]>>>>>[f]                *(p2+0) = *(p1+5)
          [b]>>>>>[b]                        *(p1+5) = *(p1+1)
          [2]<<<<<<<<<<<<<<<[2]              *(p1+1) = *(p2+2)
                    [g]>>>>>[g]              *(p2+2) = *(p1+6)
            [c]>>>>>[c]                      *(p1+6) = *(p1+2)
            [3]<<<<<<<<<<<<<<<[3]            *(p1+2) = *(p2+2)
                      [h]>>>>>[h]            *(p2+2) = *(p1+7)
              [d]>>>>>[d]                    *(p1+7) = *(p1+3)
              [4]<<<<<<<<<<<<<<<<<<<<[4]     *(p1+3) =  temp
        [1 2 3 4 a b c d e f g h i]
[download]

The above looks like 4 iterations (because the smaller is length 4), but the first iteration requires 3 internal steps and the other 3 only 2? (How to code?)

I haven't convinced myself I don't need even/even and odd/odd cases yet.

I've copied what you did and added the iterator and reexpressed the righthand sides in terms of the lengths (the lefts are just the rights from the previous line) and the pattern starts to show up (at least if you click on "download" to view it spread out).

p2+p2len            -3-2-1
p2                  +0+1+2
p1+p1len-6-5-4-3-2-1
p1      +0+1+2+3+4+5
         0 1 2 3 4 5 6 7 8 
        [a b c d e f 1 2 3] temp                           I     RHS
                    [1]>>>>>>[1]       temp   = *(p2+0)    0      *(p2
++0)
              [d]>>>[d]               *(p2+0) = *(p1+3)    0      *(p1
++(p1len-p2len))
        [a]>>>[a]                     *(p1+3) = *(p1+0)    0      *(p1
++I)
        [1]<<<<<<<<<<<<<<<<<<[1]      *(p1+0) =  temp
                      [2]>>>>[2]       temp   = *(p2+1)    1      *(p2
++I)
                [e]>>>[e]             *(p2+1) = *(p1+4)    1      *(p1
++(p1len-p2len)+I)
          [b]>>>[b]                   *(p1+4) = *(p1+1)    1      *(p1
++I)
          [2]<<<<<<<<<<<<<<<<[2]      *(p1+1) =  temp
                        [3]>>[3]       temp   = *(p2+2)    2      *(p2
++I)
                  [f]>>>[f]           *(p2+2) = *(p1+5)    2      *(p1
++(p1len-p2len)+I)
            [c]>>>[c]                 *(p1+5) = *(p1+2)    2      *(p1
++I)
            [3]<<<<<<<<<<<<<<[3]      *(p1+2) =  temp    
        [1 2 3 a b c d e f]
[download]

The pattern doesn't jump out as easily from your second example.

EDIT: I think I got the second one, too. There was a typo that messed me up for a bit, and you solved this one "backwards" so it's easier to reference from the ends of the buffers than the starts, but again there's a pattern:

p2+p2len                  -4-3-2-1
p2                        +0+1+2+3
p1+p1len-9-8-7-6-5-4-3-2-1                                       L1=la
+st element of buffer 1
p1      +0+1+2+3+4+5+6+7+8                                       L2=la
+st element of buffer 2
         0 1 2 3 4 5 6 7 8                                       diff=
+p1len-p2len=5
        [a b c d e f g h i 1 2 3 4] temp                         I
                                [4]>>[4]      temp   = *(p2+3)   0    
+  *(L2+I)
                        [i]>>>>>[i]          *(p2+3) = *(p1+8)   0    
+  *(L1+I)
                [e]>>>>>[e]                  *(p1+8) = *(p1+4)   0    
+  *(L1-diff+1+I)
        [a]>>>>>[a]                          *(p1+4) = *(p1+0)   1    
+  *(L2+I)
        [1]<<<<<<<<<<<<<<<[1]                *(p1+0) = *(p2+0)   1    
+  *(L1+I)
                  [f]>>>>>[f]                *(p2+0) = *(p1+5)   1    
+  *(L1-diff+1+I)
          [b]>>>>>[b]                        *(p1+5) = *(p1+1)   2    
+  *(L2+I)     
          [2]<<<<<<<<<<<<<<<[2]              *(p1+1) = *(p2+1)   2    
+  *(L1+I)   # I think you had a typo here 
                    [g]>>>>>[g]              *(p2+2) = *(p1+6)   2    
+  *(L1-diff+1+I)
            [c]>>>>>[c]                      *(p1+6) = *(p1+2)   3    
+  *(L2+I)
            [3]<<<<<<<<<<<<<<<[3]            *(p1+2) = *(p2+2)   3    
+  *(L1+I)
                      [h]>>>>>[h]            *(p2+2) = *(p1+7)   3    
+  *(L1-diff+1+I)
              [d]>>>>>[d]                    *(p1+7) = *(p1+3)   4    
+  *(L2+I)
              [4]<<<<<<<<<<<<<<<<<<<<[4]     *(p1+3) =  temp
        [1 2 3 4 a b c d e f g h i]
[download]

where the addition has to wrap around as graff describes

There was a typo that messed me up for a bit,

Sorry! But they aren't easy to construct. (What I need is a program .... :)

and you solved this one "backwards"

Yes. I eventually noticed that I'd switched horses mid way. I went back and re-did them all consistently. I'm not sure if one way is easier or better than the other; and if it is, if I've chosen the right way. But anyhoo, here are the (now) 4 cases I think are significant; all done the same way.

The first two are nicely consistent in that the shorter elements move in left-to-right order; albeit that in the first they always go through the temp reg, and the second, only the first one does so.

The other two are neither consistent with the first two; nor each other :(

There are definitely two nested loops; the shorter is the outer, the longer the inner. And graff is definitely right that molulo (p1 % p2len) arithmetic is key.

But the decision about when to fetch the temp register; or move from the shorter buffer (and which one) is eluding me for the moment.

even(6)/odd(3)                      odd(9)/even(4)                    
+         Even(10)/even(4)                            Odd(11)/Odd(3)
p2+p2len            -3-2-1          p2+p2len                  -4-3-2-1
+         p2+p2len                    -4-3-2-1        p2+p2len        
+          -4-3-2-1
p2                  +0+1+2          p2                        +0+1+2+3
+         p2                          +0+1+2+3        p2              
+          +0+1+2+3
p1+p1len-6-5-4-3-2-1                p1+p1len-9-8-7-6-5-4-3-2-1        
+         p1+p1len-0-9-8-7-6-5-4-3-2-1                p1+p1len-9-8-7-6
+-5-4-3-2-1
p1      +0+1+2+3+4+5                p1      +0+1+2+3+4+5+6+7+8        
+         p1      +0+1+2+3+4+5+6+7+8                  p1      +0+1+2+3
++4+5+6+7+8
         0 1 2 3 4 5 6 7 8                   0 1 2 3 4 5 6 7 8        
+                  0 1 2 3 4 5 6 7 8                           0 1 2 3
+ 4 5 6 7 8
        [a b c d e f 1 2 3] temp            [a b c d e f g h i 1 2 3 4
+] temp           [a b c d e f g h i j 1 2 3 4] temp          [a b c d
+ e f g h i j k 1 2 3] temp
                    [1]>>>>>>[1]                              [1]>>>>>
+>>>[1]                               [1]>>>>>>>[1]                   
+              [1]>>>>>>[1]
              [d]>>>[d]                               [f]>>>>>[f]     
+                             [g]>>>>>[g]                             
+        [i]>>>[i]
        [a]>>>[a]                             [b]>>>>>[b]             
+                     [c]>>>>>[c]                                     
+  [f]>>>[f]
        [1]<<<<<<<<<<<<<<<<<<[1]              [2]<<<<<<<<<<<<<<<[2]   
+                     [3]<<<<<<<<<<<<<<<<<[3]                     [c]>
+>>[c]
                      [2]>>>>[2]                        [g]>>>>>[g]   
+                                 [i]>>>>>[i]                     [2]<
+<<<<<<<<<<<<<<<<[2]
                [e]>>>[e]                       [c]>>>>>[c]           
+                         [e]>>>>>[e]                                 
+          [j]>>>[j]
          [b]>>>[b]                             [3]<<<<<<<<<<<<<<<[3] 
+                 [a]>>>>>[a]                                         
+    [g]>>>[g]
          [2]<<<<<<<<<<<<<<<<[2]                          [h]>>>>>[h] 
+                 [1]<<<<<<<<<<<<<<<<<<<<<<<<<<<[1]                 [d
+]>>>[d]
                        [3]>>[3]                  [d]>>>>>[d]         
+                                       [2]>>>>>[2]           [a]>>>[a
+]
                  [f]>>>[f]                       [4]<<<<<<<<<<<<<<<[4
+]                              [h]>>>>>[h]                   [1]<<<<<
+<<<<<<<<<<<<<<<<<<<<<<<[1]
            [c]>>>[c]                                       [i]>>>>>[i
+]                      [d]>>>>>[d]                                   
+                  [3]>>[3]
            [3]<<<<<<<<<<<<<<[3]                    [e]>>>>>[e]       
+                       [4]<<<<<<<<<<<<<<<<<[4]                       
+            [k]>>>[k]
        [1 2 3 a b c d e f]                 [a]>>>>>[a]               
+                                   [j]>>>>>[j]                       
+      [h]>>>[h]
                                            [1]<<<<<<<<<<<<<<<<<<<<<<<
+<<<[1]                     [f]>>>>>[f]                               
+[e]>>>[e]
                                            [1 2 3 4 a b c d e f g h i
+]                  [b]>>>>>[b]                                 [b]>>>
+[b]
                                                                      
+                   [2]<<<<<<<<<<<<<<<<<<<<<<<<<[2]             [3]<<<
+<<<<<<<<<<<<<<<<<<<<<<<[3]
                                                                      
+                 [1 2 3 4 a b c d e f g h i j]               [1 2 3 a
+ b c d e f g h i j k]
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

One pass, a buffer the size of the difference.

use strict;
use warnings;
use diagnostics;
use Data::Dumper;

my @buffer = qw[x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6];
my $bufsize = 10;
my $diff = 2 * $bufsize - scalar(@buffer);
my @smallbuf;
for my $i (0..$#buffer) {
    if ($i < $bufsize - $diff) {
        swap($i, $i + $bufsize)
    } elsif ($i < $bufsize) {
        push @smallbuf, $buffer[$i];
        mv($i+$diff, $i)
    } elsif ($i <= $#buffer - $diff) {
        mv($i+$diff, $i)
    } else {
        $buffer[$i] = shift @smallbuf;
    }
}
print Dumper @buffer;

sub swap {
    my ($i, $j) = @_;
    $buffer[$i] = $buffer[$i] ^ $buffer[$j];
    $buffer[$j] = $buffer[$i] ^ $buffer[$j];
    $buffer[$i] = $buffer[$i] ^ $buffer[$j];
}

sub mv {
    my ($from, $to) = @_;
    $buffer[$to] = $buffer[$from];
}
[download]

Assumptions: (1) you know the size of the buffer. (2) The "larger half" always comes first.

You may want to rewrite the swap algorithm, but it doesn't use a buffer, even of one character.

By the time I'd written this, you said you thought you had an answer, but I understand this one & don't know the language of graff's, so I'm posting it anyway.

Regards,

John Davies

Update: the more I look at this, the more sure I am that my if block can be rewritten to calculate the final position of a value from its original position. This means that with a two value buffer in memory, it should be possible to avoid swapping altogether, reducing the number of writes (possibly important for solid state devices). IOW, var1 (using Data::Dumper notation) goes to var8, so read var8 & write var1 there. Var8 goes to var15, so read var15 & write var8 to it and so on through the chain. The question is where to resume when you get to the end of the chain. Once I have sorted this out, I'll post back (or announce failure).

Chains seem to matter when the small part is a factor of the length of the large part (possibly also when the diff is a factor of the large). But AFAICT, the chain never hits the next word from the starting point unless it covers the entire buffer, i.e. when there is only one chain. Therefore, simply incrementing the start point when the chain loops back on itself is fine in every case I've tried. My solution may be logically the same as hdb's, but I'm certainly not checking tonight. This has taken longer than my usual Sunday killer sudokus. Mind you, it's also been more fun!

use strict;
use warnings;
use diagnostics;
use Data::Dumper;

my @buffer = qw[a b c d e f 0 1 2];
my $bufsize = 6;
my $diff = 2 * $bufsize - scalar(@buffer);
my @smallbuf;
my $writes = 0;
my $source = 0;
my $chainfrom = 0;
push @smallbuf, $buffer[$source];
while ($writes < scalar(@buffer)) {
    my $dest = $source < $bufsize ? $source + $bufsize - $diff : $sour
+ce - $bufsize;
    push @smallbuf, $buffer[$dest];
    $buffer[$dest] = $smallbuf[0];
    $writes++;
    shift @smallbuf;
    if ($dest == $chainfrom) {
        $chainfrom++;
        $source = $chainfrom;
        $smallbuf[0] = $buffer[$chainfrom];
    } else {
        $source = $dest;
    }
}
print Dumper @buffer;
[download]

Regards,

John Davies

Update 2015-03-12 (too late to matter): I was concerned that a chain might hit the second position in the starting buffer but not a later one. I have satisfied myself that this is not a problem. If a chain starts at one and hits 2, then a chain that starts at 2 will hit 3 and so on. Therefore, if anything can be missed, it will be the next position. So my algorithm will work for all cases unless there's something wrong with this logic. If so, please tell me.

See here 1118280 for the answers to the questions in your update.

Here is a program that does the swapping with one temp only:

use strict;
use warnings;

my @buffer = qw[X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7]
+;

sub swapsamesize {
  my( $s1, $s2, $n, $buf ) = @_;
  ($$buf[$s1+$_], $$buf[$s2+$_]) = ($$buf[$s2+$_], $$buf[$s1+$_]) for 
+0..$n-1; # too lazy to use $tmp
}

sub swapbuffers {
  my( $n1, $buf ) = @_;
  my $ntotal = @$buf;
  my $n2 = $ntotal - $n1;
  my $d = $n1 - $n2;
  print "$n1 $n2 $ntotal $d\n";
  print "@$buf\n";
  my( $s1, $s2, $n ) = ( 0, $n1, $n2 );
  swapsamesize( $s1, $s2, $n, $buf );
  print "@$buf\n";
  ( $s1, $s2, $n ) = ( $n2, $ntotal - $d, $d );
  swapsamesize( $s1, $s2, $n, $buf );
  print "@$buf\n";
  ( $s1, $s2, $n ) = ( $n2, $ntotal - 2 * $d, $d );
  swapsamesize( $s1, $s2, $n, $buf );
  print "@$buf\n";
  ( $s1, $s2, $n ) = ( $n2, $ntotal - 3 * $d, $d );
  swapsamesize( $s1, $s2, $n, $buf );
  print "@$buf\n";
  ( $s1, $s2, $n ) = ( $n2, $ntotal - 4 * $d, $d );
  swapsamesize( $s1, $s2, $n, $buf );
  print "@$buf\n";
}

swapbuffers 10, \@buffer;
[download]

Of course, the repeated calls to the utility function swapsamesize should be done in a loop until all is done. It also only works if the overlap when swapping (i.e. n1 - n2) is smaller than the rest of the smaller half. I think the logic can be adapted...

Problem:One small change (delete the last entry in the second part of the buffer):

my @buffer = qw[x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6];
[download]

and the output is:

C:\test>1118256
10 7 17 3
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6
y0 y1 y2 y3 y4 y5 y6 x7 x8 x9 x0 x1 x2 x3 x4 x5 x6
y0 y1 y2 y3 y4 y5 y6 x4 x5 x6 x0 x1 x2 x3 x7 x8 x9
y0 y1 y2 y3 y4 y5 y6 x1 x2 x3 x0 x4 x5 x6 x7 x8 x9
y0 y1 y2 y3 y4 y5 y6 x2 x3 x0 x1 x4 x5 x6 x7 x8 x9
y0 y1 y2 y3 y4 x2 x3 x0 y6 y5 x1 x4 x5 x6 x7 x8 x9
[download]

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Which means that the logic also needs to be different for odd length of buffers.

BrowserUk:

Here's what I came up with:

#!/usr/bin/env perl
use strict;
use warnings;

for my $X (3 .. 7) {
    for my $Y (2 .. 8) {
        my @orig = ((map {"X$_"} 0 .. $X),(map {"Y$_"} 0 .. $Y));
        my @wanted = ((map {"Y$_"} 0 .. $Y),(map {"X$_"} 0 .. $X));
        print "@orig\n";
        swap($X+1, \@orig, \@wanted);
        my $fl = 'Y';
        for (0 .. $#wanted) {
            if ($orig[$_] ne $wanted[$_]) {
                $fl='N'; $orig[$_]=lc($orig[$_]);
            }
        }
        print "@orig ($fl)\n\n";
    }
}

sub swap {
    my ($ofs, $list) = @_;
    my ($cnt, $src, $dst, $cmp, $tmp);

    $cnt = @$list;
    $dst = $cmp = 0;
    $tmp = $list->[$dst];
    while ($cnt--) {
        $src = ($dst+$ofs) % @$list;
        if ($src == $cmp) {
            # Loop detected, finish it and start next one
            $list->[$dst] = $tmp;
            $dst = ++$cmp;
            $tmp = $list->[$dst];
        }
        else {
            $list->[$dst] = $list->[$src];
            $dst = $src;
        }
    }
}
[download]

The two tricks are: (1) You never have to subtract from your pointers, and (2) you have to detect loops when your pointers have a smaller loop size than the buffer size.

Update: It took me a bit of time to get back to this, and I posted it before reviewing the thread. It turns out that graf already described the algorithm, as did hdb.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Seems I found the same independently 1118280. I like your modulus calculation to find the next loaction.

Thanks. I too like your modulo calculation -- it's what I was trying for when I said "And graff is definitely right that molulo[sic] (p1 % p2len) arithmetic is key." -- but I didn't get the right combination of arguments.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Having two separate 'length' parameters instead of one would make it straightforward, right?

aving two separate 'length' parameters instead of one

For the uneven buffers, you definitely need two lengths, (Or one length and a difference. :)

would make it straightforward, right?

Unfortunately not.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

use strict;
use warnings;

my @ary1 = qw( X0 X1 X2 Y0 Y1 Y2 );
my @ary2 = qw( X0 X1 Y0 Y1 Y2 Y3 );
my @ary3 = qw( X0 X1 X2 X3 Y0 Y1 );
my @ary4 = qw( X0 Y0 Y1 Y2 Y3 Y4 );
my @ary5 = qw( X0 X1 X2 X3 X4 Y0 );

my @buk1 = qw(
  X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7
);

my @buk2 = qw(
  X0 X1 X2 X3 X4 X5 X6 X7 Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9
);

swap( \@ary1, 3 );  # aref, offset of Y0
swap( \@ary2, 2 );
swap( \@ary3, 4 );
swap( \@ary4, 1 );
swap( \@ary5, 5 );
swap( \@buk1, 10 );
swap( \@buk2, 8 );

sub swap {
    my ( $ary, $offset ) = @_;
    my $swaps = do_swaps( $ary, 0, $offset, 0 );
    show( $ary, $swaps );
}

sub do_swaps {
    my ( $ary, $offset_x, $offset_y, $swaps ) = @_;

    return $swaps if $offset_y == @$ary;

    my ( $x, $y ) = ( $offset_x, $offset_y );
    my $temp;

    for ( $offset_x .. ( $offset_y - 1 ) ) {
        $y         = $offset_y if $y == @$ary;
        $temp      = $ary->[$x];
        $ary->[$x] = $ary->[$y];
        $ary->[$y] = $temp;
        $x += 1;
        $y += 1;

        $swaps += 1;
    }

    return do_swaps( $ary, $x, $y, $swaps );
}

sub show {
    my ( $ary, $swaps ) = @_;
    printf "%2d swaps => %s\n", $swaps, join ' ', @$ary;
}
[download]

 3 swaps => Y0 Y1 Y2 X0 X1 X2
 4 swaps => Y0 Y1 Y2 Y3 X0 X1
 4 swaps => Y0 Y1 X0 X1 X2 X3
 5 swaps => Y0 Y1 Y2 Y3 Y4 X0
 5 swaps => Y0 X0 X1 X2 X3 X4
16 swaps => Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 X0 X1 X2 X3 X4 X5 X6 X7 X8 X9
16 swaps => Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8 Y9 X0 X1 X2 X3 X4 X5 X6 X7
[download]

Okay. I jiggered and poked it (my apologies if you're sensitive to such things), and added a little trace and got this:

#! perl -slw
use strict;

sub show {
    my ( $ary, $swaps ) = @_;
    printf "%2d swaps => %s\n", $swaps, join ' ', @$ary;
}

sub swapElems {
    my $t = $_[0][ $_[1] ]; $_[0][ $_[1] ] = $_[0][ $_[2] ]; $_[0][ $_
+[2] ] = $t;
    print "[@{$_[0]}] $_[1] <=> $_[2]"
}

sub do_swaps {
    my( $ary, $x, $y, $swaps ) = @_;
    print "do_swaps: $x .. $y";

    return $swaps if $y == @$ary;
    my $saved_y = $y;

    for( $x .. $y - 1 ) {
        $y = $saved_y if $y == @$ary;

        swapElems( $ary, $x++, $y++ );

        ++$swaps;
    }

    return do_swaps( $ary, $x, $y, $swaps );
}

sub swap {
    my ( $ary, $offset ) = @_;
    my $swaps = do_swaps( $ary, 0, $offset, 0 );
    show( $ary, $swaps );
}


#swap( [ qw( a b c 1 2 3 ) ], 3 );  # aref, offset of Y0
#swap( [ qw( a b c d 1 2 ) ], 4 );
#swap( [ qw( a b c d e 1 ) ], 5 );
swap( [ qw( a b c d e f g h i j 1 2 3 4 5 6 7 8 ) ], 10 );
#swap( [ qw( a b c d e f 1 2 3 ) ], 6 );
[download]

Which when run on the 6/3 testcase produces:

do_swaps: 0 .. 6
[1 b c d e f a 2 3] 0 <=> 6
[1 2 c d e f a b 3] 1 <=> 7
[1 2 3 d e f a b c] 2 <=> 8
[1 2 3 a e f d b c] 3 <=> 6
[1 2 3 a b f d e c] 4 <=> 7
[1 2 3 a b c d e f] 5 <=> 8
do_swaps: 6 .. 9
 6 swaps => 1 2 3 a b c d e f
[download]

6 swaps is a perfect score. and the logic is very clear and very clean. So clean it is beautiful (which always feels right!):

1. Switch the 3 from end with the 3 from the front.
2. Then switch 3 from the middle with the 3 from the end.

With a 10/7 testcase things are little more muddy:

do_swaps: 0 .. 10
[1]b c d e f g h i j[a]2 3 4 5 6 7] 0 <=> 10
[1[2]c d e f g h i j a[b]3 4 5 6 7] 1 <=> 11
[1 2[3]d e f g h i j a b[c]4 5 6 7] 2 <=> 12
[1 2 3[4]e f g h i j a b c[d]5 6 7] 3 <=> 13
[1 2 3 4[5]f g h i j a b c d[e]6 7] 4 <=> 14
[1 2 3 4 5[6]g h i j a b c d e[f]7] 5 <=> 15
[1 2 3 4 5 6[7]h i j a b c d e f[g] 6 <=> 16 *
[1 2 3 4 5 6 7 a[i]j h[b]c d e f g] 7 <=> 10
[1 2 3 4 5 6 7 a b[j]h i[c]d e f g] 8 <=> 11
[1 2 3 4 5 6 7 a b c[h]i j[d]e f g] 9 <=> 12
do_swaps: 10 .. 13
[1 2 3 4 5 6 7 a b c d[i]j h[e]f g] 10 <=> 13
[1 2 3 4 5 6 7 a b c d e[j]h i[f]g] 11 <=> 14
[1 2 3 4 5 6 7 a b c d e f[h]i j[g] 12 <=> 15
do_swaps: 13 .. 16
[1 2 3 4 5 6 7 a b c d e f g[i]j[h] 13 <=> 16
[1 2 3 4 5 6 7 a b c d e f g h[j|i] 14 <=> 16
[1 2 3 4 5 6 7 a b c d e f g h i j] 15 <=> 16
do_swaps: 16 .. 17
16 swaps => 1 2 3 4 5 6 7 a b c d e f g h i j
[download]

1. Switch the 107 from the end, with the 107 from the front.
2. Then switch the 3 so far unmoved with the adjacent 3 that have.
3. The wiggle those latter 3 the rest of the way to the end in a series of interleaved swaps, in 2 passes.

I'm not sure what to think about that.

It sure looks like that, after the first 7(*) have been moved, then you could recurse to move the 3 to the end.

Ie. As your algorithm works regardless of long/short ordering, treat it as a 3/7 input.

Of course you'd have to 'lie' about the length of the array, which is easy to do in C, but not so in Perl.

I'm not sure if that is optimal -- I haven't (tried to) figured a formula, but it won't be grossly over -- but it sure looks like (that phrase again), that after a clean start, the end seems (perhaps, unnecessarily) busy?

I'll need to code yours and hdbs algorithms, (and finish my own/graff/bitingduck version, if I can), in C and run them on some big buffers with awkward ratios:

eg. 2GB left buffer and 536870909 & 536870923 (primes either side of 2GB/4) which ought to trigger pathological behaviour if it exists.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Well the basic idea is this: suppose we have an array like

1 2 3 4 5 6 a b c
[download]

initially, x points to 1, y points to a:

x           y
1 2 3 4 5 6 a b c
[download]

We want to move a b c all the way to the left,so we swap numbers and letters:

      x           y
a b c 4 5 6 1 2 3
[download]

Now the rightmost elements are scrambled. Note that y at this stage points to the element one off the right end of the array. We restore its position:

$y = $offset_y if $y == @$ary;

      x     y
a b c 4 5 6 1 2 3
[download]

Now we basically have a smaller array 4 5 6 1 2 3 and we want to swap 4 5 6 and 1 2 3. Hence, recursion. But it's a tail call, aka 'while loop in disguise', so:

sub do_swaps {
    my ( $ary, $offset_x, $offset_y, $swaps ) = @_;
    my ( $x, $y ) = ( $offset_x, $offset_y );

    while ( $offset_y != @$ary ) {
        for ( $offset_x .. ( $offset_y - 1 ) ) {
            $y         = $offset_y if $y == @$ary;
            my $temp   = $ary->[$x];
            $ary->[$x] = $ary->[$y];
            $ary->[$y] = $temp;
            $x += 1;
            $y += 1;

            $swaps += 1;
        }
    ( $offset_x, $offset_y ) = ( $x, $y );
    }
    
    return $swaps;
}
[download]

Same thing... I think :)

Nice! Passes my basket case:

C:\test>1118262
 3 swaps => 1 2 3 a b c
 4 swaps => 1 2 a b c d
 5 swaps => 1 a b c d e
16 swaps => 1 2 3 4 5 6 7 8 a b c d e f g h i j
 6 swaps => 1 2 3 a b c d e f
[download]

I took out the shorter/longer tests as that's never going to be a requirement. (Cool that it doesn't matter to the algorithm though!)

It'll take me a while to wrap my brain around it -- recursion always does -- but so far it ticks all the boxes. Thank you.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

For buffers of any significant size this looks like far too much work! Can't you fix your code that uses these buffers to access them through pointers and then you just swap the pointers?

No. This is to deal with the edge case where the last buffer is partial. Think:end-of-file. "swapping pointers" would not achieve the same result.

After the swap, the left (full-sized) buffer will contain the contents of the right buffer, made up the full buffer size, with the left-hand end of the left buffer.

And the right buffer contains the right-hand end the left buffer.

The buffers are mem-mapped chunks of a disk file. You can't swap chunks of disk around by swapping pointers.

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked