Php – Reverse horizontal and vertical for a HTML table

algorithmshtmlPHP

There is a two-dimensional array describing a HTML table. Each element of the array consists of:

the cell content
rowspan
colspan

Every row of this two dimensional array corresponds to <td> cells of a <tr> of the table which my software should generate.

I need to "reverse" the array (interchange vertical and horizontal direction).

Insofar I considered algorithm based on this idea: make a rectangular matrix of the size of the table and store in every element of this matrix the corresponding index of the element of the above mentioned array. (Note that two elements of the matrix may be identical due rowspan/colspan.) Then I could use this matrix to calculate rowspan/colspan for the inverted table.

But this idea seems bad for me. Any other algorithms?

Note that I program in PHP.

Best Answer

The only difficulty is to find on which column a cell starts. Once you figure how to do that you can collect the cells for each column and output them as a row, exchanging colspan and rowspan. To find the starting colum you have to track what part of the table positions is used by previous cells. Each cell starts at the next available position.

I don’t know php, so I will use pseudocode.

The input is an array that gives for each row the list of variable-sized cells. The output is in the same format.

I will assume the table fills a rectangular area. If not, some padding with empty cells will be neessary in the output.

function reverse( table:array of array of cell ) 
{
  used = new array of array of boolean.
  output = new array of array of cell

  for r = 0 to table.size()-1 {
    // process row r
    c = 0;
    for each cell in table[r] {
      // skip to next position
      while used[r][c] { c++; }
      // cell starts at column c.  add it to the output
      cell2 = cell with rowspan and colspan values switched
      output[c].append(cell2)
      // mark used table positions (use 1 for missing rowspan/colspan)
      for i = 0 to cell.rowspan-1 {
        for j = 0 to cell.colspan-1 {
          used[r+i][c+j] = true;
        }
      }
    }
  }

  return output;
}

I hope you can translate it to php.

Related Solutions

Merge sort versus quick sort performance

If you look at your code for swapping you:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

But, ~50% of the time that string you just swapped needs to be moved back, which is why faster merge sorts work from both ends at the same time.

Next if you check to see if the first and last elements are the same before doing each of the recursive call you avoid wasting time calling a function only to quickly exit it. This happens 10000000 in your final test which does add noticeable amounts of time.

Use,

if (pivot_index -1 > start) quick_sort(lines, start, pivot_index - 1);

if (pivot_index + 1 < end) quick_sort(lines, pivot_index + 1, end);

You still want an outer function to do an initial if (start < end) but that only needs to happen once so that function can just call an unsafe version of your code without that outer comparison.

Also, picking a random pivot tends to avoid N^2 worst case results, but it's probably not a big deal with your random data set.

Finally, the hidden problem is QuickSort is comparing strings in ever smaller buckets that are ever closer together,

(Edit: So, AAAAA, AAAAB, AAAAC, AAAAD then AAAAA, AAAAB. So, strcmp needs to step though a lot of A's before looking the useful parts of the strings.)

but with Merge sort you look at the smallest buckets first while they are vary random. Mergsorts final passes do compare a lot of strings close to each other, but it's less of an issue then. One way to make Quick sorts faster for strings is to compare the first digits of the outer strings and if there the same ignore them when doing the inner comparisons, but you have to be careful that all strings have enough digits that your not skipping past the null terminator.

C++ – How to Print Bottom View of a Binary Tree?

First create a list, indexed by vertical line, recording the maximum level found on that line. Walk the tree one time to fill in this list.

At this point every list[vertical] entry contains the level that can be seen in the bottom view of the tree.

Then walk the tree again, printing out each node whose level matches the maximum found on its line.

int MaxLvl[];

void printBotOne( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotOne(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]<Level then MaxLvl[Column] = Level;
    printBotOne(qNode->right, Level+1, Column+1);
  }
}

void printBotTwo( node *qNode, int Level, int Column ) {
  if qNode then {
    printBotTwo(qNode->left, Level+1, Column-1);
    if MaxLvl[Column]==Level then cout << qNode->data << " ";
    printBotTwo(qNode->right, Level+1, Column+1);
  }
}

void printBottom( node *qNode ) {
  for(int II = 0; II<nodecount; II++) MaxLvl[II] = 0;
  printBotOne(qNode, 0, nodecount/2);
  printBotTwo(qNode, 0, nodecount/2);
}

This requires a 1D array and runs in O(N).

Best Answer

Related Solutions

Merge sort versus quick sort performance

C++ – How to Print Bottom View of a Binary Tree?

Related Topic