fop-core/src/main/java/org/apache/fop/layoutmgr/BalancingColumnBreakingAlgorithm.java - xmlgraphics-fop - Git at Google

 /*
  * 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$ */

 package org.apache.fop.layoutmgr;

 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;

 import org.apache.fop.traits.MinOptMax;

 /**
  * This is a the breaking algorithm that is responsible for balancing columns in multi-column
  * layout.
  */
 public class BalancingColumnBreakingAlgorithm extends PageBreakingAlgorithm {

     private int columnCount;
     private List<Integer> idealBreaks;

     public BalancingColumnBreakingAlgorithm(LayoutManager topLevelLM,
             PageProvider pageProvider,
             PageBreakingLayoutListener layoutListener,
             int alignment, int alignmentLast,
             MinOptMax footnoteSeparatorLength,
             boolean partOverflowRecovery,
             int columnCount) {
         super(topLevelLM, pageProvider, layoutListener,
                 alignment, alignmentLast,
                 footnoteSeparatorLength, partOverflowRecovery, false, false);
         this.columnCount = columnCount;
         this.considerTooShort = true; //This is important!
     }

     /** {@inheritDoc} */
     protected double computeDemerits(KnuthNode activeNode,
             KnuthElement element, int fitnessClass, double r) {
         double demerits = Double.MAX_VALUE;
         if (idealBreaks == null) {
             idealBreaks = calculateIdealBreaks(activeNode.position);
         }
         LinkedList<Integer> curPossibility = getPossibilityTrail(activeNode);
         boolean notIdeal = false;
         int idealDemerit = columnCount + 1 - curPossibility.size();
         if (curPossibility.size() > idealBreaks.size()) {
             return demerits;
         }
         for (int breakPos = 0; breakPos < curPossibility.size(); breakPos++) {
             if (curPossibility.get(breakPos) != 0
                     && !curPossibility.get(breakPos).equals(idealBreaks.get(breakPos))) {
                 notIdeal = true;
                 break;
             }
         }
         if (!notIdeal) {
             demerits = idealDemerit;
         }
         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;
         }

         @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;
             }
         }

         @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;
             }
         }
         assert initialColumns.size() == columnCount - 1;
         initialColumns.add(new ColumnContent(colStartIndex, par.size() - 1));
         return initialColumns;
     }

     private int getNextStartIndex(int breakIndex) {
         int startIndex = breakIndex;
         @SuppressWarnings("unchecked")
         Iterator<KnuthElement> iter = par.listIterator(breakIndex);
         while (iter.hasNext() && !(iter.next() instanceof KnuthBox)) {
             startIndex++;
         }
         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 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;
     }
 }
	/*
	* 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$ */

	package org.apache.fop.layoutmgr;

	import java.util.ArrayList;
	import java.util.Iterator;
	import java.util.LinkedList;
	import java.util.List;

	import org.apache.fop.traits.MinOptMax;

	/**
	* This is a the breaking algorithm that is responsible for balancing columns in multi-column
	* layout.
	*/
	public class BalancingColumnBreakingAlgorithm extends PageBreakingAlgorithm {

	private int columnCount;
	private List<Integer> idealBreaks;

	public BalancingColumnBreakingAlgorithm(LayoutManager topLevelLM,
	PageProvider pageProvider,
	PageBreakingLayoutListener layoutListener,
	int alignment, int alignmentLast,
	MinOptMax footnoteSeparatorLength,
	boolean partOverflowRecovery,
	int columnCount) {
	super(topLevelLM, pageProvider, layoutListener,
	alignment, alignmentLast,
	footnoteSeparatorLength, partOverflowRecovery, false, false);
	this.columnCount = columnCount;
	this.considerTooShort = true; //This is important!
	}

	/** {@inheritDoc} */
	protected double computeDemerits(KnuthNode activeNode,
	KnuthElement element, int fitnessClass, double r) {
	double demerits = Double.MAX_VALUE;
	if (idealBreaks == null) {
	idealBreaks = calculateIdealBreaks(activeNode.position);
	}
	LinkedList<Integer> curPossibility = getPossibilityTrail(activeNode);
	boolean notIdeal = false;
	int idealDemerit = columnCount + 1 - curPossibility.size();
	if (curPossibility.size() > idealBreaks.size()) {
	return demerits;
	}
	for (int breakPos = 0; breakPos < curPossibility.size(); breakPos++) {
	if (curPossibility.get(breakPos) != 0
	&& !curPossibility.get(breakPos).equals(idealBreaks.get(breakPos))) {
	notIdeal = true;
	break;
	}
	}
	if (!notIdeal) {
	demerits = idealDemerit;
	}
	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;
	}

	@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;
	}
	}

	@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;
	}
	}
	assert initialColumns.size() == columnCount - 1;
	initialColumns.add(new ColumnContent(colStartIndex, par.size() - 1));
	return initialColumns;
	}

	private int getNextStartIndex(int breakIndex) {
	int startIndex = breakIndex;
	@SuppressWarnings("unchecked")
	Iterator<KnuthElement> iter = par.listIterator(breakIndex);
	while (iter.hasNext() && !(iter.next() instanceof KnuthBox)) {
	startIndex++;
	}
	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 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;
	}
	}