path: root/src/java/org/apache/fop/layoutmgr/table/TableStepper.java

/*
 * Copyright 2005 The Apache Software Foundation.
 *
 * Licensed 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.table;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.apache.fop.fo.Constants;
import org.apache.fop.fo.FONode;
import org.apache.fop.fo.flow.TableRow;
import org.apache.fop.layoutmgr.BreakElement;
import org.apache.fop.layoutmgr.ElementListUtils;
import org.apache.fop.layoutmgr.KnuthBox;
import org.apache.fop.layoutmgr.KnuthElement;
import org.apache.fop.layoutmgr.KnuthPenalty;
import org.apache.fop.layoutmgr.LayoutContext;
import org.apache.fop.layoutmgr.table.TableContentLayoutManager.GridUnitPart;
import org.apache.fop.layoutmgr.table.TableContentLayoutManager.TableContentPosition;
import org.apache.fop.layoutmgr.table.TableContentLayoutManager.TableHFPenaltyPosition;

/**
 * This class processes row groups to create combined element lists for tables.
 */
public class TableStepper {

    /** Logger **/
    private static Log log = LogFactory.getLog(TableStepper.class);

    private TableContentLayoutManager tclm;
    
    private EffRow[] rowGroup;
    private int totalHeight;
    private int activeRow;
    private List[] elementLists;
    private int[] startRow;
    private int[] start;
    private int[] end;
    private int[] widths;
    private int[] baseWidth;
    private int[] borderBefore;
    private int[] paddingBefore;
    private int[] borderAfter;
    private int[] paddingAfter;
    private boolean rowBacktrackForLastStep;
    private boolean skippedStep;
    private boolean[] keepWithNextSignals;
    private boolean[] forcedBreaks;
    
    /**
     * Main constructor
     * @param tclm The parent TableContentLayoutManager
     */
    public TableStepper(TableContentLayoutManager tclm) {
        this.tclm = tclm;
        this.activeRow = 0;
    }
    
    private void setup(int columnCount) {
        elementLists = new List[columnCount];
        startRow = new int[columnCount];
        start = new int[columnCount];
        end = new int[columnCount];
        widths = new int[columnCount];
        baseWidth = new int[columnCount];
        borderBefore = new int[columnCount];
        paddingBefore = new int[columnCount];
        borderAfter = new int[columnCount];
        paddingAfter = new int[columnCount];
        keepWithNextSignals = new boolean[columnCount];
        forcedBreaks = new boolean[columnCount];
        Arrays.fill(end, -1);
    }
    
    private void clearBreakCondition() {
        Arrays.fill(forcedBreaks, false);
    }
    
    private boolean isBreakCondition() {
        for (int i = 0; i < forcedBreaks.length; i++) {
            if (forcedBreaks[i]) {
                return true;
            }
        }
        return false;
    }
    
    private EffRow getActiveRow() {
        return rowGroup[activeRow];
    }
    
    private GridUnit getActiveGridUnit(int column) {
        return getActiveRow().safelyGetGridUnit(column);
    }
    
    private PrimaryGridUnit getActivePrimaryGridUnit(int column) {
        GridUnit gu = getActiveGridUnit(column);
        if (gu == null) {
            return null;
        } else {
            return gu.getPrimary();
        }
    }
    
    private void calcTotalHeight() {
        totalHeight = 0;
        for (int i = 0; i < rowGroup.length; i++) {
            totalHeight += rowGroup[i].getHeight().opt;
        }
        log.debug("totalHeight=" + totalHeight);
    }
    
    private int getMaxRemainingHeight() {
        int maxW = 0;
        if (!rowBacktrackForLastStep) {
            for (int i = 0; i < widths.length; i++) {
                if (elementLists[i] == null) {
                    continue;
                }
                if (end[i] == elementLists[i].size() - 1) {
                    continue;
                }
                GridUnit gu = getActiveGridUnit(i); 
                if (!gu.isLastGridUnitRowSpan()) {
                    continue;
                }
                int len = widths[i]; 
                if (len > 0) {
                    len += 2 * getTableLM().getHalfBorderSeparationBPD();
                    len += borderBefore[i] + borderAfter[i]; 
                    len += paddingBefore[i] + paddingAfter[i]; 
                }
                int nominalHeight = rowGroup[activeRow].getHeight().opt;
                for (int r = 0; r < gu.getRowSpanIndex(); r++) {
                    nominalHeight += rowGroup[activeRow - r - 1].getHeight().opt;
                }
                if (len == nominalHeight) {
                    //row is filled
                    maxW = 0;
                    break;
                }
                maxW = Math.max(maxW, nominalHeight - len);
            }
        }
        for (int i = activeRow + 1; i < rowGroup.length; i++) {
            maxW += rowGroup[i].getHeight().opt;
        }
        //log.debug("maxRemainingHeight=" + maxW);
        return maxW;
    }

    private void setupElementList(int column) {
        GridUnit gu = getActiveGridUnit(column);
        EffRow row = getActiveRow();
        if (gu == null || gu.isEmpty()) {
            elementLists[column] = null;
            start[column] = 0;
            end[column] = -1;
            widths[column] = 0;
            startRow[column] = activeRow;
            keepWithNextSignals[column] = false;
            forcedBreaks[column] = false;
        } else if (gu.isPrimary()) {
            PrimaryGridUnit pgu = (PrimaryGridUnit)gu;
            boolean makeBoxForWholeRow = false;
            if (row.getExplicitHeight().min > 0) {
                boolean contentsSmaller = ElementListUtils.removeLegalBreaks(
                        pgu.getElements(), row.getExplicitHeight());
                if (contentsSmaller) {
                    makeBoxForWholeRow = true;
                }
            }
            if (pgu.isLastGridUnitRowSpan() && pgu.getRow() != null) {
                makeBoxForWholeRow |= pgu.getRow().mustKeepTogether();
                makeBoxForWholeRow |= pgu.getTable().mustKeepTogether();
            }
            if (makeBoxForWholeRow) {
                List list = new java.util.ArrayList(1);
                int height = row.getExplicitHeight().opt;
                if (height == 0) {
                    height = row.getHeight().opt;
                }
                list.add(new KnuthBoxCellWithBPD(height, pgu));
                elementLists[column] = list;
            } else {
                //Copy elements (LinkedList) to array lists to improve 
                //element access performance
                elementLists[column] = new java.util.ArrayList(pgu.getElements());
            }
            if (isSeparateBorderModel()) {
                borderBefore[column] = pgu.getBorders().getBorderBeforeWidth(false);
            } else {
                borderBefore[column] = pgu.getBorders().getBorderBeforeWidth(false) / 2;
            }
            paddingBefore[column] = pgu.getBorders().getPaddingBefore(false, pgu.getCellLM());
            paddingAfter[column] = pgu.getBorders().getPaddingAfter(false, pgu.getCellLM());
            start[column] = 0;
            end[column] = -1;
            widths[column] = 0;
            startRow[column] = activeRow;
            keepWithNextSignals[column] = false;
            forcedBreaks[column] = false;
        }
    }
    
    private void initializeElementLists() {
        for (int i = 0; i < start.length; i++) {
            setupElementList(i);
        }
    }

    /**
     * Creates the combined element list for a row group.
     * @param context Active LayoutContext
     * @param rowGroup the row group
     * @param maxColumnCount the maximum number of columns to expect
     * @param bodyType Indicates what type of body is processed (boder, header or footer)
     * @return the combined element list
     */
    public LinkedList getCombinedKnuthElementsForRowGroup(
            LayoutContext context,
            EffRow[] rowGroup, int maxColumnCount, int bodyType) {
        this.rowGroup = rowGroup;
        setup(maxColumnCount);
        initializeElementLists();
        calcTotalHeight();
        
        boolean signalKeepWithNext = false;
        int laststep = 0;
        int step;
        int addedBoxLen = 0;
        TableContentPosition lastTCPos = null;
        LinkedList returnList = new LinkedList();
        while ((step = getNextStep(laststep)) >= 0) {
            int normalRow = activeRow;
            if (rowBacktrackForLastStep) {
                //Even though we've already switched to the next row, we have to 
                //calculate as if we were still on the previous row
                activeRow--;
            }
            int increase = step - laststep;
            int penaltyLen = step + getMaxRemainingHeight() - totalHeight;
            int boxLen = step - addedBoxLen - penaltyLen;
            addedBoxLen += boxLen;
            
            //Put all involved grid units into a list
            List gridUnitParts = new java.util.ArrayList(maxColumnCount);
            for (int i = 0; i < start.length; i++) {
                if (end[i] >= start[i]) {
                    PrimaryGridUnit pgu = rowGroup[startRow[i]].getGridUnit(i).getPrimary();
                    if (start[i] == 0 && end[i] == 0 
                            && elementLists[i].size() == 1
                            && elementLists[i].get(0) instanceof KnuthBoxCellWithBPD) {
                        //Special case: Cell with fixed BPD
                        gridUnitParts.add(new GridUnitPart(pgu, 
                                0, pgu.getElements().size() - 1));
                    } else {
                        gridUnitParts.add(new GridUnitPart(pgu, start[i], end[i]));
                    }
                    if (end[i] + 1 == elementLists[i].size()) {
                        if (pgu.getFlag(GridUnit.KEEP_WITH_NEXT_PENDING)) {
                            log.debug("PGU has pending keep-with-next");
                            keepWithNextSignals[i] = true;
                        }
                        if (pgu.getRow() != null && pgu.getRow().mustKeepWithNext()) {
                            log.debug("table-row causes keep-with-next");
                            keepWithNextSignals[i] = true;
                        }
                    }
                    if (start[i] == 0 && end[i] >= 0) {
                        if (pgu.getFlag(GridUnit.KEEP_WITH_PREVIOUS_PENDING)) {
                            log.debug("PGU has pending keep-with-previous");
                            if (returnList.size() == 0) {
                                context.setFlags(LayoutContext.KEEP_WITH_PREVIOUS_PENDING);
                            }
                        }
                        if (pgu.getRow() != null && pgu.getRow().mustKeepWithPrevious()) {
                            log.debug("table-row causes keep-with-previous");
                            if (returnList.size() == 0) {
                                context.setFlags(LayoutContext.KEEP_WITH_PREVIOUS_PENDING);
                            }
                        }
                    }
                }
            }
            //log.debug(">>> guPARTS: " + gridUnitParts);
            
            //Create elements for step
            int effPenaltyLen = penaltyLen;
            TableContentPosition tcpos = new TableContentPosition(getTableLM(), 
                    gridUnitParts, rowGroup[normalRow]);
            if (returnList.size() == 0) {
                tcpos.setFlag(TableContentPosition.FIRST_IN_ROWGROUP, true);
            }
            lastTCPos = tcpos;
            if (log.isDebugEnabled()) {
                log.debug(" - backtrack=" + rowBacktrackForLastStep 
                        + " - row=" + activeRow + " - " + tcpos);
            }
            returnList.add(new KnuthBox(boxLen, tcpos, false));
            TableHFPenaltyPosition penaltyPos = new TableHFPenaltyPosition(getTableLM());
            if (bodyType == TableRowIterator.BODY) {
                if (!getTableLM().getTable().omitHeaderAtBreak()) {
                    effPenaltyLen += tclm.getHeaderNetHeight();
                    penaltyPos.headerElements = tclm.getHeaderElements();
                }
                if (!getTableLM().getTable().omitFooterAtBreak()) {
                    effPenaltyLen += tclm.getFooterNetHeight();
                    penaltyPos.footerElements = tclm.getFooterElements();
                }
            }
            int p = 0;
            boolean allCellsHaveContributed = true;
            signalKeepWithNext = false;
            for (int i = 0; i < start.length; i++) {
                if (start[i] == 0 && end[i] < 0 && elementLists[i] != null) {
                    allCellsHaveContributed = false;
                }
                signalKeepWithNext |= keepWithNextSignals[i];
            }
            if (!allCellsHaveContributed) {
                //Not all cells have contributed to a newly started row. The penalty here is
                //used to avoid breaks resulting in badly broken tables.
                //See also: http://marc.theaimsgroup.com/?t=112248999600005&r=1&w=2
                p = 900; //KnuthPenalty.INFINITE; //TODO Arbitrary value. Please refine.
            }
            if (signalKeepWithNext || getTableLM().mustKeepTogether()) {
                p = KnuthPenalty.INFINITE;
            }
            if (skippedStep) {
                p = KnuthPenalty.INFINITE;
                //Need to avoid breaking because borders and/or paddding from other columns would
                //not fit in the available space (see getNextStep())
            }
            if (isBreakCondition()) {
                if (skippedStep) {
                    log.error("This is a conflict situation. The output may be wrong." 
                            + " Please send your FO file to fop-dev@xmlgraphics.apache.org!");
                }
                p = -KnuthPenalty.INFINITE; //Overrides any keeps (see 4.8 in XSL 1.0)
                clearBreakCondition();
            }
            //returnList.add(new KnuthPenalty(effPenaltyLen, p, false, penaltyPos, false));
            returnList.add(new BreakElement(penaltyPos, effPenaltyLen, p, 0, context));

            log.debug("step=" + step + " (+" + increase + ")"
                    + " box=" + boxLen 
                    + " penalty=" + penaltyLen
                    + " effPenalty=" + effPenaltyLen);
            
            laststep = step;
            if (rowBacktrackForLastStep) {
                //If row was set to previous, restore now
                activeRow++;
            }
        }
        if (signalKeepWithNext) {
            //Last step signalled a keep-with-next. Since the last penalty will be removed,
            //we have to signal the still pending last keep-with-next using the LayoutContext.
            context.setFlags(LayoutContext.KEEP_WITH_NEXT_PENDING);
        }
        if (isBreakCondition()) {
            ((BreakElement)returnList.getLast()).setPenaltyValue(-KnuthPenalty.INFINITE);
        }
        if (lastTCPos != null) {
            lastTCPos.setFlag(TableContentPosition.LAST_IN_ROWGROUP, true);
        }
        return returnList;
    }
    
    private int getNextStep(int lastStep) {
        //Check for forced break conditions
        /*
        if (isBreakCondition()) {
            return -1;
        }*/
        
        int[] backupWidths = new int[start.length];
        System.arraycopy(widths, 0, backupWidths, 0, backupWidths.length);

        //set starting points
        int rowPendingIndicator = 0;
        for (int i = 0; i < start.length; i++) {
            if (elementLists[i] == null) {
                continue;
            }
            if (end[i] < elementLists[i].size()) {
                start[i] = end[i] + 1;
                if (end[i] + 1 < elementLists[i].size() 
                        && getActiveGridUnit(i).isLastGridUnitRowSpan()) {
                    rowPendingIndicator++;
                }
            } else {
                start[i] = -1; //end of list reached
                end[i] = -1;
            }
        }

        if (rowPendingIndicator == 0) {
            if (activeRow < rowGroup.length - 1) {
                TableRow rowFO = getActiveRow().getTableRow();
                if (rowFO != null && rowFO.getBreakAfter() != Constants.EN_AUTO) {
                    log.warn(FONode.decorateWithContextInfo(
                            "break-after ignored on table-row because of row spanning "
                            + "in progress (See XSL 1.0, 7.19.1)", rowFO));
                }
                activeRow++;
                if (log.isDebugEnabled()) {
                    log.debug("===> new row: " + activeRow);
                }
                initializeElementLists();
                for (int i = 0; i < backupWidths.length; i++) {
                    if (end[i] < 0) {
                        backupWidths[i] = 0;
                    }
                }
                rowFO = getActiveRow().getTableRow();
                if (rowFO != null && rowFO.getBreakBefore() != Constants.EN_AUTO) {
                    log.warn(FONode.decorateWithContextInfo(
                            "break-before ignored on table-row because of row spanning "
                            + "in progress (See XSL 1.0, 7.19.2)", rowFO));
                }
            }
        }

        //Get next possible sequence for each cell
        int seqCount = 0;
        for (int i = 0; i < start.length; i++) {
            if (elementLists[i] == null) {
                continue;
            }
            while (end[i] + 1 < elementLists[i].size()) {
                end[i]++;
                KnuthElement el = (KnuthElement)elementLists[i].get(end[i]);
                if (el.isPenalty()) {
                    if (el.getP() <= -KnuthElement.INFINITE) {
                        log.debug("FORCED break encountered!");
                        forcedBreaks[i] = true;
                        break;
                    } else if (el.getP() < KnuthElement.INFINITE) {
                        //First legal break point
                        break;
                    }
                } else if (el.isGlue()) {
                    if (end[i] > 0) {
                        KnuthElement prev = (KnuthElement)elementLists[i].get(end[i] - 1);
                        if (prev.isBox()) {
                            //Second legal break point
                            break;
                        }
                    }
                    widths[i] += el.getW();
                } else {
                    widths[i] += el.getW();
                }
            }
            if (end[i] < start[i]) {
                widths[i] = backupWidths[i];
            } else {
                seqCount++;
            }
            //log.debug("part " + start[i] + "-" + end[i] + " " + widths[i]);
            if (end[i] + 1 >= elementLists[i].size()) {
                //element list for this cell is finished
                if (isSeparateBorderModel()) {
                    borderAfter[i] = getActivePrimaryGridUnit(i)
                            .getBorders().getBorderAfterWidth(false);
                } else {
                    borderAfter[i] = getActivePrimaryGridUnit(i).getHalfMaxAfterBorderWidth();
                }
            } else {
                //element list for this cell is not finished
                if (isSeparateBorderModel()) {
                    borderAfter[i] = getActivePrimaryGridUnit(i)
                            .getBorders().getBorderAfterWidth(false);
                } else {
                    //TODO fix me!
                    borderAfter[i] = getActivePrimaryGridUnit(i).getHalfMaxAfterBorderWidth();
                }
            }
            if (log.isTraceEnabled()) {
                log.trace("borders before=" + borderBefore[i] + " after=" + borderAfter[i]);
                log.trace("padding before=" + paddingBefore[i] + " after=" + paddingAfter[i]);
            }
        }
        if (seqCount == 0) {
            return -1;
        }

        //Determine smallest possible step
        int minStep = Integer.MAX_VALUE;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < widths.length; i++) {
            baseWidth[i] = 0;
            for (int prevRow = 0; prevRow < startRow[i]; prevRow++) {
                baseWidth[i] += rowGroup[prevRow].getHeight().opt;
            }
            baseWidth[i] += 2 * getTableLM().getHalfBorderSeparationBPD();
            baseWidth[i] += borderBefore[i] + borderAfter[i];
            baseWidth[i] += paddingBefore[i] + paddingAfter[i];
            if (end[i] >= start[i]) {
                int len = baseWidth[i] + widths[i];
                sb.append(len + " ");
                minStep = Math.min(len, minStep);
            }
        }
        if (log.isDebugEnabled()) {
            log.debug("candidate steps: " + sb + " lastStep=" + lastStep);
        }

        //Check for constellations that would result in overlapping borders
        /*
        for (int i = 0; i < widths.length; i++) {
            
        }*/
        
        //Reset bigger-than-minimum sequences
        //See http://people.apache.org/~jeremias/fop/NextStepAlgoNotes.pdf
        rowBacktrackForLastStep = false;
        skippedStep = false;
        for (int i = 0; i < widths.length; i++) {
            int len = baseWidth[i] + widths[i];
            if (len > minStep) {
                widths[i] = backupWidths[i];
                end[i] = start[i] - 1;
                if (baseWidth[i] + widths[i] > minStep) {
                    log.debug("minStep vs. border/padding increase conflict:");
                    if (activeRow == 0) {
                        log.debug("  First row. Skip this step.");
                        skippedStep = true;
                    } else {
                        log.debug("  row-span situation: backtracking to last row");
                        //Stay on the previous row for another step because borders and padding on 
                        //columns may make their contribution to the step bigger than the addition
                        //of the next element for this step would make the step to grow.
                        rowBacktrackForLastStep = true;
                    }
                }
            }
        }
        if (log.isDebugEnabled()) {
            /*StringBuffer*/ sb = new StringBuffer();
            for (int i = 0; i < widths.length; i++) {
                if (end[i] >= start[i]) {
                    sb.append(i + ": " + start[i] + "-" + end[i] + "(" + widths[i] + "), ");
                } else {
                    sb.append(i + ": skip, ");
                }
            }
            log.debug(sb.toString());
        }

        return minStep;
    }
    
    
    /** @return true if the table uses the separate border model. */
    private boolean isSeparateBorderModel() {
        return getTableLM().getTable().isSeparateBorderModel();
    }

    /** @return the table layout manager */
    private TableLayoutManager getTableLM() {
        return this.tclm.getTableLM();
    }

    private class KnuthBoxCellWithBPD extends KnuthBox {
        
        private PrimaryGridUnit pgu;
        
        public KnuthBoxCellWithBPD(int w, PrimaryGridUnit pgu) {
            super(w, null, true);
            this.pgu = pgu;
        }
    }
    
}