Re: Skype-conference on page-breaking?

2005-03-09 Thread 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?

2005-03-08 Thread 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?

2005-03-07 Thread 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
mark is with side-floats as they influence 

Re: Skype-conference on page-breaking?

2005-03-07 Thread 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 http://cv.pbw.id.au/
 Project Folio http://defoe.sourceforge.net/folio/



Jeremias Maerki



Re: Skype-conference on page-breaking?

2005-03-07 Thread 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 http://cv.pbw.id.au/
Project Folio http://defoe.sourceforge.net/folio/


Re: Skype-conference on page-breaking?

2005-03-04 Thread 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?

2005-03-04 Thread 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?

2005-03-04 Thread 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?

2005-03-04 Thread 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 http://cv.pbw.id.au/
Project Folio http://defoe.sourceforge.net/folio/


Re: Skype-conference on page-breaking?

2005-03-03 Thread 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?

2005-03-03 Thread 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?

2005-03-01 Thread Renaud Richardet
I would be please to listen.

Renaud


Re: Skype-conference on page-breaking?

2005-03-01 Thread 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?

2005-03-01 Thread 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] - http://homepage.mac.com/webmaestro/
My religion is simple. My religion is kindness.
- HH The 14th Dalai Lama of Tibet