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
author: Luis Bernardo <lbernardo@apache.org> 2012-12-10 00:31:43 +0000
committer: Luis Bernardo <lbernardo@apache.org> 2012-12-10 00:31:43 +0000
commit: 0d4b815b26a14f6dda80d7986649232534a36fe6 (patch)
tree: 8caaadec6adbf0393936ffc9cafd99e92d6487a6
parent: 11e2a41b637131bc7908c62437fd07dba5b82623 (diff)
download: xmlgraphics-fop-0d4b815b26a14f6dda80d7986649232534a36fe6.tar.gz
xmlgraphics-fop-0d4b815b26a14f6dda80d7986649232534a36fe6.zip
7 files changed, 1062 insertions, 71 deletions
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<Integer> 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<Integer> 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<Integer> calculateIdealBreaks(int startPos) {
+        List<ColumnContent> previousPreviousBreaks = null;
+        List<ColumnContent> previousBreaks = null;
+        List<ColumnContent> breaks = new ArrayList<ColumnContent>();
+        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<ColumnContent> columns) {
+        int totalLength = 0;
+        for (ColumnContent col : columns) {
+            totalLength += calcContentLength(par, col.startIndex, col.endIndex);
+        }
+        return totalLength / columnCount;
+    }
+
+    private List<ColumnContent> getInitialBreaks(int startIndex, int averageColLength) {
+        List<ColumnContent> initialColumns = new ArrayList<ColumnContent>();
+        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<KnuthElement> 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<ColumnContent> sortElementsForBreaks(List<ColumnContent> 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<Integer> getElementIdBreaks(List<ColumnContent> breaks, int startPos) {
+        List<Integer> elementIdBreaks = new ArrayList<Integer>();
+        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<Integer> getPossibilityTrail(KnuthNode activeNode) {
+        LinkedList<Integer> trail = new LinkedList<Integer>();
+        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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks different row heights when balancing columns
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format" xmlns:fox="http://xmlgraphics.apache.org/fop/extensions">
+      <fo:layout-master-set>
+        <fo:simple-page-master margin-right="1cm" margin-left="1cm" margin-bottom="0.3cm" margin-top="1cm" page-width="21cm" page-height="29.7cm" master-name="all">
+          <fo:region-body column-count="4" margin-left="0cm" margin-bottom="1cm" />
+        </fo:simple-page-master>
+      </fo:layout-master-set>
+      <fo:page-sequence master-reference="all">
+        <fo:flow flow-name="xsl-region-body">
+          <fo:table table-layout="fixed" width="100%">
+            <fo:table-column column-width="proportional-column-width(1)" />
+            <fo:table-header>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>header</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-header>
+            <fo:table-footer>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>footer</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-footer>
+            <fo:table-body>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>3</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>5</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="36">7</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="18">9</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="18">11</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>13</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>15</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>17</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-body>
+          </fo:table>
+          <fo:block span="all">spanning</fo:block>
+        </fo:flow>
+      </fo:page-sequence>
+    </fo:root>
+  </fo>
+  <checks>
+    <eval expected="13" xpath="//span[1]/flow[4]//block[1]/block[2]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="11" xpath="//span[1]/flow[3]//block[1]/block[3]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="5" xpath="//span[1]/flow[1]//block[1]/block[4]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+  </checks>
+</testcase>
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks balanced columns with tables and blocks
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format" xmlns:fox="http://xmlgraphics.apache.org/fop/extensions">
+      <fo:layout-master-set>
+        <fo:simple-page-master margin-right="1cm" margin-left="1cm" margin-bottom="0.3cm" margin-top="1cm" page-width="21cm" page-height="29.7cm" master-name="all">
+          <fo:region-body column-count="4" margin-left="0cm" margin-bottom="1cm" margin-right="0cm" margin-top="0cm"/>
+        </fo:simple-page-master>
+      </fo:layout-master-set>
+      <fo:page-sequence master-reference="all">
+        <fo:flow flow-name="xsl-region-body">
+          <fo:table table-layout="fixed" width="100%">
+            <fo:table-column column-width="proportional-column-width(1)" />
+            <fo:table-header>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>header 1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-header>
+            <fo:table-footer>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>footer 1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-footer>
+            <fo:table-body>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>3</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>4</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>5</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>6</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>7</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>8</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>9</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>10</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>11</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-body>
+          </fo:table>
+          <fo:block>Some text</fo:block>
+          <fo:table table-layout="fixed" width="100%">
+            <fo:table-column column-width="proportional-column-width(1)" />
+            <fo:table-header>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>header 2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-header>
+            <fo:table-footer>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>footer 2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-footer>
+            <fo:table-body>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>3</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>4</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>5</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>6</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>7</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>8</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>9</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>10</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>11</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-body>
+          </fo:table>
+          <fo:block span="all">spanning</fo:block>
+        </fo:flow>
+      </fo:page-sequence>
+    </fo:root>
+  </fo>
+  <checks>
+    <eval expected="6" xpath="//span[1]/flow[1]/block[1]/block[7]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="Some" xpath="//span[1]/flow[2]/block[2]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="11" xpath="//span[1]/flow[4]/block[1]/block[6]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+  </checks>
+</testcase>
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks balancing with multiple tables with headers / footers
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format" >
+        <fo:layout-master-set>
+            <fo:simple-page-master master-name="simple" page-height="5in" page-width="5in">
+                <fo:region-body region-name="PageBody" column-count="3"/>
+            </fo:simple-page-master>
+        </fo:layout-master-set>
+        <fo:page-sequence master-reference="simple">
+            <fo:flow flow-name="PageBody">
+                <fo:block>
+            <fo:table table-layout="fixed" >
+              <fo:table-header font-weight="bold">
+                  <fo:table-cell>
+                      <fo:block>T1 H1</fo:block>
+                  </fo:table-cell>
+                  <fo:table-cell>
+                      <fo:block>T1 H2</fo:block>
+                  </fo:table-cell>
+              </fo:table-header>
+              <fo:table-body>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T1 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T1 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+              </fo:table-body>
+            </fo:table>
+            <fo:table table-layout="fixed" >
+              <fo:table-header font-weight="bold">
+                  <fo:table-cell>
+                      <fo:block>T2 H1</fo:block>
+                  </fo:table-cell>
+                  <fo:table-cell>
+                      <fo:block>T2 H2</fo:block>
+                  </fo:table-cell>
+              </fo:table-header>
+              <fo:table-footer font-weight="bold">
+                  <fo:table-cell>
+                      <fo:block>T2 F1</fo:block>
+                  </fo:table-cell>
+                  <fo:table-cell>
+                      <fo:block>T2 F2</fo:block>
+                  </fo:table-cell>
+              </fo:table-footer>
+              <fo:table-body>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T2 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T2 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+              </fo:table-body>
+            </fo:table>
+            <fo:table table-layout="fixed" >
+              <fo:table-header font-weight="bold">
+                  <fo:table-cell>
+                      <fo:block>T3 H1</fo:block>
+                  </fo:table-cell>
+                  <fo:table-cell>
+                      <fo:block>T3 H2</fo:block>
+                  </fo:table-cell>
+              </fo:table-header>
+              <fo:table-body>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T3 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T3 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+                <fo:table-row>
+                    <fo:table-cell>
+                        <fo:block>T3 C1</fo:block>
+                    </fo:table-cell>
+                    <fo:table-cell>
+                        <fo:block>T3 C2</fo:block>
+                    </fo:table-cell>
+                </fo:table-row>
+              </fo:table-body>
+            </fo:table>
+                </fo:block>
+                <fo:block span="all">SUMMARY</fo:block>
+            </fo:flow>
+        </fo:page-sequence>
+     </fo:root>
+  </fo>
+  <checks>
+    <eval expected="86400" xpath="//flow[1]/@bpd"/>
+    <eval expected="86400" xpath="//flow[2]/@bpd"/>
+    <eval expected="43200" xpath="//flow[3]/@bpd"/>
+  </checks>
+</testcase>
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks balancing when KnuthGlue elements are introduced
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format">
+      <fo:layout-master-set>
+        <fo:simple-page-master master-name="page"
+          page-height="320pt" page-width="420pt" margin="10pt">
+          <fo:region-body column-count="2"/>
+        </fo:simple-page-master>
+      </fo:layout-master-set>
+
+      <fo:page-sequence master-reference="page">
+        <fo:flow flow-name="xsl-region-body" text-align="justify">
+
+          <fo:block border="1pt solid black" border-before-width.conditionality="retain" 
+            border-after-width.conditionality="retain">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.</fo:block>
+
+          <fo:block span="all"/>
+
+        </fo:flow>
+      </fo:page-sequence>
+
+    </fo:root>
+  </fo>
+  <checks>
+    <eval expected="placerat" xpath="//span[1]/flow[1]/block[1]/lineArea[14]/text[1]/word[5]"/>
+    <eval expected="nibh," xpath="//span[1]/flow[2]/block[1]/lineArea[1]/text[1]/word[1]"/>
+  </checks>
+</testcase>
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks column balancing with different row heights
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format" xmlns:fox="http://xmlgraphics.apache.org/fop/extensions">
+      <fo:layout-master-set>
+        <fo:simple-page-master margin-right="1cm" margin-left="1cm" margin-bottom="0.3cm" margin-top="1cm" page-width="21cm" page-height="29.7cm" master-name="all">
+          <fo:region-body column-count="4" margin-left="0cm" margin-bottom="1cm"/>
+        </fo:simple-page-master>
+      </fo:layout-master-set>
+      <fo:page-sequence master-reference="all">
+        <fo:flow flow-name="xsl-region-body">
+          <fo:table table-layout="fixed" width="100%">
+            <fo:table-column column-width="proportional-column-width(1)" />
+            <fo:table-header>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>header</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-header>
+            <fo:table-footer>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>footer</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-footer>
+            <fo:table-body>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="36">1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">3</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">4</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="6">5</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="6">6</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">7</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">8</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">9</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-body>
+          </fo:table>
+          <fo:block span="all">spanning</fo:block>
+        </fo:flow>
+      </fo:page-sequence>
+    </fo:root>
+  </fo>
+  <checks>
+    <eval expected="4" xpath="//span[1]/flow[2]/block[1]/block[4]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="7" xpath="//span[1]/flow[3]/block[1]/block[4]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="8" xpath="//span[1]/flow[4]/block[1]/block[2]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+  </checks>
+</testcase>
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 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  Licensed to the Apache Software Foundation (ASF) under one or more
+  contributor license agreements.  See the NOTICE file distributed with
+  this work for additional information regarding copyright ownership.
+  The ASF licenses this file to You under the Apache License, Version 2.0
+  (the "License"); you may not use this file except in compliance with
+  the License.  You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+  Unless required by applicable law or agreed to in writing, software
+  distributed under the License is distributed on an "AS IS" BASIS,
+  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  See the License for the specific language governing permissions and
+  limitations under the License.
+-->
+<!-- $Id$ -->
+<testcase>
+  <info>
+    <p>
+      This test checks column balancing with different row heights.
+    </p>
+  </info>
+  <fo>
+    <fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format" xmlns:fox="http://xmlgraphics.apache.org/fop/extensions">
+      <fo:layout-master-set>
+        <fo:simple-page-master margin-right="1cm" margin-left="1cm" margin-bottom="0.3cm" margin-top="1cm" page-width="21cm" page-height="29.7cm" master-name="all">
+          <fo:region-body column-count="4" margin-left="0cm" margin-bottom="1cm"/>
+        </fo:simple-page-master>
+      </fo:layout-master-set>
+      <fo:page-sequence master-reference="all">
+        <fo:flow flow-name="xsl-region-body">
+          <fo:table table-layout="fixed" width="100%">
+            <fo:table-column column-width="proportional-column-width(1)" />
+            <fo:table-header>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>header</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-header>
+            <fo:table-footer>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block>footer</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-footer>
+            <fo:table-body>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="36">1</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">2</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">3</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">4</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">5</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">6</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="6">7</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="6">8</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+              <fo:table-row>
+                <fo:table-cell>
+                  <fo:block>
+                    <fo:block font-size="12">9</fo:block>
+                  </fo:block>
+                </fo:table-cell>
+              </fo:table-row>
+            </fo:table-body>
+          </fo:table>
+          <fo:block span="all">spanning</fo:block>
+        </fo:flow>
+      </fo:page-sequence>
+    </fo:root>
+  </fo>
+  <checks>
+    <eval expected="1" xpath="//span[1]/flow[1]/block[1]/block[2]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="4" xpath="//span[1]/flow[2]/block[1]/block[4]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="6" xpath="//span[1]/flow[3]/block[1]/block[3]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+    <eval expected="7" xpath="//span[1]/flow[4]/block[1]/block[2]/block[1]/block[1]/lineArea[1]/text[1]/word[1]"/>
+  </checks>
+</testcase>
author	Luis Bernardo <lbernardo@apache.org>	2012-12-10 00:31:43 +0000
committer	Luis Bernardo <lbernardo@apache.org>	2012-12-10 00:31:43 +0000
commit	0d4b815b26a14f6dda80d7986649232534a36fe6 (patch)
tree	8caaadec6adbf0393936ffc9cafd99e92d6487a6
parent	11e2a41b637131bc7908c62437fd07dba5b82623 (diff)
download	xmlgraphics-fop-0d4b815b26a14f6dda80d7986649232534a36fe6.tar.gz xmlgraphics-fop-0d4b815b26a14f6dda80d7986649232534a36fe6.zip