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 1805173 2017-08-16 10:50:04Z ssteiner $ */ 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.Constants; 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 * {@link 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 < 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 final 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 /** Holder for symbolic literals for the fitness classes */ 61 static final class FitnessClasses { 62 FitnessClasses()63 private FitnessClasses() { 64 } 65 66 static final int VERY_TIGHT = 0; 67 static final int TIGHT = 1; 68 static final int LOOSE = 2; 69 static final int VERY_LOOSE = 3; 70 71 static final String[] NAMES = { 72 "VERY TIGHT", "TIGHT", "LOOSE", "VERY LOOSE" 73 }; 74 75 /** 76 * Figure out the fitness class of this line (tight, loose, 77 * very tight or very loose). 78 * See the section on "More Bells and Whistles" in Knuth's 79 * "Breaking Paragraphs Into Lines". 80 * 81 * @param adjustRatio the adjustment ratio 82 * @return the fitness class 83 */ computeFitness(double adjustRatio)84 static int computeFitness(double adjustRatio) { 85 if (adjustRatio < -0.5) { 86 return FitnessClasses.VERY_TIGHT; 87 } else if (adjustRatio <= 0.5) { 88 return FitnessClasses.TIGHT; 89 } else if (adjustRatio <= 1.0) { 90 return FitnessClasses.LOOSE; 91 } else { 92 return FitnessClasses.VERY_LOOSE; 93 } 94 } 95 } 96 97 // parameters of Knuth's algorithm: 98 /** Demerit for consecutive lines ending at flagged penalties. */ 99 protected int repeatedFlaggedDemerit = KnuthPenalty.FLAGGED_PENALTY; 100 /** Demerit for consecutive lines belonging to incompatible fitness classes . */ 101 protected int incompatibleFitnessDemerit = KnuthPenalty.FLAGGED_PENALTY; 102 /** Maximum number of consecutive lines ending with a flagged penalty. 103 * Only a value >= 1 is a significant limit. 104 */ 105 protected int maxFlaggedPenaltiesCount; 106 107 /** 108 * The threshold for considering breaks to be acceptable. The adjustment ratio must be 109 * inferior to this threshold. 110 */ 111 private double threshold; 112 113 /** 114 * The paragraph of KnuthElements. 115 */ 116 protected KnuthSequence par; 117 118 /** 119 * The width of a line (or height of a column in page-breaking mode). 120 * -1 indicates that the line widths are different for each line. 121 */ 122 protected int lineWidth = -1; 123 /** Force the algorithm to find a set of breakpoints, even if no feasible breakpoints 124 * exist. 125 */ 126 private boolean force; 127 /** If set to true, doesn't ignore break possibilities which are definitely too short. */ 128 protected boolean considerTooShort; 129 130 /** When in forced mode, the best node leading to a too long line. The line will be 131 * too long anyway, but this one will lead to a paragraph with fewest demerits. 132 */ 133 private KnuthNode lastTooLong; 134 /** When in forced mode, the best node leading to a too short line. The line will be 135 * too short anyway, but this one will lead to a paragraph with fewest demerits. 136 */ 137 private KnuthNode lastTooShort; 138 /** The node to be reactivated if no set of feasible breakpoints can be found for this 139 * paragraph. 140 */ 141 private KnuthNode lastDeactivated; 142 143 /** Alignment of the paragraph/page. One of EN_START, EN_JUSTIFY, etc. */ 144 protected int alignment; 145 /** Alignment of the paragraph's last line. */ 146 protected int alignmentLast; 147 /** Used to handle the text-indent property (indent the first line of a paragraph). */ 148 protected boolean indentFirstPart; 149 150 /** 151 * The set of active nodes in ascending line order. For each line l, activeLines[2l] contains a 152 * link to l's first active node, and activeLines[2l+1] a link to l's last active node. The 153 * line number l corresponds to the number of the line ending at the node's breakpoint. 154 */ 155 protected KnuthNode[] activeLines; 156 157 /** 158 * The number of active nodes. 159 */ 160 protected int activeNodeCount; 161 162 /** 163 * The lowest available line in the set of active nodes. 164 */ 165 protected int startLine; 166 167 /** 168 * The highest + 1 available line in the set of active nodes. 169 */ 170 protected int endLine; 171 172 /** 173 * The total width of all elements handled so far. 174 */ 175 protected int totalWidth; 176 177 /** 178 * The total stretch of all elements handled so far. 179 */ 180 protected int totalStretch; 181 182 /** 183 * The total shrink of all elements handled so far. 184 */ 185 protected int totalShrink; 186 187 /** 188 * Best records. 189 */ 190 protected BestRecords best; 191 192 private boolean partOverflowRecoveryActivated = true; 193 private KnuthNode lastRecovered; 194 195 /** 196 * Create a new instance. 197 * 198 * @param align alignment of the paragraph/page. One of {@link Constants#EN_START}, 199 * {@link Constants#EN_JUSTIFY}, {@link Constants#EN_CENTER}, 200 * {@link Constants#EN_END}. 201 * For pages, {@link Constants#EN_BEFORE} and {@link Constants#EN_AFTER} 202 * are mapped to the corresponding inline properties, 203 * {@link Constants#EN_START} and {@link Constants#EN_END}. 204 * @param alignLast alignment of the paragraph's last line 205 * @param first for the text-indent property ({@code true} if the first line 206 * of a paragraph should be indented) 207 * @param partOverflowRecovery {@code true} if too long elements should be moved to 208 * the next line/part 209 * @param maxFlagCount maximum allowed number of consecutive lines ending at a flagged penalty 210 * item 211 */ BreakingAlgorithm(int align, int alignLast, boolean first, boolean partOverflowRecovery, int maxFlagCount)212 public BreakingAlgorithm(int align, int alignLast, 213 boolean first, boolean partOverflowRecovery, 214 int maxFlagCount) { 215 this.alignment = align; 216 this.alignmentLast = alignLast; 217 this.indentFirstPart = first; 218 this.partOverflowRecoveryActivated = partOverflowRecovery; 219 this.best = new BestRecords(); 220 this.maxFlaggedPenaltiesCount = maxFlagCount; 221 } 222 223 224 /** 225 * Class recording all the informations of a feasible breaking point. 226 */ 227 public class KnuthNode { 228 /** index of the breakpoint represented by this node */ 229 public final int position; 230 231 /** number of the line ending at this breakpoint */ 232 public final int line; 233 234 /** fitness class of the line ending at this breakpoint. One of 0, 1, 2, 3. */ 235 public final int fitness; 236 237 /** accumulated width of the KnuthElements up to after this breakpoint. */ 238 public final int totalWidth; 239 240 /** accumulated stretchability of the KnuthElements up to after this breakpoint. */ 241 public final int totalStretch; 242 243 /** accumulated shrinkability of the KnuthElements up to after this breakpoint. */ 244 public final int totalShrink; 245 246 /** adjustment ratio if the line ends at this breakpoint */ 247 public final double adjustRatio; 248 249 /** available stretch of the line ending at this breakpoint */ 250 public final int availableShrink; 251 252 /** available shrink of the line ending at this breakpoint */ 253 public final int availableStretch; 254 255 /** difference between target and actual line width */ 256 public final int difference; 257 258 /** minimum total demerits up to this breakpoint */ 259 public double totalDemerits; 260 261 /** best node for the preceding breakpoint */ 262 public KnuthNode previous; 263 264 /** next possible node in the same line */ 265 public KnuthNode next; 266 267 /** 268 * Holds the number of subsequent recovery attempty that are made to get content fit 269 * into a line. 270 */ 271 public int fitRecoveryCounter; 272 273 /** 274 * Construct node. 275 * @param position an integer 276 * @param line an integer 277 * @param fitness an integer 278 * @param totalWidth an integer 279 * @param totalStretch an integer 280 * @param totalShrink an integer 281 * @param adjustRatio a real number 282 * @param availableShrink an integer 283 * @param availableStretch an integer 284 * @param difference an integer 285 * @param totalDemerits a real number 286 * @param previous a node 287 */ KnuthNode(int position, int line, int fitness, int totalWidth, int totalStretch, int totalShrink, double adjustRatio, int availableShrink, int availableStretch, int difference, double totalDemerits, KnuthNode previous)288 public KnuthNode(int position, int line, int fitness, 289 int totalWidth, int totalStretch, int totalShrink, 290 double adjustRatio, int availableShrink, int availableStretch, 291 int difference, double totalDemerits, KnuthNode previous) { 292 this.position = position; 293 this.line = line; 294 this.fitness = fitness; 295 this.totalWidth = totalWidth; 296 this.totalStretch = totalStretch; 297 this.totalShrink = totalShrink; 298 this.adjustRatio = adjustRatio; 299 this.availableShrink = availableShrink; 300 this.availableStretch = availableStretch; 301 this.difference = difference; 302 this.totalDemerits = totalDemerits; 303 this.previous = previous; 304 } 305 306 /** {@inheritDoc} */ toString()307 public String toString() { 308 return "<KnuthNode at " + position + " " 309 + totalWidth + "+" + totalStretch + "-" + totalShrink 310 + " line:" + line + " prev:" + (previous != null ? previous.position : -1) 311 + " dem:" + totalDemerits 312 + " fitness:" + FitnessClasses.NAMES[fitness] + ">"; 313 } 314 } 315 316 /** Class that stores, for each fitness class, the best active node that could start 317 * a line of the corresponding fitness ending at the current element. 318 */ 319 protected class BestRecords { 320 private static final double INFINITE_DEMERITS = Double.POSITIVE_INFINITY; 321 322 private final double[] bestDemerits = new double[4]; 323 private final KnuthNode[] bestNode = new KnuthNode[4]; 324 private final double[] bestAdjust = new double[4]; 325 private final int[] bestDifference = new int[4]; 326 private final int[] bestAvailableShrink = new int[4]; 327 private final int[] bestAvailableStretch = new int[4]; 328 /** Points to the fitness class which currently leads to the best demerits. */ 329 private int bestIndex = -1; 330 331 /** default constructor */ BestRecords()332 public BestRecords() { 333 reset(); 334 } 335 336 /** Registers the new best active node for the given fitness class. 337 * @param demerits the total demerits of the new optimal set of breakpoints 338 * @param node the node starting the line ending at the current element 339 * @param adjust adjustment ratio of the current line 340 * @param availableShrink how much the current line can be shrinked 341 * @param availableStretch how much the current line can be stretched 342 * @param difference difference between the width of the considered line and the 343 * width of the "real" line 344 * @param fitness fitness class of the current line 345 */ addRecord(double demerits, KnuthNode node, double adjust, int availableShrink, int availableStretch, int difference, int fitness)346 public void addRecord(double demerits, KnuthNode node, double adjust, 347 int availableShrink, int availableStretch, 348 int difference, int fitness) { 349 if (demerits > bestDemerits[fitness]) { 350 log.error("New demerits value greater than the old one"); 351 } 352 bestDemerits[fitness] = demerits; 353 bestNode[fitness] = node; 354 bestAdjust[fitness] = adjust; 355 bestAvailableShrink[fitness] = availableShrink; 356 bestAvailableStretch[fitness] = availableStretch; 357 bestDifference[fitness] = difference; 358 if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) { 359 bestIndex = fitness; 360 } 361 } 362 363 /** @return true if has records (best index not -1) */ hasRecords()364 public boolean hasRecords() { 365 return (bestIndex != -1); 366 } 367 368 /** 369 * @param fitness fitness class (0, 1, 2 or 3, i.e. "tight" to "very loose") 370 * @return true if there is a set of feasible breakpoints registered for the 371 * given fitness. 372 */ notInfiniteDemerits(int fitness)373 public boolean notInfiniteDemerits(int fitness) { 374 return (bestDemerits[fitness] != INFINITE_DEMERITS); 375 } 376 377 /** 378 * @param fitness to use 379 * @return best demerits 380 */ getDemerits(int fitness)381 public double getDemerits(int fitness) { 382 return bestDemerits[fitness]; 383 } 384 385 /** 386 * @param fitness to use 387 * @return best node 388 */ getNode(int fitness)389 public KnuthNode getNode(int fitness) { 390 return bestNode[fitness]; 391 } 392 393 /** 394 * @param fitness to use 395 * @return adjustment 396 */ getAdjust(int fitness)397 public double getAdjust(int fitness) { 398 return bestAdjust[fitness]; 399 } 400 401 /** 402 * @param fitness to use 403 * @return available shrink 404 */ getAvailableShrink(int fitness)405 public int getAvailableShrink(int fitness) { 406 return bestAvailableShrink[fitness]; 407 } 408 409 /** 410 * @param fitness to use 411 * @return available stretch 412 */ getAvailableStretch(int fitness)413 public int getAvailableStretch(int fitness) { 414 return bestAvailableStretch[fitness]; 415 } 416 417 /** 418 * @param fitness to use 419 * @return difference 420 */ getDifference(int fitness)421 public int getDifference(int fitness) { 422 return bestDifference[fitness]; 423 } 424 425 /** @return minimum demerits */ getMinDemerits()426 public double getMinDemerits() { 427 if (bestIndex != -1) { 428 return getDemerits(bestIndex); 429 } else { 430 // anyway, this should never happen 431 return INFINITE_DEMERITS; 432 } 433 } 434 435 /** Reset when a new breakpoint is being considered. */ reset()436 public void reset() { 437 for (int i = 0; i < 4; i++) { 438 bestDemerits[i] = INFINITE_DEMERITS; 439 // there is no need to reset the other arrays 440 } 441 bestIndex = -1; 442 } 443 } 444 445 /** 446 * @return the number of times the algorithm should try to move overflowing content to the 447 * next line/page. 448 */ getMaxRecoveryAttempts()449 protected int getMaxRecoveryAttempts() { 450 return MAX_RECOVERY_ATTEMPTS; 451 } 452 453 /** 454 * Controls the behaviour of the algorithm in cases where the first element of a part 455 * overflows a line/page. 456 * @return true if the algorithm should try to send the element to the next line/page. 457 */ isPartOverflowRecoveryActivated()458 protected boolean isPartOverflowRecoveryActivated() { 459 return this.partOverflowRecoveryActivated; 460 } 461 getLastTooLong()462 protected KnuthNode getLastTooLong() { 463 return lastTooLong; 464 } 465 466 /** 467 * Empty method, hook for subclasses. Called before determining the optimal 468 * breakpoints corresponding to a given active node. 469 * @param total number of lines for the active node 470 * @param demerits total demerits of the paragraph for the active node 471 */ updateData1(int total, double demerits)472 public abstract void updateData1(int total, double demerits); 473 474 /** 475 * Empty method, hook for subclasses. Called when determining the optimal breakpoints 476 * for a given active node. 477 * @param bestActiveNode a node in the chain of best active nodes, corresponding to 478 * one of the optimal breakpoints 479 * @param sequence the corresponding paragraph 480 * @param total the number of lines into which the paragraph will be broken 481 */ updateData2(KnuthNode bestActiveNode, KnuthSequence sequence, int total)482 public abstract void updateData2(KnuthNode bestActiveNode, 483 KnuthSequence sequence, 484 int total); 485 486 /** @param lineWidth the line width */ setConstantLineWidth(int lineWidth)487 public void setConstantLineWidth(int lineWidth) { 488 this.lineWidth = lineWidth; 489 } 490 491 /** 492 * @param par the paragraph to break 493 * @param threshold upper bound of the adjustment ratio 494 * @param force {@code true} if a set of breakpoints must be found, even 495 * if there are no feasible ones 496 * @param allowedBreaks the type(s) of breaks allowed. One of {@link #ONLY_FORCED_BREAKS}, 497 * {@link #NO_FLAGGED_PENALTIES} or {@link #ALL_BREAKS}. 498 * 499 * @return the number of effective breaks 500 * @see #findBreakingPoints(KnuthSequence, int, double, boolean, int) 501 */ findBreakingPoints(KnuthSequence par, double threshold, boolean force, int allowedBreaks)502 public int findBreakingPoints(KnuthSequence par, 503 double threshold, 504 boolean force, 505 int allowedBreaks) { 506 return findBreakingPoints(par, 0, threshold, force, allowedBreaks); 507 } 508 509 /** 510 * Finds an optimal set of breakpoints for the given paragraph. 511 * 512 * @param par the paragraph to break 513 * @param startIndex index of the Knuth element at which the breaking must start 514 * @param threshold upper bound of the adjustment ratio 515 * @param force {@code true} if a set of breakpoints must be found, even 516 * if there are no feasible ones 517 * @param allowedBreaks the type(s) of breaks allowed. One of {@link #ONLY_FORCED_BREAKS}, 518 * {@link #NO_FLAGGED_PENALTIES} or {@link #ALL_BREAKS}. 519 * 520 * @return the number of effective breaks 521 */ findBreakingPoints(KnuthSequence par, int startIndex, double threshold, boolean force, int allowedBreaks)522 public int findBreakingPoints(KnuthSequence par, int startIndex, 523 double threshold, boolean force, 524 int allowedBreaks) { 525 this.par = par; 526 this.threshold = threshold; 527 this.force = force; 528 529 // initialize the algorithm 530 initialize(); 531 532 // previous element in the paragraph is a KnuthBox? 533 boolean previousIsBox = false; 534 535 // index of the first KnuthBox in the sequence, in case of non-centered 536 // alignment. For centered alignment, we need to take into account preceding 537 // penalties+glues used for the filler spaces 538 int previousPosition = startIndex; 539 if (alignment != Constants.EN_CENTER) { 540 int firstBoxIndex = par.getFirstBoxIndex(startIndex); 541 previousPosition = (firstBoxIndex >= par.size()) ? startIndex : firstBoxIndex - 1; 542 } 543 previousPosition = (previousPosition < 0) ? 0 : previousPosition; 544 545 // create an active node representing the starting point 546 addNode(0, createNode(previousPosition, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, null)); 547 KnuthNode lastForced = getNode(0); 548 549 if (log.isTraceEnabled()) { 550 log.trace("Looping over " + (par.size() - startIndex) + " elements"); 551 log.trace(par); 552 } 553 554 // main loop 555 for (int elementIndex = startIndex; elementIndex < par.size(); elementIndex++) { 556 557 previousIsBox = handleElementAt( 558 elementIndex, previousIsBox, allowedBreaks).isBox(); 559 560 if (activeNodeCount == 0) { 561 if (handlingFloat()) { 562 return handleFloat(); 563 } 564 if (getIPDdifference() != 0) { 565 return handleIpdChange(); 566 } 567 if (!force) { 568 log.debug("Could not find a set of breaking points " + threshold); 569 return 0; 570 } 571 572 // lastDeactivated was a "good" break, while lastTooShort and lastTooLong 573 // were "bad" breaks since the beginning; 574 // if it is not the node we just restarted from, lastDeactivated can 575 // replace either lastTooShort or lastTooLong 576 if (lastDeactivated != null 577 && lastDeactivated != lastForced) { 578 replaceLastDeactivated(); 579 } 580 581 if (lastTooShort == null 582 || lastForced.position == lastTooShort.position) { 583 lastForced = recoverFromOverflow(); 584 } else { 585 lastForced = lastTooShort; 586 this.lastRecovered = null; 587 } 588 elementIndex = restartFrom(lastForced, elementIndex); 589 } 590 591 } 592 593 finish(); 594 595 // there is at least one set of breaking points 596 // select one or more active nodes, removing the others from the list 597 int line = filterActiveNodes(); 598 599 // for each active node, create a set of breaking points 600 for (int i = startLine; i < endLine; i++) { 601 for (KnuthNode node = getNode(i); node != null; node = node.next) { 602 updateData1(node.line, node.totalDemerits); 603 calculateBreakPoints(node, par, node.line); 604 } 605 } 606 607 activeLines = null; 608 return line; 609 } 610 611 /** 612 * obtain ipd difference 613 * @return an integer 614 */ getIPDdifference()615 protected int getIPDdifference() { 616 return 0; 617 } 618 619 /** 620 * handle ipd change 621 * @return an integer 622 */ handleIpdChange()623 protected int handleIpdChange() { 624 throw new IllegalStateException(); 625 } 626 627 /** 628 * Recover from a {@link KnuthNode} leading to a line that is too long. 629 * The default implementation creates a new node corresponding to a break 630 * point after the previous node that led to a line that was too short. 631 * 632 * @param lastTooLong the node that leads to a "too long" line 633 * @return node corresponding to a breakpoint after the previous "too short" line 634 */ recoverFromTooLong(KnuthNode lastTooLong)635 protected KnuthNode recoverFromTooLong(KnuthNode lastTooLong) { 636 if (log.isDebugEnabled()) { 637 log.debug("Recovering from too long: " + lastTooLong); 638 } 639 640 // if lastTooLong would be the very first break in the blockList, and 641 // the first element in the paragraph is not a penalty, add an auxiliary 642 // penalty now to make it possible to create a genuine 'empty' node that 643 // represents a break before the first box/glue 644 if (lastTooLong.previous.previous == null) { 645 ListElement el = (ListElement)this.par.get(0); 646 if (!el.isPenalty()) { 647 this.par.add(0, KnuthPenalty.DUMMY_ZERO_PENALTY); 648 } 649 } 650 651 // content would overflow, insert empty line/page and try again 652 return createNode( 653 lastTooLong.previous.position, lastTooLong.previous.line + 1, 1, 654 0, 0, 0, 655 0, 0, 0, 656 0, 0, lastTooLong.previous); 657 } 658 659 /** Initializes the algorithm's variables. */ initialize()660 protected void initialize() { 661 this.totalWidth = 0; 662 this.totalStretch = 0; 663 this.totalShrink = 0; 664 this.lastTooShort = null; 665 this.lastTooLong = null; 666 this.startLine = 0; 667 this.endLine = 0; 668 this.activeLines = new KnuthNode[20]; 669 } 670 671 /** 672 * Creates a new active node for a feasible breakpoint at the given position. Only 673 * called in forced mode. 674 * 675 * @param position index of the element in the Knuth sequence 676 * @param line number of the line ending at the breakpoint 677 * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3. 678 * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint 679 * @param totalStretch accumulated stretchability of the KnuthElements up to after the 680 * breakpoint 681 * @param totalShrink accumulated shrinkability of the KnuthElements up to after the 682 * breakpoint 683 * @param adjustRatio adjustment ratio if the line ends at this breakpoint 684 * @param availableShrink available stretch of the line ending at this breakpoint 685 * @param availableStretch available shrink of the line ending at this breakpoint 686 * @param difference difference between target and actual line width 687 * @param totalDemerits minimum total demerits up to the breakpoint 688 * @param previous active node for the preceding breakpoint 689 * @return a new node 690 */ createNode(int position, int line, int fitness, int totalWidth, int totalStretch, int totalShrink, double adjustRatio, int availableShrink, int availableStretch, int difference, double totalDemerits, KnuthNode previous)691 protected KnuthNode createNode(int position, int line, int fitness, 692 int totalWidth, int totalStretch, int totalShrink, 693 double adjustRatio, int availableShrink, int availableStretch, 694 int difference, double totalDemerits, KnuthNode previous) { 695 return new KnuthNode(position, line, fitness, 696 totalWidth, totalStretch, totalShrink, 697 adjustRatio, availableShrink, availableStretch, 698 difference, totalDemerits, previous); 699 } 700 701 /** Creates a new active node for a break from the best active node of the given 702 * fitness class to the element at the given position. 703 * @param position index of the element in the Knuth sequence 704 * @param line number of the line ending at the breakpoint 705 * @param fitness fitness class of the line ending at the breakpoint. One of 0, 1, 2, 3. 706 * @param totalWidth accumulated width of the KnuthElements up to after the breakpoint 707 * @param totalStretch accumulated stretchability of the KnuthElements up to after the 708 * breakpoint 709 * @param totalShrink accumulated shrinkability of the KnuthElements up to after the 710 * breakpoint 711 * @return a new node 712 * @see #createNode(int, int, int, int, int, int, double, int, int, int, double, 713 * org.apache.fop.layoutmgr.BreakingAlgorithm.KnuthNode) 714 * @see BreakingAlgorithm.BestRecords 715 */ createNode(int position, int line, int fitness, int totalWidth, int totalStretch, int totalShrink)716 protected KnuthNode createNode(int position, int line, int fitness, 717 int totalWidth, int totalStretch, int totalShrink) { 718 return new KnuthNode(position, line, fitness, 719 totalWidth, totalStretch, totalShrink, best.getAdjust(fitness), 720 best.getAvailableShrink(fitness), best.getAvailableStretch(fitness), 721 best.getDifference(fitness), best.getDemerits(fitness), 722 best.getNode(fitness)); 723 } 724 725 /** 726 * Return the last node that yielded a too short line. 727 * @return the node corresponding to the last too short line 728 */ getLastTooShort()729 protected final KnuthNode getLastTooShort() { 730 return this.lastTooShort; 731 } 732 733 /** 734 * Generic handler for a {@link KnuthElement} at the given {@code position}, 735 * taking into account whether the preceding element was a box, and which 736 * type(s) of breaks are allowed. 737 * Non-overridable. This method simply serves to route the call to one of the 738 * more specific handlers ({@link #handleBox(KnuthBox)}, 739 * {@link #handleGlueAt(KnuthGlue,int,boolean,int)} or 740 * {@link #handlePenaltyAt(KnuthPenalty,int,int)}. The specialized handlers 741 * can be overridden by subclasses to add to or modify the default behavior 742 * for the different types of elements. 743 * 744 * @param position the position index of the element in the paragraph 745 * @param previousIsBox {@code true} if the previous element is a box 746 * @param allowedBreaks the type(s) of breaks allowed; should be one 747 * of {@link #ALL_BREAKS}, {@link #NO_FLAGGED_PENALTIES} 748 * or {@link #ONLY_FORCED_BREAKS} 749 * @return the handled element 750 */ handleElementAt(int position, boolean previousIsBox, int allowedBreaks)751 protected final KnuthElement handleElementAt(int position, 752 boolean previousIsBox, 753 int allowedBreaks) { 754 KnuthElement element = getElement(position); 755 if (element.isBox()) { 756 handleBox((KnuthBox) element); 757 } else if (element.isGlue()) { 758 handleGlueAt((KnuthGlue) element, position, previousIsBox, allowedBreaks); 759 } else if (element.isPenalty()) { 760 handlePenaltyAt((KnuthPenalty) element, position, allowedBreaks); 761 } else { 762 throw new IllegalArgumentException( 763 "Unknown KnuthElement type: expecting KnuthBox, KnuthGlue or KnuthPenalty"); 764 } 765 return element; 766 } 767 768 /** 769 * Handle a {@link KnuthBox}. 770 * <br><em>Note: default implementation just adds the box's width 771 * to the total content width. Subclasses that do not keep track 772 * of this themselves, but override this method, should remember 773 * to call {@code super.handleBox(box)} to avoid unwanted side-effects.</em> 774 * 775 * @param box the {@link KnuthBox} to handle 776 */ handleBox(KnuthBox box)777 protected void handleBox(KnuthBox box) { 778 // a KnuthBox object is not a legal line break, 779 // just add the width to the total 780 totalWidth += box.getWidth(); 781 } 782 783 /** 784 * Handle a {@link KnuthGlue} at the given position, 785 * taking into account the additional parameters. 786 * 787 * @param glue the {@link KnuthGlue} to handle 788 * @param position the position of the glue in the list 789 * @param previousIsBox {@code true} if the preceding element is a box 790 * @param allowedBreaks the type of breaks that are allowed 791 */ handleGlueAt(KnuthGlue glue, int position, boolean previousIsBox, int allowedBreaks)792 protected void handleGlueAt(KnuthGlue glue, int position, 793 boolean previousIsBox, int allowedBreaks) { 794 // a KnuthGlue object is a legal line break 795 // only if the previous object is a KnuthBox 796 // consider these glues according to the value of allowedBreaks 797 if (previousIsBox 798 && !(allowedBreaks == ONLY_FORCED_BREAKS)) { 799 considerLegalBreak(glue, position); 800 } 801 totalWidth += glue.getWidth(); 802 totalStretch += glue.getStretch(); 803 totalShrink += glue.getShrink(); 804 } 805 806 /** 807 * Handle a {@link KnuthPenalty} at the given position, 808 * taking into account the type of breaks allowed. 809 * 810 * @param penalty the {@link KnuthPenalty} to handle 811 * @param position the position of the penalty in the list 812 * @param allowedBreaks the type of breaks that are allowed 813 */ handlePenaltyAt(KnuthPenalty penalty, int position, int allowedBreaks)814 protected void handlePenaltyAt(KnuthPenalty penalty, int position, 815 int allowedBreaks) { 816 // a KnuthPenalty is a legal line break 817 // only if its penalty is not infinite; 818 // consider all penalties, non-flagged penalties or non-forcing penalties 819 // according to the value of allowedBreaks 820 if (((penalty.getPenalty() < KnuthElement.INFINITE) 821 && (!(allowedBreaks == NO_FLAGGED_PENALTIES) || !penalty.isPenaltyFlagged()) 822 && (!(allowedBreaks == ONLY_FORCED_BREAKS) 823 || penalty.isForcedBreak()))) { 824 considerLegalBreak(penalty, position); 825 } 826 } 827 828 /** 829 * Replace the last too-long or too-short node by the last deactivated 830 * node, if applicable. 831 */ replaceLastDeactivated()832 protected final void replaceLastDeactivated() { 833 if (lastDeactivated.adjustRatio > 0) { 834 //last deactivated was too short 835 lastTooShort = lastDeactivated; 836 } else { 837 //last deactivated was too long or exactly the right width 838 lastTooLong = lastDeactivated; 839 } 840 } 841 842 /** 843 * Recover from an overflow condition. 844 * 845 * @return the new {@code lastForced} node 846 */ recoverFromOverflow()847 protected KnuthNode recoverFromOverflow() { 848 KnuthNode lastForced; 849 if (isPartOverflowRecoveryActivated()) { 850 if (lastRecovered == null) { 851 lastRecovered = lastTooLong; 852 if (log.isDebugEnabled()) { 853 log.debug("Recovery point: " + lastRecovered); 854 } 855 } 856 KnuthNode node = recoverFromTooLong(lastTooLong); 857 lastForced = node; 858 node.fitRecoveryCounter = lastTooLong.previous.fitRecoveryCounter + 1; 859 if (log.isDebugEnabled()) { 860 log.debug("first part doesn't fit into line, recovering: " 861 + node.fitRecoveryCounter); 862 } 863 if (node.fitRecoveryCounter > getMaxRecoveryAttempts()) { 864 while (lastForced.fitRecoveryCounter > 0 865 && lastForced.previous != null) { 866 lastForced = lastForced.previous; 867 lastDeactivated = lastForced.previous; 868 } 869 lastForced = lastRecovered; 870 lastRecovered = null; 871 startLine = lastForced.line; 872 endLine = lastForced.line; 873 log.debug("rolled back..."); 874 } 875 } else { 876 lastForced = lastTooLong; 877 } 878 return lastForced; 879 } 880 881 /** 882 * Restart from the given node at the given index. 883 * 884 * @param restartingNode the {@link KnuthNode} to restart from 885 * @param currentIndex the current position index 886 * @return the index of the restart point 887 */ restartFrom(KnuthNode restartingNode, int currentIndex)888 protected int restartFrom(KnuthNode restartingNode, int currentIndex) { 889 if (log.isDebugEnabled()) { 890 log.debug("Restarting at node " + restartingNode); 891 } 892 893 restartingNode.totalDemerits = 0; 894 addNode(restartingNode.line, restartingNode); 895 startLine = restartingNode.line; 896 endLine = startLine + 1; 897 totalWidth = restartingNode.totalWidth; 898 totalStretch = restartingNode.totalStretch; 899 totalShrink = restartingNode.totalShrink; 900 lastTooShort = null; 901 lastTooLong = null; 902 // the width, stretch and shrink already include the width, 903 // stretch and shrink of the suppressed glues; 904 // advance in the sequence in order to avoid taking into account 905 // these elements twice 906 int restartingIndex = restartingNode.position; 907 while (restartingIndex + 1 < par.size() 908 && !(getElement(restartingIndex + 1).isBox())) { 909 restartingIndex++; 910 } 911 return restartingIndex; 912 } 913 914 /** 915 * Determines if the given breakpoint is a feasible breakpoint. That is, if a decent 916 * line may be built between one of the currently active nodes and this breakpoint. 917 * @param element the paragraph's element to consider 918 * @param elementIdx the element's index inside the paragraph 919 */ considerLegalBreak(KnuthElement element, int elementIdx)920 protected void considerLegalBreak(KnuthElement element, int elementIdx) { 921 922 if (log.isTraceEnabled()) { 923 log.trace("considerLegalBreak() at " + elementIdx 924 + " (" + totalWidth + "+" + totalStretch + "-" + totalShrink 925 + "), parts/lines: " + startLine + "-" + endLine); 926 log.trace("\tCurrent active node list: " + activeNodeCount + " " + this.toString("\t")); 927 } 928 929 lastDeactivated = null; 930 lastTooLong = null; 931 for (int line = startLine; line < endLine; line++) { 932 for (KnuthNode node = getNode(line); node != null; node = node.next) { 933 if (node.position == elementIdx) { 934 continue; 935 } 936 int difference = computeDifference(node, element, elementIdx); 937 if (!elementCanEndLine(element, endLine, difference)) { 938 log.trace("Skipping legal break"); 939 break; 940 } 941 942 double r = computeAdjustmentRatio(node, difference); 943 int availableShrink = totalShrink - node.totalShrink; 944 int availableStretch = totalStretch - node.totalStretch; 945 946 if (log.isTraceEnabled()) { 947 log.trace("\tr=" + r + " difference=" + difference); 948 log.trace("\tline=" + line); 949 } 950 951 if (element.isForcedBreak() && handlingFloat()) { 952 disableFloatHandling(); // so that we do not create a float edge position later 953 } 954 // The line would be too long. 955 if (r < -1 || element.isForcedBreak() || handlingFloat()) { 956 deactivateNode(node, line); 957 } 958 959 int fitnessClass = FitnessClasses.computeFitness(r); 960 double demerits = computeDemerits(node, element, fitnessClass, r); 961 // The line is within the available shrink and the threshold. 962 if (r >= -1 && r <= threshold) { 963 activateNode(node, difference, r, 964 demerits, fitnessClass, availableShrink, availableStretch); 965 } 966 967 // The line is way too short/long, but we are in forcing mode, so a node is 968 // calculated and stored in lastValidNode. 969 if (force && (r <= -1 || r > threshold)) { 970 forceNode(node, line, elementIdx, difference, r, 971 demerits, fitnessClass, availableShrink, availableStretch); 972 } 973 } 974 addBreaks(line, elementIdx); 975 } 976 } 977 978 /** 979 * Check if the given {@link KnuthElement} can end the line with the given 980 * number. 981 * @param element the element 982 * @param line the line number 983 * @param difference an integer 984 * @return {@code true} if the element can end the line 985 */ elementCanEndLine(KnuthElement element, int line, int difference)986 protected boolean elementCanEndLine(KnuthElement element, int line, int difference) { 987 return (!element.isPenalty() 988 || element.getPenalty() < KnuthElement.INFINITE); 989 } 990 991 /** 992 * Force the given {@link KnuthNode}, and register it. 993 * 994 * @param node the node 995 * @param line the line number 996 * @param elementIdx the position index of the element 997 * @param difference the difference between content-length and available width 998 * @param r the adjustment ratio 999 * @param demerits demerits produced by the node 1000 * @param fitnessClass the fitness class 1001 * @param availableShrink the available amount of shrink 1002 * @param availableStretch tha available amount of stretch 1003 */ forceNode(KnuthNode node, int line, int elementIdx, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch)1004 protected void forceNode(KnuthNode node, 1005 int line, 1006 int elementIdx, 1007 int difference, 1008 double r, 1009 double demerits, 1010 int fitnessClass, 1011 int availableShrink, 1012 int availableStretch) { 1013 1014 int newWidth = totalWidth; 1015 int newStretch = totalStretch; 1016 int newShrink = totalShrink; 1017 1018 // add the width, stretch and shrink of glue elements after 1019 // the break 1020 // this does not affect the dimension of the line / page, only 1021 // the values stored in the node; these would be as if the break 1022 // was just before the next box element, thus ignoring glues and 1023 // penalties between the "real" break and the following box 1024 for (int i = elementIdx; i < par.size(); i++) { 1025 KnuthElement tempElement = getElement(i); 1026 if (tempElement.isBox()) { 1027 break; 1028 } else if (tempElement.isGlue()) { 1029 newWidth += tempElement.getWidth(); 1030 newStretch += tempElement.getStretch(); 1031 newShrink += tempElement.getShrink(); 1032 } else if (tempElement.isForcedBreak() && i != elementIdx) { 1033 break; 1034 } 1035 } 1036 1037 createForcedNodes(node, line, elementIdx, difference, r, demerits, fitnessClass, availableShrink, 1038 availableStretch, newWidth, newStretch, newShrink); 1039 } 1040 createForcedNodes(KnuthNode node, int line, int elementIdx, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch, int newWidth, int newStretch, int newShrink)1041 protected void createForcedNodes(KnuthNode node, int line, int elementIdx, int difference, double r, 1042 double demerits, int fitnessClass, int availableShrink, int availableStretch, int newWidth, 1043 int newStretch, int newShrink) { 1044 if (r <= -1) { 1045 log.debug("Considering tooLong, demerits=" + demerits); 1046 if (lastTooLong == null || demerits < lastTooLong.totalDemerits) { 1047 lastTooLong = createNode(elementIdx, line + 1, fitnessClass, 1048 newWidth, newStretch, newShrink, 1049 r, availableShrink, availableStretch, 1050 difference, demerits, node); 1051 if (log.isTraceEnabled()) { 1052 log.trace("Picking tooLong " + lastTooLong); 1053 } 1054 } 1055 } else { 1056 if (lastTooShort == null || demerits <= lastTooShort.totalDemerits) { 1057 if (considerTooShort) { 1058 // consider possibilities which are too short 1059 best.addRecord(demerits, node, r, availableShrink, availableStretch, difference, 1060 fitnessClass); 1061 } 1062 lastTooShort = createNode(elementIdx, line + 1, fitnessClass, 1063 newWidth, newStretch, newShrink, 1064 r, availableShrink, availableStretch, 1065 difference, demerits, node); 1066 if (log.isTraceEnabled()) { 1067 log.trace("Picking tooShort " + lastTooShort); 1068 } 1069 } 1070 } 1071 } 1072 1073 /** 1074 * Activate the given node. Will result in the given {@link KnuthNode} 1075 * being registered as a feasible breakpoint, if the {@code demerits} are better 1076 * than that of the best node registered for the given {@code fitnessClass}. 1077 * 1078 * @param node the node 1079 * @param difference the difference between content-length and available width 1080 * @param r the adjustment ratio 1081 * @param demerits demerits produced by the node 1082 * @param fitnessClass the fitness class 1083 * @param availableShrink the available amount of shrink 1084 * @param availableStretch the available amount of stretch 1085 */ activateNode(KnuthNode node, int difference, double r, double demerits, int fitnessClass, int availableShrink, int availableStretch)1086 protected void activateNode(KnuthNode node, 1087 int difference, 1088 double r, 1089 double demerits, 1090 int fitnessClass, 1091 int availableShrink, 1092 int availableStretch) { 1093 1094 if (log.isTraceEnabled()) { 1095 log.trace("\tDemerits=" + demerits); 1096 log.trace("\tFitness class=" + FitnessClasses.NAMES[fitnessClass]); 1097 } 1098 1099 if (demerits < best.getDemerits(fitnessClass)) { 1100 // updates best demerits data 1101 best.addRecord(demerits, node, r, availableShrink, availableStretch, 1102 difference, fitnessClass); 1103 lastTooShort = null; 1104 } 1105 } 1106 1107 /** 1108 * Deactivate the given node 1109 * 1110 * @param node the node 1111 * @param line the line number 1112 */ deactivateNode(KnuthNode node, int line)1113 protected void deactivateNode(KnuthNode node, int line) { 1114 // Deactivate node... 1115 if (log.isTraceEnabled()) { 1116 log.trace("Removing " + node); 1117 } 1118 removeNode(line, node); 1119 // ... and remember it, if it was a good candidate 1120 lastDeactivated = compareNodes(lastDeactivated, node); 1121 } 1122 1123 /** 1124 * Adds new active nodes for breaks at the given element. 1125 * @param line number of the previous line; this element will end line number (line+1) 1126 * @param elementIdx the element's index 1127 */ addBreaks(int line, int elementIdx)1128 private void addBreaks(int line, int elementIdx) { 1129 if (!best.hasRecords()) { 1130 return; 1131 } 1132 1133 int newWidth = totalWidth; 1134 int newStretch = totalStretch; 1135 int newShrink = totalShrink; 1136 1137 // add the width, stretch and shrink of glue elements after 1138 // the break 1139 // this does not affect the dimension of the line / page, only 1140 // the values stored in the node; these would be as if the break 1141 // was just before the next box element, thus ignoring glues and 1142 // penalties between the "real" break and the following box 1143 for (int i = elementIdx; i < par.size(); i++) { 1144 KnuthElement tempElement = getElement(i); 1145 if (tempElement.isBox()) { 1146 break; 1147 } else if (tempElement.isGlue()) { 1148 newWidth += tempElement.getWidth(); 1149 newStretch += tempElement.getStretch(); 1150 newShrink += tempElement.getShrink(); 1151 } else if (tempElement.isForcedBreak() && i != elementIdx) { 1152 break; 1153 } 1154 } 1155 1156 // add nodes to the active nodes list 1157 double minimumDemerits = best.getMinDemerits() + incompatibleFitnessDemerit; 1158 for (int i = 0; i <= 3; i++) { 1159 if (best.notInfiniteDemerits(i) && best.getDemerits(i) <= minimumDemerits) { 1160 // the nodes in activeList must be ordered 1161 // by line number and position; 1162 if (log.isTraceEnabled()) { 1163 log.trace("\tInsert new break in list of " + activeNodeCount 1164 + " from fitness class " + FitnessClasses.NAMES[i]); 1165 } 1166 KnuthNode newNode = createNode(elementIdx, line + 1, i, 1167 newWidth, newStretch, newShrink); 1168 addNode(line + 1, newNode); 1169 } 1170 } 1171 best.reset(); 1172 } 1173 1174 /** 1175 * Return the difference between the natural width of a line that would be made 1176 * between the given active node and the given element, and the available width of the 1177 * real line. 1178 * @param activeNode node for the previous breakpoint 1179 * @param element currently considered breakpoint 1180 * @param elementIndex index of the element that is considered as a breakpoint 1181 * @return The difference in width. Positive numbers mean extra space in the line, 1182 * negative number that the line overflows. 1183 */ computeDifference(KnuthNode activeNode, KnuthElement element, int elementIndex)1184 protected int computeDifference(KnuthNode activeNode, KnuthElement element, 1185 int elementIndex) { 1186 // compute the adjustment ratio 1187 int actualWidth = totalWidth - activeNode.totalWidth; 1188 if (element.isPenalty()) { 1189 actualWidth += element.getWidth(); 1190 } 1191 return getLineWidth() - actualWidth; 1192 } 1193 1194 /** 1195 * Return the adjustment ratio needed to make up for the difference. A ratio of 1196 * <ul> 1197 * <li>0 means that the break has the exact right width</li> 1198 * <li>>= -1 && < 0 means that the break is wider than the line, 1199 * but within the minimim values of the glues.</li> 1200 * <li>>0 && < 1 means that the break is smaller than the line width, 1201 * but within the maximum values of the glues.</li> 1202 * <li>> 1 means that the break is too small to make up for the glues.</li> 1203 * </ul> 1204 * @param activeNode the currently active node 1205 * @param difference the difference between content-length and available width 1206 * @return The adjustment ratio. 1207 */ computeAdjustmentRatio(KnuthNode activeNode, int difference)1208 protected double computeAdjustmentRatio(KnuthNode activeNode, int difference) { 1209 // compute the adjustment ratio 1210 if (difference > 0) { 1211 int maxAdjustment = totalStretch - activeNode.totalStretch; 1212 if (maxAdjustment > 0) { 1213 return (double) difference / maxAdjustment; 1214 } else { 1215 return INFINITE_RATIO; 1216 } 1217 } else if (difference < 0) { 1218 int maxAdjustment = totalShrink - activeNode.totalShrink; 1219 if (maxAdjustment > 0) { 1220 return (double) difference / maxAdjustment; 1221 } else { 1222 return -INFINITE_RATIO; 1223 } 1224 } else { 1225 return 0; 1226 } 1227 } 1228 1229 /** 1230 * Computes the demerits of the current breaking (that is, up to the given element), 1231 * if the next-to-last chosen breakpoint is the given active node. This adds to the 1232 * total demerits of the given active node, the demerits of a line starting at this 1233 * node and ending at the given element. 1234 * @param activeNode considered preceding line break 1235 * @param element considered current line break 1236 * @param fitnessClass fitness of the current line 1237 * @param r adjustment ratio for the current line 1238 * @return the demerit of the current line 1239 */ computeDemerits(KnuthNode activeNode, KnuthElement element, int fitnessClass, double r)1240 protected double computeDemerits(KnuthNode activeNode, KnuthElement element, 1241 int fitnessClass, double r) { 1242 double demerits = 0; 1243 // compute demerits 1244 double f = Math.abs(r); 1245 f = 1 + 100 * f * f * f; 1246 if (element.isPenalty()) { 1247 double penalty = element.getPenalty(); 1248 if (penalty >= 0) { 1249 f += penalty; 1250 demerits = f * f; 1251 } else if (!element.isForcedBreak()) { 1252 demerits = f * f - penalty * penalty; 1253 } else { 1254 demerits = f * f; 1255 } 1256 } else { 1257 demerits = f * f; 1258 } 1259 1260 if (element.isPenalty() && ((KnuthPenalty) element).isPenaltyFlagged() 1261 && getElement(activeNode.position).isPenalty() 1262 && ((KnuthPenalty) getElement(activeNode.position)).isPenaltyFlagged()) { 1263 // add demerit for consecutive breaks at flagged penalties 1264 demerits += repeatedFlaggedDemerit; 1265 // there are at least two consecutive lines ending with a flagged penalty; 1266 // check if the previous line end with a flagged penalty too, 1267 // and if this situation is allowed 1268 int flaggedPenaltiesCount = 2; 1269 for (KnuthNode prevNode = activeNode.previous; 1270 prevNode != null && flaggedPenaltiesCount <= maxFlaggedPenaltiesCount; 1271 prevNode = prevNode.previous) { 1272 KnuthElement prevElement = getElement(prevNode.position); 1273 if (prevElement.isPenalty() 1274 && ((KnuthPenalty) prevElement).isPenaltyFlagged()) { 1275 // the previous line ends with a flagged penalty too 1276 flaggedPenaltiesCount++; 1277 } else { 1278 // the previous line does not end with a flagged penalty, 1279 // exit the loop 1280 break; 1281 } 1282 } 1283 if (maxFlaggedPenaltiesCount >= 1 1284 && flaggedPenaltiesCount > maxFlaggedPenaltiesCount) { 1285 // add infinite demerits, so this break will not be chosen 1286 // unless there isn't any alternative break 1287 demerits += BestRecords.INFINITE_DEMERITS; 1288 } 1289 } 1290 if (Math.abs(fitnessClass - activeNode.fitness) > 1) { 1291 // add demerit for consecutive breaks 1292 // with very different fitness classes 1293 demerits += incompatibleFitnessDemerit; 1294 } 1295 demerits += activeNode.totalDemerits; 1296 return demerits; 1297 } 1298 1299 /** 1300 * Hook for subclasses to trigger special behavior after ending the 1301 * main loop in {@link #findBreakingPoints(KnuthSequence,int,double,boolean,int)} 1302 */ finish()1303 protected void finish() { 1304 if (log.isTraceEnabled()) { 1305 log.trace("Main loop completed " + activeNodeCount); 1306 log.trace("Active nodes=" + toString("")); 1307 } 1308 } 1309 1310 /** 1311 * Return the element at index idx in the paragraph. 1312 * @param idx index of the element. 1313 * @return the element at index idx in the paragraph. 1314 */ getElement(int idx)1315 protected KnuthElement getElement(int idx) { 1316 return (KnuthElement) par.get(idx); 1317 } 1318 1319 /** 1320 * Compare two KnuthNodes and return the node with the least demerit. 1321 * @param node1 The first knuth node. 1322 * @param node2 The other knuth node. 1323 * @return the node with the least demerit. 1324 */ compareNodes(KnuthNode node1, KnuthNode node2)1325 protected KnuthNode compareNodes(KnuthNode node1, KnuthNode node2) { 1326 if (node1 == null || node2.position > node1.position) { 1327 return node2; 1328 } 1329 if (node2.position == node1.position) { 1330 if (node2.totalDemerits < node1.totalDemerits) { 1331 return node2; 1332 } 1333 } 1334 return node1; 1335 } 1336 1337 /** 1338 * Add a node at the end of the given line's existing active nodes. 1339 * If this is the first node in the line, adjust endLine accordingly. 1340 * @param line number of the line ending at the node's corresponding breakpoint 1341 * @param node the active node to add 1342 */ addNode(int line, KnuthNode node)1343 protected void addNode(int line, KnuthNode node) { 1344 int headIdx = line * 2; 1345 if (headIdx >= activeLines.length) { 1346 KnuthNode[] oldList = activeLines; 1347 activeLines = new KnuthNode[headIdx + headIdx]; 1348 System.arraycopy(oldList, 0, activeLines, 0, oldList.length); 1349 } 1350 node.next = null; 1351 if (activeLines[headIdx + 1] != null) { 1352 activeLines[headIdx + 1].next = node; 1353 } else { 1354 activeLines[headIdx] = node; 1355 endLine = line + 1; 1356 } 1357 activeLines[headIdx + 1] = node; 1358 activeNodeCount++; 1359 } 1360 1361 /** 1362 * Remove the given active node registered for the given line. If there are no more active nodes 1363 * for this line, adjust the startLine accordingly. 1364 * @param line number of the line ending at the node's corresponding breakpoint 1365 * @param node the node to deactivate 1366 */ removeNode(int line, KnuthNode node)1367 protected void removeNode(int line, KnuthNode node) { 1368 int headIdx = line * 2; 1369 KnuthNode n = getNode(line); 1370 if (n != node) { 1371 // nodes could be rightly deactivated in a different order 1372 KnuthNode prevNode = null; 1373 while (n != node) { 1374 prevNode = n; 1375 n = n.next; 1376 } 1377 prevNode.next = n.next; 1378 if (prevNode.next == null) { 1379 activeLines[headIdx + 1] = prevNode; 1380 } 1381 } else { 1382 activeLines[headIdx] = node.next; 1383 if (node.next == null) { 1384 activeLines[headIdx + 1] = null; 1385 } 1386 while (startLine < endLine && getNode(startLine) == null) { 1387 startLine++; 1388 } 1389 } 1390 activeNodeCount--; 1391 } 1392 1393 /** 1394 * Returns the first active node for the given line. 1395 * @param line the line/part number 1396 * @return the requested active node 1397 */ getNode(int line)1398 protected KnuthNode getNode(int line) { 1399 return activeLines[line * 2]; 1400 } 1401 1402 /** 1403 * Returns the line/part width of a given line/part. 1404 * @param line the line/part number 1405 * @return the width/length in millipoints 1406 */ getLineWidth(int line)1407 protected int getLineWidth(int line) { 1408 assert lineWidth >= 0; 1409 return this.lineWidth; 1410 } 1411 1412 /** @return the constant line/part width or -1 if there is no such value */ getLineWidth()1413 protected int getLineWidth() { 1414 return this.lineWidth; 1415 } 1416 1417 /** 1418 * Creates a string representation of the active nodes. Used for debugging. 1419 * @param prepend a string to prepend on each entry 1420 * @return the requested string 1421 */ toString(String prepend)1422 public String toString(String prepend) { 1423 StringBuffer sb = new StringBuffer(); 1424 sb.append("[\n"); 1425 for (int i = startLine; i < endLine; i++) { 1426 for (KnuthNode node = getNode(i); node != null; node = node.next) { 1427 sb.append(prepend).append('\t').append(node).append(",\n"); 1428 } 1429 } 1430 sb.append(prepend).append("]"); 1431 return sb.toString(); 1432 } 1433 1434 /** 1435 * Filter active nodes. 1436 * @return an integer 1437 */ filterActiveNodes()1438 protected abstract int filterActiveNodes(); 1439 1440 /** 1441 * Determines the set of optimal breakpoints corresponding to the given active node. 1442 * @param node the active node 1443 * @param par the corresponding paragraph 1444 * @param total the number of lines into which the paragraph will be broken 1445 */ calculateBreakPoints(KnuthNode node, KnuthSequence par, int total)1446 protected void calculateBreakPoints(KnuthNode node, KnuthSequence par, 1447 int total) { 1448 KnuthNode bestActiveNode = node; 1449 // use bestActiveNode to determine the optimum breakpoints 1450 for (int i = node.line; i > 0; i--) { 1451 updateData2(bestActiveNode, par, total); 1452 bestActiveNode = bestActiveNode.previous; 1453 } 1454 } 1455 1456 /** @return the alignment for normal lines/parts */ getAlignment()1457 public int getAlignment() { 1458 return this.alignment; 1459 } 1460 1461 /** @return the alignment for the last line/part */ getAlignmentLast()1462 public int getAlignmentLast() { 1463 return this.alignmentLast; 1464 } 1465 handlingFloat()1466 protected boolean handlingFloat() { 1467 return false; 1468 } 1469 handleFloat()1470 protected int handleFloat() { 1471 throw new IllegalStateException(); 1472 } 1473 disableFloatHandling()1474 protected void disableFloatHandling() { 1475 throw new IllegalStateException(); 1476 } 1477 } 1478