Re: [GSoC] BreakingAlgorithm: simplify handling of activeLines
Hi All, Good news: before-floats are working. There probably are bugs and place for improvement but I think it is time to submit a first patch, so that you may see what I've done. I'm currently cleaning up and documenting my code, and I think the handling of the activeLines array may be simplified: currently, for a line l, activeLines[2*l] points to the first active node for this line, and activeLines[2*l+1] points to the last node. But the last node is never directly accessed, only by starting at the first one and following the links. Perhaps I misunderstand your question, but I think the last active node in a line is used when adding yet another active node for that line at the end of the linked list. In BreakingAlgorithm:addNode(): activeLines[headIdx + 1].next = node; Ah yes, I get it now, thanks Finn. In fact this is to have the insertion of a new node in constant time. Grrr, should have found it out by myself. On the other hand, a different data structure of nodes might very well open up different improvement. The current structure of using a linked list for each line, is just the best I could come up with at the time. I think the structure is fine; I was about to propose to just switch to Java Collections, as Simon said he did in his implementation, but I think I'll leave it as is for now. As Simon's work will probably be eventually integrated, this will be an opportunity of refactoring (BTW, your work may help me implement side-floats; I'll have a closer look at it once I'm done with before-floats). Vincent
Re: [GSoC] BreakingAlgorithm: simplify handling of activeLines
Vincent Hennebert wrote: Hi All, Good news: before-floats are working. There probably are bugs and place for improvement but I think it is time to submit a first patch, so that you may see what I've done. I'm currently cleaning up and documenting my code, and I think the handling of the activeLines array may be simplified: currently, for a line l, activeLines[2*l] points to the first active node for this line, and activeLines[2*l+1] points to the last node. But the last node is never directly accessed, only by starting at the first one and following the links. Perhaps I misunderstand your question, but I think the last active node in a line is used when adding yet another active node for that line at the end of the linked list. In BreakingAlgorithm:addNode(): activeLines[headIdx + 1].next = node; On the other hand, a different data structure of nodes might very well open up different improvement. The current structure of using a linked list for each line, is just the best I could come up with at the time. regards, finn
Re: [GSoC] BreakingAlgorithm: simplify handling of activeLines
On Mon, Jul 17, 2006 at 02:08:54PM +0200, Finn Bock wrote: Vincent Hennebert wrote: I'm currently cleaning up and documenting my code, and I think the handling of the activeLines array may be simplified: currently, for a line l, activeLines[2*l] points to the first active node for this line, and activeLines[2*l+1] points to the last node. But the last node is never directly accessed, only by starting at the first one and following the links. Perhaps I misunderstand your question, but I think the last active node in a line is used when adding yet another active node for that line at the end of the linked list. In BreakingAlgorithm:addNode(): activeLines[headIdx + 1].next = node; On the other hand, a different data structure of nodes might very well open up different improvement. The current structure of using a linked list for each line, is just the best I could come up with at the time. In my own implementation I use Java Collections, a list of lists. Once the active nodes have been separated by line number, there is no reason to preserve any remaining order. Simon -- Simon Pepping home page: http://www.leverkruid.eu
