views:

174

answers:

4

I have an non-square array like this:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

and I need to convert it to:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

that is, rotate/shuffle it counter-clockwise (or clockwise, the algorithm should be similiar).

The algorithm should use a minimal amount of space. I have to rotate an image in an extremely memory-constrained environment, so the less space the better. Speed is not as big an issue.

A: 

You can use xor to use no additional memory.

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

Then you can use a simple for loop to make your whole matrix.

Wernight
Looks that would easily work for square matrix, but (as far as I can see) not for non square matrixes.
kriss
It's of size [12]. it's not 2 dimentional in memory. Only the interpretation.
Wernight
+4  A: 

You can transpose the matrix in-place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition) and then reverse the rows which is trivial.

ybungalobill
It'd be nice to have an algorithm in C, converting from Fortran is not something I'm prepared to do.
Kronikarz
I'm afraid that your only choice is either translate the fortran source or read the papers and implement it from scratch. Note that any algorithm you find for your original problem implies a solution for matrix-transposition problem which is widely known.
ybungalobill
A: 

The 2D rotation formula is:

x' = x cos f - y sin f
y' = y cos f + x sin f

If you only rotate in 90° steps, the resulting formula becomes:

x' = -y
y' =  x

Since the array isn't square you'll have to look for assignment cycles, i.e. element (0, 0) gets assigned element (2, 0) which in turn gets assigned (2, 2) etc. You'll need to assign each cycle at the "same" time.

Thus to rotate the whole array you'll do something like (pseudo-code):

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}
Andreas Magnusson
I think you are answering different question here.
wilx
@wilx: Please read the question again, rotate the array in place! Please don't downvote unless you understand both the question and the answer.
Andreas Magnusson
@wilx: Agreed my initial attempt may have been a bit naïve, but it was no less helpful than the answer describing an xor swap and it was definitely not a different question I was answering.
Andreas Magnusson
A: 

Not rotating at all may be an option. You just set a flag that would give the way the matrix should be read.

The drawback is that if that image must be provided to some display device or such with fixed direction, that may not be possible.

kriss
@kriss: there is also a cache locality penalty when traversing the table. Before, traversing row by row is efficient, afterward it would imply seemingly random reads.
Matthieu M.
@Matthieu M. This is right if you are traversing tables by rows but we have no information on that. Also OP explicitely stated that he was more concerned about space than speed.
kriss
@kriss: I know, yet it is somewhat to take into account. Most of the times I don't care too much about performance, unless it makes my soft unusable that is :-)
Matthieu M.
@Matthieu M.: in such a case not using the right access to memory could indeed slow down by several orders of magnitude.
kriss