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: BalancingColumnBreakingAlgorithm.java 1427143 2012-12-31 14:46:01Z gadams $ */ 19 20 package org.apache.fop.layoutmgr; 21 22 import java.util.ArrayList; 23 import java.util.Iterator; 24 import java.util.LinkedList; 25 import java.util.List; 26 27 import org.apache.fop.traits.MinOptMax; 28 29 /** 30 * This is a the breaking algorithm that is responsible for balancing columns in multi-column 31 * layout. 32 */ 33 public class BalancingColumnBreakingAlgorithm extends PageBreakingAlgorithm { 34 35 private int columnCount; 36 private List<Integer> idealBreaks; 37 BalancingColumnBreakingAlgorithm(LayoutManager topLevelLM, PageProvider pageProvider, PageBreakingLayoutListener layoutListener, int alignment, int alignmentLast, MinOptMax footnoteSeparatorLength, boolean partOverflowRecovery, int columnCount)38 public BalancingColumnBreakingAlgorithm(LayoutManager topLevelLM, 39 PageProvider pageProvider, 40 PageBreakingLayoutListener layoutListener, 41 int alignment, int alignmentLast, 42 MinOptMax footnoteSeparatorLength, 43 boolean partOverflowRecovery, 44 int columnCount) { 45 super(topLevelLM, pageProvider, layoutListener, 46 alignment, alignmentLast, 47 footnoteSeparatorLength, partOverflowRecovery, false, false); 48 this.columnCount = columnCount; 49 this.considerTooShort = true; //This is important! 50 } 51 52 /** {@inheritDoc} */ computeDemerits(KnuthNode activeNode, KnuthElement element, int fitnessClass, double r)53 protected double computeDemerits(KnuthNode activeNode, 54 KnuthElement element, int fitnessClass, double r) { 55 double demerits = Double.MAX_VALUE; 56 if (idealBreaks == null) { 57 idealBreaks = calculateIdealBreaks(activeNode.position); 58 } 59 LinkedList<Integer> curPossibility = getPossibilityTrail(activeNode); 60 boolean notIdeal = false; 61 int idealDemerit = columnCount + 1 - curPossibility.size(); 62 if (curPossibility.size() > idealBreaks.size()) { 63 return demerits; 64 } 65 for (int breakPos = 0; breakPos < curPossibility.size(); breakPos++) { 66 if (curPossibility.get(breakPos) != 0 67 && !curPossibility.get(breakPos).equals(idealBreaks.get(breakPos))) { 68 notIdeal = true; 69 break; 70 } 71 } 72 if (!notIdeal) { 73 demerits = idealDemerit; 74 } 75 return demerits; 76 } 77 calculateIdealBreaks(int startPos)78 private List<Integer> calculateIdealBreaks(int startPos) { 79 List<ColumnContent> previousPreviousBreaks = null; 80 List<ColumnContent> previousBreaks = null; 81 List<ColumnContent> breaks = new ArrayList<ColumnContent>(); 82 breaks.add(new ColumnContent(startPos, par.size() - 1)); 83 do { 84 previousPreviousBreaks = previousBreaks; 85 previousBreaks = breaks; 86 breaks = getInitialBreaks(startPos, getAverageColumnLength(breaks)); 87 } while (!breaks.equals(previousBreaks) && !breaks.equals(previousPreviousBreaks)); 88 breaks = sortElementsForBreaks(breaks); 89 return getElementIdBreaks(breaks, startPos); 90 } 91 92 private static final class ColumnContent { 93 94 public final int startIndex; 95 96 public final int endIndex; 97 ColumnContent(int startIndex, int endIndex)98 ColumnContent(int startIndex, int endIndex) { 99 this.startIndex = startIndex; 100 this.endIndex = endIndex; 101 } 102 103 @Override hashCode()104 public int hashCode() { 105 return startIndex << 16 | endIndex; 106 } 107 108 @Override equals(Object obj)109 public boolean equals(Object obj) { 110 if (!(obj instanceof ColumnContent)) { 111 return false; 112 } else { 113 ColumnContent other = (ColumnContent) obj; 114 return other.startIndex == startIndex && other.endIndex == endIndex; 115 } 116 } 117 118 @Override toString()119 public String toString() { 120 return startIndex + "-" + endIndex; 121 } 122 123 } 124 getAverageColumnLength(List<ColumnContent> columns)125 private int getAverageColumnLength(List<ColumnContent> columns) { 126 int totalLength = 0; 127 for (ColumnContent col : columns) { 128 totalLength += calcContentLength(par, col.startIndex, col.endIndex); 129 } 130 return totalLength / columnCount; 131 } 132 getInitialBreaks(int startIndex, int averageColLength)133 private List<ColumnContent> getInitialBreaks(int startIndex, int averageColLength) { 134 List<ColumnContent> initialColumns = new ArrayList<ColumnContent>(); 135 int colStartIndex = startIndex; 136 int totalLength = 0; 137 int idealBreakLength = averageColLength; 138 int previousBreakLength = 0; 139 int prevBreakIndex = startIndex; 140 boolean prevIsBox = false; 141 int colNumber = 1; 142 for (int i = startIndex; i < par.size(); i++) { 143 KnuthElement element = (KnuthElement) par.get(i); 144 if (isLegalBreak(i, prevIsBox)) { 145 int breakLength = totalLength 146 + (element instanceof KnuthPenalty ? element.getWidth() : 0); 147 if (breakLength > idealBreakLength && colNumber < columnCount) { 148 int breakIndex; 149 if (breakLength - idealBreakLength > idealBreakLength - previousBreakLength) { 150 breakIndex = prevBreakIndex; 151 totalLength = previousBreakLength; 152 } else { 153 breakIndex = element instanceof KnuthPenalty ? i : i - 1; 154 totalLength = breakLength; 155 } 156 initialColumns.add(new ColumnContent(colStartIndex, breakIndex)); 157 i = getNextStartIndex(breakIndex); 158 colStartIndex = i--; 159 colNumber++; 160 idealBreakLength += averageColLength; 161 } else { 162 previousBreakLength = breakLength; 163 prevBreakIndex = element instanceof KnuthPenalty ? i : i - 1; 164 prevIsBox = false; 165 } 166 } else { 167 totalLength += element instanceof KnuthPenalty ? 0 : element.getWidth(); 168 prevIsBox = element instanceof KnuthBox; 169 } 170 } 171 assert initialColumns.size() == columnCount - 1; 172 initialColumns.add(new ColumnContent(colStartIndex, par.size() - 1)); 173 return initialColumns; 174 } 175 getNextStartIndex(int breakIndex)176 private int getNextStartIndex(int breakIndex) { 177 int startIndex = breakIndex; 178 @SuppressWarnings("unchecked") 179 Iterator<KnuthElement> iter = par.listIterator(breakIndex); 180 while (iter.hasNext() && !(iter.next() instanceof KnuthBox)) { 181 startIndex++; 182 } 183 return startIndex; 184 } 185 sortElementsForBreaks(List<ColumnContent> breaks)186 private List<ColumnContent> sortElementsForBreaks(List<ColumnContent> breaks) { 187 boolean changes; 188 /* Relax factor to make balancing more visually appealing as in some cases 189 * strict balancing would lead to ragged column endings. */ 190 int fFactor = 4000; 191 do { 192 changes = false; 193 ColumnContent curColumn = breaks.get(breaks.size() - 1); 194 int curColLength = calcContentLength(par, curColumn.startIndex, curColumn.endIndex); 195 for (int colIndex = (breaks.size() - 1); colIndex > 0; colIndex--) { 196 ColumnContent prevColumn = breaks.get(colIndex - 1); 197 int prevColLength = calcContentLength(par, prevColumn.startIndex, prevColumn.endIndex); 198 if (prevColLength < curColLength) { 199 int newBreakIndex = curColumn.startIndex; 200 boolean prevIsBox = true; 201 while (newBreakIndex <= curColumn.endIndex && !(isLegalBreak(newBreakIndex, prevIsBox))) { 202 newBreakIndex++; 203 prevIsBox = par.get(newBreakIndex) instanceof KnuthBox; 204 } 205 if (newBreakIndex < curColumn.endIndex) { 206 if (prevIsBox) { 207 newBreakIndex--; 208 } 209 int newStartIndex = getNextStartIndex(newBreakIndex); 210 int newPrevColLength = calcContentLength(par, prevColumn.startIndex, newBreakIndex); 211 if (newPrevColLength <= fFactor + curColLength) { 212 prevColumn = new ColumnContent(prevColumn.startIndex, newBreakIndex); 213 breaks.set(colIndex - 1, prevColumn); 214 breaks.set(colIndex, new ColumnContent(newStartIndex, curColumn.endIndex)); 215 prevColLength = calcContentLength(par, prevColumn.startIndex, newBreakIndex); 216 changes = true; 217 } 218 } 219 } 220 curColLength = prevColLength; 221 curColumn = prevColumn; 222 } 223 } while (changes); 224 return breaks; 225 } 226 isLegalBreak(int index, boolean prevIsBox)227 private boolean isLegalBreak(int index, boolean prevIsBox) { 228 KnuthElement element = (KnuthElement) par.get(index); 229 return element instanceof KnuthPenalty && element.getPenalty() < KnuthPenalty.INFINITE 230 || prevIsBox && element instanceof KnuthGlue; 231 } 232 calcContentLength(KnuthSequence par, int startIndex, int endIndex)233 private int calcContentLength(KnuthSequence par, int startIndex, int endIndex) { 234 return ElementListUtils.calcContentLength(par, startIndex, endIndex) + getPenaltyWidth(endIndex); 235 } 236 getPenaltyWidth(int index)237 private int getPenaltyWidth(int index) { 238 KnuthElement element = (KnuthElement) par.get(index); 239 return element instanceof KnuthPenalty ? element.getWidth() : 0; 240 } 241 getElementIdBreaks(List<ColumnContent> breaks, int startPos)242 private List<Integer> getElementIdBreaks(List<ColumnContent> breaks, int startPos) { 243 List<Integer> elementIdBreaks = new ArrayList<Integer>(); 244 elementIdBreaks.add(startPos); 245 for (ColumnContent column : breaks) { 246 if (breaks.get(breaks.size() - 1).equals(column)) { 247 continue; 248 } 249 elementIdBreaks.add(column.endIndex); 250 } 251 return elementIdBreaks; 252 } 253 getPossibilityTrail(KnuthNode activeNode)254 private LinkedList<Integer> getPossibilityTrail(KnuthNode activeNode) { 255 LinkedList<Integer> trail = new LinkedList<Integer>(); 256 KnuthNode previous = activeNode; 257 do { 258 trail.addFirst(previous.position); 259 previous = previous.previous; 260 } while (previous != null); 261 return trail; 262 } 263 } 264