Reversing a flat array of coordinates

Question

I have a path of (x,y) coordinates as a flat array, like this:

[x1, y1, x2, y2, x3, y3, ...]

To flip it from clockwise to counterclockwise, I need to reverse it pairwise: x3,y3,x2,y2,x1,y1. The following works and is pretty fast to boot:

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];
for (var i = 0; i < (a.length/2); i = i + 2) {
    var x = a[i];
    var y = a[i+1];
    a[i] = a[a.length - 2 - i];
    a[i+1] = a[a.length - 1 - i];
    a[a.length - 2 - i] = x;
    a[a.length - 1 - i] = y;
};

But is there a more elegant approach? I played with splice for a bit, but it returns the spliced items as an array and wants them back as arguments, which breaks things:

for (var i = 0; i < (a.length/2); i = i + 2) {
    a.splice(i, 0, a.splice(a.length-2-i, 2)); // doesn't work
};

Although I suppose you could work around that with creative use of apply, but ergh.

Filtering in an array of x's and y's, calling reverse on each and splicing them back together seems possible, but it's pretty verbose in JS and probably a lot less efficient.

Edit: The arrays are of arbitrary length and may contain hundreds of thousands of pairs, so speed and memory usage are important.

Answer 1

A little cleaner if you use two counters, one from the start, and the other from the end.

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];

for (var i = 0, j = a.length-2; i < j; i+=2, j-=2) {
    var t1 = a[i],
        t2 = a[i+1];
    a[i]   = a[j];
    a[i+1] = a[j+1];
    a[j]   = t1;
    a[j+1] = t2;
}

---

Or with a little hackery, you can shorten it a little.

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];

for (var i = 0, j = a.length-2; i < j; i+=2, j-=2) {
    a[ i ] = [a[ j ], a[ j ] = a[ i ]][0];
    a[i+1] = [a[j+1], a[j+1] = a[i+1]][0];
}

---

And let's not forget about destructuring assignment. This is coming in ECMAScript 6, but will work right now in Firefox.

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];

for (var i = 0, j = a.length-2; i < j; i+=2, j-=2) {
    [a[i], a[j], a[i+1], a[j+1]] = [a[j], a[i], a[j+1], a[i+1]];
}

---

One other possibility would be to first reverse the entire array, then reverse the pairs.

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];

a.reverse();

for (var i = 0; i < a.length; i+=2) {
    var t  = a[i];
    a[i]   = a[i+1];
    a[i+1] = t;
}

Probably slower, but certainly cleaner.

---

Or using a separate array for the result can eliminate temporary variables.

var a = ['x1', 'y1', 'x2', 'y2', 'x3', 'y3'];
var b = new Array(a.length);

for (var i = 0, j = a.length-2; i <= j; i+=2, j-=2) {
    b[j]   = a[i],
    b[j+1] = a[i+1];
    b[i]   = a[j];
    b[i+1] = a[j+1];
}

Initializing the Array with its full length can give a performance boost in modern implementations.

Answer 2

Cookie monster's algorithm actually becomes faster, more readable, and DRYer if you introduce a swapping helper function:

function swap(ary, x, y) {
  var t = ary[x];
  ary[x] = ary[y];
  ary[y] = t;
}

function helperDualCounterPairwiseReverse(coords) {
  var a = coords.slice(0);
  for (var i = 0, j = a.length-2; i < j; i+=2, j-=2) {
    swap(a, i, j);
    swap(a, i+1, j+1);
  };
  return a;
}

Here's another readable, but less performant variation:

function semanticPairwiseReverse(coords) {
  var prev, reversed = [];
  for (var i = 0; i < coords.length/2 + 2; i = i + 2) {
    reversed.unshift(coords[i], coords[i + 1]);
  };
  return reversed;
}

If you're only dealing with 3D data sets and you're overly concerned with performance, you may want to consider a "dumb" approach wherein you hard code the swaps:

function dumbPairwiseReverse(coords) {
  var reversed = coords.slice(0); // Duplicates the coordinate list
  reversed[0] = coords[4]; reversed[4] = coords[0];
  reversed[1] = coords[5]; reversed[5] = coords[1];
  return reversed;
}

Here are some benchmarks of the above along with the other presented solutions: http://jsperf.com/pairwise-reverse/5