/*
 * 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 org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
import org.apache.fop.apps.FOPException;
import org.apache.fop.datatypes.Numeric;

import org.apache.fop.area.AreaTreeHandler;
import org.apache.fop.area.AreaTreeModel;
import org.apache.fop.area.Block;
import org.apache.fop.area.Footnote;
import org.apache.fop.area.PageViewport;
import org.apache.fop.area.LineArea;
import org.apache.fop.area.Resolvable;

import org.apache.fop.fo.Constants;
import org.apache.fop.fo.FONode;
import org.apache.fop.fo.FObj;
import org.apache.fop.fo.flow.Marker;
import org.apache.fop.fo.flow.RetrieveMarker;

import org.apache.fop.fo.pagination.Flow;
import org.apache.fop.fo.pagination.PageSequence;
import org.apache.fop.fo.pagination.Region;
import org.apache.fop.fo.pagination.RegionBody;
import org.apache.fop.fo.pagination.SideRegion;
import org.apache.fop.fo.pagination.SimplePageMaster;
import org.apache.fop.fo.pagination.StaticContent;
import org.apache.fop.layoutmgr.PageBreakingAlgorithm.PageBreakingLayoutListener;
import org.apache.fop.layoutmgr.inline.ContentLayoutManager;

import org.apache.fop.traits.MinOptMax;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

/**
 * LayoutManager for a PageSequence.  This class is instantiated by
 * area.AreaTreeHandler for each fo:page-sequence found in the
 * input document.
 */
public class PageSequenceLayoutManager extends AbstractLayoutManager {

    private static Log log = LogFactory.getLog(PageSequenceLayoutManager.class);

    /** 
     * AreaTreeHandler which activates the PSLM and controls
     * the rendering of its pages.
     */
    private AreaTreeHandler areaTreeHandler;

    /** 
     * fo:page-sequence formatting object being
     * processed by this class
     */
    private PageSequence pageSeq;

    private PageProvider pageProvider;
    
    /** 
     * Current page with page-viewport-area being filled by
     * the PSLM.
     */
    private Page curPage = null;

    /**
     * The FlowLayoutManager object, which processes
     * the single fo:flow of the fo:page-sequence
     */
    private FlowLayoutManager childFLM = null;

    private int startPageNum = 0;
    private int currentPageNum = 0;

    private Block separatorArea = null;
    
    /**
     * Constructor
     *
     * @param ath the area tree handler object
     * @param pseq fo:page-sequence to process
     */
    public PageSequenceLayoutManager(AreaTreeHandler ath, PageSequence pseq) {
        super(pseq);
        this.areaTreeHandler = ath;
        this.pageSeq = pseq;
        this.pageProvider = new PageProvider(this.pageSeq);
    }

    /**
     * @see org.apache.fop.layoutmgr.LayoutManager
     * @return the LayoutManagerMaker object
     */
    public LayoutManagerMaker getLayoutManagerMaker() {
        return areaTreeHandler.getLayoutManagerMaker();
    }

    /** @return the PageProvider applicable to this page-sequence. */
    public PageProvider getPageProvider() {
        return this.pageProvider;
    }
    
    /**
     * Activate the layout of this page sequence.
     * PageViewports corresponding to each page generated by this 
     * page sequence will be created and sent to the AreaTreeModel
     * for rendering.
     */
    public void activateLayout() {
        startPageNum = pageSeq.getStartingPageNumber();
        currentPageNum = startPageNum - 1;

        LineArea title = null;

        if (pageSeq.getTitleFO() != null) {
            try {
                ContentLayoutManager clm = getLayoutManagerMaker().
                    makeContentLayoutManager(this, pageSeq.getTitleFO());
                title = (LineArea) clm.getParentArea(null);
            } catch (IllegalStateException e) {
                // empty title; do nothing
            }
        }

        areaTreeHandler.getAreaTreeModel().startPageSequence(title);
        log.debug("Starting layout");

        curPage = makeNewPage(false, false);

        
        Flow mainFlow = pageSeq.getMainFlow();
        childFLM = getLayoutManagerMaker().
            makeFlowLayoutManager(this, mainFlow);

        PageBreaker breaker = new PageBreaker(this);
        int flowBPD = (int)getCurrentPV().getBodyRegion().getRemainingBPD();
        breaker.doLayout(flowBPD);

        finishPage();
    }
        
    /**
     * Finished the page-sequence and notifies everyone about it.
     */
    public void finishPageSequence() {
        if (!pageSeq.getId().equals("")) {
            areaTreeHandler.signalIDProcessed(pageSeq.getId());
        }

        pageSeq.getRoot().notifyPageSequenceFinished(currentPageNum,
                (currentPageNum - startPageNum) + 1);
        areaTreeHandler.notifyPageSequenceFinished(pageSeq,
                (currentPageNum - startPageNum) + 1);
        pageSeq.releasePageSequence();
        log.debug("Ending layout");
    }


    private class PageBreaker extends AbstractBreaker {
        
        private PageSequenceLayoutManager pslm;
        private boolean firstPart = true;
        private boolean pageBreakHandled;
        private boolean needColumnBalancing;
        
        private StaticContentLayoutManager footnoteSeparatorLM = null;

        public PageBreaker(PageSequenceLayoutManager pslm) {
            this.pslm = pslm;
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker */
        protected void updateLayoutContext(LayoutContext context) {
            int flowIPD = getCurrentPV().getCurrentSpan().getColumnWidth();
            context.setRefIPD(flowIPD);
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker#getTopLevelLM() */
        protected LayoutManager getTopLevelLM() {
            return pslm;
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker#getPageProvider() */
        protected PageSequenceLayoutManager.PageProvider getPageProvider() {
            return pageProvider;
        }
        
        /**
         * @see org.apache.fop.layoutmgr.AbstractBreaker#getLayoutListener()
         */
        protected PageBreakingLayoutListener getLayoutListener() {
            return new PageBreakingLayoutListener() {

                public void notifyOverflow(int part, FObj obj) {
                    Page p = pageProvider.getPage(
                                false, part, PageProvider.RELTO_CURRENT_ELEMENT_LIST);
                    RegionBody body = (RegionBody)p.getSimplePageMaster().getRegion(
                            Region.FO_REGION_BODY);
                    String err = FONode.decorateWithContextInfo(
                            "Content of the region-body on page " 
                            + p.getPageViewport().getPageNumberString() 
                            + " overflows the available area in block-progression dimension.", 
                            obj);
                    if (body.getOverflow() == Constants.EN_ERROR_IF_OVERFLOW) {
                        throw new RuntimeException(err);
                    } else {
                        PageSequenceLayoutManager.log.warn(err);
                    }
                }
                
            };
        }

        /** @see org.apache.fop.layoutmgr.AbstractBreaker */
        protected int handleSpanChange(LayoutContext childLC, int nextSequenceStartsOn) {
            needColumnBalancing = false;
            if (childLC.getNextSpan() != Constants.NOT_SET) {
                //Next block list will have a different span.
                nextSequenceStartsOn = childLC.getNextSpan();
                needColumnBalancing = (childLC.getNextSpan() == Constants.EN_ALL);
            }
            if (needColumnBalancing) {
                AbstractBreaker.log.debug(
                        "Column balancing necessary for the next element list!!!");
            }
            return nextSequenceStartsOn;
        }

        /** @see org.apache.fop.layoutmgr.AbstractBreaker */
        protected int getNextBlockList(LayoutContext childLC, 
                int nextSequenceStartsOn, 
                List blockLists) {
            if (!firstPart) {
                // if this is the first page that will be created by
                // the current BlockSequence, it could have a break
                // condition that must be satisfied;
                // otherwise, we may simply need a new page
                handleBreakTrait(nextSequenceStartsOn);
            }
            firstPart = false;
            pageBreakHandled = true;
            pageProvider.setStartOfNextElementList(currentPageNum, 
                    getCurrentPV().getCurrentSpan().getCurrentFlowIndex());
            return super.getNextBlockList(childLC, nextSequenceStartsOn, blockLists);
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker */
        protected LinkedList getNextKnuthElements(LayoutContext context, int alignment) {
            LinkedList contentList = null;
            
            while (!childFLM.isFinished() && contentList == null) {
                contentList = childFLM.getNextKnuthElements(context, alignment);
            }

            // scan contentList, searching for footnotes
            boolean bFootnotesPresent = false;
            if (contentList != null) {
                ListIterator contentListIterator = contentList.listIterator();
                while (contentListIterator.hasNext()) {
                    ListElement element = (ListElement) contentListIterator.next();
                    if (element instanceof KnuthBlockBox
                        && ((KnuthBlockBox) element).hasAnchors()) {
                        // element represents a line with footnote citations
                        bFootnotesPresent = true;
                        LayoutContext footnoteContext = new LayoutContext(context);
                        footnoteContext.setStackLimit(context.getStackLimit());
                        footnoteContext.setRefIPD(getCurrentPV()
                                .getRegionReference(Constants.FO_REGION_BODY).getIPD());
                        LinkedList footnoteBodyLMs = ((KnuthBlockBox) element).getFootnoteBodyLMs();
                        ListIterator footnoteBodyIterator = footnoteBodyLMs.listIterator();
                        // store the lists of elements representing the footnote bodies
                        // in the box representing the line containing their references
                        while (footnoteBodyIterator.hasNext()) {
                            FootnoteBodyLayoutManager fblm 
                                = (FootnoteBodyLayoutManager) footnoteBodyIterator.next();
                            fblm.setParent(childFLM);
                            fblm.initialize();
                            ((KnuthBlockBox) element).addElementList(
                                    fblm.getNextKnuthElements(footnoteContext, alignment));
                        }
                    }
                }
            }

            // handle the footnote separator
            StaticContent footnoteSeparator;
            if (bFootnotesPresent
                    && (footnoteSeparator = pageSeq.getStaticContent(
                                            "xsl-footnote-separator")) != null) {
                // the footnote separator can contain page-dependent content such as
                // page numbers or retrieve markers, so its areas cannot simply be 
                // obtained now and repeated in each page;
                // we need to know in advance the separator bpd: the actual separator
                // could be different from page to page, but its bpd would likely be
                // always the same

                // create a Block area that will contain the separator areas
                separatorArea = new Block();
                separatorArea.setIPD(pslm.getCurrentPV()
                            .getRegionReference(Constants.FO_REGION_BODY).getIPD());
                // create a StaticContentLM for the footnote separator
                footnoteSeparatorLM = (StaticContentLayoutManager)
                    getLayoutManagerMaker().makeStaticContentLayoutManager(
                    pslm, footnoteSeparator, separatorArea);
                footnoteSeparatorLM.doLayout();

                footnoteSeparatorLength = new MinOptMax(separatorArea.getBPD());
            }
            return contentList;
        }
        
        protected int getCurrentDisplayAlign() {
            return curPage.getSimplePageMaster().getRegion(
                    Constants.FO_REGION_BODY).getDisplayAlign();
        }
        
        protected boolean hasMoreContent() {
            return !childFLM.isFinished();
        }
        
        protected void addAreas(PositionIterator posIter, LayoutContext context) {
            if (footnoteSeparatorLM != null) {
                StaticContent footnoteSeparator = pageSeq.getStaticContent(
                        "xsl-footnote-separator");
                // create a Block area that will contain the separator areas
                separatorArea = new Block();
                separatorArea.setIPD(
                        getCurrentPV().getRegionReference(Constants.FO_REGION_BODY).getIPD());
                // create a StaticContentLM for the footnote separator
                footnoteSeparatorLM = (StaticContentLayoutManager)
                    getLayoutManagerMaker().makeStaticContentLayoutManager(
                    pslm, footnoteSeparator, separatorArea);
                footnoteSeparatorLM.doLayout();
            }

            childFLM.addAreas(posIter, context);    
        }
        
        protected void doPhase3(PageBreakingAlgorithm alg, int partCount, 
                BlockSequence originalList, BlockSequence effectiveList) {
            if (needColumnBalancing) {
                doPhase3WithColumnBalancing(alg, partCount, originalList, effectiveList);
            } else {
                if (!hasMoreContent() && pageSeq.hasPagePositionLast()) {
                    //last part is reached and we have a "last page" condition
                    doPhase3WithLastPage(alg, partCount, originalList, effectiveList);
                } else {
                    //Directly add areas after finding the breaks
                    addAreas(alg, partCount, originalList, effectiveList);
                }
            }
        }

        private void doPhase3WithLastPage(PageBreakingAlgorithm alg, int partCount, 
                BlockSequence originalList, BlockSequence effectiveList) {
            int newStartPos;
            int restartPoint = pageProvider.getStartingPartIndexForLastPage(partCount);
            if (restartPoint > 0) {
                //Add definitive areas before last page
                addAreas(alg, restartPoint, originalList, effectiveList);
                //Get page break from which we restart
                PageBreakPosition pbp = (PageBreakPosition)
                        alg.getPageBreaks().get(restartPoint - 1);
                newStartPos = pbp.getLeafPos();
                //Handle page break right here to avoid any side-effects
                if (newStartPos > 0) {
                    handleBreakTrait(EN_PAGE);
                }
            } else {
                newStartPos = 0;
            }
            AbstractBreaker.log.debug("Last page handling now!!!");
            AbstractBreaker.log.debug("===================================================");
            AbstractBreaker.log.debug("Restarting at " + restartPoint 
                    + ", new start position: " + newStartPos);

            pageBreakHandled = true;
            //Update so the available BPD is reported correctly
            pageProvider.setStartOfNextElementList(currentPageNum, 
                    getCurrentPV().getCurrentSpan().getCurrentFlowIndex());
            pageProvider.setLastPageIndex(currentPageNum);

            //Restart last page
            PageBreakingAlgorithm algRestart = new PageBreakingAlgorithm(
                    getTopLevelLM(),
                    getPageProvider(), getLayoutListener(),
                    alg.getAlignment(), alg.getAlignmentLast(), 
                    footnoteSeparatorLength,
                    isPartOverflowRecoveryActivated(), false, false);
            //alg.setConstantLineWidth(flowBPD);
            int iOptPageCount = algRestart.findBreakingPoints(effectiveList,
                        newStartPos,
                        1, true, BreakingAlgorithm.ALL_BREAKS);
            AbstractBreaker.log.debug("restart: iOptPageCount= " + iOptPageCount
                    + " pageBreaks.size()= " + algRestart.getPageBreaks().size());
            boolean replaceLastPage 
                    = iOptPageCount <= getCurrentPV().getBodyRegion().getColumnCount(); 
            if (replaceLastPage) {

                //Replace last page
                pslm.curPage = pageProvider.getPage(false, currentPageNum);
                //Make sure we only add the areas we haven't added already
                effectiveList.ignoreAtStart = newStartPos;
                addAreas(algRestart, iOptPageCount, originalList, effectiveList);
            } else {
                effectiveList.ignoreAtStart = newStartPos;
                addAreas(alg, restartPoint, partCount - restartPoint, originalList, effectiveList);
                //Add blank last page
                pageProvider.setLastPageIndex(currentPageNum + 1);
                pslm.curPage = makeNewPage(true, true);
            }
            AbstractBreaker.log.debug("===================================================");
        }

        private void doPhase3WithColumnBalancing(PageBreakingAlgorithm alg, int partCount, 
                BlockSequence originalList, BlockSequence effectiveList) {
            AbstractBreaker.log.debug("Column balancing now!!!");
            AbstractBreaker.log.debug("===================================================");
            int newStartPos;
            int restartPoint = pageProvider.getStartingPartIndexForLastPage(partCount);
            if (restartPoint > 0) {
                //Add definitive areas
                addAreas(alg, restartPoint, originalList, effectiveList);
                //Get page break from which we restart
                PageBreakPosition pbp = (PageBreakPosition)
                        alg.getPageBreaks().get(restartPoint - 1);
                newStartPos = pbp.getLeafPos();
                //Handle page break right here to avoid any side-effects
                if (newStartPos > 0) {
                    handleBreakTrait(EN_PAGE);
                }
            } else {
                newStartPos = 0;
            }
            AbstractBreaker.log.debug("Restarting at " + restartPoint 
                    + ", new start position: " + newStartPos);

            pageBreakHandled = true;
            //Update so the available BPD is reported correctly
            pageProvider.setStartOfNextElementList(currentPageNum, 
                    getCurrentPV().getCurrentSpan().getCurrentFlowIndex());

            //Restart last page
            PageBreakingAlgorithm algRestart = new BalancingColumnBreakingAlgorithm(
                    getTopLevelLM(),
                    getPageProvider(), getLayoutListener(),
                    alignment, Constants.EN_START, footnoteSeparatorLength,
                    isPartOverflowRecoveryActivated(),
                    getCurrentPV().getBodyRegion().getColumnCount());
            //alg.setConstantLineWidth(flowBPD);
            int iOptPageCount = algRestart.findBreakingPoints(effectiveList,
                        newStartPos,
                        1, true, BreakingAlgorithm.ALL_BREAKS);
            AbstractBreaker.log.debug("restart: iOptPageCount= " + iOptPageCount
                    + " pageBreaks.size()= " + algRestart.getPageBreaks().size());
            if (iOptPageCount > getCurrentPV().getBodyRegion().getColumnCount()) {
                AbstractBreaker.log.warn(
                        "Breaking algorithm produced more columns than are available.");
                /* reenable when everything works
                throw new IllegalStateException(
                        "Breaking algorithm must not produce more columns than available.");
                */
            }
            //Make sure we only add the areas we haven't added already
            effectiveList.ignoreAtStart = newStartPos;
            addAreas(algRestart, iOptPageCount, originalList, effectiveList);
            AbstractBreaker.log.debug("===================================================");
        }
        
        protected void startPart(BlockSequence list, int breakClass) {
            AbstractBreaker.log.debug("startPart() breakClass=" + breakClass);
            if (curPage == null) {
                throw new IllegalStateException("curPage must not be null");
            }
            if (!pageBreakHandled) {
                
                //firstPart is necessary because we need the first page before we start the 
                //algorithm so we have a BPD and IPD. This may subject to change later when we
                //start handling more complex cases.
                if (!firstPart) {
                    // if this is the first page that will be created by
                    // the current BlockSequence, it could have a break
                    // condition that must be satisfied;
                    // otherwise, we may simply need a new page
                    handleBreakTrait(breakClass);
                }
                pageProvider.setStartOfNextElementList(currentPageNum, 
                        getCurrentPV().getCurrentSpan().getCurrentFlowIndex());
            }
            pageBreakHandled = false;
            // add static areas and resolve any new id areas
            // finish page and add to area tree
            firstPart = false;
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker#handleEmptyContent() */
        protected void handleEmptyContent() {
            getCurrentPV().getPage().fakeNonEmpty();
        }
        
        protected void finishPart(PageBreakingAlgorithm alg, PageBreakPosition pbp) {
            // add footnote areas
            if (pbp.footnoteFirstListIndex < pbp.footnoteLastListIndex
                || pbp.footnoteFirstElementIndex <= pbp.footnoteLastElementIndex) {
                // call addAreas() for each FootnoteBodyLM
                for (int i = pbp.footnoteFirstListIndex; i <= pbp.footnoteLastListIndex; i++) {
                    LinkedList elementList = alg.getFootnoteList(i);
                    int firstIndex = (i == pbp.footnoteFirstListIndex 
                            ? pbp.footnoteFirstElementIndex : 0);
                    int lastIndex = (i == pbp.footnoteLastListIndex 
                            ? pbp.footnoteLastElementIndex : elementList.size() - 1);

                    SpaceResolver.performConditionalsNotification(elementList, 
                            firstIndex, lastIndex, -1);
                    LayoutContext childLC = new LayoutContext(0);
                    AreaAdditionUtil.addAreas(null, 
                            new KnuthPossPosIter(elementList, firstIndex, lastIndex + 1), 
                            childLC);
                }
                // set the offset from the top margin
                Footnote parentArea = (Footnote) getCurrentPV().getBodyRegion().getFootnote();
                int topOffset = (int) getCurrentPV().getBodyRegion().getBPD() - parentArea.getBPD();
                if (separatorArea != null) {
                    topOffset -= separatorArea.getBPD();
                }
                parentArea.setTop(topOffset);
                parentArea.setSeparator(separatorArea);
            }
            getCurrentPV().getCurrentSpan().notifyFlowsFinished();
        }
        
        protected LayoutManager getCurrentChildLM() {
            return childFLM;
        }
        
        /** @see org.apache.fop.layoutmgr.AbstractBreaker#observeElementList(java.util.List) */
        protected void observeElementList(List elementList) {
            ElementListObserver.observe(elementList, "breaker", 
                    ((PageSequence)pslm.getFObj()).getId());
        }
        
    }
    
    /**
     * Provides access to the current page.
     * @return the current Page
     */
    public Page getCurrentPage() {
        return curPage;
    }

    /**
     * Provides access to the current page viewport.
     * @return the current PageViewport
     *//*
    public PageViewport getCurrentPageViewport() {
        return curPage.getPageViewport();
    }*/

    /**
     * Provides access to this object
     * @return this PageSequenceLayoutManager instance
     */
    public PageSequenceLayoutManager getPSLM() {
        return this;
    }
    
    /**
     * This returns the first PageViewport that contains an id trait
     * matching the idref argument, or null if no such PV exists.
     *
     * @param idref the idref trait needing to be resolved 
     * @return the first PageViewport that contains the ID trait
     */
    public PageViewport getFirstPVWithID(String idref) {
        List list = areaTreeHandler.getPageViewportsContainingID(idref);
        if (list != null && list.size() > 0) {
            return (PageViewport) list.get(0);
        }
        return null;
    }

    /**
     * This returns the last PageViewport that contains an id trait
     * matching the idref argument, or null if no such PV exists.
     *
     * @param idref the idref trait needing to be resolved 
     * @return the last PageViewport that contains the ID trait
     */
    public PageViewport getLastPVWithID(String idref) {
        List list = areaTreeHandler.getPageViewportsContainingID(idref);
        if (list != null && list.size() > 0) {
            return (PageViewport) list.get(list.size() - 1);
        }
        return null;
    }
    
    /**
     * Add an ID reference to the current page.
     * When adding areas the area adds its ID reference.
     * For the page layout manager it adds the id reference
     * with the current page to the area tree.
     *
     * @param id the ID reference to add
     */
    public void addIDToPage(String id) {
        if (id != null && id.length() > 0) {
            areaTreeHandler.associateIDWithPageViewport(id, curPage.getPageViewport());
        }
    }
    
    /**
     * Add an id reference of the layout manager in the AreaTreeHandler,
     * if the id hasn't been resolved yet
     * @param id the id to track
     * @return a boolean indicating if the id has already been resolved
     * TODO Maybe give this a better name
     */
    public boolean associateLayoutManagerID(String id) {
        if (log.isDebugEnabled()) {
            log.debug("associateLayoutManagerID(" + id + ")");
        }
        if (!areaTreeHandler.alreadyResolvedID(id)) {
            areaTreeHandler.signalPendingID(id);
            return false;
        } else {
            return true;
        }
    }
    
    /**
     * Notify the areaTreeHandler that the LayoutManagers containing
     * idrefs have finished creating areas
     * @param id the id for which layout has finished
     */
    public void notifyEndOfLayout(String id) {
        areaTreeHandler.signalIDProcessed(id);
    }
    
    /**
     * Identify an unresolved area (one needing an idref to be 
     * resolved, e.g. the internal-destination of an fo:basic-link)
     * for both the AreaTreeHandler and PageViewport object.
     * 
     * The AreaTreeHandler keeps a document-wide list of idref's
     * and the PV's needing them to be resolved.  It uses this to  
     * send notifications to the PV's when an id has been resolved.
     * 
     * The PageViewport keeps lists of id's needing resolving, along
     * with the child areas (page-number-citation, basic-link, etc.)
     * of the PV needing their resolution.
     *
     * @param id the ID reference to add
     * @param res the resolvable object that needs resolving
     */
    public void addUnresolvedArea(String id, Resolvable res) {
        curPage.getPageViewport().addUnresolvedIDRef(id, res);
        areaTreeHandler.addUnresolvedIDRef(id, curPage.getPageViewport());
    }

    /**
     * Bind the RetrieveMarker to the corresponding Marker subtree.
     * If the boundary is page then it will only check the
     * current page. For page-sequence and document it will
     * lookup preceding pages from the area tree and try to find
     * a marker.
     * If we retrieve a marker from a preceding page,
     * then the containing page does not have a qualifying area,
     * and all qualifying areas have ended.
     * Therefore we use last-ending-within-page (Constants.EN_LEWP)
     * as the position. 
     *
     * @param rm the RetrieveMarker instance whose properties are to
     * used to find the matching Marker.
     * @return a bound RetrieveMarker instance, or null if no Marker
     * could be found.
     */
    public RetrieveMarker resolveRetrieveMarker(RetrieveMarker rm) {
        AreaTreeModel areaTreeModel = areaTreeHandler.getAreaTreeModel();
        String name = rm.getRetrieveClassName();
        int pos = rm.getRetrievePosition();
        int boundary = rm.getRetrieveBoundary();               
        
        // get marker from the current markers on area tree
        Marker mark = (Marker)getCurrentPV().getMarker(name, pos);
        if (mark == null && boundary != EN_PAGE) {
            // go back over pages until mark found
            // if document boundary then keep going
            boolean doc = boundary == EN_DOCUMENT;
            int seq = areaTreeModel.getPageSequenceCount();
            int page = areaTreeModel.getPageCount(seq) - 1;
            while (page < 0 && doc && seq > 1) {
                seq--;
                page = areaTreeModel.getPageCount(seq) - 1;
            }
            while (page >= 0) {
                PageViewport pv = areaTreeModel.getPage(seq, page);
                mark = (Marker)pv.getMarker(name, Constants.EN_LEWP);
                if (mark != null) {
                    break;
                }
                page--;
                if (page < 0 && doc && seq > 1) {
                    seq--;
                    page = areaTreeModel.getPageCount(seq) - 1;
                }
            }
        }

        if (mark == null) {
            log.debug("found no marker with name: " + name);
            return null;
        } else {
            rm.bindMarker(mark);
            return rm;
        }
    }

    private Page makeNewPage(boolean bIsBlank, boolean bIsLast) {
        if (curPage != null) {
            finishPage();
        }

        currentPageNum++;

        curPage = pageProvider.getPage(bIsBlank,
                currentPageNum, PageProvider.RELTO_PAGE_SEQUENCE);

        if (log.isDebugEnabled()) {
            log.debug("[" + curPage.getPageViewport().getPageNumberString() 
                    + (bIsBlank ? "*" : "") + "]");
        }
        
        addIDToPage(pageSeq.getId());
        return curPage;
    }

    private void layoutSideRegion(int regionID) {
        SideRegion reg = (SideRegion)curPage.getSimplePageMaster().getRegion(regionID);
        if (reg == null) {
            return;
        }
        StaticContent sc = pageSeq.getStaticContent(reg.getRegionName());
        if (sc == null) {
            return;
        }

        StaticContentLayoutManager lm = (StaticContentLayoutManager)
            getLayoutManagerMaker().makeStaticContentLayoutManager(
                    this, sc, reg);
        lm.doLayout();
    }

    private void finishPage() {
        curPage.getPageViewport().dumpMarkers();
        // Layout side regions
        layoutSideRegion(FO_REGION_BEFORE); 
        layoutSideRegion(FO_REGION_AFTER);
        layoutSideRegion(FO_REGION_START);
        layoutSideRegion(FO_REGION_END);
        
        // Try to resolve any unresolved IDs for the current page.
        // 
        areaTreeHandler.tryIDResolution(curPage.getPageViewport());
        // Queue for ID resolution and rendering
        areaTreeHandler.getAreaTreeModel().addPage(curPage.getPageViewport());
        if (log.isDebugEnabled()) {
            log.debug("page finished: " + curPage.getPageViewport().getPageNumberString() 
                    + ", current num: " + currentPageNum);
        }
        curPage = null;
    }
    
    /**
     * Depending on the kind of break condition, move to next column
     * or page. May need to make an empty page if next page would
     * not have the desired "handedness".
     * @param breakVal - value of break-before or break-after trait.
     */
    private void handleBreakTrait(int breakVal) {
        if (breakVal == Constants.EN_ALL) {
            //break due to span change in multi-column layout
            curPage.getPageViewport().createSpan(true);
            return;
        } else if (breakVal == Constants.EN_NONE) {
            curPage.getPageViewport().createSpan(false);
            return;
        } else if (breakVal == Constants.EN_COLUMN || breakVal <= 0) {
            PageViewport pv = curPage.getPageViewport();
            
            //Check if previous page was spanned
            boolean forceNewPageWithSpan = false;
            RegionBody rb = (RegionBody)curPage.getSimplePageMaster().getRegion(
                    Constants.FO_REGION_BODY);
            if (breakVal < 0 
                    && rb.getColumnCount() > 1 
                    && pv.getCurrentSpan().getColumnCount() == 1) {
                forceNewPageWithSpan = true;
            }
            
            if (forceNewPageWithSpan) {
                curPage = makeNewPage(false, false);
                curPage.getPageViewport().createSpan(true);
            } else if (pv.getCurrentSpan().hasMoreFlows()) {
                pv.getCurrentSpan().moveToNextFlow();
            } else {
                curPage = makeNewPage(false, false);
            }
            return;
        }
        log.debug("handling break-before after page " + currentPageNum 
            + " breakVal=" + breakVal);
        if (needBlankPageBeforeNew(breakVal)) {
            curPage = makeNewPage(true, false);
        }
        if (needNewPage(breakVal)) {
            curPage = makeNewPage(false, false);
        }
    }

    /**
     * Check if a blank page is needed to accomodate
     * desired even or odd page number.
     * @param breakVal - value of break-before or break-after trait.
     */
    private boolean needBlankPageBeforeNew(int breakVal) {
        if (breakVal == Constants.EN_PAGE || (curPage.getPageViewport().getPage().isEmpty())) {
            // any page is OK or we already have an empty page
            return false;
        } else {
            /* IF we are on the kind of page we need, we'll need a new page. */
            if (currentPageNum % 2 == 0) { // even page
                return (breakVal == Constants.EN_EVEN_PAGE);
            } else { // odd page
                return (breakVal == Constants.EN_ODD_PAGE);
            }
        }
    }

    /**
     * See if need to generate a new page
     * @param breakVal - value of break-before or break-after trait.
     */
    private boolean needNewPage(int breakVal) {
        if (curPage.getPageViewport().getPage().isEmpty()) {
            if (breakVal == Constants.EN_PAGE) {
                return false;
            } else if (currentPageNum % 2 == 0) { // even page
                return (breakVal == Constants.EN_ODD_PAGE);
            } else { // odd page
                return (breakVal == Constants.EN_EVEN_PAGE);
            }
        } else {
            return true;
        }
    }
    
    
    /**
     * <p>This class delivers Page instances. It also caches them as necessary.
     * </p>
     * <p>Additional functionality makes sure that surplus instances that are requested by the
     * page breaker are properly discarded, especially in situations where hard breaks cause
     * blank pages. The reason for that: The page breaker sometimes needs to preallocate 
     * additional pages since it doesn't know exactly until the end how many pages it really needs.
     * </p>
     */
    public class PageProvider {
        
        private Log log = LogFactory.getLog(PageProvider.class);

        /** Indices are evaluated relative to the first page in the page-sequence. */
        public static final int RELTO_PAGE_SEQUENCE = 0;
        /** Indices are evaluated relative to the first page in the current element list. */
        public static final int RELTO_CURRENT_ELEMENT_LIST = 1;
        
        private int startPageOfPageSequence;
        private int startPageOfCurrentElementList;
        private int startColumnOfCurrentElementList;
        private List cachedPages = new java.util.ArrayList();
        
        private int lastPageIndex = -1;
        private int indexOfCachedLastPage = -1;
        
        //Cache to optimize getAvailableBPD() calls
        private int lastRequestedIndex = -1;
        private int lastReportedBPD = -1;
        
        /**
         * Main constructor.
         * @param ps The page-sequence the provider operates on
         */
        public PageProvider(PageSequence ps) {
            this.startPageOfPageSequence = ps.getStartingPageNumber();
        }
        
        /**
         * The page breaker notifies the provider about the page number an element list starts
         * on so it can later retrieve PageViewports relative to this first page.
         * @param startPage the number of the first page for the element list.
         * @param startColumn the starting column number for the element list. 
         */
        public void setStartOfNextElementList(int startPage, int startColumn) {
            log.debug("start of the next element list is:"
                    + " page=" + startPage + " col=" + startColumn);
            this.startPageOfCurrentElementList = startPage - startPageOfPageSequence + 1;
            this.startColumnOfCurrentElementList = startColumn;
            //Reset Cache
            this.lastRequestedIndex = -1;
            this.lastReportedBPD = -1;
        }
        
        /**
         * Sets the index of the last page. This is done as soon as the position of the last page
         * is known or assumed.
         * @param index the index relative to the first page in the page-sequence
         */
        public void setLastPageIndex(int index) {
            this.lastPageIndex = index;
        }
        
        /**
         * Returns the available BPD for the part/page indicated by the index parameter.
         * The index is the part/page relative to the start of the current element list.
         * This method takes multiple columns into account.
         * @param index zero-based index of the requested part/page
         * @return the available BPD
         */
        public int getAvailableBPD(int index) {
            //Special optimization: There may be many equal calls by the BreakingAlgorithm
            if (this.lastRequestedIndex == index) {
                if (log.isTraceEnabled()) {
                    log.trace("getAvailableBPD(" + index + ") -> (cached) " + lastReportedBPD);
                }
                return this.lastReportedBPD;
            }
            int c = index;
            int pageIndex = 0;
            int colIndex = startColumnOfCurrentElementList;
            Page page = getPage(
                    false, pageIndex, RELTO_CURRENT_ELEMENT_LIST);
            while (c > 0) {
                colIndex++;
                if (colIndex >= page.getPageViewport().getCurrentSpan().getColumnCount()) {
                    colIndex = 0;
                    pageIndex++;
                    page = getPage(
                            false, pageIndex, RELTO_CURRENT_ELEMENT_LIST);
                }
                c--;
            }
            this.lastRequestedIndex = index;
            this.lastReportedBPD = page.getPageViewport().getBodyRegion().getRemainingBPD();
            if (log.isTraceEnabled()) {
                log.trace("getAvailableBPD(" + index + ") -> " + lastReportedBPD);
            }
            return this.lastReportedBPD;
        }
        
        /**
         * Returns the part index (0<x<partCount) which denotes the first part on the last page 
         * generated by the current element list.
         * @param partCount Number of parts determined by the breaking algorithm
         * @return the requested part index
         */
        public int getStartingPartIndexForLastPage(int partCount) {
            int result = 0;
            int idx = 0;
            int pageIndex = 0;
            int colIndex = startColumnOfCurrentElementList;
            Page page = getPage(
                    false, pageIndex, RELTO_CURRENT_ELEMENT_LIST);
            while (idx < partCount) {
                if ((colIndex >= page.getPageViewport().getCurrentSpan().getColumnCount())) {
                    colIndex = 0;
                    pageIndex++;
                    page = getPage(
                            false, pageIndex, RELTO_CURRENT_ELEMENT_LIST);
                    result = idx;
                }
                colIndex++;
                idx++;
            }
            return result;
        }

        /**
         * Returns a Page.
         * @param isBlank true if this page is supposed to be blank.
         * @param index Index of the page (see relativeTo)
         * @param relativeTo Defines which value the index parameter should be evaluated relative 
         * to. (One of PageProvider.RELTO_*)
         * @return the requested Page
         */
        public Page getPage(boolean isBlank, int index, int relativeTo) {
            if (relativeTo == RELTO_PAGE_SEQUENCE) {
                return getPage(isBlank, index);
            } else if (relativeTo == RELTO_CURRENT_ELEMENT_LIST) {
                int effIndex = startPageOfCurrentElementList + index;
                effIndex += startPageOfPageSequence - 1;
                return getPage(isBlank, effIndex);
            } else {
                throw new IllegalArgumentException(
                        "Illegal value for relativeTo: " + relativeTo);
            }
        }
        
        private Page getPage(boolean isBlank, int index) {
            boolean isLastPage = (lastPageIndex >= 0) && (index == lastPageIndex);
            if (log.isTraceEnabled()) {
                log.trace("getPage(" + index + " " + (isBlank ? "blank" : "non-blank") 
                        + (isLastPage ? " <LAST>" : "") + ")");
            }
            int intIndex = index - startPageOfPageSequence;
            if (log.isTraceEnabled()) {
                if (isBlank) {
                    log.trace("blank page requested: " + index);
                }
                if (isLastPage) {
                    log.trace("last page requested: " + index);
                }
            }
            while (intIndex >= cachedPages.size()) {
                if (log.isTraceEnabled()) {
                    log.trace("Caching " + index);
                }
                cacheNextPage(index, isBlank, isLastPage);
            }
            Page page = (Page)cachedPages.get(intIndex);
            boolean replace = false;
            if (page.getPageViewport().isBlank() != isBlank) {
                log.debug("blank condition doesn't match. Replacing PageViewport.");
                replace = true;
            }
            if ((isLastPage && indexOfCachedLastPage != intIndex)
                    || (!isLastPage && indexOfCachedLastPage >= 0)) {
                log.debug("last page condition doesn't match. Replacing PageViewport.");
                replace = true;
                indexOfCachedLastPage = (isLastPage ? intIndex : -1);
            }
            if (replace) {
                disardCacheStartingWith(intIndex);
                page = cacheNextPage(index, isBlank, isLastPage);
            }
            return page;
        }

        private void disardCacheStartingWith(int index) {
            while (index < cachedPages.size()) {
                this.cachedPages.remove(cachedPages.size() - 1);
                if (!pageSeq.goToPreviousSimplePageMaster()) {
                    log.warn("goToPreviousSimplePageMaster() on the first page called!");
                }
            }
        }
        
        private Page cacheNextPage(int index, boolean isBlank, boolean isLastPage) {
            try {
                String pageNumberString = pageSeq.makeFormattedPageNumber(index);
                SimplePageMaster spm = pageSeq.getNextSimplePageMaster(
                        index, (startPageOfPageSequence == index), isLastPage, isBlank);
                    
                Region body = spm.getRegion(FO_REGION_BODY);
                if (!pageSeq.getMainFlow().getFlowName().equals(body.getRegionName())) {
                    // this is fine by the XSL Rec (fo:flow's flow-name can be mapped to
                    // any region), but we don't support it yet.
                    throw new FOPException("Flow '" + pageSeq.getMainFlow().getFlowName()
                        + "' does not map to the region-body in page-master '"
                        + spm.getMasterName() + "'.  FOP presently "
                        + "does not support this.");
                }
                Page page = new Page(spm, index, pageNumberString, isBlank);
                //Set unique key obtained from the AreaTreeHandler
                page.getPageViewport().setKey(areaTreeHandler.generatePageViewportKey());
                page.getPageViewport().setForeignAttributes(spm.getForeignAttributes());
                cachedPages.add(page);
                return page;
            } catch (FOPException e) {
                //TODO Maybe improve. It'll mean to propagate this exception up several
                //methods calls.
                throw new IllegalStateException(e.getMessage());
            }
        }
        
    }

    /**
     * Act upon the force-page-count trait,
     * in relation to the initial-page-number trait of the following page-sequence.
     * @param nextPageSeqInitialPageNumber initial-page-number trait of next page-sequence
     */
    public void doForcePageCount(Numeric nextPageSeqInitialPageNumber) {

        int forcePageCount = pageSeq.getForcePageCount();

        // xsl-spec version 1.0   (15.oct 2001)
        // auto | even | odd | end-on-even | end-on-odd | no-force | inherit
        // auto:
        // Force the last page in this page-sequence to be an odd-page 
        // if the initial-page-number of the next page-sequence is even. 
        // Force it to be an even-page 
        // if the initial-page-number of the next page-sequence is odd. 
        // If there is no next page-sequence 
        // or if the value of its initial-page-number is "auto" do not force any page.
            

        // if force-page-count is auto then set the value of forcePageCount 
        // depending on the initial-page-number of the next page-sequence
        if (nextPageSeqInitialPageNumber != null && forcePageCount == Constants.EN_AUTO) {
            if (nextPageSeqInitialPageNumber.getEnum() != 0) {
                // auto | auto-odd | auto-even
                int nextPageSeqPageNumberType = nextPageSeqInitialPageNumber.getEnum();
                if (nextPageSeqPageNumberType == Constants.EN_AUTO_ODD) {
                    forcePageCount = Constants.EN_END_ON_EVEN;
                } else if (nextPageSeqPageNumberType == Constants.EN_AUTO_EVEN) {
                    forcePageCount = Constants.EN_END_ON_ODD;
                } else {   // auto
                    forcePageCount = Constants.EN_NO_FORCE;
                }
            } else { // <integer> for explicit page number
                int nextPageSeqPageStart = nextPageSeqInitialPageNumber.getValue();
                // spec rule
                nextPageSeqPageStart = (nextPageSeqPageStart > 0) ? nextPageSeqPageStart : 1;
                if (nextPageSeqPageStart % 2 == 0) {   // explicit even startnumber
                    forcePageCount = Constants.EN_END_ON_ODD;
                } else {    // explicit odd startnumber
                    forcePageCount = Constants.EN_END_ON_EVEN;
                }
            }
        }

        if (forcePageCount == Constants.EN_EVEN) {
            if ((currentPageNum - startPageNum + 1) % 2 != 0) { // we have a odd number of pages
                curPage = makeNewPage(true, false);
            }
        } else if (forcePageCount == Constants.EN_ODD) {
            if ((currentPageNum - startPageNum + 1) % 2 == 0) { // we have a even number of pages
                curPage = makeNewPage(true, false);
            }
        } else if (forcePageCount == Constants.EN_END_ON_EVEN) {
            if (currentPageNum % 2 != 0) { // we are now on a odd page
                curPage = makeNewPage(true, false);
            }
        } else if (forcePageCount == Constants.EN_END_ON_ODD) {
            if (currentPageNum % 2 == 0) { // we are now on a even page
                curPage = makeNewPage(true, false);
            }
        } else if (forcePageCount == Constants.EN_NO_FORCE) {
            // i hope: nothing special at all
        }

        if (curPage != null) {
            finishPage();
        }
    }
}