path: root/src/java/org/apache/fop/layoutmgr/LineLayoutManager.java

/*
 * Copyright 1999-2004 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: LineLayoutManager.java,v 1.17 2004/04/02 10:38:29 cbowditch Exp $ */

package org.apache.fop.layoutmgr;

import org.apache.fop.datatypes.Length;
import org.apache.fop.fo.Constants;
import org.apache.fop.fo.flow.Block;
import org.apache.fop.fo.properties.CommonHyphenation;
import org.apache.fop.hyphenation.Hyphenation;
import org.apache.fop.hyphenation.Hyphenator;
import org.apache.fop.area.LineArea;
import org.apache.fop.area.Resolvable;

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

import org.apache.fop.traits.MinOptMax;

/**
 * LayoutManager for lines. It builds one or more lines containing
 * inline areas generated by its sub layout managers.
 * A break is found for each line which may contain one of more
 * breaks from the child layout managers.
 * Once a break is found then it is return for the parent layout
 * manager to handle.
 * When the areas are being added to the page this manager
 * creates a line area to contain the inline areas added by the
 * child layout managers.
 */
public class LineLayoutManager extends InlineStackingLayoutManager {
    private Block fobj; 
    
    /**
     * Create a new Line Layout Manager.
     * This is used by the block layout manager to create
     * line managers for handling inline areas flowing into line areas.
     *
     * @param lh the default line height
     * @param l the default lead, from top to baseline
     * @param f the default follow, from baseline to bottom
     */
    public LineLayoutManager(Block node, int lh, int l, int f, int ms) {
        super(node);
        fobj = node;
        // the child FObj are owned by the parent BlockLM
        // this LM has all its childLMs preloaded
        fobjIter = null;
        lineHeight = lh;
        lead = l;
        follow = f;
        middleShift = ms;
        initialize(); // Normally done when started by parent!
    }

    /**
     * @see org.apache.fop.layoutmgr.AbstractLayoutManager#initProperties()
     */
    protected void initProperties() {
        bTextAlignment = fobj.getTextAlign();
        bTextAlignmentLast = fobj.getTextAlignLast();
        textIndent = fobj.getTextIndent();
        hyphProps = fobj.getCommonHyphenation();
        
        //
        if (bTextAlignment != JUSTIFY && bTextAlignmentLast == JUSTIFY) {
            effectiveAlignment = 0;
        } else {
            effectiveAlignment = bTextAlignment;
        }
    }

    /**
     * Private class to store information about inline breaks.
     * Each value holds the start and end indexes into a List of
     * inline break positions.
     */
    private static class LineBreakPosition extends LeafPosition {
        // int iPos;
        double dAdjust; // Percentage to adjust (stretch or shrink)
        double ipdAdjust; // Percentage to adjust (stretch or shrink)
        int startIndent;
        int lineHeight;
        int baseline;

        LineBreakPosition(LayoutManager lm, int iBreakIndex,
                          double ipdA, double adjust, int ind, int lh, int bl) {
            super(lm, iBreakIndex);
            // iPos = iBreakIndex;
            ipdAdjust = ipdA;
            dAdjust = adjust;
            startIndent = ind;
            lineHeight = lh;
            baseline = bl;
        }
    }


    /** Break positions returned by inline content. */
    private List vecInlineBreaks = new ArrayList();

    private BreakPoss prevBP = null; // Last confirmed break position
    private int bTextAlignment = TextAlign.JUSTIFY;
    private int bTextAlignmentLast;
    private int effectiveAlignment;
    private Length textIndent;
    private CommonHyphenation hyphProps;

    private int lineHeight;
    private int lead;
    private int follow;
    // offset of the middle baseline with respect to the main baseline
    private int middleShift;

    // inline start pos when adding areas
    private int iStartPos = 0;

    private ArrayList knuthParagraphs = null;
    private LinkedList activeList = null;
    private LinkedList inactiveList = null;
    private ArrayList breakpoints = null;
    private int iReturnedLBP = 0;
    private int iStartElement = 0;
    private int iEndElement = 0;
    private int iCurrParIndex = 0;

    private KnuthNode lastDeactivatedNode = null;

    //     parameters of Knuth's algorithm:
    // penalty value for flagged penalties
    private int flaggedPenalty = 50;
    // demerit for consecutive lines ending at flagged penalties
    private int repeatedFlaggedDemerit = 50;
    // demerit for consecutive lines belonging to incompatible fitness classes 
    private int incompatibleFitnessDemerit = 50;
    // suggested modification to the "optimum" number of lines
    private int looseness = 0;

    // this constant is used to create elements when text-align is center:
    // every TextLM descendant of LineLM must use the same value, 
    // otherwise the line breaking algorithm does not find the right
    // break point
    public static final int DEFAULT_SPACE_WIDTH = 3336;
    private static final int INFINITE_RATIO = 1000;

    // this class represent a feasible breaking point
    private class KnuthNode {
        // index of the breakpoint represented by this node
        public int position;

        // number of the line ending at this breakpoint
        public int line;

        // fitness class of the line ending at his breakpoint
        public int fitness;

        // accumulated width of the KnuthElements
        public int totalWidth;

        // accumulated stretchability of the KnuthElements
        public int totalStretch;

        // accumulated shrinkability of the KnuthElements
        public int totalShrink;

        // adjustment ratio if the line ends at this breakpoint
        public double adjustRatio;

        // difference between target and actual line width
        public int difference;

        // minimum total demerits up to this breakpoint
        public double totalDemerits;

        // best node for the preceding breakpoint
        public KnuthNode previous;

        public KnuthNode(int position, int line, int fitness,
                         int totalWidth, int totalStretch, int totalShrink,
                         double adjustRatio, int difference,
                         double totalDemerits, KnuthNode previous) {
            this.position = position;
            this.line = line;
            this.fitness = fitness;
            this.totalWidth = totalWidth;
            this.totalStretch = totalStretch;
            this.totalShrink = totalShrink;
            this.adjustRatio = adjustRatio;
            this.difference = difference;
            this.totalDemerits = totalDemerits;
            this.previous = previous;
        }
    }

    // this class stores information about how the nodes
    // which could start a line
    // ending at the current element
    private class BestRecords {
        private static final double INFINITE_DEMERITS = 1E11;

        private double bestDemerits[] = {
            INFINITE_DEMERITS, INFINITE_DEMERITS,
            INFINITE_DEMERITS, INFINITE_DEMERITS
        };
        private KnuthNode bestNode[] = {null, null, null, null};
        private double bestAdjust[] = {0.0, 0.0, 0.0, 0.0};
        private int bestDifference[] = {0, 0, 0, 0};
        private int bestIndex = -1;

        public BestRecords() {
        }

        public void addRecord(double demerits, KnuthNode node, double adjust,
                              int difference, int fitness) {
            if (demerits > bestDemerits[fitness]) {
                log.error("New demerits value greter than the old one");
            }
            bestDemerits[fitness] = demerits;
            bestNode[fitness] = node;
            bestAdjust[fitness] = adjust;
            bestDifference[fitness] = difference;
            if (bestIndex == -1 || demerits < bestDemerits[bestIndex]) {
                bestIndex = fitness;
            }
        }

        public boolean hasRecords() {
            return (bestIndex != -1);
        }

        public boolean notInfiniteDemerits(int fitness) {
            return (bestDemerits[fitness] != INFINITE_DEMERITS);
        }

        public double getDemerits(int fitness) {
            return bestDemerits[fitness];
        }

        public KnuthNode getNode(int fitness) {
            return bestNode[fitness];
        }

        public double getAdjust(int fitness) {
            return bestAdjust[fitness];
        }

        public int getDifference(int fitness) {
            return bestDifference[fitness];
        }

        public double getMinDemerits() {
            if (bestIndex != -1) {
                return getDemerits(bestIndex);
            } else {
                // anyway, this should never happen
                return INFINITE_DEMERITS;
            }
        }
    }

    // this class is used to remember
    // which was the first element in the paragraph
    // returned by each LM
    private class Update {
        private InlineLevelLayoutManager inlineLM;
        private int iFirstIndex;

        public Update(InlineLevelLayoutManager lm, int index) {
            inlineLM = lm;
            iFirstIndex = index;
        }
    }

    // this class represents a paragraph
    private class Paragraph extends LinkedList {
        // number of KnuthElements added by the LineLayoutManager
        public int ignoreAtStart = 0;
        public int ignoreAtEnd = 0;
        // minimum space at the end of the last line (in millipoints)
        public int lineFillerWidth;

        public void startParagraph(int lineWidth) {
            // set the minimum amount of empty space at the end of the
            // last line
            if (bTextAlignment == CENTER) {
                lineFillerWidth = 0; 
            } else {
                lineFillerWidth = (int)(lineWidth / 12); 
            }

            // add auxiliary elements at the beginning of the paragraph
            if (bTextAlignment == CENTER && bTextAlignmentLast != JUSTIFY) {
                this.add(new KnuthGlue(0, 3 * DEFAULT_SPACE_WIDTH, 0,
                                       null, false));
                ignoreAtStart ++;
            }

            // add the element representing text indentation
            // at the beginning of the first paragraph
            if (knuthParagraphs.size() == 0
                && textIndent.getValue() != 0) {
                this.add(new KnuthBox(textIndent.getValue(), 0, 0, 0,
                                      null, false));
                ignoreAtStart ++;
            }
        }

        public void endParagraph() {
            // remove glue and penalty item at the end of the paragraph
            while (this.size() > ignoreAtStart
                   && !((KnuthElement) this.get(this.size() - 1)).isBox()) {
                this.remove(this.size() - 1);
            }
            if (this.size() > ignoreAtStart) {
                if (bTextAlignment == CENTER
                    && bTextAlignmentLast != JUSTIFY) {
                    this.add(new KnuthGlue(0, 3 * DEFAULT_SPACE_WIDTH, 0,
                                           null, false));
                    this.add(new KnuthPenalty(0, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 2;
                } else if (bTextAlignmentLast != JUSTIFY) {
                    // add the elements representing the space
                    // at the end of the last line
                    // and the forced break
                    this.add(new KnuthPenalty(0, KnuthElement.INFINITE,
                                              false, null, false));
                    this.add(new KnuthGlue(lineFillerWidth, 10000000, 0,
                                           null, false));
                    this.add(new KnuthPenalty(0, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 3;
                } else {
                    // add only the element representing the forced break
                    this.add(new KnuthPenalty(0, -KnuthElement.INFINITE,
                                              false, null, false));
                    ignoreAtEnd = 1;
                }
                knuthParagraphs.add(this);
            }
        }
    }


    /**
     * Call child layout managers to generate content.
     * This gets the next break which is a full line.
     *
     * @param context the layout context for finding breaks
     * @return the next break position
     */
    public BreakPoss getNextBreakPoss(LayoutContext context) {
        // Get a break from currently active child LM
        // Set up constraints for inline level managers
        InlineLevelLayoutManager curLM ; // currently active LM
        BreakPoss prev = null;
        BreakPoss bp = null; // proposed BreakPoss

        ArrayList vecPossEnd = new ArrayList();

        // IPD remaining in line
        MinOptMax availIPD = context.getStackLimit();

        LayoutContext inlineLC = new LayoutContext(context);

        clearPrevIPD();
        int iPrevLineEnd = vecInlineBreaks.size();

        if (iPrevLineEnd == 0 && bTextAlignment == TextAlign.START) {
            availIPD.subtract(new MinOptMax(textIndent.getValue()));
        }
        prevBP = null;

        // here starts Knuth's algorithm
        KnuthElement thisElement = null;
        LinkedList returnedList = null;
        LineBreakPosition lbp = null;

        if (knuthParagraphs == null) {
            // it's the first time this method is called
            knuthParagraphs = new ArrayList();
            breakpoints = new ArrayList();

            // convert all the text in a sequence of paragraphs made
            // of KnuthBox, KnuthGlue and KnuthPenalty objects
            boolean bPrevWasKnuthBox = false;
            KnuthBox prevBox = null;

            Paragraph knuthPar = new Paragraph();
            knuthPar.startParagraph(availIPD.opt);
            while ((curLM = (InlineLevelLayoutManager) getChildLM()) != null) {
                if ((returnedList
                     = curLM.getNextKnuthElements(inlineLC,
                                                  effectiveAlignment))
                    != null) {
                    // look at the first element
                    thisElement = (KnuthElement) returnedList.getFirst();
                    if (thisElement.isBox() && !thisElement.isAuxiliary()
                        && bPrevWasKnuthBox) {
                        prevBox = (KnuthBox) knuthPar.removeLast();
                        // if there are two consecutive KnuthBoxes the
                        // first one does not represent a whole word,
                        // so it must be given one more letter space
                        if (!prevBox.isAuxiliary()) {
                            // if letter spacing is constant,
                            // only prevBox needs to be replaced;
                            knuthPar.addLast(((InlineLevelLayoutManager)
                                              prevBox.getLayoutManager())
                                             .addALetterSpaceTo(prevBox));
                        } else {
                            // prevBox is the last element
                            // in the sub-sequence
                            //   <box> <aux penalty> <aux glue> <aux box>
                            // the letter space is added to <aux glue>,
                            // while the other elements are not changed
                            KnuthBox auxBox = prevBox;
                            KnuthGlue auxGlue
                                = (KnuthGlue) knuthPar.removeLast();
                            KnuthPenalty auxPenalty
                                = (KnuthPenalty) knuthPar.removeLast();
                            prevBox = (KnuthBox) knuthPar.getLast();
                            knuthPar.addLast(auxPenalty);
                            knuthPar.addLast(((InlineLevelLayoutManager)
                                              prevBox.getLayoutManager())
                                             .addALetterSpaceTo(prevBox));
                            knuthPar.addLast(auxBox);
                        }
                    }

                    // look at the last element
                    KnuthElement lastElement = (KnuthElement) returnedList.getLast();
                    boolean bForceLinefeed = false;
                    if (lastElement.isBox()) {
                        bPrevWasKnuthBox = true;
                    } else {
                        bPrevWasKnuthBox = false;
                        if (lastElement.isPenalty()
                            && ((KnuthPenalty) lastElement).getP()
                                == -KnuthPenalty.INFINITE) {
                            // a penalty item whose value is -inf
                            // represents a preserved linefeed,
                            // wich forces a line break
                            bForceLinefeed = true;
                            returnedList.removeLast();
                        }
                    }

                    // add the new elements to the paragraph
                    knuthPar.addAll(returnedList);
                    if (bForceLinefeed) {
                        knuthPar.endParagraph();
                        knuthPar = new Paragraph();
                        knuthPar.startParagraph(availIPD.opt);
                        bPrevWasKnuthBox = false;
                    }
                } else {
                    // curLM returned null; this can happen
                    // if it has nothing more to layout,
                    // so just iterate once more to see
                    // if there are other children
                }
            }
            knuthPar.endParagraph();

            // find the optimal line breaking points for each paragraph
            ListIterator paragraphsIterator
                = knuthParagraphs.listIterator(knuthParagraphs.size());
            Paragraph currPar = null;
            while (paragraphsIterator.hasPrevious()) {
                currPar = (Paragraph) paragraphsIterator.previous();
                double maxAdjustment = 1;
                int iBPcount = 0;

                // first try
                if ((iBPcount
                     = findBreakingPoints(currPar,
                                          context.getStackLimit().opt,
                                          maxAdjustment, false)) == 0) {
                    // the first try failed, now try something different
                    log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment);
                    if (hyphProps.hyphenate == Constants.TRUE) {
                        // consider every hyphenation point as a legal break
                        findHyphenationPoints(currPar);
                    } else {
                        // try with a higher threshold
                        maxAdjustment = 5;
                    }

                    if ((iBPcount
                         = findBreakingPoints(currPar,
                                              context.getStackLimit().opt,
                                              maxAdjustment, false)) == 0) {
                        // the second try failed too, try with a huge threshold
                        // and force the algorithm to find
                        // a set of breaking points
                        log.debug("No set of breaking points found with maxAdjustment = " + maxAdjustment
                                         + (hyphProps.hyphenate == Constants.TRUE ? " and hyphenation" : ""));
                        maxAdjustment = 20;
                        iBPcount
                            = findBreakingPoints(currPar,
                                                 context.getStackLimit().opt,
                                                 maxAdjustment, true);
                    }
                }
            }
        } else {
            // this method has been called before
            // all line breaks are already calculated
        }

        // get a break point from the list
        lbp = (LineBreakPosition) breakpoints.get(iReturnedLBP ++);
        if (iReturnedLBP == breakpoints.size()) {
            setFinished(true);
        }

        BreakPoss curLineBP = new BreakPoss(lbp);
        curLineBP.setFlag(BreakPoss.ISLAST, isFinished());
        curLineBP.setStackingSize(new MinOptMax(lbp.lineHeight));
        return curLineBP;
    }

    private int findBreakingPoints(Paragraph par, int lineWidth,
                                   double threshold, boolean force) {
        int totalWidth = 0;
        int totalStretch = 0;
        int totalShrink = 0;
        boolean bForced = false;

        // current element in the paragraph
        KnuthElement thisElement = null;
        // previous element in the paragraph is a KnuthBox
        boolean previousIsBox = false;

        // create an active node representing the starting point
        activeList = new LinkedList();
        activeList.add(new KnuthNode(0, 0, 1, 0, 0, 0, 0, 0, 0, null));
        inactiveList = new LinkedList();

        // main loop
        ListIterator paragraphIterator = par.listIterator();
        while (paragraphIterator.hasNext()) {
            thisElement = (KnuthElement) paragraphIterator.next();
            if (thisElement.isBox()) {
                // a KnuthBox object is not a legal line break
                totalWidth += thisElement.getW();
                previousIsBox = true;
            } else if (thisElement.isGlue()) {
                // a KnuthGlue object is a legal line break
                // only if the previous object is a KnuthBox
                if (previousIsBox) {
                    considerLegalBreak(par, lineWidth, thisElement,
                                       totalWidth, totalStretch, totalShrink,
                                       threshold);
                }
                totalWidth += thisElement.getW();
                totalStretch += ((KnuthGlue) thisElement).getY();
                totalShrink += ((KnuthGlue) thisElement).getZ();
                previousIsBox = false;
            } else {
                // a KnuthPenalty is a legal line break
                // only if its penalty is not infinite
                if (((KnuthPenalty) thisElement).getP()
                    < KnuthElement.INFINITE) {
                    considerLegalBreak(par, lineWidth, thisElement,
                                       totalWidth, totalStretch, totalShrink,
                                       threshold);
                }
                previousIsBox = false;
            }
        }

        if (activeList.size() == 0) {
            if (force) {
                activeList.add(lastDeactivatedNode);
                bForced = true;
                log.error("Could not find a set of breaking points");
            } else {
                inactiveList.clear();
                return 0;
                }
        }

        // there is at least one set of breaking points
        // choose the active node with fewest total demerits
        ListIterator activeListIterator = activeList.listIterator();
        KnuthNode tempNode = null;
        KnuthNode bestActiveNode = null;
        double bestDemerits = BestRecords.INFINITE_DEMERITS;
        int line = 0;
        while (activeListIterator.hasNext()) {
            tempNode = (KnuthNode) activeListIterator.next();
            if (tempNode.totalDemerits < bestDemerits) {
                bestActiveNode = tempNode;
                bestDemerits = bestActiveNode.totalDemerits;
            }
        }
        line = bestActiveNode.line;

        if (looseness != 0) {
            // choose the appropriate active node
            activeListIterator = activeList.listIterator();
            int s = 0;
            while (activeListIterator.hasNext()) {
                tempNode = (KnuthNode) activeListIterator.next();
                int delta = tempNode.line - line;
                if (looseness <= delta && delta < s
                    || s < delta && delta <= looseness) {
                    s = delta;
                    bestActiveNode = tempNode;
                    bestDemerits = tempNode.totalDemerits;
                } else if (delta == s
                           && tempNode.totalDemerits < bestDemerits) {
                    bestActiveNode = tempNode;
                    bestDemerits = tempNode.totalDemerits;
                }
            }
            line = bestActiveNode.line;
        }

        // use the chosen node to determine the optimum breakpoints
        for (int i = line; i > 0; i--) {
            // compute indent and adjustment ratio, according to
            // the value of text-align and text-align-last
            int indent = 0;
            int difference = (bestActiveNode.line < line || bForced)
                ? bestActiveNode.difference
                : bestActiveNode.difference + par.lineFillerWidth;
            int textAlign = (bestActiveNode.line < line || bForced)
                ? bTextAlignment : bTextAlignmentLast;
            indent += (textAlign == CENTER)
                ? difference / 2
                : (textAlign == END) ? difference : 0;
            indent += (bestActiveNode.line == 1
                       && knuthParagraphs.indexOf(par) == 0)
                ? textIndent.getValue() : 0;
            double ratio = (textAlign == JUSTIFY)
                ? bestActiveNode.adjustRatio : 0;

            makeLineBreakPosition(par,
                                  (i > 1 ? bestActiveNode.previous.position + 1: 0),
                                                  bestActiveNode.position,
                                  0, ratio, indent);

            bestActiveNode = bestActiveNode.previous;
        }
        if (bForced) {
            fallback(par, line);
        }
        activeList.clear();
        inactiveList.clear();
        return line;
    }

    private void fallback(Paragraph par, int line) {
        makeLineBreakPosition(par,
                              lastDeactivatedNode.position,
                              par.size() - 1,
                              line, 0, 0);
    }

    private void makeLineBreakPosition(Paragraph par,
                                       int firstElementIndex, int lastElementIndex,
                                       int insertIndex, double ratio, int indent) {
        // line height calculation

        int halfLeading = (lineHeight - lead - follow) / 2;
        // height above the main baseline
        int lineLead = lead + halfLeading;
        // maximum size of top and bottom alignment
        int maxtb = follow + halfLeading;
        // max size of middle alignment above and below the middle baseline
        int middlefollow = maxtb;

        ListIterator inlineIterator
            = par.listIterator(firstElementIndex);
        for (int j = firstElementIndex;
             j <= lastElementIndex;
             j++) {
            KnuthElement element = (KnuthElement) inlineIterator.next();
            if (element.isBox()) {
                if (((KnuthBox) element).getLead() > lineLead) {
                    lineLead = ((KnuthBox) element).getLead();
                }
                if (((KnuthBox) element).getTotal() > maxtb) {
                    maxtb = ((KnuthBox) element).getTotal();
                }
                if (((KnuthBox) element).getMiddle() > lineLead + middleShift) {
                    lineLead += ((KnuthBox) element).getMiddle()
                                - lineLead - middleShift;
                }
                if (((KnuthBox) element).getMiddle() > middlefollow - middleShift) {
                    middlefollow += ((KnuthBox) element).getMiddle()
                                    - middlefollow + middleShift;
                }
            }
        }

        if (maxtb - lineLead > middlefollow) {
                    middlefollow = maxtb - lineLead;
        }

        breakpoints.add(insertIndex,
                        new LineBreakPosition(this,
                                              lastElementIndex ,
                                              ratio, 0, indent,
                                              lineLead + middlefollow,
                                              lineLead));
    }

    private void considerLegalBreak(LinkedList par, int lineWidth,
                                    KnuthElement element,
                                    int totalWidth, int totalStretch,
                                    int totalShrink, double threshold) {
        KnuthNode activeNode = null;

        ListIterator activeListIterator = activeList.listIterator();
        if (activeListIterator.hasNext()) {
            activeNode = (KnuthNode) activeListIterator.next();
        } else {
            activeNode = null;
        }

        while (activeNode != null) {
            BestRecords best = new BestRecords();

            // these are the new values that must be computed
            // in order to define a new active node
            int newLine = 0;
            int newFitnessClass = 0;
            int newWidth = 0;
            int newStretch = 0;
            int newShrink = 0;
            double newIPDAdjust = 0;
            double newDemerits = 0;

            while (activeNode != null) {
                // compute the line number
                newLine = activeNode.line + 1;

                // compute the adjustment ratio
                int actualWidth = totalWidth - activeNode.totalWidth;
                if (element.isPenalty()) {
                    actualWidth += element.getW();
                }
                int neededAdjustment = lineWidth - actualWidth;
                int maxAdjustment = 0;
                if (neededAdjustment > 0) {
                    maxAdjustment = totalStretch - activeNode.totalStretch;
                    if (maxAdjustment > 0) {
                        newIPDAdjust
                            = (double) neededAdjustment / maxAdjustment;
                    } else {
                        newIPDAdjust = INFINITE_RATIO;
                    }
                } else if (neededAdjustment < 0) {
                    maxAdjustment = totalShrink - activeNode.totalShrink;
                    if (maxAdjustment > 0) {
                        newIPDAdjust
                            = (double) neededAdjustment / maxAdjustment;
                    } else {
                        newIPDAdjust = INFINITE_RATIO;
                    }
                } else {
                    // neededAdjustment == 0
                    newIPDAdjust = 0;
                }
                if (newIPDAdjust < -1
                    || (element.isPenalty()
                        && ((KnuthPenalty) element).getP()
                        == -KnuthElement.INFINITE)
                    && !(activeNode.position == par.indexOf(element))) {
                    // deactivate activeNode
                    KnuthNode tempNode
                        = (KnuthNode) activeListIterator.previous();
                    int iCallNext = 0;
                    while (tempNode != activeNode) {
                        // this is not the node we meant to remove!
                        tempNode = (KnuthNode) activeListIterator.previous();
                        iCallNext ++;
                    }
                    lastDeactivatedNode = tempNode;
                    inactiveList.add(tempNode);
                    activeListIterator.remove();
                    for (int i = 0; i < iCallNext; i++) {
                        activeListIterator.next();
                    }
                }

                if ((-1 <= newIPDAdjust) && (newIPDAdjust <= threshold)) {
                    // compute demerits and fitness class
                    if (element.isPenalty()
                        && ((KnuthPenalty) element).getP() >= 0) {
                        newDemerits
                            = Math.pow((1
                                        + 100 * Math.pow(Math.abs(newIPDAdjust), 3)
                                        + ((KnuthPenalty) element).getP()), 2);
                    } else if (element.isPenalty()
                               && ((KnuthPenalty) element).getP()
                               > -INFINITE_RATIO) {
                        newDemerits
                            = Math.pow((1
                                        + 100 * Math.pow(Math.abs(newIPDAdjust), 3)), 2)
                            - Math.pow(((KnuthPenalty) element).getP(), 2);
                    } else {
                        newDemerits
                            = Math.pow((1
                                        + 100 * Math.pow(Math.abs(newIPDAdjust), 3)), 2);
                    }
                    if (element.isPenalty()
                        && ((KnuthPenalty) element).isFlagged()
                        && ((KnuthElement) par.get(activeNode.position)).isPenalty()
                        && ((KnuthPenalty) par.get(activeNode.position)).isFlagged()) {
                        // add demerit for consecutive breaks at flagged penalties
                        newDemerits += repeatedFlaggedDemerit;
                    }
                    if (newIPDAdjust < -0.5) {
                        newFitnessClass = 0;
                    } else if (newIPDAdjust <= 0.5) {
                        newFitnessClass = 1;
                    } else if (newIPDAdjust <= 1) {
                        newFitnessClass = 2;
                    } else {
                        newFitnessClass = 3;
                    }
                    if (Math.abs(newFitnessClass - activeNode.fitness) > 1) {
                        // add demerit for consecutive breaks
                        // with very different fitness classes
                        newDemerits += incompatibleFitnessDemerit;
                    }
                    newDemerits += activeNode.totalDemerits;
                    if (newDemerits < best.getDemerits(newFitnessClass)) {
                        // updates best demerits data
                        best.addRecord(newDemerits, activeNode, newIPDAdjust,
                                       neededAdjustment, newFitnessClass);
                    }
                }

                 
                if (activeListIterator.hasNext()) {
                    activeNode = (KnuthNode) activeListIterator.next();
                } else {
                    activeNode = null;
                    break;
                }
                if (activeNode.line >= newLine) {
                    break;
                }
            } // end of the inner while

            if (best.hasRecords()) {
                // compute width, stratchability and shrinkability
                newWidth = totalWidth;
                newStretch = totalStretch;
                newShrink = totalShrink;
                ListIterator tempIterator
                    = par.listIterator(par.indexOf(element));
                while (tempIterator.hasNext()) {
                    KnuthElement tempElement
                        = (KnuthElement) tempIterator.next();
                    if (tempElement.isBox()) {
                        break;
                    } else if (tempElement.isGlue()) {
                        newWidth += ((KnuthGlue) tempElement).getW();
                        newStretch += ((KnuthGlue) tempElement).getY();
                        newShrink += ((KnuthGlue) tempElement).getZ();
                    } else if (((KnuthPenalty) tempElement).getP()
                               == -KnuthElement.INFINITE
                               && tempElement != element) {
                        break;
                    }
                }

                // add nodes to the active nodes list
                for (int i = 0; i <= 3; i++) {
                    if (best.notInfiniteDemerits(i)
                        && best.getDemerits(i)
                        <= (best.getMinDemerits()
                            + incompatibleFitnessDemerit)) {
                        // the nodes in activeList must be ordered
                        // by line number and position;
                        // so:
                        // 1) advance in the list until the end,
                        // or a node with a higher line number, is reached
                        int iStepsForward = 0;
                        KnuthNode tempNode;
                        while (activeListIterator.hasNext()) {
                            iStepsForward ++;
                            tempNode = (KnuthNode) activeListIterator.next();
                            if (tempNode.line > (best.getNode(i).line + 1)) {
                                activeListIterator.previous();
                                iStepsForward --;
                                break;
                            }
                        }
                        // 2) add the new node
                        activeListIterator.add
                            (new KnuthNode(par.indexOf(element),
                                           best.getNode(i).line + 1, i,
                                           newWidth, newStretch, newShrink,
                                           best.getAdjust(i),
                                           best.getDifference(i),
                                           best.getDemerits(i),
                                           best.getNode(i)));
                        // 3) go back
                        for (int j = 0;
                             j <= iStepsForward;
                             j ++) {
                            activeListIterator.previous();
                        }
                    }
                }
            }
            if (activeNode == null) {
                break;
            }
        } // end of the outer while
    }

    /**
     * find hyphenation points for every word int the current paragraph
     * @ param currPar the paragraph whose words will be hyphenated
     */
    private void findHyphenationPoints(Paragraph currPar){
        // hyphenate every word
        ListIterator currParIterator
            = currPar.listIterator(currPar.ignoreAtStart);
        // list of TLM involved in hyphenation
        LinkedList updateList = new LinkedList();
        KnuthElement firstElement = null;
        KnuthElement nextElement = null;
        // current InlineLevelLayoutManager
        InlineLevelLayoutManager currLM = null;
        // number of KnuthBox elements containing word fragments
        int boxCount;
        // number of auxiliary KnuthElements between KnuthBoxes
        int auxCount;
        StringBuffer sbChars = null;

        // find all hyphenation points
        while (currParIterator.hasNext()) {
            firstElement = (KnuthElement) currParIterator.next();
            // 
            if (firstElement.getLayoutManager() != currLM) {
                currLM = (InlineLevelLayoutManager) firstElement.getLayoutManager();
                if (currLM != null) { 
                    updateList.add(new Update(currLM, currParIterator.previousIndex()));
                } else {
                    break;
                }
            }

            // collect word fragments, ignoring auxiliary elements;
            // each word fragment was created by a different TextLM
            if (firstElement.isBox() && !firstElement.isAuxiliary()) {
                boxCount = 1;
                auxCount = 0;
                sbChars = new StringBuffer();
                currLM.getWordChars(sbChars, firstElement.getPosition());
                // look if next elements are boxes too
                while (currParIterator.hasNext()) {
                    nextElement = (KnuthElement) currParIterator.next();
                    if (nextElement.isBox() && !nextElement.isAuxiliary()) {
                        // a non-auxiliary KnuthBox: append word chars
                        if (currLM != nextElement.getLayoutManager()) {
                            currLM = (InlineLevelLayoutManager) nextElement.getLayoutManager();
                            updateList.add(new Update(currLM, currParIterator.previousIndex()));
                        }
                        // append text to recreate the whole word
                        boxCount ++;
                        currLM.getWordChars(sbChars, nextElement.getPosition());
                    } else if (!nextElement.isAuxiliary()) {
                        // a non-auxiliary non-box KnuthElement: stop
                        // go back to the last box or auxiliary element
                        currParIterator.previous(); 
                        break;
                    } else {
                        // an auxiliary KnuthElement: simply ignore it
                        auxCount ++;
                    }
                }
                log.trace(" Word to hyphenate: " + sbChars.toString());
                // find hyphenation points
                HyphContext hc = getHyphenContext(sbChars);
                // ask each LM to hyphenate its word fragment
                if (hc != null) {
                    KnuthElement element = null;
                    for (int i = 0; i < (boxCount + auxCount); i++) {
                        currParIterator.previous();
                    }
                    for (int i = 0; i < (boxCount + auxCount); i++) {
                        element = (KnuthElement) currParIterator.next();
                        if (element.isBox() && !element.isAuxiliary()) {
                            ((InlineLevelLayoutManager)
                             element.getLayoutManager()).hyphenate(element.getPosition(), hc);
                        } else {
                            // nothing to do, element is an auxiliary KnuthElement
                        }
                    }
                }
            }
        }

        // create iterator for the updateList
        ListIterator updateListIterator = updateList.listIterator();
        Update currUpdate = null;
        int iPreservedElements = 0;
        int iAddedElements = 0;
        int iRemovedElements = 0;

        while (updateListIterator.hasNext()) {
            // ask the LMs to apply the changes and return 
            // the new KnuthElements to replace the old ones
            currUpdate = (Update) updateListIterator.next();
            int fromIndex = currUpdate.iFirstIndex;
            int toIndex;
            if (updateListIterator.hasNext()) {
                Update nextUpdate = (Update) updateListIterator.next();
                toIndex = nextUpdate.iFirstIndex;
                updateListIterator.previous();
            } else {
                // maybe this is not always correct!
                toIndex = currPar.size() - currPar.ignoreAtEnd
                    - iAddedElements;
            }

            // applyChanges() returns true if the LM modifies its data,
            // so it must return new KnuthElements to replace the old ones
            if (((InlineLevelLayoutManager) currUpdate.inlineLM)
                .applyChanges(currPar.subList(fromIndex + iAddedElements,
                                              toIndex + iAddedElements))) {
                // insert the new KnuthElements
                LinkedList newElements = null;
                newElements
                    = currUpdate.inlineLM.getChangedKnuthElements
                    (currPar.subList(fromIndex + iAddedElements,
                                     toIndex + iAddedElements),
                     flaggedPenalty, effectiveAlignment);
                // remove the old elements
                currPar.subList(fromIndex + iAddedElements,
                                toIndex + iAddedElements).clear();
                // insert the new elements
                currPar.addAll(fromIndex + iAddedElements, newElements);
                iAddedElements += newElements.size() - (toIndex - fromIndex);
            }
        }
        updateListIterator = null;
        updateList.clear();
    }

    private void resetBP(BreakPoss resetBP) {
        if (resetBP == null) {
            reset((Position) null);
        } else {
            while (vecInlineBreaks.get(vecInlineBreaks.size() - 1) != resetBP) {
                vecInlineBreaks.remove(vecInlineBreaks.size() - 1);
            }
            reset(resetBP.getPosition());
        }
    }

    private void reset() {
        resetBP(prevBP);
    }

    protected boolean couldEndLine(BreakPoss bp) {
        if (bp.canBreakAfter()) {
            return true; // no keep, ends on break char
        } else if (bp.isSuppressible()) {
            // NOTE: except at end of content for this LM!!
            // Never break after only space chars or any other sequence
            // of areas which would be suppressed at the end of the line.
            return false;
        } else {
            // See if could break before next area
            // TODO: do we need to set anything on the layout context?
            LayoutContext lc = new LayoutContext(0);
            LayoutManager nextLM = getChildLM();
            return (nextLM == null || nextLM.canBreakBefore(lc));
        }
    }

    private BreakPoss getBestBP(ArrayList vecPossEnd) {
        if (vecPossEnd.size() == 1) {
            return ((BreakCost) vecPossEnd.get(0)).getBP();
        }
        // Choose the best break (use a sort on cost!)
        Iterator iter = vecPossEnd.iterator();
        int minCost = Integer.MAX_VALUE;
        BreakPoss bestBP = null;
        while (iter.hasNext()) {
            BreakCost bc = (BreakCost) iter.next();
            if (bc.getCost() < minCost) {
                minCost = bc.getCost();
                bestBP = bc.getBP();
            }
        }
        return bestBP;
    }

    /** Line area is always considered to act as a fence. */
    protected boolean hasLeadingFence(boolean bNotFirst) {
        return true;
    }

    /** Line area is always considered to act as a fence. */
    protected boolean hasTrailingFence(boolean bNotLast) {
        return true;
    }

    /** Return true if we are at the end of this LM,
        and BPs after prev have been added to vecInlineBreaks
        and all breakposs in vecInlineBreaks
        back to and excluding prev are suppressible */
    private boolean condAllAreSuppressible(BreakPoss prev) {
        if (!isFinished()) {
            return false;
        }
        if (vecInlineBreaks.get(vecInlineBreaks.size() - 1) == prev) {
            return false;
        }
        return allAreSuppressible(prev);
    }

    /** Test whether all breakposs in vecInlineBreaks
        back to and excluding prev are suppressible */
    private boolean allAreSuppressible(BreakPoss prev) {
        ListIterator bpIter =
            vecInlineBreaks.listIterator(vecInlineBreaks.size());
        boolean allAreSuppressible = true;
        BreakPoss bp;
        while (bpIter.hasPrevious()
               && (bp = (BreakPoss) bpIter.previous()) != prev
               && (allAreSuppressible = bp.isSuppressible())) {
        }
        return allAreSuppressible;
    }

    /** Remove all BPs from the end back to and excluding prev
        from vecInlineBreaks*/
    private void removeAllBP(BreakPoss prev) {
        int iPrev;
        if (prev == null) {
            vecInlineBreaks.clear();
        } else if ((iPrev = vecInlineBreaks.indexOf(prev)) != -1) {
            for (int i = vecInlineBreaks.size()-1; iPrev < i; --i) {
                vecInlineBreaks.remove(i);
            }
        }
    }

    private HyphContext getHyphenContext(StringBuffer sbChars) {
        // Find all hyphenation points in this word
        // (get in an array of offsets)
        // hyphProps are from the block level?.
        // Note that according to the spec,
        // they also "apply to" fo:character.
        // I don't know what that means, since
        // if we change language in the middle of a "word",
        // the effect would seem quite strange!
        // Or perhaps in that case, we say that it's several words.
        // We probably should bring the hyphenation props up from the actual
        // TextLM which generate the hyphenation buffer,
        // since these properties inherit and could be specified
        // on an inline or wrapper below the block level.
        Hyphenation hyph
            = Hyphenator.hyphenate(hyphProps.language,
                                   hyphProps.country, sbChars.toString(),
                                   hyphProps.hyphenationRemainCharacterCount,
                                   hyphProps.hyphenationPushCharacterCount);
        // They hyph structure contains the information we need
        // Now start from prev: reset to that position, ask that LM to get
        // a Position for the first hyphenation offset. If the offset isn't in
        // its characters, it returns null,
        // but must tell how many chars it had.
        // Keep looking at currentBP using next hyphenation point until the
        // returned size is greater than the available size
        // or no more hyphenation points remain. Choose the best break.
        if (hyph != null) {
            return new HyphContext(hyph.getHyphenationPoints());
        } else {
            return null;
        }
    }

    /**
     * Make a line break for returning as the next break.
     * This makes the line break and calculates the height and
     * ipd adjustment factors.
     *
     * @param prevLineEnd previous line break index
     * @param target the target ipd value
     * @param textalign the text align in operation for this line
     * @return the line break position
     */
    private BreakPoss makeLineBreak(int prevLineEnd, MinOptMax target,
                                    int textalign) {
        // make a new BP
        // Store information needed to make areas in the LineBreakPosition!

        // lead to baseline is
        // max of: baseline fixed alignment and middle/2
        // after baseline is
        // max: top height-lead, middle/2 and bottom height-lead
        int halfLeading = (lineHeight - lead - follow) / 2;
        // height before baseline
        int lineLead = lead + halfLeading;
        // maximum size of top and bottom alignment
        int maxtb = follow + halfLeading;
        // max size of middle alignment below baseline
        int middlefollow = maxtb;

        // calculate actual ipd
        MinOptMax actual = new MinOptMax();
        BreakPoss lastBP = null;
        LayoutManager lastLM = null;
        for (Iterator iter = vecInlineBreaks.listIterator(prevLineEnd);
                iter.hasNext();) {
            BreakPoss bp = (BreakPoss) iter.next();
            if (bp.getLead() > lineLead) {
                lineLead = bp.getLead();
            }
            if (bp.getTotal() > maxtb) {
                maxtb = bp.getTotal();
            }
            if (bp.getMiddle() > middlefollow) {
                middlefollow = bp.getMiddle();
            }

            // the stacking size of textLM accumulate for each break
            // so the ipd is only added at the end of each LM
            if (bp.getLayoutManager() != lastLM) {
                if (lastLM != null) {
                    actual.add(lastBP.getStackingSize());
                }
                lastLM = bp.getLayoutManager();
            }
            lastBP = bp;
        }
        if (lastBP != null) {
            // add final ipd
            actual.add(lastBP.getStackingSize());
            // ATTENTION: make sure this hasn't gotten start space for next
            // LM added onto it!
            actual.add(lastBP.resolveTrailingSpace(true));
        }

        if (maxtb - lineLead > middlefollow) {
            middlefollow = maxtb - lineLead;
        }

        // in 7.21.4 the spec suggests that the leader and other
        // similar min/opt/max areas should be adjusted before
        // adjusting word spacing

        // Calculate stretch or shrink factor
        double ipdAdjust = 0;
        int targetWith = target.opt;
        int realWidth = actual.opt;
        if (actual.opt > targetWith) {
            if (actual.opt - targetWith < (actual.opt - actual.min)) {
                ipdAdjust = -(actual.opt - targetWith)
                                / (float) (actual.opt - actual.min);
                realWidth = targetWith;
            } else {
                ipdAdjust = -1;
                realWidth = actual.min;
            }
        } else {
            if (targetWith - actual.opt < actual.max - actual.opt) {
                ipdAdjust = (targetWith - actual.opt)
                                / (float) (actual.max - actual.opt);
                realWidth = targetWith;
            } else {
                ipdAdjust = 1;
                realWidth = actual.max;
            }
        }

        // if justifying then set the space adjustment
        // after the normal ipd adjustment
        double dAdjust = 0.0;
        int indent = 0;
        switch (textalign) {
            case TextAlign.JUSTIFY:
                if (realWidth != 0) {
                    dAdjust = (double) (targetWith - realWidth) / realWidth;
                }
            break;
            case TextAlign.START:
                if (prevLineEnd == 0) {
                    indent = textIndent.getValue();
                }
                break;
            case TextAlign.CENTER:
                indent = (targetWith - realWidth) / 2;
            break;
            case TextAlign.END:
                indent = targetWith - realWidth;
            break;
        }

        LineBreakPosition lbp;
        lbp = new LineBreakPosition(this,
                                    vecInlineBreaks.size() - 1,
                                    ipdAdjust, dAdjust, indent,
                                    lineLead + middlefollow, lineLead);
        BreakPoss curLineBP = new BreakPoss(lbp);

        curLineBP.setFlag(BreakPoss.ISLAST, isFinished());
        curLineBP.setStackingSize(new MinOptMax(lineLead + middlefollow));
        return curLineBP;
    }

    /**
     * Reset the positions to the given position.
     *
     * @param resetPos the position to reset to
     */
    public void resetPosition(Position resetPos) {
        if (resetPos == null) {
            setFinished(false);
            iReturnedLBP = 0;
        } else {
            if (isFinished()) {
                // if isFinished is true, iReturned LBP == breakpoints.size()
                // and breakpoints.get(iReturnedLBP) would generate
                // an IndexOutOfBoundException
                setFinished(false);
                iReturnedLBP--;
            }
            while ((LineBreakPosition) breakpoints.get(iReturnedLBP)
                   != (LineBreakPosition) resetPos) {
                iReturnedLBP --;
            }
            iReturnedLBP ++;
        }
    }

    /**
     * Add the areas with the break points.
     *
     * @param parentIter the iterator of break positions
     * @param context the context for adding areas
     */
    public void addAreas(PositionIterator parentIter,
                         LayoutContext context) {
        addAreas(parentIter, 0.0);

        //vecInlineBreaks.clear();
        prevBP = null;
    }

    // Generate and add areas to parent area
    // Set size etc
    // dSpaceAdjust should reference extra space in the BPD
    /**
     * Add the areas with the associated space adjustment.
     *
     * @param parentIter the iterator of breaks positions
     * @param dSpaceAdjust the space adjustment
     */
    public void addAreas(PositionIterator parentIter, double dSpaceAdjust) {
        LayoutManager childLM;
        LayoutContext lc = new LayoutContext(0);
        iCurrParIndex = 0;
        while (parentIter.hasNext()) {
            ListIterator paragraphIterator = null;
            KnuthElement tempElement = null;
            // the TLM which created the last KnuthElement in this line
            LayoutManager lastLM = null;

            LineBreakPosition lbp = (LineBreakPosition) parentIter.next();
            LineArea lineArea = new LineArea();
            lineArea.setStartIndent(lbp.startIndent);
            lineArea.setBPD(lbp.lineHeight);
            lc.setBaseline(lbp.baseline);
            lc.setLineHeight(lbp.lineHeight);
            lc.setMiddleShift(middleShift);
            setCurrentArea(lineArea);

            Paragraph currPar = (Paragraph) knuthParagraphs.get(iCurrParIndex);
            iEndElement = lbp.getLeafPos();

            // ignore the first elements added by the LineLayoutManager
            iStartElement += (iStartElement == 0) ? currPar.ignoreAtStart : 0;

            // ignore the last elements added by the LineLayoutManager
            iEndElement -= (iEndElement == (currPar.size() - 1))
                ? currPar.ignoreAtEnd : 0;

            // ignore the last element in the line if it is a KnuthGlue object
            paragraphIterator = currPar.listIterator(iEndElement);
            tempElement = (KnuthElement) paragraphIterator.next();
            if (tempElement.isGlue()) {
                iEndElement --;
                // this returns the same KnuthElement
                paragraphIterator.previous();
                tempElement = (KnuthElement) paragraphIterator.previous();
            }
            lastLM = tempElement.getLayoutManager();

            // ignore KnuthGlue and KnuthPenalty objects
            // at the beginning of the line
            paragraphIterator = currPar.listIterator(iStartElement);
            tempElement = (KnuthElement) paragraphIterator.next();
            while (!tempElement.isBox() && paragraphIterator.hasNext()) {
                tempElement = (KnuthElement) paragraphIterator.next();
                iStartElement ++;
            }

            // Add the inline areas to lineArea
            PositionIterator inlinePosIter
                = new KnuthPossPosIter(currPar, iStartElement,
                                       iEndElement + 1);

            iStartElement = lbp.getLeafPos() + 1;
            if (iStartElement == currPar.size()) {
                // advance to next paragraph
                iCurrParIndex++;
                iStartElement = 0;
            }

            lc.setSpaceAdjust(lbp.dAdjust);
            lc.setIPDAdjust(lbp.ipdAdjust);
            lc.setLeadingSpace(new SpaceSpecifier(true));
            lc.setTrailingSpace(new SpaceSpecifier(false));
            lc.setFlags(LayoutContext.RESOLVE_LEADING_SPACE, true);
            setChildContext(lc);
            while ((childLM = inlinePosIter.getNextChildLM()) != null) {
                lc.setFlags(LayoutContext.LAST_AREA, (childLM == lastLM));
                childLM.addAreas(inlinePosIter, lc);
                lc.setLeadingSpace(lc.getTrailingSpace());
                lc.setTrailingSpace(new SpaceSpecifier(false));
            }
            // when can this be null?
            if (lc.getTrailingSpace() != null) {
                addSpace(lineArea, lc.getTrailingSpace().resolve(true),
                         lc.getSpaceAdjust());
            }
            parentLM.addChild(lineArea);
        }
        setCurrentArea(null); // ?? necessary
    }

    /**
     * Add an unresolved area.
     * If a child layout manager needs to add an unresolved area
     * for page reference or linking then this intercepts it for
     * line area handling.
     * A line area may need to have the inline areas adjusted
     * to properly fill the line area. This adds a resolver that
     * resolves the inline area and can do the necessary
     * adjustments to the line and inline areas.
     *
     * @param id the id reference of the resolvable
     * @param res the resolvable object
     */
    public void addUnresolvedArea(String id, Resolvable res) {
        // create a resolvable class that handles ipd
        // adjustment for the current line

        parentLM.addUnresolvedArea(id, res);
    }

}