/* ====================================================================
   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.
==================================================================== */

package org.apache.poi.util;

import java.util.Comparator;

import org.apache.xmlbeans.XmlCursor;
import org.apache.xmlbeans.XmlObject;

public final class XmlSort {
    /**
     * Sorts the children of <code>element</code> according to the order indicated by the
     * comparator.
     * @param element the element whose content is to be sorted. Only element children are sorted,
     * attributes are not touched. When elements are reordered, all the text, comments and PIs
     * follow the element that they come immediately after.
     * @param comp a comparator that is to be used when comparing the <code>QName</code>s of two
     * elements. 
     * @throws IllegalArgumentException if the input <code>XmlObject</code> does not represent
     * an element
     */
    public static void sort(XmlObject element, Comparator<XmlCursor> comp) {
        XmlCursor headCursor = element.newCursor();
        if (!headCursor.isStart()) {
            throw new IllegalStateException("The element parameter must point to a STARTDOC");
        }
        // We use insertion sort to minimize the number of swaps, because each swap means
        // moving a part of the document
        /* headCursor points to the beginning of the list of the already sorted items and
           listCursor points to the beginning of the list of unsorted items
           At the beginning, headCursor points to the first element and listCursor points to the
           second element. The algorithm ends when listCursor cannot be moved to the "next"
           element in the unsorted list, i.e. the unsorted list becomes empty */
        boolean moved = headCursor.toFirstChild();
        if (!moved) {
            // Cursor was not moved, which means that the given element has no children and
            // therefore there is nothing to sort
            return;
        }
        XmlCursor listCursor = headCursor.newCursor();
        boolean moreElements = listCursor.toNextSibling();
        while (moreElements) {
            moved = false;
            // While we can move the head of the unsorted list, it means that there are still
            // items (elements) that need to be sorted
            while (headCursor.comparePosition(listCursor) < 0) {
                if (comp.compare(headCursor, listCursor) > 0) {
                    // We have found the position in the sorted list, insert the element and the
                    // text following the element in the current position
                    // Move the element
                    listCursor.moveXml(headCursor);
                    // Move the text following the element
                    while (!listCursor.isStart() && !listCursor.isEnd())
                        listCursor.moveXml(headCursor);
                    moreElements = listCursor.isStart();
                    moved = true;
                    break;
                }
                headCursor.toNextSibling();
            }
            if (!moved) {
                // Because during the move of a fragment of XML, the listCursor is also moved, in
                // case we didn't need to move XML (the new element to be inserted happened to
                // be the last one in order), we need to move this cursor
                moreElements = listCursor.toNextSibling();
            }
            // Reposition the head of the sorted list
            headCursor.toParent();
            headCursor.toFirstChild();
        }
    }
}