Source code

001/*
002 * This library is part of OpenCms -
003 * the Open Source Content Management System
004 *
005 * Copyright (c) Alkacon Software GmbH & Co. KG (http://www.alkacon.com)
006 *
007 * This library is free software; you can redistribute it and/or
008 * modify it under the terms of the GNU Lesser General Public
009 * License as published by the Free Software Foundation; either
010 * version 2.1 of the License, or (at your option) any later version.
011 *
012 * This library is distributed in the hope that it will be useful,
013 * but WITHOUT ANY WARRANTY; without even the implied warranty of
014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 * Lesser General Public License for more details.
016 *
017 * For further information about Alkacon Software, please see the
018 * company website: http://www.alkacon.com
019 *
020 * For further information about OpenCms, please see the
021 * project website: http://www.opencms.org
022 *
023 * You should have received a copy of the GNU Lesser General Public
024 * License along with this library; if not, write to the Free Software
025 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
026 */
027
028package org.opencms.ade.sitemap;
029
030import org.opencms.file.CmsResource;
031import org.opencms.jsp.CmsJspNavElement;
032import org.opencms.main.CmsLog;
033
034import java.util.ArrayList;
035import java.util.Collections;
036import java.util.HashMap;
037import java.util.Iterator;
038import java.util.List;
039
040import org.apache.commons.logging.Log;
041
042/**
043 * Helper class for recalculating navigation positions when a user has changed the order of navigation entries in the sitemap
044 * editor.<p>
045 *
046 *  This is harder than it sounds because we need to handle special cases like e.g. the user inserting an entry
047 * between two existing entries with the same navigation position, which means we need to update the navigation positions
048 * of multiple entries to force the ordering which the user wanted.<p>
049 */
050public class CmsSitemapNavPosCalculator {
051
052    /**
053     * Internal class which encapsulates information about a position in the navigation list.<p>
054     */
055    private class PositionInfo {
056
057        /** Flag which indicates whether the position is inside the navigation list. */
058        private boolean m_exists;
059
060        /** The navigation position as a float. */
061        private float m_navPos;
062
063        /**
064         * Creates a new position info bean.<p>
065         *
066         * @param exists true if the position is not out of bounds
067         *
068         * @param navPos the navigation position
069         */
070        public PositionInfo(boolean exists, float navPos) {
071
072            m_exists = exists;
073            m_navPos = navPos;
074        }
075
076        /**
077         * Gets the navigation position.
078         *
079         * @return the navigation position
080         */
081        public float getNavPos() {
082
083            return m_navPos;
084        }
085
086        /**
087         * Checks whether there is a maximal nav pos value at the position.<p>
088         *
089         * @return true if there is a maximal nav pos value at the position
090         */
091        public boolean isMax() {
092
093            return m_navPos == Float.MAX_VALUE;
094        }
095
096        /**
097         * Returns true if the position is neither out of bounds nor a position with a maximal nav pos value.<p>
098         *
099         * @return true if the position is neither out of bounds nor a position with a maximal nav pos value
100         */
101        public boolean isNormal() {
102
103            return !isOutOfBounds() && !isMax();
104        }
105
106        /**
107         * Returns true if the position is not in the list of navigation entries.<p>
108         *
109         * @return true if the position is not in the list of navigation entries
110         */
111        public boolean isOutOfBounds() {
112
113            return !m_exists;
114        }
115    }
116
117    /** Dummy file name for the inserted dummy navigation element. */
118    public static final String DUMMY_PATH = "@moved@";
119
120    /** The logger instance for this class. */
121    private static final Log LOG = CmsLog.getLog(CmsSitemapNavPosCalculator.class);
122
123    /** The insert position in the final result list. */
124    private int m_insertPositionInResult;
125
126    /** The final result list. */
127    private List<CmsJspNavElement> m_resultList;
128
129    /**
130     * Creates a new sitemap navigation position calculator and performs the navigation position calculation for a given
131     * insertion operation.<p>
132     *
133     * @param navigation the existing navigation element list
134     * @param movedElement the resource which should be inserted
135     * @param insertPosition the insertion position in the list
136     */
137    public CmsSitemapNavPosCalculator(List<CmsJspNavElement> navigation, CmsResource movedElement, int insertPosition) {
138
139        List<CmsJspNavElement> workList = new ArrayList<CmsJspNavElement>(navigation);
140        CmsJspNavElement dummyNavElement = new CmsJspNavElement(
141            DUMMY_PATH,
142            movedElement,
143            new HashMap<String, String>());
144
145        // There may be another navigation element for the same resource in the navigation, so remove it
146        for (int i = 0; i < workList.size(); i++) {
147            CmsJspNavElement currentElement = workList.get(i);
148            if ((i != insertPosition)
149                && currentElement.getResource().getStructureId().equals(movedElement.getStructureId())) {
150                workList.remove(i);
151                break;
152            }
153        }
154        if (insertPosition > workList.size()) {
155            // could happen if the navigation was concurrently changed by another user
156            insertPosition = workList.size();
157        }
158        // First, insert the dummy element at the correct position in the list.
159        workList.add(insertPosition, dummyNavElement);
160
161        // now remove elements which aren't actually part of the navigation
162        Iterator<CmsJspNavElement> it = workList.iterator();
163        while (it.hasNext()) {
164            CmsJspNavElement nav = it.next();
165            if (!nav.isInNavigation() && (nav != dummyNavElement)) {
166                it.remove();
167            }
168        }
169        insertPosition = workList.indexOf(dummyNavElement);
170        m_insertPositionInResult = insertPosition;
171
172        /*
173         * Now calculate the "block" of the inserted element.
174         * The block is the range of indices for which the navigation
175         * positions need to be updated. This range only needs to contain
176         * more than the inserted element if it was inserted either between two elements
177         * with the same navigation position or after an element with Float.MAX_VALUE
178         * navigation position. In either of those two cases, the block will contain
179         * all elements with the same navigation position.
180         */
181
182        int blockStart = insertPosition;
183        int blockEnd = insertPosition + 1;
184
185        PositionInfo before = getPositionInfo(workList, insertPosition - 1);
186        PositionInfo after = getPositionInfo(workList, insertPosition + 1);
187        boolean extendBlock = false;
188        float blockValue = 0;
189
190        if (before.isMax()) {
191            blockValue = Float.MAX_VALUE;
192            extendBlock = true;
193        } else if (before.isNormal() && after.isNormal() && (before.getNavPos() == after.getNavPos())) {
194            blockValue = before.getNavPos();
195            extendBlock = true;
196        }
197        if (extendBlock) {
198            while ((blockStart > 0) && (workList.get(blockStart - 1).getNavPosition() == blockValue)) {
199                blockStart -= 1;
200            }
201            while ((blockEnd < workList.size())
202                && ((blockEnd == (insertPosition + 1)) || (workList.get(blockEnd).getNavPosition() == blockValue))) {
203                blockEnd += 1;
204            }
205        }
206
207        /*
208         * Now calculate the new navigation positions for the elements in the block using the information
209         * from the elements directly before and after the block, and set the positions in the nav element
210         * instances.
211         */
212        PositionInfo beforeBlock = getPositionInfo(workList, blockStart - 1);
213        PositionInfo afterBlock = getPositionInfo(workList, blockEnd);
214
215        // now calculate the new navigation positions for the elements in the block (
216
217        List<Float> newNavPositions = interpolatePositions(beforeBlock, afterBlock, blockEnd - blockStart);
218        for (int i = 0; i < (blockEnd - blockStart); i++) {
219            workList.get(i + blockStart).setNavPosition(newNavPositions.get(i).floatValue());
220        }
221        m_resultList = Collections.unmodifiableList(workList);
222    }
223
224    /**
225     * Gets the insert position in the final result list.<p>
226     *
227     * @return the insert position in the final result
228     */
229    public int getInsertPositionInResult() {
230
231        return m_insertPositionInResult;
232    }
233
234    /**
235     * Gets the changed navigation entries from the final result list.<p>
236     *
237     * @return the changed navigation entries for the final result list
238     */
239    public List<CmsJspNavElement> getNavigationChanges() {
240
241        List<CmsJspNavElement> newNav = getResultList();
242        List<CmsJspNavElement> changedElements = new ArrayList<CmsJspNavElement>();
243        for (CmsJspNavElement elem : newNav) {
244            if (elem.hasChangedNavPosition()) {
245                changedElements.add(elem);
246            }
247        }
248        return changedElements;
249    }
250
251    /**
252     * Gets the final result list.<p>
253     *
254     * @return the final  result list
255     */
256    public List<CmsJspNavElement> getResultList() {
257
258        return m_resultList;
259    }
260
261    /**
262     * Gets the position info bean for a given position.<p>
263     *
264     * @param navigation the navigation element list
265     * @param index the index in the navigation element list
266     *
267     * @return the position info bean for a given position
268     */
269    private PositionInfo getPositionInfo(List<CmsJspNavElement> navigation, int index) {
270
271        if ((index < 0) || (index >= navigation.size())) {
272            return new PositionInfo(false, -1);
273        }
274        float navPos = navigation.get(index).getNavPosition();
275        return new PositionInfo(true, navPos);
276    }
277
278    /**
279     * Helper method to generate a list of floats between two given values.<p>
280     *
281     * @param min the lower bound
282     * @param max the upper bound
283     * @param steps the number of floats to generate
284     *
285     * @return the generated floats
286     */
287    private List<Float> interpolateBetween(float min, float max, int steps) {
288
289        float delta = (max - min) / (steps + 1);
290        List<Float> result = new ArrayList<Float>();
291        float num = min;
292
293        for (int i = 0; i < steps; i++) {
294            num += delta;
295            result.add(Float.valueOf(num));
296        }
297        return result;
298    }
299
300    /**
301     * Helper method to generate an ascending list of floats below a given number.<p>
302     *
303     * @param max the upper bound
304     * @param steps the number of floats to generate
305     *
306     * @return the generated floats
307     */
308    private List<Float> interpolateDownwards(float max, int steps) {
309
310        List<Float> result = new ArrayList<Float>();
311        if (max > 0) {
312            // We try to generate a "nice" descending list of non-negative floats
313            // where the step size is bigger for bigger "max" values.
314            float base = (max > 1) ? (float)Math.floor(max) : max;
315            float stepSize = 1000f;
316
317            // reduce step size until the smallest element is greater than max/10.
318            while ((base - (steps * stepSize)) < (max / 10.0f)) {
319                stepSize = reduceStepSize(stepSize);
320            }
321            // we have determined the step size, now we generate the actual numbers
322            for (int i = 0; i < steps; i++) {
323                result.add(Float.valueOf(base - ((i + 1) * stepSize)));
324            }
325            Collections.reverse(result);
326        } else {
327            LOG.warn("Invalid navpos value: " + max);
328            for (int i = 0; i < steps; i++) {
329                result.add(Float.valueOf(max - (i + 1)));
330            }
331            Collections.reverse(result);
332        }
333        return result;
334    }
335
336    /**
337     * Helper method to generate an ascending list of floats.<p>
338     *
339     * @param steps the number of floats to generate
340     *
341     * @return the generated floats
342     */
343    private List<Float> interpolateEmpty(int steps) {
344
345        List<Float> result = new ArrayList<Float>();
346        for (int i = 0; i < steps; i++) {
347            result.add(Float.valueOf(1 + i));
348        }
349        return result;
350    }
351
352    /**
353     * Generates the new navigation positions for a range of navigation items.<p>
354     *
355     * @param left the position info for the navigation entry left of the range
356     * @param right the position info for the navigation entry right of the range
357     * @param steps the number of entries in the range
358     *
359     * @return the list of new navigation positions
360     */
361    private List<Float> interpolatePositions(PositionInfo left, PositionInfo right, int steps) {
362
363        if (left.isOutOfBounds()) {
364            if (right.isNormal()) {
365                return interpolateDownwards(right.getNavPos(), steps);
366            } else if (right.isMax() || right.isOutOfBounds()) {
367                return interpolateEmpty(steps);
368            } else {
369                // can't happen
370                assert false;
371            }
372        } else if (left.isNormal()) {
373            if (right.isOutOfBounds() || right.isMax()) {
374                return interpolateUpwards(left.getNavPos(), steps);
375            } else if (right.isNormal()) {
376                return interpolateBetween(left.getNavPos(), right.getNavPos(), steps);
377            } else {
378                // can't happen
379                assert false;
380            }
381        } else {
382            // can't happen
383            assert false;
384        }
385        return null;
386
387    }
388
389    /**
390     * Helper method for generating an ascending list of floats above a given number.<p>
391     *
392     * @param min the lower bound
393     * @param steps the number of floats to generate
394     *
395     * @return the generated floats
396     */
397    private List<Float> interpolateUpwards(float min, int steps) {
398
399        List<Float> result = new ArrayList<Float>();
400        for (int i = 0; i < steps; i++) {
401            result.add(Float.valueOf(min + 1 + i));
402        }
403        return result;
404    }
405
406    /**
407     * Reduces the step size for generating descending navpos sequences.<p>
408     *
409     * @param oldStepSize the previous step size
410     *
411     * @return the new (smaller) step size
412     */
413    private float reduceStepSize(float oldStepSize) {
414
415        if (oldStepSize > 1) {
416            // try to reduce unnecessary digits after the decimal point
417            return oldStepSize / 10f;
418        } else {
419            return oldStepSize / 2f;
420        }
421    }
422}