HTML like layouting

Question

I'm trying to implement my own little flow-based layout engine. It should imitate the behavior of HTML layouting, but only the render-tree, not the DOM part. The base class for elements in the render-tree is the Node class. It has:

• A link to the element in the DOM (for the ones that build a render-tree with that library)
• A reference to it's parent (which is a ContainerNode instance or None, see later)
• A reference to the layouting-options
• X, Y, width and height (the position is computed in layout(), after the size has been computed in compute_size(). While the position is defined by the layout() method of the parent, the size is defined by the options reference, for instance).

It's methods are:

• reflow() invoking compute_size() and layout()
• compute_size() that is intended to compute the width and height of the node.
• layout() which is intended to position the sub-nodes of the node, not the node itself.
• paint() which is there to be overwritten by the user of the library.

The ContainerNode class is implementing the handling of sub-nodes. It provides a new method called add_node(), which adds the passed node to the containers children. The function also accepts a parameter force which defaults to False, because the container is allowed to deny the passed node, except force is set to True.

These two classes do not implement any layouting algorithm. My aim was to create different classes for the different types of layouts (In CSS, mainly defined by the display attribute). I did some tests with text-layouting last night and you can find my code from at pastebin.com (requires pygame). You can save it to a python script file and invoke it like this:

python text_test block -c -f "Georgia" -s 15

Note: The code is really really crappy. I appreciate comments on deep lying misconceptions.

The class InlineNodeRow from the code mentioned above actually represents my idea of how to implement the node that lays out similar to the display:inline attribute (in combination with the NodeBox).

Problem 1 - Margin & Padding for inline-text

Back to my current approach in the library: A single word from a text would also be represented as a single node (just like in the code above). But I noticed two things about margins and paddings in a <span> tag.

1. When margin is set, only horizontal margin is taken in account, the vertical margin is ignored.
2. The padding is overflowing the parent container and does not "move" the span node.

See http://jsfiddle.net/CeRkT/1/.

I see the problem here: When I want to compute the size of the InlineNodeBox, I ask a text-node for it's size and add it to the size of the node. But the text-nodes size is including it's margin and padding, which is not included in the HTML renderer's positioning. Therefore the following code would not be right:

def compute_size(self):
    # Propagates the computation to the child-nodes.
    super(InlineNodeBox, self).compute_size()

    self.w = 0
    self.h = 0
    for node in self.nodes:
        self.w += node.w
        if self.h < node.h:
            self.h = node.h

node.w would include the margin and padding. Next problem I see is, that I for laying out the text-nodes correctly, I wanted to split them into single TextNodes for each word, but the margin and padding would then be applied to all these nodes, while the margin and padding in HTML is to the <span> tag only.

I think my current idea of putting each word into a seperate node is not ideal. How to browsers structure their render-tree, or do you have a better idea?

Problem 2 - Word too long, put it into the next line.

The InlineNodeBox class currently only organizes a single line. In the code example above, I've created a new InlineNodeBox from within the NodeBox when the former refused to accept the node (which means it didn't fit in). I can not to this with my current approach, as I do not want to rebuild the render-tree all over again. When a node was accepted once, but exceeds the InlineNodeBox on the next reflow, how do I properly manage to put the word into the next line (assuming I keep the idea of the InlineNodeBox class only organizing a single line of nodes)?

---

I really hope this all makes sense. Feel free to ask if you do not understand my concept. I'm also very open to criticism and ideas for other concepts, links to resources, documentations, publications and alike.

Ninetieth

Upvote for the long and well written text...but too long to think about it :-) – Hatcher

Hopefully some genius mind will spare some time thinking about it. I've spent much time trying to get my thoughts sorted and bring it into something readable and hopefully understandable. – Ninetieth

long and well written, but still nothing more than articulate begging for someone else to do research for them, voting to close as there is no real question here that fits the SO format. You should really get this migrated to programmers.stackexchange.com, that is where things like this might get answered – Matsuyama

I wrote steps that can solve both problems. If will be very useful if you write a test layout in HTML/CSS that should be imitated by that simple library. I'm before important deciding about final classes. Maybe two examples - the minimal and the maximal would be useful: with features that are important for you now and with features that you will never be thinking about extending by more features that should be correctly resized in some combination together. (Paste it similarly as you did with example to problem 1.) – Cheffetz

Closed bounty before any feedback? OK. I stop working on my code. – Cheffetz

Answer 1

Problem 2:

You can do it like HTML renderers do and render a multiline (e.g. check if the new word to be added exceeds the width and add a new line if it does). You can do it in your InlineNodeRow, by taking care of height too and wrapping words if they exceed the max width.

Problem 1:

If you do figure out problem 2 for text, then you can put in the offset (horizontal padding) only for the first line.

Although <span> doesn't take height into consideration, it does take line-height, so your calculation could be that the default height is the font height unless you have a line-height option available.

Mind you, if you have two or more successive InlineNodeRow representing spans, you'd need some smart logic to make the second one continue from where the first one ended :)

As a side note, From what I remember from Qt's rich text label, each set of words with the same rendering properties is considered to be a node, and its render function takes care of calculating all the stuff. Your approach is a bit more granular and its only disadvantage from what I see is that you can't split words.

HTH,

Fai

Yes, the note about line-height is important because increasing the top and down margins of inline element without increasing line-height hides some foots of the letter in the example jsfiddle.net/CeRkT/1 . – Cheffetz

Thank you for your answer. This far I was not able to play around with it anymore, but it gave me a new insight to the topic. Congrats for your new 500 reps! – Ninetieth

Answer 2

May have found solution to problem 1 in the box model documentation (you may want to check out the documentation about clearance and the one for overflow as well for problem 2).

"margins of absolutely positioned boxes do not collapse."

You can see this jsfiddle for an example.

Newish

This is not a solution. Try to add two similar paragraphs into box. It is not possible with flow design or not easy or absolute positioned element hide other elements. See at PO's example code. It tries to dynamically resize elements - reflow – Cheffetz