(quick response appreciated): change to box-packing algorithm?

[Adam Megacz]

Hey, what do people think of changing the packing algorithm from:

"a box will be placed as far up and to the left as it can fit"

to

"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

I need to do this in order to be 100% independent of the number of
columns/rows (ie so you can set parent.rows=10000 and child.rowspan to
1000 and still get great performance).

This also happens to be the exact same packing algorithm used by text
reflow...

- a

[Charles Goodwin]

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit"
to
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

Um, sort of. At least, I'd note:

Obviously that's not quite right in that a box that is in a later row
but earlier column will be further to the left than a preceeding sibling
in an earlier row but later column.

Also, this is pre-align as well. (ie not forcing top-left only).

Also, this doesn't apply to non-packed boxes.

[David Crawshaw]

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit"
to
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

I thought that limitation already existed. :)

Fine by me.

-- d

[Adam Megacz]

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

Scratch that.

A box will be placed:

- no higher than its preceeding sibling
- either
- no farther to the left of its preceeding sibling
- below the bottoms of all of its preceeding siblings

- as far up and to the left as possible subject to the previous two
constraints.

Basically this means that the packing algorithm requires O(1) space.
There's a cool algorithm [*] that can do the original form of the
box-packing algorithm in O(numboxes log numboxes) space, but it's a
huge huge pain in the butt.

This is also the (correct) statement of the intuitive text-reflow
system (when colspan==width).

- a

[*] it was actually invented by the people who did the original GUI
Toolbox for the mac... it represents 1-bit bitmaps as an
RLE-encoded array of RLE-encoded arrays. Turns out to be hugely
efficient for bitmaps that are made of big, contiguous rectangles
(which is exactly what the "which-cells-are-taken" map is)

[Adam Megacz]

Hold on, I think I found a way to do the old way quickly.

- a

Post by Adam Megacz

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

Scratch that.
- no higher than its preceeding sibling
- either
- no farther to the left of its preceeding sibling
- below the bottoms of all of its preceeding siblings
- as far up and to the left as possible subject to the previous two
constraints.
Basically this means that the packing algorithm requires O(1) space.
There's a cool algorithm [*] that can do the original form of the
box-packing algorithm in O(numboxes log numboxes) space, but it's a
huge huge pain in the butt.
This is also the (correct) statement of the intuitive text-reflow
system (when colspan==width).
- a
[*] it was actually invented by the people who did the original GUI
Toolbox for the mac... it represents 1-bit bitmaps as an
RLE-encoded array of RLE-encoded arrays. Turns out to be hugely
efficient for bitmaps that are made of big, contiguous rectangles
(which is exactly what the "which-cells-are-taken" map is)
_______________________________________________
core mailing list
http://lists.xwt.org/listinfo/core

[Adam Megacz]

(a new personal record: four replies to myself without any intervening posts)

David, if you want the "new" behavior in the old system, just make
sure rowspan=1 for all the boxes; then the lines of text won't
overlap.

- a

Post by Adam Megacz

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

Scratch that.
- no higher than its preceeding sibling
- either
- no farther to the left of its preceeding sibling
- below the bottoms of all of its preceeding siblings
- as far up and to the left as possible subject to the previous two
constraints.
Basically this means that the packing algorithm requires O(1) space.
There's a cool algorithm [*] that can do the original form of the
box-packing algorithm in O(numboxes log numboxes) space, but it's a
huge huge pain in the butt.
This is also the (correct) statement of the intuitive text-reflow
system (when colspan==width).
- a
[*] it was actually invented by the people who did the original GUI
Toolbox for the mac... it represents 1-bit bitmaps as an
RLE-encoded array of RLE-encoded arrays. Turns out to be hugely
efficient for bitmaps that are made of big, contiguous rectangles
(which is exactly what the "which-cells-are-taken" map is)
_______________________________________________
core mailing list
http://lists.xwt.org/listinfo/core

[Charles Goodwin]

Post by Adam Megacz
Scratch that.
- no higher than its preceeding sibling
- either
- no farther to the left of its preceeding sibling
- below the bottoms of all of its preceeding siblings
- as far up and to the left as possible subject to the previous two
constraints.

<box cols="1">
<box height="200" />
<box height="100" align="bottom" />
<box height="200" />
<box height="100" align="top" />
</box>

That'll still be:

b1b1 b3b3 b4b4
b1b1 b2b2 b3b3

Right?

[Charles Goodwin]

ROWS="1"! (I'm tired!)

Post by Charles Goodwin
<box cols="1">
<box height="200" />
<box height="100" align="bottom" />
<box height="200" />
<box height="100" align="top" />
</box>
b1b1 b3b3 b4b4
b1b1 b2b2 b3b3
Right?

[Andrew Kohlsmith]

Post by Charles Goodwin
<box cols="1">
<box height="200" />
<box height="100" align="bottom" />
<box height="200" />
<box height="100" align="top" />
</box>
b1b1 b3b3 b4b4
b1b1 b2b2 b3b3

You had me worried for a moment there... at least until I hit 'x' in my MUA
to toggle monospaced fonts. :-)

-A.

[Adam Megacz]

I got the best of both worlds.

- a

Post by Adam Megacz

Post by Adam Megacz
"a box will be placed as far up and to the left as it can fit and
still be no higher above and no farther to the left than its
preceeding sibling"

Scratch that.
- no higher than its preceeding sibling
- either
- no farther to the left of its preceeding sibling
- below the bottoms of all of its preceeding siblings
- as far up and to the left as possible subject to the previous two
constraints.
Basically this means that the packing algorithm requires O(1) space.
There's a cool algorithm [*] that can do the original form of the
box-packing algorithm in O(numboxes log numboxes) space, but it's a
huge huge pain in the butt.
This is also the (correct) statement of the intuitive text-reflow
system (when colspan==width).
- a
[*] it was actually invented by the people who did the original GUI
Toolbox for the mac... it represents 1-bit bitmaps as an
RLE-encoded array of RLE-encoded arrays. Turns out to be hugely
efficient for bitmaps that are made of big, contiguous rectangles
(which is exactly what the "which-cells-are-taken" map is)
_______________________________________________
core mailing list
http://lists.xwt.org/listinfo/core