BreakingAlgorithm


1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /* $Id: BreakingAlgorithm.java 453310 2006-10-05 18:44:15Z spepping $ */
19  
20  package org.apache.fop.layoutmgr;
21  
22  import org.apache.commons.logging.Log;
23  import org.apache.commons.logging.LogFactory;
24  
25  import org.apache.fop.fo.FONode;
26  
27  /**
28   * The set of nodes is sorted into lines indexed into activeLines.
29   * The nodes in each line are linked together in a single linked list by the 
30   * KnuthNode.next field. The activeLines array contains a link to the head of
31   * the linked list in index 'line*2' and a link to the tail at index 'line*2+1'.
32   * <p>
33   * The set of active nodes can be traversed by 
34   * <pre>
35   * for (int line = startLine; line &lt; endLine; line++) {
36   *     for (KnuthNode node = getNode(line); node != null; node = node.next) {
37   *         // Do something with 'node'
38   *     }
39   * }
40   * </pre> 
41   */
42  public abstract class BreakingAlgorithm {
43  
44      /** the logger for the class */
45      protected static Log log = LogFactory.getLog(BreakingAlgorithm.class);
46      
47      /** Maximum adjustment ration */
48      protected static final int INFINITE_RATIO = 1000;
49  
50      private static final int MAX_RECOVERY_ATTEMPTS = 5;
51  
52      // constants identifying a subset of the feasible breaks
53      /** All feasible breaks are ok. */
54      public static final int ALL_BREAKS = 0;
55      /** This forbids hyphenation. */
56      public static final int NO_FLAGGED_PENALTIES = 1;
57      /** wrap-option = "no-wrap". */
58      public static final int ONLY_FORCED_BREAKS = 2;
59  
60      // parameters of Knuth's algorithm:
61      /** Penalty value for flagged penalties. */
62      private int flaggedPenalty = 50;
63      /** Demerit for consecutive lines ending at flagged penalties. */
64      protected int repeatedFlaggedDemerit = 50;
65      /** Demerit for consecutive lines belonging to incompatible fitness classes . */
66      protected int incompatibleFitnessDemerit = 50;
67      /** Maximum number of consecutive lines ending with a flagged penalty.
68       * Only a value >= 1 is a significant limit.
69       */
70      protected int maxFlaggedPenaltiesCount;
71  
72      /**
73       * The threshold for considering breaks to be acceptable. The adjustment ratio must be
74       * inferior to this threshold.
75       */
76      private double threshold;
77  
78      /**
79       * The paragraph of KnuthElements.
80       */
81      protected KnuthSequence par;
82      
83      /**
84       * The width of a line (or height of a column in page-breaking mode).
85       * -1 indicates that the line widths are different for each line.
86       */
87      protected int lineWidth = -1;
88      /** Force the algorithm to find a set of breakpoints, even if no feasible breakpoints
89       * exist.
90       */
91      private boolean force =  false;
92      /** If set to true, doesn't ignore break possibilities which are definitely too short. */
93      protected boolean considerTooShort = false;
94  
95      /** When in forced mode, the best node leading to a too long line. The line will be
96       * too long anyway, but this one will lead to a paragraph with fewest demerits.
97       */
98      private KnuthNode lastTooLong;
99      /** When in forced mode, the best node leading to a too short line. The line will be
100      * too short anyway, but this one will lead to a paragraph with fewest demerits.
101      */
102     private KnuthNode lastTooShort;
103     /** The node to be reactivated if no set of feasible breakpoints can be found for this
104      * paragraph.
105      */
106     private KnuthNode lastDeactivated;
107 
108     /** Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. */
109     protected int alignment;
110     /** Alignment of the paragraph's last line. */
111     protected int alignmentLast;
112     /** Used to handle the text-indent property (indent the first line of a paragraph). */
113     protected boolean bFirst;
114 
115     /**
116      * The set of active nodes in ascending line order. For each line l, activeLines[2l] contains a
117      * link to l's first active node, and activeLines[2l+1] a link to l's last active node. The
118      * line number l corresponds to the number of the line ending at the node's breakpoint.
119      */
120     protected KnuthNode[] activeLines;
121     
122     /**
123      * The number of active nodes.
124      */
125     protected int activeNodeCount;
126     
127     /**
128      * The lowest available line in the set of active nodes.
129      */
130     protected int startLine = 0;
131 
132     /**
133      * The highest + 1 available line in the set of active nodes.
134      */
135     protected int endLine = 0;
136 
137     /**
138      * The total width of all elements handled so far.
139      */
140     protected int totalWidth;
141 
142     /**
143      * The total stretch of all elements handled so far.
144      */
145     protected int totalStretch = 0;
146 
147     /**
148      * The total shrink of all elements handled so far.
149      */
150     protected int totalShrink = 0;
151 
152     protected BestRecords best;
153 
154     /** @see #isPartOverflowRecoveryActivated() */
155     private boolean partOverflowRecoveryActivated = true;
156     private KnuthNode lastRecovered;
157 
158     /**
159      * Create a new instance.
160      * @param align alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. For
161      * pages EN_BEFORE, EN_AFTER are mapped to the corresponding inline properties
162      * (EN_START, EN_END)
163      * @param alignLast alignment of the paragraph's last line
164      * @param first for the text-indent property (indent the first line of a paragraph)
165      * @param partOverflowRecovery true if too long elements should be moved to the next line/part
166      * @param maxFlagCount maximum allowed number of consecutive lines ending at a flagged penalty
167      * item
168      */
169     public BreakingAlgorithm(int align, int alignLast,
170                              boolean first, boolean partOverflowRecovery,
171                              int maxFlagCount) {
172         alignment = align;
173         alignmentLast = alignLast;
174         bFirst = first;
175         this.partOverflowRecoveryActivated = partOverflowRecovery;
176         this.best = new BestRecords();
177         maxFlaggedPenaltiesCount = maxFlagCount;
178     }
179 
180 
181     /**
182      * Class recording all the informations of a feasible breaking point.
183      */
184     public class KnuthNode {
185         /** index of the breakpoint represented by this node */
186         public int position;
187 
188         /** number of the line ending at this breakpoint */
189         public int line;
190 
191         /** fitness class of the line ending at this breakpoint. One of 0, 1, 2, 3. */
192         public int fitness;
193 
194         /** accumulated width of the KnuthElements up to after this breakpoint. */
195         public int totalWidth;
196 
197         /** accumulated stretchability of the KnuthElements up to after this breakpoint. */
198         public int totalStretch;
199 
200         /** accumulated shrinkability of the KnuthElements up to after this breakpoint. */
201         public int totalShrink;
202 
203         /** adjustment ratio if the line ends at this breakpoint */
204         public double adjustRatio;
205 
206         /** available stretch of the line ending at this breakpoint */
207         public int availableShrink;
208 
209         /** available shrink of the line ending at this breakpoint */
210         public int availableStretch;
211 
212         /** difference between target and actual line width */
213         public int difference;
214 
215         /** minimum total demerits up to this breakpoint */
216         public double totalDemerits;
217 
218         /** best node for the preceding breakpoint */
219         public KnuthNode previous;
220 
221         /** next possible node in the same line */ 
222         public KnuthNode next;
223 
224         /**
225          * Holds the number of subsequent recovery attempty that are made to get content fit
226          * into a line.
227          */
228         public int fitRecoveryCounter = 0;
229         
230         public KnuthNode(int position, int line, int fitness,
231                          int totalWidth, int totalStretch, int totalShrink,
232                          double adjustRatio, int availableShrink, int availableStretch,
233                          int difference, double totalDemerits, KnuthNode previous) {
234             this.position = position;
235             this.line = line;
236             this.fitness = fitness;
237             this.totalWidth = totalWidth;
238             this.totalStretch = totalStretch;
239             this.totalShrink = totalShrink;
240             this.adjustRatio = adjustRatio;
241             this.availableShrink = availableShrink;
242             this.availableStretch = availableStretch;
243             this.difference = difference;
244             this.totalDemerits = totalDemerits;
245             this.previous = previous;
246         }
247 
248         public String   toString() {
249             return "<KnuthNode at " + position + " "
250                     + totalWidth + "+" + totalStretch + "-" + totalShrink
251                     + " line:" + line + " prev:" + (previous != null ? previous.position : -1)
252                     + " dem:" + totalDemerits + ">"; 
253         }
254     }
255 
256     /** Class that stores, for each fitness class, the best active node that could start
257      * a line of the corresponding fitness ending at the current element.
258      */
259     protected class BestRecords {
260         private static final double INFINITE_DEMERITS = Double.POSITIVE_INFINITY;
261         //private static final double INFINITE_DEMERITS = 1E11;
262 
263         private double[] bestDemerits = new double[4];
264         private KnuthNode[] bestNode = new KnuthNode[4];
265         private double[] bestAdjust = new double[4];
266         private int[] bestDifference = new int[4];
267         private int[] bestAvailableShrink = new int[4];
268         private int[] bestAvailableStretch = new int[4];
269         /** Points to the fitness class which currently leads to the best demerits. */
270         private int bestIndex = -1;
271 
272         public BestRecords() {
273             reset();
274         }
275 
276         /** Registers the new best active node for the given fitness class.
277          * @param demerits the total demerits of the new optimal set of breakpoints
278          * @param node the node starting the line ending at the current element
279          * @param adjust adjustment ratio of the current line
280          * @param availableShrink how much the current line can be shrinked
281          * @param availableStretch how much the current line can be stretched
282          * @param difference difference between the width of the considered line and the
283          * width of the "real" line
284          * @param fitness fitness class of the current line
285          */
286         public void addRecord(double demerits, KnuthNode node, double adjust,
287                               int availableShrink, int availableStretch,
288                               int difference, int fitness) {
289             if (demerits > bestDemerits[fitness]) {
290                 log.error("New demerits value greater than the old one");
291             }
292             bestDemerits[fitness] = demerits;
293             bestNode[fitness] = node;
294             bestAdjust[fitness] = adjust;
295             bestAvailableShrink[fitness] = availableShrink;
296             bestAvailableStretch[fitness] = availableStretch;
297             bestDifference[fitness] = difference;
298             if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) {
299                 bestIndex = fitness;
300             }
301         }
302 
303         public boolean hasRecords() {
304             return (bestIndex != -1);
305         }
306 
307         /**
308          * @param fitness fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose")
309          * @return true if there is a set of feasible breakpoints registered for the
310          *              given fitness.
311          */
312         public boolean notInfiniteDemerits(int fitness) {
313             return (bestDemerits[fitness] != INFINITE_DEMERITS);
314         }
315 
316         public double getDemerits(int fitness) {
317             return bestDemerits[fitness];
318         }
319 
320         public KnuthNode getNode(int fitness) {
321             return bestNode[fitness];
322         }
323 
324         public double getAdjust(int fitness) {
325             return bestAdjust[fitness];
326         }
327 
328         public int getAvailableShrink(int fitness) {
329             return bestAvailableShrink[fitness];
330         }
331 
332         public int getAvailableStretch(int fitness) {
333             return bestAvailableStretch[fitness];
334         }
335 
336        public int getDifference(int fitness) {
337             return bestDifference[fitness];
338         }
339 
340         public double getMinDemerits() {
341             if (bestIndex != -1) {
342                 return getDemerits(bestIndex);
343             } else {
344                 // anyway, this should never happen
345                 return INFINITE_DEMERITS;
346             }
347         }
348 
349         /** Reset when a new breakpoint is being considered. */
350         public void reset() {
351             for (int i = 0; i < 4; i++) {
352                 bestDemerits[i] = INFINITE_DEMERITS;
353                 // there is no need to reset the other arrays
354             }
355             bestIndex = -1;
356         }
357     }
358 
359     /**
360      * @return the number of times the algorithm should try to move overflowing content to the
361      * next line/page.
362      */
363     protected int getMaxRecoveryAttempts() {
364         return MAX_RECOVERY_ATTEMPTS;
365     }
366     
367     /**
368      * Controls the behaviour of the algorithm in cases where the first element of a part
369      * overflows a line/page. 
370      * @return true if the algorithm should try to send the element to the next line/page.
371      */
372     protected boolean isPartOverflowRecoveryActivated() {
373         return this.partOverflowRecoveryActivated;
374     }
375 
376     /** Empty method, hook for subclasses. Called before determining the optimal
377      * breakpoints corresponding to a given active node.
378      * @param total number of lines for the active node
379      * @param demerits total demerits of the paragraph for the active node
380      */
381     public abstract void updateData1(int total, double demerits);
382 
383     /** Empty method, hook for subclasses. Called when determining the optimal breakpoints
384      * for a given active node.
385      * @param bestActiveNode a node in the chain of best active nodes, corresponding to
386      * one of the optimal breakpoints
387      * @param sequence the corresponding paragraph
388      * @param total the number of lines into which the paragraph will be broken
389      * @see #calculateBreakPoints(KnuthNode, KnuthSequence, int)
390      */
391     public abstract void updateData2(KnuthNode bestActiveNode,
392                                      KnuthSequence sequence,
393                                      int total);
394 
395     public void setConstantLineWidth(int lineWidth) {
396         this.lineWidth = lineWidth;
397     }
398 
399     /** @see #findBreakingPoints(KnuthSequence, int, double, boolean, int) */
400     public int findBreakingPoints(KnuthSequence par, /*int lineWidth,*/
401             double threshold, boolean force,
402             int allowedBreaks) {
403         return findBreakingPoints(par, 0, threshold, force, allowedBreaks);
404     }
405     
406     /** Finds an optimal set of breakpoints for the given paragraph.
407      * @param par the paragraph to break
408      * @param startIndex index of the Knuth element at which the breaking must start
409      * @param threshold upper bound of the adjustment ratio
410      * @param force true if a set of breakpoints must be found even if there are no
411      * feasible ones
412      * @param allowedBreaks one of ONLY_FORCED_BREAKS, NO_FLAGGED_PENALTIES, ALL_BREAKS
413      */
414     public int findBreakingPoints(KnuthSequence par, int startIndex,
415                                   /*int lineWidth,*/
416                                   double threshold, boolean force,
417                                   int allowedBreaks) {
418         this.par = par;
419         this.threshold = threshold;
420         this.force = force;
421         //this.lineWidth = lineWidth;
422         initialize();
423 
424         activeLines = new KnuthNode[20];
425 
426         // reset lastTooShort and lastTooLong, as they could be not null
427         // because of previous calls to findBreakingPoints
428         lastTooShort = lastTooLong = null; 
429         // reset startLine and endLine
430         startLine = endLine = 0;
431         // current element in the paragraph
432         KnuthElement thisElement = null;
433         // previous element in the paragraph is a KnuthBox?
434         boolean previousIsBox = false;
435 
436         // index of the first KnuthBox in the sequence
437         int firstBoxIndex = startIndex;
438         if (alignment != org.apache.fop.fo.Constants.EN_CENTER) {
439             while (par.size() > firstBoxIndex
440                     && !((KnuthElement) par.get(firstBoxIndex)).isBox()) {
441                 firstBoxIndex++;
442             }
443         }
444 
445         // create an active node representing the starting point
446         activeLines = new KnuthNode[20];
447         addNode(0, createNode(firstBoxIndex, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, null));
448 
449         if (log.isTraceEnabled()) {
450             log.trace("Looping over " + (par.size() - startIndex) + " elements");
451         }
452         
453         KnuthNode lastForced = getNode(0);
454 
455         // main loop
456         for (int i = startIndex; i < par.size(); i++) {
457             thisElement = getElement(i);
458             if (thisElement.isBox()) {
459                 // a KnuthBox object is not a legal line break
460                 totalWidth += thisElement.getW();
461                 previousIsBox = true;
462                 handleBox((KnuthBox) thisElement);
463             } else if (thisElement.isGlue()) {
464                 // a KnuthGlue object is a legal line break
465                 // only if the previous object is a KnuthBox
466                 // consider these glues according to the value of allowedBreaks
467                 if (previousIsBox
468                     && !(allowedBreaks == ONLY_FORCED_BREAKS)) {
469                     considerLegalBreak(thisElement, i);
470                 }
471                 totalWidth += thisElement.getW();
472                 totalStretch += thisElement.getY();
473                 totalShrink += thisElement.getZ();
474                 previousIsBox = false;
475             } else {
476                 // a KnuthPenalty is a legal line break
477                 // only if its penalty is not infinite;
478                 // consider all penalties, non-flagged penalties or non-forcing penalties
479                 // according to the value of allowedBreaks
480                 if (((KnuthPenalty) thisElement).getP() < KnuthElement.INFINITE
481                     && (!(allowedBreaks == NO_FLAGGED_PENALTIES) 
482                             || !(((KnuthPenalty) thisElement).isFlagged()))
483                     && (!(allowedBreaks == ONLY_FORCED_BREAKS) 
484                             || ((KnuthPenalty) thisElement).getP() == -KnuthElement.INFINITE)) {
485                     considerLegalBreak(thisElement, i);
486                 }
487                 previousIsBox = false;
488             }
489             if (activeNodeCount == 0) {
490                 if (!force) {
491                     log.debug("Could not find a set of breaking points " + threshold);
492                     return 0;
493                 }
494                 if (lastTooShort == null || lastForced.position == lastTooShort.position) {
495                     if (isPartOverflowRecoveryActivated()) {
496                         if (this.lastRecovered == null) {
497                             this.lastRecovered = lastTooLong;
498                             if (log.isDebugEnabled()) {
499                                 log.debug("Recovery point: " + lastRecovered);
500                             }
501                         }
502                         // content would overflow, insert empty line/page and try again
503                         KnuthNode node = createNode(
504                                 lastTooLong.previous.position, lastTooLong.previous.line + 1, 1,
505                                 0, 0, 0,
506                                 0, 0, 0,
507                                 0, 0, lastTooLong.previous);
508                         lastForced = node;
509                         node.fitRecoveryCounter = lastTooLong.previous.fitRecoveryCounter + 1;
510                         if (log.isDebugEnabled()) {
511                             log.debug("first part doesn't fit into line, recovering: " 
512                                     + node.fitRecoveryCounter);
513                         }
514                         if (node.fitRecoveryCounter > getMaxRecoveryAttempts()) {
515                             while (lastForced.fitRecoveryCounter > 0) {
516                                 lastForced = lastForced.previous;
517                                 lastDeactivated = lastForced.previous;
518                                 startLine--;
519                                 endLine--;
520                             }
521                             lastForced = this.lastRecovered;
522                             this.lastRecovered = null;
523                             startLine = lastForced.line;
524                             endLine = lastForced.line;
525                             log.debug("rolled back...");
526                         }
527                     } else {
528                         lastForced = lastTooLong;
529                     }
530                 } else {
531                     lastForced = lastTooShort;
532                     this.lastRecovered = null;
533                 }
534 
535                 if (log.isDebugEnabled()) {
536                     log.debug("Restarting at node " + lastForced);
537                 }
538                 i = restartFrom(lastForced, i);
539             }
540         }
541         finish();
542         if (log.isTraceEnabled()) {
543             log.trace("Main loop completed " + activeNodeCount);
544             log.trace("Active nodes=" + toString(""));
545         }
546 
547         // there is at least one set of breaking points
548         // select one or more active nodes, removing the others from the list
549         int line = filterActiveNodes();
550 
551         // for each active node, create a set of breaking points
552         for (int i = startLine; i < endLine; i++) {
553             for (KnuthNode node = getNode(i); node != null; node = node.next) {
554                 updateData1(node.line, node.totalDemerits);
555                 calculateBreakPoints(node, par, node.line);
556             }
557         }
558 
559         activeLines = null;
560         return line;
561     }
562 
563     /**
564      * This method tries to find the context FO for a position in a KnuthSequence.
565      * @param seq the KnuthSequence to inspect
566      * @param position the index of the position in the KnuthSequence
567      * @return the requested context FO note or null, if no context node could be determined
568      */
569     private FONode findContextFO(KnuthSequence seq, int position) {
570         ListElement el = seq.getElement(position);
571         while (el.getLayoutManager() == null && position < seq.size() - 1) {
572             position++;
573             el = seq.getElement(position);
574         }
575         Position pos = (el != null ? el.getPosition() : null);
576         LayoutManager lm = (pos != null ? pos.getLM() : null);
577         while (pos instanceof NonLeafPosition) {
578             pos = ((NonLeafPosition)pos).getPosition();
579             if (pos != null && pos.getLM() != null) {
580                 lm = pos.getLM();
581             }
582         }
583         if (lm != null) {
584             return lm.getFObj();
585         } else {
586             return null;
587         }
588     }
589 
590     /** Resets the algorithm's variables. */
591     protected void initialize() {
592         this.totalWidth = 0;
593         this.totalStretch = 0;
594         this.totalShrink = 0;
595     }
596 
597     /** Creates a new active node for a feasible breakpoint at the given position. Only
598      * called in forced mode.
599      * @param position index of the element in the Knuth sequence
600      * @param line number of the line ending at the breakpoint
601      * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3.
602      * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint
603      * @param totalStretch accumulated stretchability of the KnuthElements up to after the
604      * breakpoint
605      * @param totalShrink accumulated shrinkability of the KnuthElements up to after the
606      * breakpoint
607      * @param adjustRatio adjustment ratio if the line ends at this breakpoint
608      * @param availableShrink available stretch of the line ending at this breakpoint
609      * @param availableStretch available shrink of the line ending at this breakpoint
610      * @param difference difference between target and actual line width
611      * @param totalDemerits minimum total demerits up to the breakpoint
612      * @param previous active node for the preceding breakpoint
613      */ 
614     protected KnuthNode createNode(int position, int line, int fitness,
615                                    int totalWidth, int totalStretch, int totalShrink,
616                                    double adjustRatio, int availableShrink, int availableStretch,
617                                    int difference, double totalDemerits, KnuthNode previous) {
618         return new KnuthNode(position, line, fitness,
619                              totalWidth, totalStretch, totalShrink,
620                              adjustRatio, availableShrink, availableStretch,
621                              difference, totalDemerits, previous);
622     }
623 
624     /** Creates a new active node for a break from the best active node of the given
625      * fitness class to the element at the given position.
626      * @see #createNode(int, int, int, int, int, int, double, int, int, int, double, KnuthNode)
627      * @see BreakingAlgorithm.BestRecords
628      */
629     protected KnuthNode createNode(int position, int line, int fitness,
630                                    int totalWidth, int totalStretch, int totalShrink) {
631         return new KnuthNode(position, line, fitness,
632                              totalWidth, totalStretch, totalShrink, best.getAdjust(fitness),
633                              best.getAvailableShrink(fitness), best.getAvailableStretch(fitness),
634                              best.getDifference(fitness), best.getDemerits(fitness),
635                              best.getNode(fitness));
636     }
637 
638     /** Empty method, hook for subclasses. */
639     protected void handleBox(KnuthBox box) {
640     }
641 
642     protected int restartFrom(KnuthNode restartingNode, int currentIndex) {
643         restartingNode.totalDemerits = 0;
644         addNode(restartingNode.line, restartingNode);
645         startLine = restartingNode.line;
646         endLine = startLine + 1;
647         totalWidth = restartingNode.totalWidth;
648         totalStretch = restartingNode.totalStretch;
649         totalShrink = restartingNode.totalShrink;
650         lastTooShort = null;
651         lastTooLong = null;
652         // the width, stretch and shrink already include the width,
653         // stretch and shrink of the suppressed glues;
654         // advance in the sequence in order to avoid taking into account
655         // these elements twice
656         int restartingIndex = restartingNode.position;
657         while (restartingIndex + 1 < par.size()
658                && !(getElement(restartingIndex + 1).isBox())) {
659             restartingIndex++;
660         }
661         return restartingIndex;
662     }
663 
664     /** Determines if the given breakpoint is a feasible breakpoint. That is, if a decent
665      * line may be built between one of the currently active nodes and this breakpoint.
666      * @param element the paragraph's element to consider
667      * @param elementIdx the element's index inside the paragraph
668      */
669     protected void considerLegalBreak(KnuthElement element, int elementIdx) {
670 
671         if (log.isTraceEnabled()) {
672             log.trace("considerLegalBreak() at " + elementIdx 
673                     + " (" + totalWidth + "+" + totalStretch + "-" + totalShrink 
674                     + "), parts/lines: " + startLine + "-" + endLine);
675             log.trace("\tCurrent active node list: " + activeNodeCount + " " + this.toString("\t"));
676         }
677 
678         lastDeactivated = null;
679         lastTooLong = null;
680         for (int line = startLine; line < endLine; line++) {
681             for (KnuthNode node = getNode(line); node != null; node = node.next) {
682                 if (node.position == elementIdx) {
683                     continue;
684                 }
685                 int difference = computeDifference(node, element, elementIdx);
686                 double r = computeAdjustmentRatio(node, difference);
687                 int availableShrink = totalShrink - node.totalShrink;
688                 int availableStretch = totalStretch - node.totalStretch;
689                 if (log.isTraceEnabled()) {
690                     log.trace("\tr=" + r + " difference=" + difference);
691                     log.trace("\tline=" + line);
692                 }
693 
694                 // The line would be too long.
695                 if (r < -1 || element.isForcedBreak()) {
696                     // Deactivate node.
697                     if (log.isTraceEnabled()) {
698                         log.trace("Removing " + node);
699                     }
700                     removeNode(line, node);
701                     lastDeactivated = compareNodes(lastDeactivated, node);
702                 }
703     
704                 // The line is within the available shrink and the threshold.
705                 if (r >= -1 && r <= threshold) {
706                     int fitnessClass = computeFitness(r);
707                     double demerits = computeDemerits(node, element, fitnessClass, r);
708     
709                     if (log.isTraceEnabled()) {
710                         log.trace("\tDemerits=" + demerits);
711                         log.trace("\tFitness class=" + fitnessClass);
712                     }
713     
714                     if (demerits < best.getDemerits(fitnessClass)) {
715                         // updates best demerits data
716                         best.addRecord(demerits, node, r, availableShrink, availableStretch,
717                                        difference, fitnessClass);
718                         lastTooShort = null;
719                     }
720                 }
721                 
722                 // The line is way too short, but we are in forcing mode, so a node is
723                 // calculated and stored in lastValidNode.
724                 if (force && (r <= -1 || r > threshold)) {
725                     int fitnessClass = computeFitness(r);
726                     double demerits = computeDemerits(node, element, fitnessClass, r);
727                     int newWidth = totalWidth;
728                     int newStretch = totalStretch;
729                     int newShrink = totalShrink;
730 
731                     // add the width, stretch and shrink of glue elements after 
732                     // the break
733                     // this does not affect the dimension of the line / page, only
734                     // the values stored in the node; these would be as if the break
735                     // was just before the next box element, thus ignoring glues and
736                     // penalties between the "real" break and the following box
737                     for (int i = elementIdx; i < par.size(); i++) {
738                         KnuthElement tempElement = getElement(i);
739                         if (tempElement.isBox()) {
740                             break;
741                         } else if (tempElement.isGlue()) {
742                             newWidth += tempElement.getW();
743                             newStretch += tempElement.getY();
744                             newShrink += tempElement.getZ();
745                         } else if (tempElement.isForcedBreak() && i != elementIdx) {
746                             break;
747                         }
748                     }
749 
750                     if (r <= -1) {
751                         if (lastTooLong == null || demerits < lastTooLong.totalDemerits) {
752                             lastTooLong = createNode(elementIdx, line + 1, fitnessClass,
753                                     newWidth, newStretch, newShrink,
754                                     r, availableShrink, availableStretch,
755                                     difference, demerits, node);
756                             if (log.isTraceEnabled()) {
757                                 log.trace("Picking tooLong " + lastTooLong);
758                             }
759                         }
760                     } else {
761                         if (lastTooShort == null || demerits <= lastTooShort.totalDemerits) {
762                             if (considerTooShort) {
763                                 //consider possibilities which are too short
764                                 best.addRecord(demerits, node, r, 
765                                         availableShrink, availableStretch,
766                                         difference, fitnessClass);
767                             }
768                             lastTooShort = createNode(elementIdx, line + 1, fitnessClass,
769                                     newWidth, newStretch, newShrink,
770                                     r, availableShrink, availableStretch,
771                                     difference, demerits, node);
772                             if (log.isTraceEnabled()) {
773                                 log.trace("Picking tooShort " + lastTooShort);
774                             }
775                         }
776                     }
777                 }
778             }
779             addBreaks(line, elementIdx);
780         }
781     }
782 
783     /**
784      * Adds new active nodes for breaks at the given element.
785      * @param line number of the previous line; this element will end line number (line+1)
786      * @param elementIdx the element's index
787      */
788     private void addBreaks(int line, int elementIdx) {
789         if (!best.hasRecords()) {
790             return;
791         }
792 
793         int newWidth = totalWidth;
794         int newStretch = totalStretch;
795         int newShrink = totalShrink;
796 
797         // add the width, stretch and shrink of glue elements after 
798         // the break
799         // this does not affect the dimension of the line / page, only
800         // the values stored in the node; these would be as if the break
801         // was just before the next box element, thus ignoring glues and
802         // penalties between the "real" break and the following box
803         for (int i = elementIdx; i < par.size(); i++) {
804             KnuthElement tempElement = getElement(i);
805             if (tempElement.isBox()) {
806                 break;
807             } else if (tempElement.isGlue()) {
808                 newWidth += tempElement.getW();
809                 newStretch += tempElement.getY();
810                 newShrink += tempElement.getZ();
811             } else if (tempElement.isForcedBreak() && i != elementIdx) {
812                 break;
813             }
814         }
815 
816         // add nodes to the active nodes list
817         double minimumDemerits = best.getMinDemerits() + incompatibleFitnessDemerit;
818         for (int i = 0; i <= 3; i++) {
819             if (best.notInfiniteDemerits(i) && best.getDemerits(i) <= minimumDemerits) {
820                 // the nodes in activeList must be ordered
821                 // by line number and position;
822                 if (log.isTraceEnabled()) {
823                     log.trace("\tInsert new break in list of " + activeNodeCount 
824                             + " from fitness class " + i);
825                 }
826                 KnuthNode newNode = createNode(elementIdx, line + 1, i,
827                                                newWidth, newStretch, newShrink);
828                 addNode(line + 1, newNode);
829             }
830         }
831         best.reset();
832     }
833 
834     /**
835      * Return the difference between the natural width of a line that would be made
836      * between the given active node and the given element, and the available width of the
837      * real line.
838      * @param activeNode node for the previous breakpoint
839      * @param element currently considered breakpoint
840      * @return The difference in width. Positive numbers mean extra space in the line,
841      * negative number that the line overflows. 
842      */
843     protected int computeDifference(KnuthNode activeNode, KnuthElement element,
844                                     int elementIndex) {
845         // compute the adjustment ratio
846         int actualWidth = totalWidth - activeNode.totalWidth;
847         if (element.isPenalty()) {
848             actualWidth += element.getW();
849         }
850         return getLineWidth() - actualWidth;
851     }
852 
853     /**
854      * Return the adjust ration needed to make up for the difference. A ration of 
855      * <ul>
856      *    <li>0 means that the break has the exact right width</li>
857      *    <li>&gt;= -1 &amp;&amp; &lt; 0  means that the break is wider than the line, 
858      *        but within the minimim values of the glues.</li> 
859      *    <li>&gt;0 &amp;&amp; &lt; 1 means that the break is smaller than the line width, 
860      *        but within the maximum values of the glues.</li>
861      *    <li>&gt; 1 means that the break is too small to make up for the glues.</li> 
862      * </ul>
863      * @param activeNode
864      * @param difference
865      * @return The ration.
866      */
867     protected double computeAdjustmentRatio(KnuthNode activeNode, int difference) {
868         // compute the adjustment ratio
869         if (difference > 0) {
870             int maxAdjustment = totalStretch - activeNode.totalStretch;
871             if (maxAdjustment > 0) {
872                 return (double) difference / maxAdjustment;
873             } else {
874                 return INFINITE_RATIO;
875             }
876         } else if (difference < 0) {
877             int maxAdjustment = totalShrink - activeNode.totalShrink;
878             if (maxAdjustment > 0) {
879                 return (double) difference / maxAdjustment;
880             } else {
881                 return -INFINITE_RATIO;
882             }
883         } else {
884             return 0;
885         }
886     }
887     
888     /**
889      * Figure out the fitness class of this line (tight, loose,
890      * very tight or very loose).
891      * See the section on "More Bells and Whistles" in Knuth's 
892      * "Breaking Paragraphs Into Lines".
893      * @param r
894      * @return the fitness class
895      */
896     private int computeFitness(double r) {
897         if (r < -0.5) {
898             return 0;
899         } else if (r <= 0.5) {
900             return 1;
901         } else if (r <= 1) {
902             return 2;
903         } else {
904             return 3;
905         }
906     }
907 
908     /**
909      * Computes the demerits of the current breaking (that is, up to the given element),
910      * if the next-to-last chosen breakpoint is the given active node. This adds to the
911      * total demerits of the given active node, the demerits of a line starting at this
912      * node and ending at the given element.
913      * @param activeNode considered preceding line break
914      * @param element considered current line break
915      * @param fitnessClass fitness of the current line 
916      * @param r adjustment ratio for the current line
917      * @return the demerit of the current line
918      */
919     protected double computeDemerits(KnuthNode activeNode, KnuthElement element, 
920                                   int fitnessClass, double r) {
921         double demerits = 0;
922         // compute demerits
923         double f = Math.abs(r);
924         f = 1 + 100 * f * f * f;
925         if (element.isPenalty() && element.getP() >= 0) {
926             f += element.getP();
927             demerits = f * f;
928         } else if (element.isPenalty() && !element.isForcedBreak()) {
929             double penalty = element.getP();
930             demerits = f * f - penalty * penalty;
931         } else {
932             demerits = f * f;
933         }
934     
935         if (element.isPenalty() && ((KnuthPenalty) element).isFlagged()
936             && getElement(activeNode.position).isPenalty()
937             && ((KnuthPenalty) getElement(activeNode.position)).isFlagged()) {
938             // add demerit for consecutive breaks at flagged penalties
939             demerits += repeatedFlaggedDemerit;
940             // there are at least two consecutive lines ending with a flagged penalty;
941             // check if the previous line end with a flagged penalty too, 
942             // and if this situation is allowed
943             int flaggedPenaltiesCount = 2;
944             for (KnuthNode prevNode = activeNode.previous;
945                  prevNode != null && flaggedPenaltiesCount <= maxFlaggedPenaltiesCount;
946                  prevNode = prevNode.previous) {
947                 KnuthElement prevElement = getElement(prevNode.position);
948                 if (prevElement.isPenalty()
949                     && ((KnuthPenalty) prevElement).isFlagged()) {
950                     // the previous line ends with a flagged penalty too
951                     flaggedPenaltiesCount++;
952                 } else {
953                     // the previous line does not end with a flagged penalty,
954                     // exit the loop
955                     break;
956                 }
957             }
958             if (maxFlaggedPenaltiesCount >= 1
959                 && flaggedPenaltiesCount > maxFlaggedPenaltiesCount) {
960                 // add infinite demerits, so this break will not be chosen
961                 // unless there isn't any alternative break
962                 demerits += BestRecords.INFINITE_DEMERITS;
963             }
964         }
965         if (Math.abs(fitnessClass - activeNode.fitness) > 1) {
966             // add demerit for consecutive breaks
967             // with very different fitness classes
968             demerits += incompatibleFitnessDemerit;
969         }
970         demerits += activeNode.totalDemerits;
971         return demerits;
972     }
973 
974     protected void finish() {
975     }
976 
977     /**
978      * Return the element at index idx in the paragraph.
979      * @param idx index of the element.
980      * @return the element at index idx in the paragraph.
981      */
982     protected KnuthElement getElement(int idx) {
983         return (KnuthElement) par.get(idx);
984     }
985 
986     /**
987      * Compare two KnuthNodes and return the node with the least demerit.
988      * @param node1 The first knuth node.
989      * @param node2 The other knuth node.
990      * @return the node with the least demerit.
991      */
992     protected KnuthNode compareNodes(KnuthNode node1, KnuthNode node2) {
993         if (node1 == null || node2.position > node1.position) {
994             return node2;
995         }
996         if (node2.position == node1.position) {
997             if (node2.totalDemerits < node1.totalDemerits) {
998                 return node2;
999             }
1000        }
1001        return node1;
1002    }
1003
1004    /**
1005     * Add a node at the end of the given line's existing active nodes.
1006     * If this is the first node in the line, adjust endLine accordingly.
1007     * @param line number of the line ending at the node's corresponding breakpoint
1008     * @param node the active node to add
1009     */
1010    protected void addNode(int line, KnuthNode node) {
1011        int headIdx = line * 2;
1012        if (headIdx >= activeLines.length) {
1013            KnuthNode[] oldList = activeLines;
1014            activeLines = new KnuthNode[headIdx + headIdx];
1015            System.arraycopy(oldList, 0, activeLines, 0, oldList.length);
1016        }
1017        node.next = null;
1018        if (activeLines[headIdx + 1] != null) {
1019            activeLines[headIdx + 1].next = node;
1020        } else {
1021            activeLines[headIdx] = node;
1022            endLine = line + 1;
1023        }
1024        activeLines[headIdx + 1] = node;
1025        activeNodeCount++;
1026    }
1027
1028    /**
1029     * Remove the given active node registered for the given line. If there are no more active nodes
1030     * for this line, adjust the startLine accordingly.
1031     * @param line number of the line ending at the node's corresponding breakpoint
1032     * @param node the node to deactivate
1033     */
1034    protected void removeNode(int line, KnuthNode node) {
1035        int headIdx = line * 2;
1036        KnuthNode n = getNode(line);
1037        if (n != node) {
1038            // nodes could be rightly deactivated in a different order
1039            KnuthNode prevNode = null;
1040            while (n != node) {
1041                prevNode = n;
1042                n = n.next;
1043            }
1044            prevNode.next = n.next;
1045            if (prevNode.next == null) {
1046                activeLines[headIdx + 1] = prevNode;
1047            }
1048        } else {
1049            activeLines[headIdx] = node.next;
1050            if (node.next == null) {
1051                activeLines[headIdx + 1] = null;
1052            }
1053            while (startLine < endLine && getNode(startLine) == null) {
1054                startLine++;
1055            }
1056        }
1057        activeNodeCount--;
1058    }
1059
1060    /**
1061     * Returns the first active node for the given line.
1062     * @param line the line/part number
1063     * @return the requested active node
1064     */
1065    protected KnuthNode getNode(int line) {
1066        return activeLines[line * 2];
1067    }
1068
1069    /**
1070     * Returns the line/part width of a given line/part.
1071     * @param line the line/part number
1072     * @return the width/length in millipoints
1073     */
1074    protected int getLineWidth(int line) {
1075        if (this.lineWidth < 0) {
1076            throw new IllegalStateException  ("lineWidth must be set" 
1077                    + (this.lineWidth != 0 ? " and positive, but it is: " + this.lineWidth : ""));
1078        } else {
1079            return this.lineWidth;
1080        }
1081    }
1082    
1083    /** @return the constant line/part width or -1 if there is no such value */
1084    protected int getLineWidth() {
1085        return this.lineWidth;
1086    }
1087    
1088    /**
1089     * Creates a string representation of the active nodes. Used for debugging.
1090     * @param prepend a string to prepend on each entry
1091     * @return the requested string
1092     */
1093    public String   toString(String   prepend) {
1094        StringBuffer   sb = new StringBuffer  ();
1095        sb.append("[\n");
1096        for (int i = startLine; i < endLine; i++) {
1097            for (KnuthNode node = getNode(i); node != null; node = node.next) {
1098                sb.append(prepend + "\t" + node + ",\n");
1099            }
1100        }
1101        sb.append(prepend + "]");
1102        return sb.toString();
1103    }
1104
1105    protected abstract int filterActiveNodes();
1106
1107    /**
1108     * Determines the set of optimal breakpoints corresponding to the given active node.
1109     * @param node the active node
1110     * @param par the corresponding paragraph
1111     * @param total the number of lines into which the paragraph will be broken
1112     */
1113    private void calculateBreakPoints(KnuthNode node, KnuthSequence par,
1114                                      int total) {
1115        KnuthNode bestActiveNode = node;
1116        // use bestActiveNode to determine the optimum breakpoints
1117        for (int i = node.line; i > 0; i--) {
1118            updateData2(bestActiveNode, par, total);
1119            bestActiveNode = bestActiveNode.previous;
1120        }
1121    }
1122    
1123    /** @return the alignment for normal lines/parts */
1124    public int getAlignment() {
1125        return this.alignment;
1126    }
1127
1128    /** @return the alignment for the last line/part */
1129    public int getAlignmentLast() {
1130        return this.alignmentLast;
1131    }
1132
1133}
1134
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags