Method and computer readable medium for optimized paragraph layout

A method for laying out a paragraph of text on a page, the method comprising:

• generating one or more layout nodes for the text from a current layout node, each layout node comprising data representing a possible layout of the paragraph to a point within a backing store and identifying any changes to a geometry of the page caused by the layout of the paragraph defined by the layout node;
• producing a line-by-line paragraph layout for the text to determine a maximum penalty for the paragraph
• calculating a penalty for each of the generated layout nodes;
• adding each layout node to a node pool that has a penalty less than the maximum penalty for the paragraph;
• removing the current layout node from the node pool;
• and
• repeating the generating, calculating, adding, and removing operations until only a single node remains in the node pool that represents the entire paragraph of text, wherein producing a line-by-line layout of the paragraph comprises iteratively processing the text to locate a best possible break for each line of text, calculating a penalty for the line-by-line paragraph layout by summing a penalty for each line of text in the paragraph, identifying any figures that are on a page containing the paragraph after performing the line-by-line layout of the paragraph, and removing all layout nodes from the node pool that cause any of the figures identified during the line-by-line layout to be pushed to a next page.