Patent ID: 7191396

Claim:
A method computer-implemented method comprising: maintaining an index of candidate start nodes of a current line, the index of candidate start nodes being a list of nodes that will be considered as a potential start node of the current line, the current line being a line on which a node being processed falls when an optimal line break scheme is being calculated for a paragraph layout that ends with the node being processed; beginning with a first node in the reading order of a paragraph, adjusting the index, calculating a width of the current line, and calculating an optimal line break scheme for a paragraph layout that ends with the first node, the optimal line break scheme having a last line that begins with one of the candidate start nodes and ends with the first node, the paragraph ending with a last node, the first node and the last node being different nodes; for every subsequent node in the reading order of the paragraph, adjusting the index, calculating the width of the current line, and calculating an optimal line break scheme for a paragraph layout that ends with that subsequent node, each optimal line break scheme having a last line that begins with one of the candidate start nodes, the first node and each subsequent node defining an unbreakable segment of characters; and formatting the paragraph in accordance with the optimal line break scheme of a last node in the paragraph.