Tiling a plane efficiently (web design, database)

Here’s an interesting one for you.

DISCLAIMER: I am being paid for this as a freelance web designer, so if you don’t want to / can’t offer help that’s absolutely fine & I totally understand.
MODS: I’m asking for some help, not touting for any freebies - please!

Suppose I have an arbitrary list of 2x1 and 1x1 tiles. They can be either:


X     (single 1x1)
WW  (double width 2x1)         
H
H     (double height 1x2)

They are stored in a database like so


id     IsDoubleW     Is DoubleH    Order       (more fields)
int    bool             bool        int           etc

Can anyone think of a way of efficiently tiling a 3 column plane such that it is as compact as possible, and preserving the order as much as possible?

Example: I select from the database : “SELECT * FROM Table ORDER BY Order ASC”
Which gives me the following list of tiles (ignoring other fields) (S = single, H=double-height, W=double-width):
“S1, H1, W1, H2, S2, S3”

Which I would like to tile something like:


S1  H1  S2
S3  H1  H2
W1  W1  H2

as opposed to:


S1  H1
    H1
W1  W1 H2
       H2
S2  S3

I’ve been warcking my head on how to come up with a good way of doing it using left-floated sized divs. I’m open to alternatives of course
Using php & mysql.

I had a thought about building (somehow) some kind of 2-dimensional “world” bitmap (an array of the ID’s perhaps), and then iterating over it, selecting unique IDs. I think I’d need to have a special token for a “blank” square, as obviously if I select and get back “W1,W2,W3”, no amout of futzing will tile a 3 column plane.

If I only have 1x1 tiles, it is easy assuming a 300px wide container:

select * from Table
while <row>
echo div style=“float:left; width:100px; height:100px”

Any ideas anyone?

Ok, well. I figured something out for the case of 1x1 and 2x1 (single & double-width):

pseudo-code:


assume an array with unique tiles in it, zero based
int colIndex=0 'the current column in the 3xn grid

while <array>
  if array[0] isSingle then
    addTile(array[0])
    array.removeAt[0]
    colIndex ++1
  elseif array[0] isDoubleWidth then
    if colIndex > 1 then
      if array.contains(singleTitle) then
        addTile(array[Indexof(Singletile)]
        array.removeAt[array.indexOf(SingleTitle)]
        colIndex ++1
      else
        colIndex=0
      endif
    else
      addTile(array[0])
      array.RemoveAt[0]
      colIndex ++2
    endif
  endif
end while 

Which works OK, but is a bit ugly. Haven’t yet figured out how to do double-height.