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