FOP-2292: First bits of a whitespace management extension

Patch by Seifeddine Dridi, applied with some modifications (mainly, Java compliance and Checkstyle)


git-svn-id: https://svn.apache.org/repos/asf/xmlgraphics/fop/branches/Temp_WhitespaceManagement@1518691 13f79535-47bb-0310-9956-ffa450edef68

11 files changed, 857 insertions, 21 deletions

diff --git a/src/java/org/apache/fop/layoutmgr/AbstractBreaker.java b/src/java/org/apache/fop/layoutmgr/AbstractBreaker.java
index 51e80e8d4..edd78d5ab 100644
--- a/src/java/org/apache/fop/layoutmgr/AbstractBreaker.java
+++ b/src/java/org/apache/fop/layoutmgr/AbstractBreaker.java
@@ -611,7 +611,7 @@ public abstract class AbstractBreaker {
                 // Handle SpaceHandling(Break)Positions, see SpaceResolver!
                 SpaceResolver.performConditionalsNotification(effectiveList,
                         startElementIndex, notificationEndElementIndex, lastBreak);
-
+                childLC.setAlternativeManager(alg.getAlternativeManager());
                 // Add areas now!
                 addAreas(new KnuthPossPosIter(effectiveList,
                         startElementIndex, endElementIndex + 1), childLC);
diff --git a/src/java/org/apache/fop/layoutmgr/AlternativeBlockLayoutManager.java b/src/java/org/apache/fop/layoutmgr/AlternativeBlockLayoutManager.java
new file mode 100644
index 000000000..1029940a6
--- /dev/null
+++ b/src/java/org/apache/fop/layoutmgr/AlternativeBlockLayoutManager.java
@@ -0,0 +1,239 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.layoutmgr;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Stack;
+
+import org.apache.fop.area.Area;
+import org.apache.fop.area.Block;
+import org.apache.fop.area.LineArea;
+import org.apache.fop.fo.extensions.AlternativeBlock;
+
+/**
+ * Layout manager for {@link AlternativeBlock}
+ */
+
+public class AlternativeBlockLayoutManager extends AbstractLayoutManager {
+
+    private Block curBlockArea;
+
+    public AlternativeBlockLayoutManager(AlternativeBlock node) {
+        super(node);
+        setGeneratesBlockArea(true);
+    }
+
+    /**
+     * Creates and initializes a {@link LayoutContext} to pass to the child LM
+     *
+     * @param context the parent {@link LayoutContext}
+     * @return a new child layout context
+     */
+    protected LayoutContext makeChildLayoutContext(LayoutContext context) {
+        LayoutContext childLC = LayoutContext.newInstance();
+        childLC.copyPendingMarksFrom(context);
+        childLC.setStackLimitBP(context.getStackLimitBP());
+        childLC.setRefIPD(context.getRefIPD());
+        childLC.setWritingMode(context.getWritingMode());
+        return childLC;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public List getNextKnuthElements(LayoutContext context, int alignment) {
+        return getNextKnuthElements(context, alignment, null, null, null);
+    }
+
+    /** {@inheritDoc} */
+    public List getNextKnuthElements(LayoutContext context, int alignment,
+            Stack lmStack, Position positionAtIPDChange,
+            LayoutManager restartAtLM) {
+        LayoutManager curLM;
+        List<ListElement> returnList = new LinkedList<ListElement>();
+        while ((curLM = getChildLM()) != null) {
+            LayoutContext childLC = makeChildLayoutContext(context);
+
+            List returnedList = null;
+            if (!curLM.isFinished()) {
+                returnedList = curLM.getNextKnuthElements(childLC, alignment);
+            }
+            if (returnedList != null) {
+                wrapPositionElements(returnedList, returnList);
+            }
+        }
+        setFinished(true);
+        return returnList;
+    }
+
+    /**
+     * "wrap" the Position inside each element moving the elements from SourceList to targetList
+     *
+     * @param sourceList source list
+     * @param targetList target list receiving the wrapped position elements
+     */
+    protected void wrapPositionElements(List sourceList, List targetList) {
+        wrapPositionElements(sourceList, targetList, false);
+    }
+
+    /**
+     * "wrap" the Position inside each element moving the elements from
+     * SourceList to targetList
+     *
+     * @param sourceList source list
+     * @param targetList target list receiving the wrapped position elements
+     * @param force if true, every Position is wrapped regardless of its LM of origin
+     */
+    protected void wrapPositionElements(List sourceList, List targetList,
+            boolean force) {
+
+        ListIterator listIter = sourceList.listIterator();
+        Object tempElement;
+        while (listIter.hasNext()) {
+            tempElement = listIter.next();
+            if (tempElement instanceof ListElement) {
+                wrapPositionElement((ListElement) tempElement, targetList,
+                        force);
+            } else if (tempElement instanceof List) {
+                wrapPositionElements((List) tempElement, targetList, force);
+            }
+        }
+    }
+
+    /**
+     * "wrap" the Position inside the given element and add it to the target list.
+     *
+     * @param el the list element
+     * @param targetList target list receiving the wrapped position elements
+     * @param force if true, every Position is wrapped regardless of its LM of origin
+     */
+    protected void wrapPositionElement(ListElement el, List targetList,
+            boolean force) {
+        if (force || el.getLayoutManager() != this) {
+            el.setPosition(notifyPos(new NonLeafPosition(this, el.getPosition())));
+        }
+        targetList.add(el);
+    }
+
+    @Override
+    public Area getParentArea(Area childArea) {
+        if (curBlockArea == null) {
+            curBlockArea = new Block();
+            // Set up dimensions
+            // Must get dimensions from parent area
+            /*Area parentArea = */parentLayoutManager.getParentArea(curBlockArea);
+        }
+        return curBlockArea;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public void addChildArea(Area childArea) {
+        if (curBlockArea != null) {
+            if (childArea instanceof LineArea) {
+                curBlockArea.addLineArea((LineArea) childArea);
+            } else {
+                curBlockArea.addBlock((Block) childArea);
+            }
+        }
+    }
+
+    /**
+     * Force current area to be added to parent area.
+     */
+    protected void flush() {
+        if (getCurrentArea() != null) {
+            parentLayoutManager.addChildArea(getCurrentArea());
+        }
+    }
+
+    private Area getCurrentArea() {
+        return curBlockArea;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public void addAreas(PositionIterator parentIter,
+            LayoutContext layoutContext) {
+
+        getParentArea(null);
+
+        addId();
+
+        LayoutManager childLM;
+        LayoutContext lc = LayoutContext.offspringOf(layoutContext);
+        LayoutManager firstLM = null;
+        LayoutManager lastLM = null;
+        Position firstPos = null;
+        Position lastPos = null;
+
+        // "unwrap" the NonLeafPositions stored in parentIter
+        // and put them in a new list;
+        LinkedList<Position> positionList = new LinkedList<Position>();
+        Position pos;
+        while (parentIter.hasNext()) {
+            pos = parentIter.next();
+            if (pos.getIndex() >= 0) {
+                if (firstPos == null) {
+                    firstPos = pos;
+                }
+                lastPos = pos;
+            }
+            if (pos instanceof NonLeafPosition && (pos.getPosition() != null)
+                    && pos.getPosition().getLM() != this) {
+                // pos was created by a child of this BestFitBlockLM
+                positionList.add(pos.getPosition());
+                lastLM = pos.getPosition().getLM();
+                if (firstLM == null) {
+                    firstLM = lastLM;
+                }
+            }
+        }
+
+        registerMarkers(true, isFirst(firstPos), isLast(lastPos));
+
+        PositionIterator childPosIter = new PositionIterator(
+                positionList.listIterator());
+        while ((childLM = childPosIter.getNextChildLM()) != null) {
+            // Add the block areas to Area
+            // set the space adjustment ratio
+            lc.setSpaceAdjust(layoutContext.getSpaceAdjust());
+            lc.setFlags(LayoutContext.FIRST_AREA, childLM == firstLM);
+            lc.setFlags(LayoutContext.LAST_AREA, childLM == lastLM);
+            lc.setStackLimitBP(layoutContext.getStackLimitBP());
+            childLM.addAreas(childPosIter, lc);
+        }
+
+        registerMarkers(false, isFirst(firstPos), isLast(lastPos));
+
+        flush();
+
+        curBlockArea = null;
+
+        checkEndOfLayout(lastPos);
+    }
+
+    /** {@inheritDoc} */
+    public boolean isRestartable() {
+        return true;
+    }
+
+}
diff --git a/src/java/org/apache/fop/layoutmgr/AlternativeManager.java b/src/java/org/apache/fop/layoutmgr/AlternativeManager.java
new file mode 100644
index 000000000..8ffc96a9e
--- /dev/null
+++ b/src/java/org/apache/fop/layoutmgr/AlternativeManager.java
@@ -0,0 +1,150 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.layoutmgr;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * A simple alternative manager that holds a set of {@link Alternative}
+ */
+public class AlternativeManager {
+
+    public static class Alternative {
+
+        /** remaining BPD after inserting the alternative */
+        private int remainingBPD;
+        /** width of the alternative in block-progressing-dimension */
+        private int width;
+        /** Knuth element list */
+        private List<ListElement> knuthList;
+
+        public Alternative(List<ListElement> knuthList, int width) {
+            this.knuthList = knuthList;
+            this.width = width;
+            this.remainingBPD = 0;
+        }
+        public List<ListElement> getKnuthList() {
+            return knuthList;
+        }
+        public int getRemainingBPD() {
+            return remainingBPD;
+        }
+        public int getWidth() {
+            return width;
+        }
+        public void setRemainingBPD(int remainingBPD) {
+            this.remainingBPD = remainingBPD;
+        }
+    }
+
+    public static enum FittingStrategy {
+
+        FIRST_FIT {
+
+            @Override
+            public Alternative filter(List<Alternative> alternatives) {
+                for (Alternative alt : alternatives) {
+                    if (alt.getRemainingBPD() > 0) {
+                        return alt;
+                    }
+                }
+                return null;
+            }
+        },
+
+        SMALLEST_FIT {
+
+            @Override
+            public Alternative filter(List<Alternative> alternatives) {
+                Iterator<Alternative> iter = alternatives.iterator();
+                int biggestDiff = -Integer.MAX_VALUE;
+                Alternative bestAlt = null;
+
+                while (iter.hasNext()) {
+                    Alternative alt = iter.next();
+                    if (alt.getRemainingBPD() > biggestDiff) {
+                        biggestDiff = alt.getRemainingBPD();
+                        bestAlt = alt;
+                    }
+                }
+                return bestAlt;
+            }
+        },
+
+        BIGGEST_FIT {
+
+            @Override
+            public Alternative filter(List<Alternative> alternatives) {
+                Iterator<Alternative> iter = alternatives.iterator();
+                int smallestDiff = Integer.MAX_VALUE;
+                Alternative bestAlt = null;
+
+                while (iter.hasNext()) {
+                    Alternative alt = iter.next();
+                    if (alt.getRemainingBPD() < smallestDiff) {
+                        smallestDiff = alt.getRemainingBPD();
+                        bestAlt = alt;
+                    }
+                }
+                return bestAlt;
+            }
+        };
+
+        public abstract Alternative filter(List<Alternative> alternatives);
+
+    }
+
+    private LinkedList<Alternative> alternatives;
+    private LinkedList<Alternative> bestAlternatives;
+
+    public AlternativeManager() {
+        alternatives = new LinkedList<Alternative>();
+        bestAlternatives = new LinkedList<Alternative>();
+    }
+
+    public void addAlternative(Alternative alt) {
+        alternatives.add(alt);
+    }
+
+    public boolean hasAny() {
+        return bestAlternatives.size() > 0;
+    }
+
+    public Alternative getNextBestAlternative() {
+        return bestAlternatives.removeFirst();
+    }
+
+    public Alternative getBestAlternative(FittingStrategy strategy) {
+        try {
+            Alternative bestAlt = strategy.filter(alternatives);
+            if (bestAlt != null) {
+                bestAlternatives.add(bestAlt);
+            }
+            return bestAlt;
+        } catch (NullPointerException e) {
+            return null;
+        } finally {
+            // We don't need the store alternatives anymore
+            alternatives.clear();
+        }
+    }
+}
diff --git a/src/java/org/apache/fop/layoutmgr/BestFitLayoutManager.java b/src/java/org/apache/fop/layoutmgr/BestFitLayoutManager.java
new file mode 100644
index 000000000..aca4d341b
--- /dev/null
+++ b/src/java/org/apache/fop/layoutmgr/BestFitLayoutManager.java
@@ -0,0 +1,277 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.layoutmgr;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Stack;
+
+import org.apache.fop.area.Area;
+import org.apache.fop.area.Block;
+import org.apache.fop.area.LineArea;
+import org.apache.fop.fo.extensions.BestFit;
+import org.apache.fop.layoutmgr.AlternativeManager.Alternative;
+import org.apache.fop.layoutmgr.AlternativeManager.FittingStrategy;
+
+/**
+ * LayoutManager for a fox:best-fit. It selects the "best" alternative
+ * to render based on the chosen fitting strategy.
+ */
+public class BestFitLayoutManager extends AbstractLayoutManager {
+
+    private Block curBlockArea;
+
+    private static class BestFitPosition extends Position {
+
+        public BestFitPosition(LayoutManager lm) {
+            super(lm);
+        }
+
+    }
+
+    private FittingStrategy fittingStrategy;
+
+    public BestFitLayoutManager(BestFit node) {
+        super(node);
+        fittingStrategy = node.getStrategy();
+        setGeneratesBlockArea(true);
+    }
+
+    /**
+     * Creates and initializes a {@link LayoutContext} to pass to the child LM
+     *
+     * @param context the parent {@link LayoutContext}
+     * @return a new child layout context
+     */
+    protected LayoutContext makeChildLayoutContext(LayoutContext context) {
+        LayoutContext childLC = LayoutContext.newInstance();
+        childLC.copyPendingMarksFrom(context);
+        childLC.setStackLimitBP(context.getStackLimitBP());
+        childLC.setRefIPD(context.getRefIPD());
+        childLC.setWritingMode(context.getWritingMode());
+        return childLC;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public List getNextKnuthElements(LayoutContext context, int alignment) {
+        return getNextKnuthElements(context, alignment, null, null, null);
+    }
+
+    /** {@inheritDoc} */
+    public List getNextKnuthElements(LayoutContext context, int alignment,
+            Stack lmStack, Position positionAtIPDChange,
+            LayoutManager restartAtLM) {
+        LayoutManager curLM; // currently active LM
+        BestFitPenalty bestFitPenalty =
+                new BestFitPenalty(fittingStrategy, new BestFitPosition(this));
+        while ((curLM = getChildLM()) != null) {
+            LayoutContext childLC = makeChildLayoutContext(context);
+
+            List returnedList = null;
+            if (!curLM.isFinished()) {
+                returnedList = curLM.getNextKnuthElements(childLC, alignment);
+            }
+            if (returnedList != null) {
+                List<ListElement> returnList = new LinkedList<ListElement>();
+                this.wrapPositionElements(returnedList, returnList);
+                int contentLength = ElementListUtils.calcFullContentLength(returnList);
+                // Add a new variant
+                bestFitPenalty.addAlternative(new Alternative(returnList, contentLength));
+            }
+        }
+        setFinished(true);
+        List<ListElement> finalList = new LinkedList<ListElement>();
+        // Insert an empty Knuth box to prevent the layout engine from ignoring our penalty
+        finalList.add(new KnuthBox(0, new Position(this), false));
+        finalList.add(bestFitPenalty);
+        return finalList;
+    }
+
+    /**
+     * "wrap" the Position inside each element moving the elements from
+     * SourceList to targetList
+     *
+     * @param sourceList source list
+     * @param targetList target list receiving the wrapped position elements
+     */
+    protected void wrapPositionElements(List sourceList, List targetList) {
+        wrapPositionElements(sourceList, targetList, false);
+    }
+
+    /**
+     * "wrap" the Position inside each element moving the elements from
+     * SourceList to targetList
+     *
+     * @param sourceList source list
+     * @param targetList target list receiving the wrapped position elements
+     * @param force if true, every Position is wrapped regardless of its LM of origin
+     */
+    protected void wrapPositionElements(List sourceList, List targetList,
+            boolean force) {
+
+        ListIterator listIter = sourceList.listIterator();
+        Object tempElement;
+        while (listIter.hasNext()) {
+            tempElement = listIter.next();
+            if (tempElement instanceof ListElement) {
+                wrapPositionElement((ListElement) tempElement, targetList,
+                        force);
+            } else if (tempElement instanceof List) {
+                wrapPositionElements((List) tempElement, targetList, force);
+            }
+        }
+    }
+
+    /**
+     * "wrap" the Position inside the given element and add it to the target list.
+     *
+     * @param el the list element
+     * @param targetList target list receiving the wrapped position elements
+     * @param force if true, every Position is wrapped regardless of its LM of origin
+     */
+    protected void wrapPositionElement(ListElement el, List targetList,
+            boolean force) {
+        if (force || el.getLayoutManager() != this) {
+            el.setPosition(notifyPos(new NonLeafPosition(this, el.getPosition())));
+        }
+        targetList.add(el);
+    }
+
+    @Override
+    public Area getParentArea(Area childArea) {
+        if (curBlockArea == null) {
+            curBlockArea = new Block();
+            // Set up dimensions
+            // Must get dimensions from parent area
+            /*Area parentArea = */parentLayoutManager.getParentArea(curBlockArea);
+        }
+        return curBlockArea;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public void addChildArea(Area childArea) {
+        if (curBlockArea != null) {
+            if (childArea instanceof LineArea) {
+                curBlockArea.addLineArea((LineArea) childArea);
+            } else {
+                curBlockArea.addBlock((Block) childArea);
+            }
+        }
+    }
+
+    /**
+     * Force current area to be added to parent area.
+     */
+    protected void flush() {
+        if (getCurrentArea() != null) {
+            parentLayoutManager.addChildArea(getCurrentArea());
+        }
+    }
+
+    private Area getCurrentArea() {
+        return curBlockArea;
+    }
+
+    /** {@inheritDoc} */
+    @Override
+    public void addAreas(PositionIterator parentIter,
+            LayoutContext layoutContext) {
+
+        getParentArea(null);
+
+        addId();
+
+        LayoutManager childLM;
+        LayoutContext lc = LayoutContext.offspringOf(layoutContext);
+        LayoutManager firstLM = null;
+        LayoutManager lastLM = null;
+        Position firstPos = null;
+        Position lastPos = null;
+
+        // "unwrap" the NonLeafPositions stored in parentIter
+        // and put them in a new list;
+        LinkedList<Position> positionList = new LinkedList<Position>();
+        Position pos;
+        AlternativeManager altManager = layoutContext.getAlternativeManager();
+        while (parentIter.hasNext()) {
+            pos = parentIter.next();
+            if (pos.getIndex() >= 0) {
+                if (firstPos == null) {
+                    firstPos = pos;
+                }
+                lastPos = pos;
+            }
+            if (pos instanceof NonLeafPosition && (pos.getPosition() != null)
+                    && pos.getPosition().getLM() != this) {
+                // pos was created by a child of this BestFitBlockLM
+                positionList.add(pos.getPosition());
+                lastLM = pos.getPosition().getLM();
+                if (firstLM == null) {
+                    firstLM = lastLM;
+                }
+            }
+            else if (pos instanceof BestFitPosition) {
+                if (altManager.hasAny()) {
+                    Alternative bestAlt = altManager.getNextBestAlternative();
+                    Iterator<ListElement> it = bestAlt.getKnuthList().iterator();
+                    while (it.hasNext()) {
+                        positionList.add(it.next().getPosition());
+                    }
+                }
+                lastLM = pos.getLM();
+                if (firstLM == null) {
+                    firstLM = lastLM;
+                }
+            }
+        }
+
+        //registerMarkers(true, isFirst(firstPos), isLast(lastPos));
+
+        PositionIterator childPosIter = new PositionIterator(
+                positionList.listIterator());
+        while ((childLM = childPosIter.getNextChildLM()) != null) {
+            // Add the block areas to Area
+            // set the space adjustment ratio
+            lc.setSpaceAdjust(layoutContext.getSpaceAdjust());
+            lc.setFlags(LayoutContext.FIRST_AREA, childLM == firstLM);
+            lc.setFlags(LayoutContext.LAST_AREA, childLM == lastLM);
+            lc.setStackLimitBP(layoutContext.getStackLimitBP());
+            childLM.addAreas(childPosIter, lc);
+        }
+
+        //registerMarkers(false, isFirst(firstPos), isLast(lastPos));
+
+        flush();
+
+        curBlockArea = null;
+
+        checkEndOfLayout(lastPos);
+    }
+
+    /** {@inheritDoc} */
+    public boolean isRestartable() {
+        return true;
+    }
+
+}
diff --git a/src/java/org/apache/fop/layoutmgr/BestFitPenalty.java b/src/java/org/apache/fop/layoutmgr/BestFitPenalty.java
new file mode 100644
index 000000000..6a9658d2a
--- /dev/null
+++ b/src/java/org/apache/fop/layoutmgr/BestFitPenalty.java
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* $Id$ */
+
+package org.apache.fop.layoutmgr;
+
+import java.util.LinkedList;
+
+import org.apache.fop.layoutmgr.AlternativeManager.Alternative;
+import org.apache.fop.layoutmgr.AlternativeManager.FittingStrategy;
+
+/**
+ * A dummy penalty used in {@link BestFitLayoutManager} to store
+ * the different alternatives in {@link fox:best-fit}
+ */
+
+public class BestFitPenalty extends KnuthPenalty {
+
+    private LinkedList<Alternative> alternatives;
+    private FittingStrategy strategy;
+
+    public BestFitPenalty(FittingStrategy strategy, Position pos) {
+        super(0, 0, false, pos, false);
+        this.strategy = strategy;
+        alternatives = new LinkedList<Alternative>();
+    }
+
+    public void addAlternative(Alternative alternative) {
+        alternatives.add(alternative);
+    }
+
+    public Alternative getAlternative(int index) {
+        return alternatives.get(index);
+    }
+
+    public int getAlternativeCount() {
+        return alternatives.size();
+    }
+
+    public FittingStrategy getStrategyType() {
+        return strategy;
+    }
+
+    /** {@inheritDoc} */
+    public String toString() {
+        String str = super.toString();
+        StringBuffer buffer = new StringBuffer(64);
+        buffer.append(" number of alternatives = " + getAlternativeCount());
+        buffer.append(" fitting-strategy = " + strategy);
+        return str + buffer.toString();
+    }
+
+}
diff --git a/src/java/org/apache/fop/layoutmgr/BreakingAlgorithm.java b/src/java/org/apache/fop/layoutmgr/BreakingAlgorithm.java
index c7048295f..54d68c3d8 100644
--- a/src/java/org/apache/fop/layoutmgr/BreakingAlgorithm.java
+++ b/src/java/org/apache/fop/layoutmgr/BreakingAlgorithm.java
@@ -23,6 +23,7 @@ import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
 
 import org.apache.fop.fo.Constants;
+import org.apache.fop.layoutmgr.AlternativeManager.Alternative;
 
 /**
  * The set of nodes is sorted into lines indexed into activeLines.
@@ -192,6 +193,8 @@ public abstract class BreakingAlgorithm {
     private boolean partOverflowRecoveryActivated = true;
     private KnuthNode lastRecovered;
 
+    private AlternativeManager altManager = new AlternativeManager();
+
     /**
      * Create a new instance.
      *
@@ -822,6 +825,30 @@ public abstract class BreakingAlgorithm {
         }
     }
 
+    private int handleBestFitPenalty(BestFitPenalty penalty, KnuthNode node,
+            int elementIdx) {
+        int difference;
+        // Find the alternatives that can be fitted inside the remaining space
+        for (int i = 0; i < penalty.getAlternativeCount(); ++i) {
+            Alternative alt = penalty.getAlternative(i);
+            difference = computeDifference(node, new KnuthPenalty(alt.getWidth(),
+                    0, false, null, false), elementIdx);
+            if (difference > 0) {
+                alt.setRemainingBPD(difference);
+                altManager.addAlternative(alt);
+            }
+        }
+        Alternative bestAlt = altManager.getBestAlternative(penalty.getStrategyType());
+        if (bestAlt != null) {
+            difference = bestAlt.getRemainingBPD();
+            return difference;
+        } else {
+            // No alternative can be fitted inside the remaining space
+            return computeDifference(node, new KnuthPenalty(0,
+                    0, false, null, false), elementIdx);
+        }
+    }
+
     /**
      * Replace the last too-long or too-short node by the last deactivated
      * node, if applicable.
@@ -930,7 +957,13 @@ public abstract class BreakingAlgorithm {
                 if (node.position == elementIdx) {
                     continue;
                 }
-                int difference = computeDifference(node, element, elementIdx);
+                int difference;
+                if (element instanceof BestFitPenalty) {
+                    BestFitPenalty penalty = (BestFitPenalty)element;
+                    difference = handleBestFitPenalty(penalty, node, elementIdx);
+                } else {
+                    difference = computeDifference(node, element, elementIdx);
+                }
                 if (!elementCanEndLine(element, endLine, difference)) {
                     log.trace("Skipping legal break");
                     break;
@@ -1451,4 +1484,9 @@ public abstract class BreakingAlgorithm {
         return this.alignmentLast;
     }
 
+    /** @return the alternative manager (used by fox:best-fit) */
+    public AlternativeManager getAlternativeManager() {
+        return altManager;
+    }
+
 }
diff --git a/src/java/org/apache/fop/layoutmgr/ElementListUtils.java b/src/java/org/apache/fop/layoutmgr/ElementListUtils.java
index 2bd6f429a..d16bd3117 100644
--- a/src/java/org/apache/fop/layoutmgr/ElementListUtils.java
+++ b/src/java/org/apache/fop/layoutmgr/ElementListUtils.java
@@ -163,6 +163,37 @@ public final class ElementListUtils {
     }
 
     /**
+     * Calculates the full content length of the given element list. Warning: It doesn't take any
+     * stretch and shrink possibilities into account.
+     * @param elems the element list
+     * @return the content length
+     */
+    public static int calcFullContentLength(List elems) {
+        ListIterator iter = elems.listIterator(0);
+        int count = elems.size();
+        int len = 0;
+        while (iter.hasNext()) {
+            ListElement el = (ListElement)iter.next();
+            if (el.isBox()) {
+                len += ((KnuthElement)el).getWidth();
+            } else if (el.isGlue()) {
+                len += ((KnuthElement)el).getWidth();
+            }
+            else if (el.isUnresolvedElement() && (el instanceof BreakElement) == false) {
+                // Handle properties space-before and space-after
+                UnresolvedListElementWithLength uresolvedEl = (UnresolvedListElementWithLength)el;
+                if (uresolvedEl.isLast() || uresolvedEl.isFirst())
+                    len += uresolvedEl.getLength().getOpt();
+            }
+            count--;
+            if (count == 0) {
+                break;
+            }
+        }
+        return len;
+    }
+
+    /**
      * Calculates the content length of the given element list. Warning: It doesn't take any
      * stretch and shrink possibilities into account.
      * @param elems the element list
@@ -201,7 +232,7 @@ public final class ElementListUtils {
         if (last.isPenalty() && ((KnuthPenalty)last).getPenalty() < KnuthElement.INFINITE) {
             return true;
         } else if (last instanceof BreakElement
-                        && ((BreakElement)last).getPenaltyValue() < KnuthElement.INFINITE) {
+                && ((BreakElement)last).getPenaltyValue() < KnuthElement.INFINITE) {
             return true;
         }
         return false;
diff --git a/src/java/org/apache/fop/layoutmgr/FlowLayoutManager.java b/src/java/org/apache/fop/layoutmgr/FlowLayoutManager.java
index 0260046e1..ae99ba578 100644
--- a/src/java/org/apache/fop/layoutmgr/FlowLayoutManager.java
+++ b/src/java/org/apache/fop/layoutmgr/FlowLayoutManager.java
@@ -204,6 +204,7 @@ public class FlowLayoutManager extends BlockStackingLayoutManager
         childLC.setStackLimitBP(context.getStackLimitBP());
         childLC.setRefIPD(context.getRefIPD());
         childLC.setWritingMode(getCurrentPage().getSimplePageMaster().getWritingMode());
+        childLC.setAlternativeManager(context.getAlternativeManager());
         return childLC;
     }
 
diff --git a/src/java/org/apache/fop/layoutmgr/LayoutContext.java b/src/java/org/apache/fop/layoutmgr/LayoutContext.java
index 21983c20f..3120b147e 100644
--- a/src/java/org/apache/fop/layoutmgr/LayoutContext.java
+++ b/src/java/org/apache/fop/layoutmgr/LayoutContext.java
@@ -23,6 +23,7 @@ import java.util.Collections;
 import java.util.List;
 
 import org.apache.fop.fo.Constants;
+import org.apache.fop.fo.extensions.AlternativeBlock;
 import org.apache.fop.layoutmgr.inline.AlignmentContext;
 import org.apache.fop.layoutmgr.inline.HyphContext;
 import org.apache.fop.traits.MinOptMax;
@@ -35,6 +36,9 @@ import org.apache.fop.traits.WritingMode;
  */
 public final class LayoutContext {
 
+    /** Manager of @{link {@link AlternativeBlock} and only used by {@link BestFitLayoutManager}*/
+    private AlternativeManager altManager;
+
     /** Generated break possibility is first in a new area */
     public static final int NEW_AREA = 0x01;
 
@@ -142,6 +146,7 @@ public final class LayoutContext {
     public static LayoutContext offspringOf(LayoutContext parent) {
         LayoutContext offspring = new LayoutContext(0);
         offspring.setTreatAsArtifact(parent.treatAsArtifact());
+        offspring.setAlternativeManager(parent.getAlternativeManager());
         return offspring;
     }
 
@@ -646,24 +651,24 @@ public final class LayoutContext {
     /** {@inheritDoc} */
     public String toString() {
         return "Layout Context:"
-        + "\nStack Limit BPD: \t"
-            + (getStackLimitBP() == null ? "null" : getStackLimitBP().toString())
-        + "\nTrailing Space: \t"
-            + (getTrailingSpace() == null ? "null" : getTrailingSpace().toString())
-        + "\nLeading Space: \t"
-            + (getLeadingSpace() == null ? "null" : getLeadingSpace().toString())
-        + "\nReference IPD: \t" + getRefIPD()
-        + "\nSpace Adjust: \t" + getSpaceAdjust()
-        + "\nIPD Adjust: \t" + getIPDAdjust()
-        + "\nResolve Leading Space: \t" + resolveLeadingSpace()
-        + "\nSuppress Break Before: \t" + suppressBreakBefore()
-        + "\nIs First Area: \t" + isFirstArea()
-        + "\nStarts New Area: \t" + startsNewArea()
-        + "\nIs Last Area: \t" + isLastArea()
-        + "\nKeeps: \t[keep-with-next=" + getKeepWithNextPending()
+                + "\nStack Limit BPD: \t"
+                + (getStackLimitBP() == null ? "null" : getStackLimitBP().toString())
+                + "\nTrailing Space: \t"
+                + (getTrailingSpace() == null ? "null" : getTrailingSpace().toString())
+                + "\nLeading Space: \t"
+                + (getLeadingSpace() == null ? "null" : getLeadingSpace().toString())
+                + "\nReference IPD: \t" + getRefIPD()
+                + "\nSpace Adjust: \t" + getSpaceAdjust()
+                + "\nIPD Adjust: \t" + getIPDAdjust()
+                + "\nResolve Leading Space: \t" + resolveLeadingSpace()
+                + "\nSuppress Break Before: \t" + suppressBreakBefore()
+                + "\nIs First Area: \t" + isFirstArea()
+                + "\nStarts New Area: \t" + startsNewArea()
+                + "\nIs Last Area: \t" + isLastArea()
+                + "\nKeeps: \t[keep-with-next=" + getKeepWithNextPending()
                 + "][keep-with-previous=" + getKeepWithPreviousPending() + "] pending"
-        + "\nBreaks: \tforced [" + (breakBefore != Constants.EN_AUTO ? "break-before" : "") + "]["
-        + (breakAfter != Constants.EN_AUTO ? "break-after" : "") + "]";
+                + "\nBreaks: \tforced [" + (breakBefore != Constants.EN_AUTO ? "break-before" : "") + "]["
+                + (breakAfter != Constants.EN_AUTO ? "break-after" : "") + "]";
     }
 
     /**
@@ -692,5 +697,13 @@ public final class LayoutContext {
     public void setTreatAsArtifact(boolean treatAsArtifact) {
         setFlags(TREAT_AS_ARTIFACT, treatAsArtifact);
     }
+
+    public void setAlternativeManager(AlternativeManager altManager) {
+        this.altManager = altManager;
+    }
+
+    public AlternativeManager getAlternativeManager() {
+        return altManager;
+    }
 }
 
diff --git a/src/java/org/apache/fop/layoutmgr/LayoutManagerMapping.java b/src/java/org/apache/fop/layoutmgr/LayoutManagerMapping.java
index 292251a84..2d08e674c 100644
--- a/src/java/org/apache/fop/layoutmgr/LayoutManagerMapping.java
+++ b/src/java/org/apache/fop/layoutmgr/LayoutManagerMapping.java
@@ -34,6 +34,8 @@ import org.apache.fop.fo.FONode;
 import org.apache.fop.fo.FONode.FONodeIterator;
 import org.apache.fop.fo.FOText;
 import org.apache.fop.fo.FObjMixed;
+import org.apache.fop.fo.extensions.AlternativeBlock;
+import org.apache.fop.fo.extensions.BestFit;
 import org.apache.fop.fo.extensions.ExternalDocument;
 import org.apache.fop.fo.flow.BasicLink;
 import org.apache.fop.fo.flow.BidiOverride;
@@ -142,6 +144,8 @@ public class LayoutManagerMapping implements LayoutManagerMaker {
         registerMaker(TableHeader.class, new Maker());
         registerMaker(Wrapper.class, new WrapperLayoutManagerMaker());
         registerMaker(Title.class, new InlineLayoutManagerMaker());
+        registerMaker(BestFit.class, new BestFitLayoutManagerMaker());
+        registerMaker(AlternativeBlock.class, new AlternativeBlockLayoutManagerMaker());
     }
 
     /**
@@ -445,4 +449,20 @@ public class LayoutManagerMapping implements LayoutManagerMaker {
         }
     }
 
+    /** a layout manager maker */
+    public class BestFitLayoutManagerMaker extends Maker {
+        /** {@inheritDoc} */
+        public void make(FONode node, List lms) {
+            lms.add(new BestFitLayoutManager((BestFit) node));
+        }
+    }
+
+    /** a layout manager maker */
+    public class AlternativeBlockLayoutManagerMaker extends Maker {
+        /** {@inheritDoc} */
+        public void make(FONode node, List lms) {
+            lms.add(new AlternativeBlockLayoutManager((AlternativeBlock) node));
+        }
+    }
+
 }
diff --git a/src/java/org/apache/fop/layoutmgr/PageBreakingAlgorithm.java b/src/java/org/apache/fop/layoutmgr/PageBreakingAlgorithm.java
index 59145dd72..81aff8845 100644
--- a/src/java/org/apache/fop/layoutmgr/PageBreakingAlgorithm.java
+++ b/src/java/org/apache/fop/layoutmgr/PageBreakingAlgorithm.java
@@ -26,7 +26,6 @@ import java.util.ListIterator;
 
 import org.apache.commons.logging.Log;
 import org.apache.commons.logging.LogFactory;
-
 import org.apache.fop.fo.Constants;
 import org.apache.fop.fo.FObj;
 import org.apache.fop.layoutmgr.AbstractBreaker.PageBreakPosition;