Given a data matrix, calculate html rowspan and colspan

Question

I have a sparse matrix similar to the one below, consisting of data cells (1..9) and empty cells (= zero):

[ [ 1, 2, 0, 3 ], [ 0, 4, 0, 0 ], [ 5, 6, 7, 8 ], ] 

I would like to display this as an html table, but there should be no empty cells - they should be "covered" by the neighboring cells of the rows and spans of neighboring data:

 <table border=1 cellpadding=10> <tr> <td rowspan=2>1</td> <td colspan=2>2</td> <td>3</td> </tr> <tr> <td colspan=3>4</td> </tr> <tr> <td>5</td> <td>6</td> <td>7</td> <td>8</td> </tr> </table> 

(this is one of the possible implementations, we could also use colspan=4 in the second line and without lines).

Generating up-to-date html is not a problem, but it's hard for me to write an algorithm for calculating rows and columns for data cells.

EDIT : Still looking for an answer for this. It seems trivial to work only with colspans and concatenate each data cell with empty cells left / right. However, I would like the cells to be as square as possible, so the answer should include row logic. Thanks!

EDIT2 : all answers are still summarized here: http://jsfiddle.net/ThQt4/

Answer 1

There are several things to consider in what you want.

If you always prefer squares over the largest figure, you can get many single lines in the form of columns, because the rectangle always starts with a square. A square or rectangle can only begin if the upper left is significant.

Consider this array:

 [1, 2, 3, 4, 5], [7, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 2, 0, 0, 5] 

If you select the squares above the largest figure, you get a square and three columns

 [1] [2] [3] [4] [5] instead of [1] [2] [3] [4] [5] [ 7 ] [ ] [ ] [ ] [ 7 ] [ ] [ ] [ ] [ ] [ ] 

In addition, you can get empty individual cells:

 [1, 1, 2, 0], gives [1] [1] [ 2 ] [3, 0, 0, 0], [ ] [?] <--- [0, 0, 0, 5], [ 3 ] [5] [0, 0, 0, 1] [ ] [1] 

The biggest square here is 3x3, starting at 3. If you first declare 3x3 and then a line starting at 2, you will get an empty cell [?] Above 5.

Last, if you have zeros in the top row or in the left column, you may also encounter a problem:

  V [1, 0, 0, 2], will leave you with [ 1 ] [?] [2] [0, 0, 3, 4], [ ] [3] [4] [0, 5, 6, 7] --->[?] [5] [6] [7] 

However, maybe your array is not so complex, and maybe you are not against empty cells. In any case, it was fun to solve this puzzle with your specifications. My decision is subject to the following rules:

1) first the squares.

2) Size matters. The bigger, the better

3) Rows and columns: size matters. The biggest ones go first.

4) Colspan skips rowspan

Fiddle

 var maxv = arr.length; var maxh = arr[0].length; var rsv = []; var rsh = []; pop_arr(); var shape; try_sq(); try_rect(); try_loose(); //TRY SQUARES FIRST function try_sq() { var sv, sh; shape = []; for (sv = 0; sv < maxv - 1; sv++) { for (sh = 0; sh < maxh - 1; sh++) { if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) { continue; } check_sq(sv, sh); } } if (shape.length > 0) { occu(); } } //TRY RECTANGLES function try_rect() { var sv, sh; var rect = false; do { shape = []; for (sv = 0; sv < maxv; sv++) { for (sh = 0; sh < maxh; sh++) { if (arr[sv][sh] === 0 || rsv[sv][sh] > -1 || rsh[sv][sh] > -1) continue; check_rec(sv, sh); } } if (shape.length > 0) { occu(); } else { rect = false; } } while (rect === true); } //TRY LOOSE function try_loose() { var sv, sh; //SET THE 1x1 with value for (sv = 0; sv < maxv; sv++) { for (sh = 0; sh < maxh; sh++) { if (arr[sv][sh] !== 0 && (rsv[sv][sh] == -1 || rsh[sv][sh] == -1)) { rsv[sv][sh] = 1; rsh[sv][sh] = 1; } } } //SEARCH FOR rectangles wit no value var rect = true; do { shape = []; for (sv = 0; sv < maxv; sv++) { for (sh = 0; sh < maxh; sh++) { if (arr[sv][sh] !== 0 || (rsv[sv][sh] > -1 || rsh[sv][sh] > -1)) { continue; } rect = check_loose(sv, sh); } } if (shape.length > 0) occu(); else { rect = false; } } while (rect === true); } //check SINGLES function check_loose(start_v, start_h) { var vd, hd, iv, ih, rect; var hor = ver = 1; var horb = 0; var mxv = maxv - 1; var mxh = maxh - 1; rect = true; vd = start_v + ver; hd = start_h + hor; //check horizontal for (sh = start_h + 1; sh <= mxh; sh++) { if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) { break; } hor++; } //check vertical for (iv = start_v + 1; iv <= mxv; iv++) { if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) { break; } ver++; } if (hor > ver || hor == ver) { shape.unshift({ 0: (hor), 1: [start_v, start_h, 1, hor] }); return true; } else if (ver > hor) { shape.push({ 0: (ver), 1: [start_v, start_h, ver, 1] }); return true; } return false; } //check SQUARE function check_sq(start_v, start_h) { if (arr[start_v + 1][start_h] !== 0) { return false; } if (arr[start_v][start_h + 1] !== 0) { return false; } var vd, hd, sv, sh, square; var hor = ver = 1; var mxv = maxv - 1; var mxh = maxh - 1; //CHECK DIAGONAL do { square = true; vd = start_v + ver; hd = start_h + hor; //diagonal OK if (arr[vd][hd] !== 0) { if (hor == 1) { if (ver == 1) { return false; } square = false; break; } } //check horizontal for (sh = start_h; sh <= hd; sh++) { if (arr[vd][sh] !== 0) { square = false; break; } } if (square === false) break; //check vertical for (sv = start_v; sv <= vd; sv++) { if (arr[sv][hd] !== 0) { square = false; break; } } if (square === false) break; hor++; ver++; } while (square === true && vd < mxv && hd < mxh); //SQUARE OK if (hor > 1 && ver > 1 && hor == ver) { shape.push({ 0: (hor * ver), 1: [start_v, start_h, ver, hor] }); } } //check RECTANGLE function check_rec(start_v, start_h) { var vd, hd, iv, ih, rect; var hor = ver = 1; var horb = 0; var mxv = maxv - 1; var mxh = maxh - 1; rect = true; vd = start_v + ver; hd = start_h + hor; //check horizontal if (start_h < maxh) { for (sh = start_h + 1; sh <= mxh; sh++) { if (arr[start_v][sh] !== 0 || rsh[start_v][sh] > -1) break; hor++; } } //check vertical if (start_v < maxv) { for (iv = start_v + 1; iv <= mxv; iv++) { if (arr[iv][start_h] !== 0 || rsh[iv][start_h] > -1) break; ver++; } } if (hor == 1 && ver == 1) return false; if (hor > ver || hor == ver) { shape.unshift({ 0: (hor), 1: [start_v, start_h, 1, hor] }); return true; } else { shape.push({ 0: (ver), 1: [start_v, start_h, ver, 1] }); return true; } return false; } //FIND LARGEST SHAPE function occu() { var le = shape.length; for (var i = 0; i < le; i++) { var b = Math.max.apply(Math, shape.map(function (v) { return v[0]; })); for (var j = 0; j < shape.length; j++) { if (shape[j][0] == b) break; } var c = shape.splice(j, 1); claim(c[0][1]); } } //CLAIM SHAPE function claim(sh) { var iv, ih; for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) { for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) { if (rsv[iv][ih] > -1 || rsh[iv][ih] > -1) return false; } } for (iv = sh[0]; iv < sh[0] + sh[2]; iv++) { for (ih = sh[1]; ih < sh[1] + sh[3]; ih++) { rsv[iv][ih] = 0; rsh[iv][ih] = 0; } } rsv[sh[0]][sh[1]] = sh[2]; rsh[sh[0]][sh[1]] = sh[3]; } function pop_arr() { var em = []; em[0] = arr[0].concat(); for (var i = 0; i < maxh; i++) { em[0][i] = -1; } for (i = 0; i < maxv; i++) { rsv[i] = em[0].concat(); rsh[i] = em[0].concat(); } } 

Answer 2

Do you want it to be square? I would say you want to prioritize the largest area. Now to the algorithm. First, let the matrix be a little larger:

jsFiddle

And this is where I came up with:

jsFiddle

It uses the following simple steps:

• It calculates all the possible widths and heights that a rectangle should have if it wants to find in a matrix.
• First, it sorts these values, if they are square or not, the priority of squares, and then by area: from large to small.
• Then it tries to fit into each rectangle, from large to small.
• A rectangle "fits" if there are 1 number and at least 1 zero in the rectangle.
• If it fits, it leaves a mark there, so all rectangles after that cannot use these cells.
• It ends when there is no zero.

Done.

 var Omatrix = [ //Original matrix [ 1, 2, 0, 3, 4, 0, 2 ], [ 0, 4, 0, 0, 7, 0, 4 ], [ 5, 6, 7, 8, 0, 1, 0 ], [ 1, 0, 0, 0, 4, 0, 0 ], [ 0, 4, 0, 0, 7, 2, 4 ], [ 5, 0, 0, 0, 0, 3, 0 ], [ 0, 0, 0, 0, 4, 9, 3 ], ]; var matrix = [] for (var i = 0; i < Omatrix.length; i++){ matrix[i] = Omatrix[i].slice(0); } //calculating all possible lengths var a = matrix[0].length; //maximum rectangle width var b = matrix.length; //maximum rectangle height //calculate the area of each rectangle and save it using an array var array = []; for (var i = 1; i <= a; i++) { for (var j = 1; j <= b; j++) { array.push({"width":i, "height":j, "area":i*j, "square":i===j}); } } //sort first on square, then on area: biggest first array.sort(function(a, b){ if(a.square === b.square){ x = b.area; y = a.area; return ((x < y) ? -1 : ((x > y) ? 1 : 0)); } else{ return a.square? -1:1; } }); for(var i = 0; i < array.length; i++){ //working from biggest area to smallest for(var j = 0; j < matrix.length-array[i].width+1; j++){ //working from left to right notfound: for(var k = 0; k < matrix[0].length-array[i].height+1; k++){ //working from top to bottom var nonzero = false; var zero = false //checking if there is exactly one number and atleast one zero for(var l = 0; l < array[i].width; l++){ //working from left to right for(var m = 0; m < array[i].height; m++){ //working from top to bottom if(matrix[j+l][k+m] > 0){ if(!nonzero){ //we have found the first number //and saved that number for later use nonzero = matrix[j+l][k+m]; } else{ //we have found a second number: //break and go to the next square continue notfound; } } else if(matrix[j+l][k+m] === 0){ //this is a zero zero = true; } else{ //there is already a square build from this block continue notfound; } } } if(!nonzero || !zero){ //there isn't a number here //or there isn't a zero here continue notfound; } //mark the spots with '-' for(var l = 0; l < array[i].width; l++){ for(var m = 0; m < array[i].height; m++){ matrix[j+l][k+m] = "-"; } } //pack the head of the block with data matrix[j][k] = array[i].width+"x"+array[i].height+"x"+nonzero; } } } var tablestring = ""; for(var i = 0; i < Omatrix.length; i++){ tablestring += "<tr>"; for(var j = 0; j < Omatrix[i].length; j++){ tablestring += "<td>"+Omatrix[i][j]+"</td>"; } tablestring += "</tr>"; } document.getElementById("table1").innerHTML += tablestring; var tablestring = ""; for(var i = 0; i < Omatrix.length; i++){ tablestring += "<tr>"; for(var j = 0; j < Omatrix[i].length; j++){ //going trough all the cells if(matrix[i][j] === "-"){ //a cell with a "-" will not be displayed continue; } else if(typeof(matrix[i][j]) === "string"){ //a cell with a string is the head of a big block of cells. var add = ""; var data = matrix[i][j].split("x"); if(data[0] !== "1"){ add += " rowspan="+data[0]; } if(data[1] !== "1"){ add += " colspan="+data[1]; } tablestring += "<td"+add+">"+data[2]+"</td>"; } else{ //a normal cell tablestring += "<td>"+Omatrix[i][j]+"</td>"; } } tablestring += "</tr>"; } document.getElementById("table2").innerHTML += tablestring; 

Answer 3

Interest Ask. This works in most browsers. It uses an array method method that is ideal for these problems.

 var matrix = [ [ 1, 2, 0, 3 ], [ 0, 4, 0, 0 ], [ 5, 6, 7, 8 ], ]; var table = matrix.reduce(function(rows, row){ rows.push(row.reduce(function(newRow, col){ var lastCol = newRow[newRow.length - 1]; if (!col && lastCol) { lastCol.colspan = (lastCol.colspan || 1) + 1; } else if (!col && !lastCol) { var lastRowCol = rows[rows.length-1][newRow.length]; if (lastRowCol) lastRowCol.rowspan = (lastRowCol.rowspan || 1) + 1; } else { newRow.push({value:col}); } return newRow; }, [])); return rows; }, []); var expected = [ [{value : 1, rowspan: 2}, {value:2, colspan: 2}, {value:3}], [{value : 4, colspan: 3}], [{value : 5}, {value:6}, {value:7}, {value:8}] ]; table.should.eql(expected); // Passed OK 

Answer 4

Note
When I wrote this answer, I haven't read your comments yet, in which you preferred sqare views (i.e.: colspan = 2 rowspan = 2 for 3). I will add a more flexible answer when I find the time.

A simple loop approach might be enough to handle this:

 var cells = [ [ 1, 2, 0, 3 ], [ 0, 4, 0, 0 ], [ 5, 6, 7, 8 ] ],i, j, c, r,tmpString, tbl = []; for (i=0;i<cells.length;++i) { tbl[i] = []; for (j=0;j<cells[i].length;++j) { if (cells[i][j] !== 0) { if (j === 0) {//This only works for first indexes (if not, cells[0][3] + cells[1][3] yields rowspan, too) r = 1; while(i+r < cells.length && cells[i+r][j] === 0) ++r;//while next row == 0, add rowspan count } c = 1; while(c+j < cells[i].length && cells[i][j+c] === 0) ++c; tmpString = '<td'; if (j === 0 && r > 1) tmpString += ' rowspan="' + r + '"'; if (c > 1) tmpString += ' colspan="' + c + '"'; tmpString += '>'+cells[i][j]+'</td>'; tbl[i].push(tmpString); } } tbl[i] = tbl[i].join(''); } console.log('<table border=1 cellpadding=10><tr>' + tbl.join('</tr><tr>') + '</tr></table>'); 

The vanes are awkward (at best), but the names i and j are just simple index / loop counter variables. c counts the flaps that will be needed at any given time, and r does the same for the rows. tbl is an array of arrays that will be used to build the table row.
tmpString is just a variable that is used to merge each cell together. Its main reason for being is to avoid terrible statements like:

 tmp[i].push('<td' + (j === 0 && r > 1 ? ' rowspan="' + r + '"' : '') + (c > 1 ? ' colspan="' + c +'"' : '') + '>' + cells[i][j] + '</td>' ); 

In any case, the output, after adding some indentation, is as follows:

 <table border=1 cellpadding=10> <tr> <td rowspan="2">1</td> <td colspan="2">2</td> <td>3</td> </tr> <tr> <td colspan="3">4</td> </tr> <tr> <td>5</td> <td>6</td> <td>7</td> <td>8</td> </tr> </table> 

What I would say is pretty close to what happened after

Answer 5

In your example, colspan is one plus the number of empty cells to the right of the empty empty cell, and rowspan is similar to one plus the number of empty cells below the empty cell.

When things get interesting, when not a single empty cell has empty cells both on the right and bottom. How do you want to deal with this situation?

Answer 6

Here In your Java script you need to do the following

 var str="<table border=1 cellpadding=10>" var rows=data.lenght(); if(rows>0) { for(int r=0;r<rows;r++) { var cols=data[r].lenght(); if(cols>0) { str+="<tr>"; for(int c=0;c<cols;c++) { var colstospan=getnext0(r,c,0); //This function will give you columns to be span... defination given below str+="<td colspan="+colstospan+">"+data[r][c]+"</td>"; } str+="</tr>"; } } } str+="</table>"; str will give you table you require... 

Here is the definition of getnext0

 function getnext0(rows,cols,count) { if(data[rows][cols+1]==0) { return getnext0(rows,cols+1,count+1); } return count; } 

I hope this works for you .... please ignore if there is a syntax error in the lenght() function ...