From 0d4b815b26a14f6dda80d7986649232534a36fe6 Mon Sep 17 00:00:00 2001 From: Luis Bernardo Date: Mon, 10 Dec 2012 00:31:43 +0000 Subject: [PATCH] jira fop-1840: column balancing algorithm; applied patch 12559043 submitted by Robert Meyer. git-svn-id: https://svn.apache.org/repos/asf/xmlgraphics/fop/trunk@1419183 13f79535-47bb-0310-9956-ffa450edef68 --- .../BalancingColumnBreakingAlgorithm.java | 274 +++++++++++++----- .../standard-testcases/balanced-columns_1.xml | 130 +++++++++ .../standard-testcases/balanced-columns_2.xml | 245 ++++++++++++++++ .../standard-testcases/balanced-columns_3.xml | 162 +++++++++++ .../standard-testcases/balanced-columns_4.xml | 61 ++++ .../standard-testcases/balanced-columns_5.xml | 130 +++++++++ .../standard-testcases/balanced-columns_6.xml | 131 +++++++++ 7 files changed, 1062 insertions(+), 71 deletions(-) create mode 100644 test/layoutengine/standard-testcases/balanced-columns_1.xml create mode 100644 test/layoutengine/standard-testcases/balanced-columns_2.xml create mode 100644 test/layoutengine/standard-testcases/balanced-columns_3.xml create mode 100644 test/layoutengine/standard-testcases/balanced-columns_4.xml create mode 100644 test/layoutengine/standard-testcases/balanced-columns_5.xml create mode 100644 test/layoutengine/standard-testcases/balanced-columns_6.xml diff --git a/src/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java b/src/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java index 03c159843..47a2e38fb 100644 --- a/src/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java +++ b/src/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java @@ -19,8 +19,10 @@ package org.apache.fop.layoutmgr; -import org.apache.commons.logging.Log; -import org.apache.commons.logging.LogFactory; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; import org.apache.fop.traits.MinOptMax; @@ -30,36 +32,10 @@ import org.apache.fop.traits.MinOptMax; */ public class BalancingColumnBreakingAlgorithm extends PageBreakingAlgorithm { - private static final Log LOG = LogFactory.getLog(BalancingColumnBreakingAlgorithm.class); - private int columnCount; - private int fullLen; - private int idealPartLen; - - /** - * Construct a balancing column breaking algorithm. - * @param topLevelLM the top level layout manager - * @param pageProvider the page provider - * @param layoutListener the layout listener - * @param alignment alignment of the paragraph/page. One of - * {@link org.apache.fop.fo.Constants#EN_START}, - * {@link org.apache.fop.fo.Constants#EN_JUSTIFY}, - * {@link org.apache.fop.fo.Constants#EN_CENTER}, - * {@link org.apache.fop.fo.Constants#EN_END}. - * For pages, {@link org.apache.fop.fo.Constants#EN_BEFORE} and - * {@link org.apache.fop.fo.Constants#EN_AFTER} - * are mapped to the corresponding inline properties, - * {@link org.apache.fop.fo.Constants#EN_START} and - * {@link org.apache.fop.fo.Constants#EN_END}. - * @param alignmentLast alignment of the paragraph's last line - * @param footnoteSeparatorLength length of footnote separator - * @param partOverflowRecovery {@code true} if too long elements should be moved to - * the next line/part - * @param columnCount number of columns - * @see PageBreakingAlgorithm - */ - public BalancingColumnBreakingAlgorithm( // CSOK: ParameterNumber - LayoutManager topLevelLM, + private List idealBreaks; + + public BalancingColumnBreakingAlgorithm(LayoutManager topLevelLM, PageProvider pageProvider, PageBreakingLayoutListener layoutListener, int alignment, int alignmentLast, @@ -76,56 +52,212 @@ public class BalancingColumnBreakingAlgorithm extends PageBreakingAlgorithm { /** {@inheritDoc} */ protected double computeDemerits(KnuthNode activeNode, KnuthElement element, int fitnessClass, double r) { - double dem = super.computeDemerits(activeNode, element, fitnessClass, r); - if (LOG.isTraceEnabled()) { - LOG.trace("original demerit=" + dem + " " + totalWidth - + " line=" + activeNode.line + "/" + columnCount - + " pos=" + activeNode.position + "/" + (par.size() - 1)); + double demerits = Double.MAX_VALUE; + if (idealBreaks == null) { + idealBreaks = calculateIdealBreaks(activeNode.position); } - int remParts = columnCount - activeNode.line; - int curPos = par.indexOf(element); - if (fullLen == 0) { - fullLen = ElementListUtils.calcContentLength(par, activeNode.position, par.size() - 1); - this.idealPartLen = (fullLen / columnCount); + LinkedList curPossibility = getPossibilityTrail(activeNode); + boolean notIdeal = false; + int idealDemerit = columnCount + 1 - curPossibility.size(); + if (curPossibility.size() > idealBreaks.size()) { + return demerits; } - int partLen = ElementListUtils.calcContentLength(par, activeNode.position, curPos - 1); - int restLen = ElementListUtils.calcContentLength(par, curPos - 1, par.size() - 1); - int avgRestLen = 0; - if (remParts > 0) { - avgRestLen = restLen / remParts; + for (int breakPos = 0; breakPos < curPossibility.size(); breakPos++) { + if (curPossibility.get(breakPos) != 0 && curPossibility.get(breakPos) + != idealBreaks.get(breakPos)) { + notIdeal = true; + break; + } } - if (LOG.isTraceEnabled()) { - LOG.trace("remaining parts: " + remParts + " rest len: " + restLen - + " avg=" + avgRestLen); + if (!notIdeal) { + demerits = idealDemerit; } - double balance = (idealPartLen - partLen) / 1000f; - if (LOG.isTraceEnabled()) { - LOG.trace("balance=" + balance); + return demerits; + } + + private List calculateIdealBreaks(int startPos) { + List previousPreviousBreaks = null; + List previousBreaks = null; + List breaks = new ArrayList(); + breaks.add(new ColumnContent(startPos, par.size() - 1)); + do { + previousPreviousBreaks = previousBreaks; + previousBreaks = breaks; + breaks = getInitialBreaks(startPos, getAverageColumnLength(breaks)); + } while (!breaks.equals(previousBreaks) && !breaks.equals(previousPreviousBreaks)); + breaks = sortElementsForBreaks(breaks); + return getElementIdBreaks(breaks, startPos); + } + + private static final class ColumnContent { + + public final int startIndex; + + public final int endIndex; + + ColumnContent(int startIndex, int endIndex) { + this.startIndex = startIndex; + this.endIndex = endIndex; } - double absBalance = Math.abs(balance); - dem = absBalance; - //Step 1: This does the rough balancing - if (columnCount > 2) { - if (balance > 0) { - //shorter parts are less desired than longer ones - dem = dem * 1.2f; + + @Override + public int hashCode() { + return startIndex << 16 | endIndex; + } + + @Override + public boolean equals(Object obj) { + if (!(obj instanceof ColumnContent)) { + return false; + } else { + ColumnContent other = (ColumnContent) obj; + return other.startIndex == startIndex && other.endIndex == endIndex; } - } else { - if (balance < 0) { - //shorter parts are less desired than longer ones - dem = dem * 1.2f; + } + + @Override + public String toString() { + return startIndex + "-" + endIndex; + } + + } + + private int getAverageColumnLength(List columns) { + int totalLength = 0; + for (ColumnContent col : columns) { + totalLength += calcContentLength(par, col.startIndex, col.endIndex); + } + return totalLength / columnCount; + } + + private List getInitialBreaks(int startIndex, int averageColLength) { + List initialColumns = new ArrayList(); + int colStartIndex = startIndex; + int totalLength = 0; + int idealBreakLength = averageColLength; + int previousBreakLength = 0; + int prevBreakIndex = startIndex; + boolean prevIsBox = false; + int colNumber = 1; + for (int i = startIndex; i < par.size(); i++) { + KnuthElement element = (KnuthElement) par.get(i); + if (isLegalBreak(i, prevIsBox)) { + int breakLength = totalLength + + (element instanceof KnuthPenalty ? element.getWidth() : 0); + if (breakLength > idealBreakLength && colNumber < columnCount) { + int breakIndex; + if (breakLength - idealBreakLength > idealBreakLength - previousBreakLength) { + breakIndex = prevBreakIndex; + totalLength = previousBreakLength; + } else { + breakIndex = element instanceof KnuthPenalty ? i : i - 1; + totalLength = breakLength; + } + initialColumns.add(new ColumnContent(colStartIndex, breakIndex)); + i = getNextStartIndex(breakIndex); + colStartIndex = i--; + colNumber++; + idealBreakLength += averageColLength; + } else { + previousBreakLength = breakLength; + prevBreakIndex = element instanceof KnuthPenalty ? i : i - 1; + prevIsBox = false; + } + } else { + totalLength += element instanceof KnuthPenalty ? 0 : element.getWidth(); + prevIsBox = element instanceof KnuthBox; } } - //Step 2: This helps keep the trailing parts shorter than the previous ones - dem += (avgRestLen) / 1000f; + assert initialColumns.size() == columnCount - 1; + initialColumns.add(new ColumnContent(colStartIndex, par.size() - 1)); + return initialColumns; + } - if (activeNode.line >= columnCount) { - //We don't want more columns than available - dem = Double.MAX_VALUE; + private int getNextStartIndex(int breakIndex) { + int startIndex = breakIndex; + @SuppressWarnings("unchecked") + Iterator iter = par.listIterator(breakIndex); + while (iter.hasNext() && !(iter.next() instanceof KnuthBox)) { + startIndex++; } - if (LOG.isTraceEnabled()) { - LOG.trace("effective dem=" + dem + " " + totalWidth); + return startIndex; + } + + private List sortElementsForBreaks(List breaks) { + boolean changes; + /* Relax factor to make balancing more visually appealing as in some cases + * strict balancing would lead to ragged column endings. */ + int fFactor = 4000; + do { + changes = false; + ColumnContent curColumn = breaks.get(breaks.size() - 1); + int curColLength = calcContentLength(par, curColumn.startIndex, curColumn.endIndex); + for (int colIndex = (breaks.size() - 1); colIndex > 0; colIndex--) { + ColumnContent prevColumn = breaks.get(colIndex - 1); + int prevColLength = calcContentLength(par, prevColumn.startIndex, prevColumn.endIndex); + if (prevColLength < curColLength) { + int newBreakIndex = curColumn.startIndex; + boolean prevIsBox = true; + while (newBreakIndex <= curColumn.endIndex && !(isLegalBreak(newBreakIndex, prevIsBox))) { + newBreakIndex++; + prevIsBox = par.get(newBreakIndex) instanceof KnuthBox; + } + if (newBreakIndex < curColumn.endIndex) { + if (prevIsBox) { + newBreakIndex--; + } + int newStartIndex = getNextStartIndex(newBreakIndex); + int newPrevColLength = calcContentLength(par, prevColumn.startIndex, newBreakIndex); + if (newPrevColLength <= fFactor + curColLength) { + prevColumn = new ColumnContent(prevColumn.startIndex, newBreakIndex); + breaks.set(colIndex - 1, prevColumn); + breaks.set(colIndex, new ColumnContent(newStartIndex, curColumn.endIndex)); + prevColLength = calcContentLength(par, prevColumn.startIndex, newBreakIndex); + changes = true; + } + } + } + curColLength = prevColLength; + curColumn = prevColumn; + } + } while (changes); + return breaks; + } + + private boolean isLegalBreak(int index, boolean prevIsBox) { + KnuthElement element = (KnuthElement) par.get(index); + return element instanceof KnuthPenalty && element.getPenalty() < KnuthPenalty.INFINITE + || prevIsBox && element instanceof KnuthGlue; + } + + private int calcContentLength(KnuthSequence par, int startIndex, int endIndex) { + return ElementListUtils.calcContentLength(par, startIndex, endIndex) + getPenaltyWidth(endIndex); + } + + private int getPenaltyWidth(int index) { + KnuthElement element = (KnuthElement) par.get(index); + return element instanceof KnuthPenalty ? element.getWidth() : 0; + } + + private List getElementIdBreaks(List breaks, int startPos) { + List elementIdBreaks = new ArrayList(); + elementIdBreaks.add(startPos); + for (ColumnContent column : breaks) { + if (breaks.get(breaks.size() - 1).equals(column)) { + continue; + } + elementIdBreaks.add(column.endIndex); } - return dem; + return elementIdBreaks; + } + + private LinkedList getPossibilityTrail(KnuthNode activeNode) { + LinkedList trail = new LinkedList(); + KnuthNode previous = activeNode; + do { + trail.addFirst(previous.position); + previous = previous.previous; + } while (previous != null); + return trail; } } diff --git a/test/layoutengine/standard-testcases/balanced-columns_1.xml b/test/layoutengine/standard-testcases/balanced-columns_1.xml new file mode 100644 index 000000000..621804d0f --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_1.xml @@ -0,0 +1,130 @@ + + + + + +

+ This test checks different row heights when balancing columns +

+ + + + + + + + + + + + + + + + + header + + + + + + + + + footer + + + + + + + + + 1 + + + + + + + 3 + + + + + + + 5 + + + + + + + 7 + + + + + + + 9 + + + + + + + 11 + + + + + + + 13 + + + + + + + 15 + + + + + + + 17 + + + + + + spanning + + + + + + + + + + diff --git a/test/layoutengine/standard-testcases/balanced-columns_2.xml b/test/layoutengine/standard-testcases/balanced-columns_2.xml new file mode 100644 index 000000000..f05e07221 --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_2.xml @@ -0,0 +1,245 @@ + + + + + +

+ This test checks balanced columns with tables and blocks +

+ + + + + + + + + + + + + + + + + header 1 + + + + + + + + + footer 1 + + + + + + + + + 1 + + + + + + + 2 + + + + + + + 3 + + + + + + + 4 + + + + + + + 5 + + + + + + + 6 + + + + + + + 7 + + + + + + + 8 + + + + + + + 9 + + + + + + + 10 + + + + + + + 11 + + + + + + Some text + + + + + + + header 2 + + + + + + + + + footer 2 + + + + + + + + + 1 + + + + + + + 2 + + + + + + + 3 + + + + + + + 4 + + + + + + + 5 + + + + + + + 6 + + + + + + + 7 + + + + + + + 8 + + + + + + + 9 + + + + + + + 10 + + + + + + + 11 + + + + + + spanning + + + + + + + + + + diff --git a/test/layoutengine/standard-testcases/balanced-columns_3.xml b/test/layoutengine/standard-testcases/balanced-columns_3.xml new file mode 100644 index 000000000..fe58b8ff8 --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_3.xml @@ -0,0 +1,162 @@ + + + + + +

+ This test checks balancing with multiple tables with headers / footers +

+ + + + + + + + + + + + + + + T1 H1 + + + T1 H2 + + + + + + T1 C1 + + + T1 C2 + + + + + + + + T2 H1 + + + T2 H2 + + + + + T2 F1 + + + T2 F2 + + + + + + T2 C1 + + + T2 C2 + + + + + T2 C1 + + + T2 C2 + + + + + T2 C1 + + + T2 C2 + + + + + T2 C1 + + + T2 C2 + + + + + T2 C1 + + + T2 C2 + + + + + T2 C1 + + + T2 C2 + + + + + + + + T3 H1 + + + T3 H2 + + + + + + T3 C1 + + + T3 C2 + + + + + T3 C1 + + + T3 C2 + + + + + + SUMMARY + + + + + + + + + + diff --git a/test/layoutengine/standard-testcases/balanced-columns_4.xml b/test/layoutengine/standard-testcases/balanced-columns_4.xml new file mode 100644 index 000000000..2373bd2e5 --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_4.xml @@ -0,0 +1,61 @@ + + + + + +

+ This test checks balancing when KnuthGlue elements are introduced +

+ + + + + + + + + + + + + Lorem ipsum dolor sit amet, consectetur + adipiscing elit. Vestibulum arcu felis, gravida vitae laoreet in, molestie nec libero. + Mauris non enim diam. Pellentesque nisl diam, aliquet nec euismod vitae, convallis nec + massa. Mauris gravida arcu ac erat euismod molestie. Maecenas eget neque in sem aliquam + viverra. Vivamus dictum lobortis scelerisque. In cursus venenatis arcu, id vulputate nisi + interdum non. Nulla venenatis porta ipsum. Aenean mattis placerat nibh, porttitor consequat + orci suscipit sed. Sed eget orci nisi, eget commodo arcu. Nulla urna urna, tristique ac + sagittis ut, mollis in leo. Praesent et dui nulla. Nullam nec dui quis velit pretium + tristique. Nullam et neque eros. Sed non dolor id dolor vulputate faucibus. Suspendisse non + lacus eget nibh faucibus scelerisque eget vel nunc. In malesuada ornare eros vitae sagittis. + Aliquam erat volutpat. Aenean feugiat dignissim lobortis. + + + + + + + + + + + + + diff --git a/test/layoutengine/standard-testcases/balanced-columns_5.xml b/test/layoutengine/standard-testcases/balanced-columns_5.xml new file mode 100644 index 000000000..89ffde05d --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_5.xml @@ -0,0 +1,130 @@ + + + + + +

+ This test checks column balancing with different row heights +

+ + + + + + + + + + + + + + + + + header + + + + + + + + + footer + + + + + + + + + 1 + + + + + + + 2 + + + + + + + 3 + + + + + + + 4 + + + + + + + 5 + + + + + + + 6 + + + + + + + 7 + + + + + + + 8 + + + + + + + 9 + + + + + + spanning + + + + + + + + + + diff --git a/test/layoutengine/standard-testcases/balanced-columns_6.xml b/test/layoutengine/standard-testcases/balanced-columns_6.xml new file mode 100644 index 000000000..1b78910d1 --- /dev/null +++ b/test/layoutengine/standard-testcases/balanced-columns_6.xml @@ -0,0 +1,131 @@ + + + + + +

+ This test checks column balancing with different row heights. +

+ + + + + + + + + + + + + + + + + header + + + + + + + + + footer + + + + + + + + + 1 + + + + + + + 2 + + + + + + + 3 + + + + + + + 4 + + + + + + + 5 + + + + + + + 6 + + + + + + + 7 + + + + + + + 8 + + + + + + + 9 + + + + + + spanning + + + + + + + + + + + -- 2.39.5