You are viewing a plain text version of this content. The canonical link for it is here.
Posted to fop-dev@xmlgraphics.apache.org by Vincent Hennebert <vi...@enseeiht.fr> on 2006/07/17 10:05:18 UTC
[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.
There must be a reason for this code but I don't see it. Perhaps this is
related to some older code which since was removed? Or have I missed
something? However, if it is ok I'll simplify that in my patch.
Vincent
Re: [GSoC] BreakingAlgorithm: simplify handling of activeLines
Posted by Simon Pepping <sp...@leverkruid.eu>.
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
Re: [GSoC] BreakingAlgorithm: simplify handling of activeLines
Posted by Vincent Hennebert <vi...@enseeiht.fr>.
> > 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
Posted by Finn Bock <bc...@worldonline.dk>.
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
Posted by Jeremias Maerki <de...@jeremias-maerki.ch>.
Hey, that's good news. I'm looking forward to reviewing the patch.
As for your question: This is probably a nit. I'll leave it up to the
original author to answer. I don't have a problem with leaving this as
is.
On 17.07.2006 10:05:18 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.
>
> There must be a reason for this code but I don't see it. Perhaps this is
> related to some older code which since was removed? Or have I missed
> something? However, if it is ok I'll simplify that in my patch.
>
>
> Vincent
Jeremias Maerki