Array transposition

Question

The task: take a byte[][] and transpose it.

The complication: the original array is a result of a partition operation that might not be even, so the last subarray might have fewer items than the others. This should be preserved in transposition without any padding.

For example:

$$ A^\intercal = \begin{bmatrix} 1 & 2 & 3 & 4 & 99 & 99 & 99 \\ 5 & 6 & 7 & 8 & 99 & 99 & 99 \\ 9 & 10 & & & & & \end{bmatrix} = \begin{bmatrix} 1 & 5 & 9 \\ 2 & 6 & 10 \\ 3 & 7 & \\ 4 & 8 & \\ 99 & 99 \\ 99 & 99 \\ 99 & 99 \end{bmatrix} $$

I mostly write in dynamic languages with lots of functional affordances like Python and Clojure, and hence had tons of trouble getting this to work right, mostly struggles with calculating the size of the truncated arrays at the end and the number of shorter arrays to produce. But eventually came up with this awkward, but working, monstrosity:

public static byte[][] transpose(byte[][] working){
 int resultlen = working[0].length;
 int totallen = 0;
 int longlen = working.length;
 int shortlen = longlen - 1;
 for (byte[] ba : working){
 totallen += ba.length;
 }
 // number of short rows = the number of the shortfall between the length of the last item (the broken partition) and the length of the first item (resultlen)
 int lenOfShortItem = working[working.length - 1].length;
 int shortrows = resultlen - lenOfShortItem;
 int longrows = resultlen - shortrows;
 // now I can create an array of byte arrays for the result.
 byte[][] workingresult = new byte[resultlen][];
 for (int i = 0; i < resultlen; i++){
 if (i < longrows){
 workingresult[i] = new byte[longlen];
 } else{
 workingresult[i] = new byte[shortlen];
 }
 }
 // and now I can fill up that array of byte arrays
 for (int j = 0; j < working.length; j++){
 for (int k = 0; k < working[j].length; k++){
 workingresult[k][j] = working[j][k];
 }
 }
 return workingresult;
 }

But, yuck, that’s ugly and awkward. I'd love to hear your suggestions to improve it!

Answer 1

This really doesn't seem that bad to me. I see a few minor improvements you could make:

Remove Unused Code

The totallen variable doesn't appear to be used anywhere after it's calculated. You can remove the declaration of the variable and the calculation loop.

Is This Right?

I'm not understanding how you're calculating shortlen. Is it supposed to be the length of the shortest row? It doesn't look correct to me, as it's the length of the longer rows minus 1. Or is it? Isn't working.length the number of rows in the array? I don't think you've calculated what you think you've calculated.

Naming Style

I think your names are mostly decent, but they're a little hard to read because you don't use CamelCase or underscores. (Except when you do - I'm looking at you lenOfShortItems!) I would choose one of those 2 styles and update your variable names to use that style. So they'd be resultLen, totalLen, etc., or long_len, short_len, etc.

Reduce Redundancy

You calculate shortrows and then calculate longrowsfrom that, then never use shortrows again. I would either calculate longrows in a single line and not have shortrows or just use shortrows directly in the if statement below. It makes one less variable in the function.

The same could be said for resultlen. It's only used in the calculation of shortrows and longrows, and you use working.length right above that calculation.

Break It Down

One way to clean this up would be to break out some of the functionality into separate functions. That might be overkill here, since this is a pretty small function, but it would make it more readable. You could pull out the loop of allocations into a separate function (say allocateColumns(), maybe?), and also put the actual copying of values into a separate function (transposeValues()?) just to make things more clear.

• Paul Gowder: thanks! hmm, what was I using totallen for? Heh, probably for one of the 5 or 6 bug-filled prior attempts to calculate how many short rows I'd need in the transposed version. :-)

Answer 2

It should be as simple as this:

public static byte[][] transpose(byte[][] m) {
 int lastlen = m[m.length - 1].length;
 byte[][] t = new byte[m[0].length][];
 for (int r = 0; r < t.length; r++) {
 int rowlen = m.length - (r < lastlen ? 0 : 1);
 t[r] = new byte[rowlen];
 for (int c = 0; c < rowlen; c++) {
 t[r][c] = m[c][r];
 }
 }
 return t;
}

(I did not test the above code since I'm on my mobile right now.)