Re: Skype-conference on page-breaking?

[Jeremias Maerki]

Sounds to me like 2) is the way to go right now. This would mean minimal
recreation of vertical boxes in case of changing available IPD. Sure,
this is an exotic case but XSL-FO makes it possible, therefore we must
be prepared for it.

Thanks for the hints and the helpful example.

On 08.03.2005 19:43:57 Luca Furini wrote:
> Jeremias Maerki wrote:
> 
> > Luca, do you think your total-fit approach may be written in a way to
> > handle changing available IPDs and that look-ahead can be disabled to
> > improve processing speed at the cost of optimal break decisions?
> 
> I think that a first fit algorithm could be implemented in two different ways:
> 1) wait until the list of elements representing a whole page-sequence is
>collected, and call findBreakingPoints(); this method will call a
>different considerLegalBreak() method, much simpler and faster than
>the knuth's one.
> 2) start building pages little by little: the FlowLM returns elements to
>the PageLM as soon as one of its own child returns them
> 
> Alternative 1) is much like the total fit algorithm: breaks are computed
> at the end of each page-sequence; even if the evaluation method is much
> faster than Knuth's one, there could still be a long wait in order to get
> the whole list.
> 
> With alternative 2) the PageLM would behave much the same as it now does:
> as soon as a page is filled, it is possible to call addAreas. Note that
> the last elements in the partial sequence cannot be considered as feasible
> break. For example, if there is a block which creates 6 lines, the
> sequence will be something like:
>  box
>  box
>  penalty(not infinite)
>  box
>  penalty(not infinite)
>  box
>  box
> and the evaluation must stop at the second penalty; only when some
> following elements are known it will be possible to decide whether the
> last two lines could be at the end of a page.
> 
> If the IPD is always the same, I think the two alternatives are
> equivalent, and the first one is "better" because it just needs a
> different considerLegalBreak() method; as the output file cannot be
> printed until the end of the process, the only advantage of 2) could be
> memory usage.
> 
> > That's the part where I have a big question mark about changing
> > available IPD. We may have to have a check that figures out if the
> > available IPD changes within a page-sequence by inspecting the
> > page-masters. That would allow us to switch automatically between
> > total-fit and best-fit or maybe even first-fit.
> 
> If the IPD changes, I fear 2) must be necessarily used: if a block is
> split between pages with different ipd, only a few lines need to be
> recreated.
> Using 1), the LineLM should know how wide the lines are, but this cannot
> be known as page breaking has not yet started.
> 
> The check could be done before starting the layout phase: if there is a
> change, 2) is used, otherwise 1).
> Maybe, the check could be even more sophisticated: for example, if the
> first page is different, but the following are equally wide, we could use
> 2) to create the first page and then switch to 1).
> 
> > A remaining question
> > mark is with side-floats as they influence the available IPD on a
> > line-to-line basis.
> 
> This is a question mark for me too! :-)
> 
> > One thing for a deluxe strategy for book-style
> > documents is certainly alignment of lines between facing pages. But
> > that's something that's not important at the moment.
> 
> I have created and implemented a new property right about this! :-)
> 
> > I'd be very interested to hear what you think about the difficulty of
> > changing available IPD. The more I think about it, however, the more I
> > think the total-fit model gets too complicated for what we/I need right
> > now. But I'm unsure here.
> 
> If changing ipd is really important and not just a theorical possibility,
> we could start implementing 2, and later add the check and the algorithm
> 1: the getNextKnuthElements() in the block-level LM could be used in both
> cases.
> 
> Regards
> Luca
> 
> 



Jeremias Maerki

Re: Skype-conference on page-breaking?

[Luca Furini]

Jeremias Maerki wrote:

> Luca, do you think your total-fit approach may be written in a way to
> handle changing available IPDs and that look-ahead can be disabled to
> improve processing speed at the cost of optimal break decisions?

I think that a first fit algorithm could be implemented in two different ways:
1) wait until the list of elements representing a whole page-sequence is
   collected, and call findBreakingPoints(); this method will call a
   different considerLegalBreak() method, much simpler and faster than
   the knuth's one.
2) start building pages little by little: the FlowLM returns elements to
   the PageLM as soon as one of its own child returns them

Alternative 1) is much like the total fit algorithm: breaks are computed
at the end of each page-sequence; even if the evaluation method is much
faster than Knuth's one, there could still be a long wait in order to get
the whole list.

With alternative 2) the PageLM would behave much the same as it now does:
as soon as a page is filled, it is possible to call addAreas. Note that
the last elements in the partial sequence cannot be considered as feasible
break. For example, if there is a block which creates 6 lines, the
sequence will be something like:
 box
 box
 penalty(not infinite)
 box
 penalty(not infinite)
 box
 box
and the evaluation must stop at the second penalty; only when some
following elements are known it will be possible to decide whether the
last two lines could be at the end of a page.

If the IPD is always the same, I think the two alternatives are
equivalent, and the first one is "better" because it just needs a
different considerLegalBreak() method; as the output file cannot be
printed until the end of the process, the only advantage of 2) could be
memory usage.

> That's the part where I have a big question mark about changing
> available IPD. We may have to have a check that figures out if the
> available IPD changes within a page-sequence by inspecting the
> page-masters. That would allow us to switch automatically between
> total-fit and best-fit or maybe even first-fit.

If the IPD changes, I fear 2) must be necessarily used: if a block is
split between pages with different ipd, only a few lines need to be
recreated.
Using 1), the LineLM should know how wide the lines are, but this cannot
be known as page breaking has not yet started.

The check could be done before starting the layout phase: if there is a
change, 2) is used, otherwise 1).
Maybe, the check could be even more sophisticated: for example, if the
first page is different, but the following are equally wide, we could use
2) to create the first page and then switch to 1).

> A remaining question
> mark is with side-floats as they influence the available IPD on a
> line-to-line basis.

This is a question mark for me too! :-)

> One thing for a deluxe strategy for book-style
> documents is certainly alignment of lines between facing pages. But
> that's something that's not important at the moment.

I have created and implemented a new property right about this! :-)

> I'd be very interested to hear what you think about the difficulty of
> changing available IPD. The more I think about it, however, the more I
> think the total-fit model gets too complicated for what we/I need right
> now. But I'm unsure here.

If changing ipd is really important and not just a theorical possibility,
we could start implementing 2, and later add the check and the algorithm
1: the getNextKnuthElements() in the block-level LM could be used in both
cases.

Regards
Luca

Re: Skype-conference on page-breaking?

[Peter B. West]

Jeremias Maerki wrote:
I don't know why this is important to you
Just curious.
but it's two to three months.
Ouch.  Good luck.  You might want to keep an eye on Folio.
Peter
On 04.03.2005 12:40:04 Peter B. West wrote:
Jeremias Maerki wrote:
Sounds very interesting. Would you consider sharing what you already
have? This may help us in the general discussion and may be a good
starting point.
My problem is that I have to deliver working page breaking with keeps,
breaks, multi-column, adjustable spacing etc. in a relatively short
period of time.
How short?

--
Peter B. West 
Project Folio 

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

I don't know why this is important to you but it's two to three months.

On 04.03.2005 12:40:04 Peter B. West wrote:
> Jeremias Maerki wrote:
> > Sounds very interesting. Would you consider sharing what you already
> > have? This may help us in the general discussion and may be a good
> > starting point.
> > 
> > My problem is that I have to deliver working page breaking with keeps,
> > breaks, multi-column, adjustable spacing etc. in a relatively short
> > period of time.
> > 
> 
> How short?
> 
> Peter
> -- 
> Peter B. West 
> Project Folio 



Jeremias Maerki

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

Thanks, Luca.

I've had a nice casual talk on the phone with Simon, yesterday.
Essentially, we only talked about very high-level stuff, especially the
decision for a certain strategy (or two). You know I came up with the
idea to create a simpler best-fit strategy with no look-ahead for
invoice-style documents but maybe it would be possible to design your
obvious total-fit strategy in a way that it could be used as a best-fit
without look-ahead. The problem, like I mentioned already, is the
possible change of available IPD within a page-sequence which results in
a possible back-tracking and recalculation of vertical boxes.

Of course, if it's possible to stay with one page-breaking algorithm for
all use cases that would be best (because of the reduced effort), but
only if the algorithm is reasonably fast for invoice-style documents.
I'm repeatedly confronted with certain speed requirements in this case.
Since modern high-volume single-feed printers handle about 180 pages per
minute (continuous feed systems handle over 4 times that speed, but I
think that's neither relevant, nor realistic here) FOP should be able to
operate close to these 180 pages per minute for not too complex
documents on a modern server. That means 330ms per page. Not much. Of
course, in such an environment it is possible to distribute the
formatting process over several blade servers but I had to realize that
certain companies tend to prefer spending 100'000 dollars on a big
server than spending a lot less for a much faster CPU-power-oriented
setup. It seems to be hard to say good-bye to the old host systems. Well,
that's just like the reality looks like in my environment.

Simon, for example, is much more interested in book-style documents
where there are other requirements. Speed is not a big issue, but
quality is.

In the end, I think we need to rate the chosen approach in these two
points of view. These are very contradicting requirements and it's
something that seems quite important to me not to forget here.

Luca, do you think your total-fit approach may be written in a way to
handle changing available IPDs and that look-ahead can be disabled to
improve processing speed at the cost of optimal break decisions? If it's
ok for you (and feasible) I'd like to integrate what you already have
(in code) into that branch I was talking about. I would like to avoid
recreating something you've already started, even if it doesn't work
with the changes that happened in the last weeks. Even if we may create
two different strategies I'm sure that certain parts will be shared by
both approaches, like the creation of Knuth-style elements for the
PageLM. 

Some more comments inline:

On 04.03.2005 13:23:01 Luca Furini wrote:
> 
> Jeremias Maerki wrote:
> 
> >Would you consider sharing what you already
> >have? This may help us in the general discussion and may be a good
> >starting point.
> 
> Ok, I'll try to.
> 
> The main change in the LineLM is that the line breaking algorithm does not
> select only the node in activeList with fewest demerits: all the nodes
> whose demerits are <= a threshold are used to create LineBreakPositions,
> so for each paragraph there is a set of layout options (for example, a
> paragraph could create 8 to 10 lines, 9 being the layout with fewest
> demerits).

Hmm, that's a feature that I would say is something that only book-style
documents will need. Invoice-style documents could live without it.

> According to the value of widows and orphans, the LineLM creates a
> sequence of elements: besides "normal" lines, represented by a box, there
> are "optional lines", represented by
>   box(0) penalty(inf,0) glue(0,1,0) box(0)
> and "removable lines"
>   box(0) penalty(inf,0) glue(1,0,1) box(0)
> A few complications arise if not every possible layout allows breaks
> between lines, but they all can be solved using boxes, glues and
> penalties (for example, if a paragraph needs 3 or 4 lines, if it uses 3
> it cannot be parted).

Also something that's not all too important for invoice-style documents,
although it can't hurt to have it.

> The BlockLM, and a block stacking LM in general, adds elements
> representing its children's spaces and keep condition, for example
> adding a 0 penalty or an infinite penalty according to
> child1.mustKeepWithNext(), child2.mustKeepWithPrevious() and
> this.mustKeepTogether().

That's certainly a must-have in any case.

> The PageLM, once it has the list of elements representing a whole
> page-sequence (or the content before a forced page break), calls the same
> breaking algorithm, using only a different selection method which leaves
> only one node in activeList.

That's the part where I have a big question mark about changing
available IPD. We may have to have a check that figures out if the
available IPD changes within a page-sequence by inspecting the
page-masters. That would allow us to switch automatically between
total-fit and best-fit or maybe even first-fit. A remaining question
ma

Re: Skype-conference on page-breaking?

[Luca Furini]

Jeremias Maerki wrote:

>Would you consider sharing what you already
>have? This may help us in the general discussion and may be a good
>starting point.

Ok, I'll try to.

The main change in the LineLM is that the line breaking algorithm does not
select only the node in activeList with fewest demerits: all the nodes
whose demerits are <= a threshold are used to create LineBreakPositions,
so for each paragraph there is a set of layout options (for example, a
paragraph could create 8 to 10 lines, 9 being the layout with fewest
demerits).

According to the value of widows and orphans, the LineLM creates a
sequence of elements: besides "normal" lines, represented by a box, there
are "optional lines", represented by
  box(0) penalty(inf,0) glue(0,1,0) box(0)
and "removable lines"
  box(0) penalty(inf,0) glue(1,0,1) box(0)
A few complications arise if not every possible layout allows breaks
between lines, but they all can be solved using boxes, glues and
penalties (for example, if a paragraph needs 3 or 4 lines, if it uses 3
it cannot be parted).

The BlockLM, and a block stacking LM in general, adds elements
representing its children's spaces and keep condition, for example
adding a 0 penalty or an infinite penalty according to
child1.mustKeepWithNext(), child2.mustKeepWithPrevious() and
this.mustKeepTogether().

The PageLM, once it has the list of elements representing a whole
page-sequence (or the content before a forced page break), calls the same
breaking algorithm, using only a different selection method which leaves
only one node in activeList.
It has now a rough sequence of pages: each one may may have a positive or
negative difference (with respect to the page height); the glue elements
representing adjustable lines or adjustable spaces in a page are collected
in different lists and they are used to "negotiate" a block progression
adjustment with the LM which created them. In this phase each LineLM
knows how many lines it will finally create.

Then, a new sequence of elements is created, and this time each element
has a fixed width (as the adjustments have already been decided).
This sequence is used to create the final pages; note that if the
adjustments have been enough to perfectly fill the pages, a first fit
algorithm would be enough to recreate the right page breaks.
This phase is needed, at the moment, because the Positions that the
LineLMs store in their elements are not LineBreakPosition (as they still
don't know how many lines they have to create), but maybe it could be
avoided in some way ...

Don't hesitate to ask for further details, I'll try to answer as clearly
as possible!

As per the columns, I did not think about them yet, but if they are
equally wide it shouldn't be terribly hard to handle them ...

Regards
  Luca

Re: Skype-conference on page-breaking?

[Peter B. West]

Jeremias Maerki wrote:
Sounds very interesting. Would you consider sharing what you already
have? This may help us in the general discussion and may be a good
starting point.
My problem is that I have to deliver working page breaking with keeps,
breaks, multi-column, adjustable spacing etc. in a relatively short
period of time.
How short?
Peter
--
Peter B. West 
Project Folio 

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

Sounds very interesting. Would you consider sharing what you already
have? This may help us in the general discussion and may be a good
starting point.

My problem is that I have to deliver working page breaking with keeps,
breaks, multi-column, adjustable spacing etc. in a relatively short
period of time.

On 04.03.2005 11:09:42 Luca Furini wrote:
> 
> Jeremias Maerki wrote:
> 
> >Anyway, I'd like to ask if we could hold to a brainstorming conference
> >call on page breaking either Sunday evening or next Monday or Tuesday
> >somewhere between 8:00 and 24:00 CET. Of course, on my wish list there
> >are Simon, Finn and Luca. I'm happy to call either of you on your normal
> >phone via SkypeOut if you don't have broadband. I hope I can get at
> >least one of you three on the line.
> 
> I'v very interested in page breaking, and I would be happy to contribute.
> 
> Unfortunately, I'm not much used to speaking english :-(, so I think I
> would be much more comfortable with the idea of communicating via written
> words!
> 
> As I have said before (or maybe I forgot to ...) I have done a few
> experiments trying to use Knuth's algorithm in page braking, and I have a
> working implementation which handles only some block level formatting
> objects (blocks and lists) and simplified documents (no footnotes or
> floats, at the moment, and pages with equal length and width), but it has
> some (I hope) interesting features: for example, it is able to adjust the
> number of lines used for each paragraph in order to both fill the pages
> and avoid orphans and widows.
> In a few words, using the box - penalty - glue model it is possible to
> represent paragraphs with an adjustable number of lines.
> 
> I started working on it a few months ago, and I could not keep it updated
> with all the changes, but if you are interested I could try and recreate
> these features using the most recent code. Anyway, this could be done
> after we have reached a basic implementation.
> 
> Regards
> Luca



Jeremias Maerki

Re: Skype-conference on page-breaking?

[Luca Furini]

Jeremias Maerki wrote:

>Anyway, I'd like to ask if we could hold to a brainstorming conference
>call on page breaking either Sunday evening or next Monday or Tuesday
>somewhere between 8:00 and 24:00 CET. Of course, on my wish list there
>are Simon, Finn and Luca. I'm happy to call either of you on your normal
>phone via SkypeOut if you don't have broadband. I hope I can get at
>least one of you three on the line.

I'v very interested in page breaking, and I would be happy to contribute.

Unfortunately, I'm not much used to speaking english :-(, so I think I
would be much more comfortable with the idea of communicating via written
words!

As I have said before (or maybe I forgot to ...) I have done a few
experiments trying to use Knuth's algorithm in page braking, and I have a
working implementation which handles only some block level formatting
objects (blocks and lists) and simplified documents (no footnotes or
floats, at the moment, and pages with equal length and width), but it has
some (I hope) interesting features: for example, it is able to adjust the
number of lines used for each paragraph in order to both fill the pages
and avoid orphans and widows.
In a few words, using the box - penalty - glue model it is possible to
represent paragraphs with an adjustable number of lines.

I started working on it a few months ago, and I could not keep it updated
with all the changes, but if you are interested I could try and recreate
these features using the most recent code. Anyway, this could be done
after we have reached a basic implementation.

Regards
Luca

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

Ok then, I'll call you Sunday evening 19.00 CET if nothing goes wrong.
The others interested will find me in Skype.

FYI, I'll be out of touch from later today until Sunday afternoon.

On 03.03.2005 21:46:55 Simon Pepping wrote:
> On Thu, Mar 03, 2005 at 08:34:54PM +0100, Jeremias Maerki wrote:
> > I've bought some SkypeOut credits now. Funny thing: It's cheaper to call
> > Simon in the Netherlands than to call someone in Lucerne via PSTN. 
> > 
> > Anyway, I'd like to ask if we could hold to a brainstorming conference
> > call on page breaking either Sunday evening or next Monday or Tuesday
> > somewhere between 8:00 and 24:00 CET. Of course, on my wish list there
> > are Simon, Finn and Luca. I'm happy to call either of you on your normal
> > phone via SkypeOut if you don't have broadband. I hope I can get at
> > least one of you three on the line. Others are invited to listen in and
> > contribute, of course. Max. number in the conference is four people with
> > Skype.
> 
> Sunday evening is OK. Monday and Tuesday after working hours is OK. I
> could be available from 16.00 hrs, but I would prefer after 19.00 hrs
> CET. There is no way I can do this at the office.
> 
> Regards, Simon
> 
> -- 
> Simon Pepping
> home page: http://www.leverkruid.nl



Jeremias Maerki

Re: Skype-conference on page-breaking?

[Simon Pepping]

On Thu, Mar 03, 2005 at 08:34:54PM +0100, Jeremias Maerki wrote:
> I've bought some SkypeOut credits now. Funny thing: It's cheaper to call
> Simon in the Netherlands than to call someone in Lucerne via PSTN. 
> 
> Anyway, I'd like to ask if we could hold to a brainstorming conference
> call on page breaking either Sunday evening or next Monday or Tuesday
> somewhere between 8:00 and 24:00 CET. Of course, on my wish list there
> are Simon, Finn and Luca. I'm happy to call either of you on your normal
> phone via SkypeOut if you don't have broadband. I hope I can get at
> least one of you three on the line. Others are invited to listen in and
> contribute, of course. Max. number in the conference is four people with
> Skype.

Sunday evening is OK. Monday and Tuesday after working hours is OK. I
could be available from 16.00 hrs, but I would prefer after 19.00 hrs
CET. There is no way I can do this at the office.

Regards, Simon

-- 
Simon Pepping
home page: http://www.leverkruid.nl

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

I've bought some SkypeOut credits now. Funny thing: It's cheaper to call
Simon in the Netherlands than to call someone in Lucerne via PSTN. 

Anyway, I'd like to ask if we could hold to a brainstorming conference
call on page breaking either Sunday evening or next Monday or Tuesday
somewhere between 8:00 and 24:00 CET. Of course, on my wish list there
are Simon, Finn and Luca. I'm happy to call either of you on your normal
phone via SkypeOut if you don't have broadband. I hope I can get at
least one of you three on the line. Others are invited to listen in and
contribute, of course. Max. number in the conference is four people with
Skype.

On 01.03.2005 23:31:16 Jeremias Maerki wrote:
> Maybe I could hook you into a Skype conference by using SkypeOut. It's pretty
> cheap to call to the Netherlands. According to the FAQ this is possible.
> 
> On 01.03.2005 22:26:50 Simon Pepping wrote:
> > On Tue, Mar 01, 2005 at 03:09:46PM +0100, Jeremias Maerki wrote:
> > > To speed things up could we hold a conference (using Skype, for example)
> > > to discuss further details on page-breaking? I'd volunteer to sum up any
> > > results during that discussion for the archives. I have Finn on my Skype
> > > radar already.
> > 
> > I do not have a broadband connection, and therefore no Skype or other
> > VoIP.
> 
> 
> Jeremias Maerki



Jeremias Maerki

Re: Skype-conference on page-breaking?

[The Web Maestro]

I'd be happy to 'participate' although I don't have a skype acct yet. I 
don't know what I can offer, but I'm here to help!

Cheers!
On Mar 1, 2005, at 2:31 PM, Jeremias Maerki wrote:
Maybe I could hook you into a Skype conference by using SkypeOut. It's 
pretty
cheap to call to the Netherlands. According to the FAQ this is 
possible.

On 01.03.2005 22:26:50 Simon Pepping wrote:
On Tue, Mar 01, 2005 at 03:09:46PM +0100, Jeremias Maerki wrote:
To speed things up could we hold a conference (using Skype, for 
example)
to discuss further details on page-breaking? I'd volunteer to sum up 
any
results during that discussion for the archives. I have Finn on my 
Skype
radar already.
I do not have a broadband connection, and therefore no Skype or other
VoIP.
Jeremias Maerki
Web Maestro Clay
--
<[EMAIL PROTECTED]> - 
My religion is simple. My religion is kindness.
- HH The 14th Dalai Lama of Tibet

Re: Skype-conference on page-breaking?

[Jeremias Maerki]

Maybe I could hook you into a Skype conference by using SkypeOut. It's pretty
cheap to call to the Netherlands. According to the FAQ this is possible.

On 01.03.2005 22:26:50 Simon Pepping wrote:
> On Tue, Mar 01, 2005 at 03:09:46PM +0100, Jeremias Maerki wrote:
> > To speed things up could we hold a conference (using Skype, for example)
> > to discuss further details on page-breaking? I'd volunteer to sum up any
> > results during that discussion for the archives. I have Finn on my Skype
> > radar already.
> 
> I do not have a broadband connection, and therefore no Skype or other
> VoIP.


Jeremias Maerki

Re: Skype-conference on page-breaking?

[Simon Pepping]

On Tue, Mar 01, 2005 at 03:09:46PM +0100, Jeremias Maerki wrote:
> To speed things up could we hold a conference (using Skype, for example)
> to discuss further details on page-breaking? I'd volunteer to sum up any
> results during that discussion for the archives. I have Finn on my Skype
> radar already.

I do not have a broadband connection, and therefore no Skype or other
VoIP.

Regards, Simon

-- 
Simon Pepping
home page: http://www.leverkruid.nl

Re: Skype-conference on page-breaking?

[Renaud Richardet]

I would be please to listen.

Renaud