Swapping elements of arrays

[Matthew Matic]

I have a 3 dimensional array, of the form

bool bit[L*L][L][L]

where L is the size of the thing I'm simulating. At times I need to swap all the elements in a 2 dimensional slice of this with those of the neighboring slice. I'm doing it with some loops as follows:

for (int j=0;j<L;j++){
for (int i=0;i<L;i++){

temp[j][i] = bits[k][j][i];
bits[k][j][i] = bits[k+1][j][i];
bits[k+1][j][i] = temp[j][i];

}
}

The time taken to do this is O(L^2), so I'm wondering if there's something more efficient. Is there some way to tell the program to start thinking of the kth slice as the k+1th, and vice-versa, without actually having to shift everything over?

[bartoli]

If you allocate each of the L*L 2 dimension arrays with new and save their pointers to each position of bool bit[L*L], you could then just swap the pointers to the 2dimension arrays in the first dimension of bit

[Duthomhas]

I agree with bartoli -- but be aware that it increases your bookkeepping needs on the array itself to maintain pointers to subarrays.

A simple array (one without the indirection via pointers) is stored in memory linearly, so you can do a simple linear swap.

size_t index_slice( size_t a, size_t b = 0 /* no 'c', since that specifies a single element */ ) {
  /*
  The result is:
  (size of first dimention slice) * (index into first dimension)
  plus
  (size of second dimention slice) * (index into second dimension)

  Remember that the total size of a dimension's elements is the product of the
  sizes of all lower dimensions.
  */
  return (L*L*a) + (L*b);
}

void swap_a( bool* bit, size_t a, size_t b ) {
  /*
  Notice how, as argument, we take a simple pointer to the first element:
    bit[0][0][0]
  The neat thing here is that, with the downgraded pointer, we can refer to it as
    bit[0]
  or even more simply, just
    *bit

  Keep in mind that this time, the arguments 'a' and 'b' are both indices into the first
  dimension. (Unlike in the above function, where 'a' was the index of the first and 'b'
  was the index of the second.)
  */

  // Another way to get the length of a dimension
  size_t len = index_slice( a + 1 ) - index_slice( a );

  // Now for our swaps

  // First, we'll get pointers to the first element in each slice we wish to swap
  bool* bita = bit + index_slice( a );  // same as "&(bit[a][0][0])"
  bool* bitb = bit + index_slice( b );

  // Now, we swap each element in the slices
  while (len--) {
    bool temp = *bita;
    *bita++ = *bitb;
    *bitb++ = temp;
  }
}

void swap_b( bool* bit, size_t a1, size_t a2, size_t b1, size_t b2 ) {
  /*
  Here it is again, but swaping the second dimension instead of the first.
  */
  size_t len = index_slice( a1, a2 + 1 ) - index_slice( a1, a2 );

  bool* bita = bit + index_slice( a1, a2 );
  bool* bitb = bit + index_slice( b1, b2 );

  while (len--) {
    bool temp = *bita;
    *bita++ = *bitb;
    *bitb++ = temp;
  }
}

The code assumes you are using either C++ or C99 (since you used the bool type). It is entirely possible to make all this stuff very conveniently generic, but I'd rather you get the concept first before overloading you with too much generic stuff. Once you get it -- I presume you do already -- you can write something more generic or appropriate for your actual data.

Remember, the pointer arithmetic here is the key to making this easy.

Hope this helps.

PS. Please use [code] tags.