/*

 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 * 

 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR

 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.

 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

#include "config.h"

#if ENABLE(XPATH)

#include "XPathNodeSet.h"

#include "Attr.h"

#include "Element.h"

#include "Node.h"

namespace WebCore {

namespace XPath {

static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)

{

    ASSERT(parents.size() >= depth + 1);

    return parents[parents.size() - 1 - depth];

}

static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)

{

    ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.

    unsigned minDepth = UINT_MAX;

    for (unsigned i = from; i < to; ++i) {

        unsigned depth = parentMatrix[i].size() - 1;

        if (minDepth > depth)

            minDepth = depth;

    }

    // Find the common ancestor.

    unsigned commonAncestorDepth = minDepth;

    Node* commonAncestor;

    while (true) {

        commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);

        if (commonAncestorDepth == 0)

            break;

        bool allEqual = true;

        for (unsigned i = from + 1; i < to; ++i) {

            if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {

                allEqual = false;

                break;

            }

        }

        if (allEqual)

            break;

        --commonAncestorDepth;

    }

    if (commonAncestorDepth == minDepth) {

        // One of the nodes is the common ancestor => it is the first in document order.

        // Find it and move it to the beginning.

        for (unsigned i = from; i < to; ++i)

            if (commonAncestor == parentMatrix[i][0]) {

                parentMatrix[i].swap(parentMatrix[from]);

                if (from + 2 < to)

                    sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);

                return;

            }

    }

    if (mayContainAttributeNodes && commonAncestor->isElementNode()) {

        // The attribute nodes and namespace nodes of an element occur before the children of the element.

        // The namespace nodes are defined to occur before the attribute nodes.

        // The relative order of namespace nodes is implementation-dependent.

        // The relative order of attribute nodes is implementation-dependent.

        unsigned sortedEnd = from;

        // FIXME: namespace nodes are not implemented.

        for (unsigned i = sortedEnd; i < to; ++i) {

            Node* n = parentMatrix[i][0];

            if (n->isAttributeNode() && static_cast<Attr*>(n)->ownerElement() == commonAncestor)

                parentMatrix[i].swap(parentMatrix[sortedEnd++]);

        }

        if (sortedEnd != from) {

            if (to - sortedEnd > 1)

                sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);

            return;

        }

    }

    // Children nodes of the common ancestor induce a subdivision of our node-set.

    // Sort it according to this subdivision, and recursively sort each group.

    HashSet<Node*> parentNodes;

    for (unsigned i = from; i < to; ++i)

        parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));

    unsigned previousGroupEnd = from;

    unsigned groupEnd = from;

    for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {

        // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.

        if (parentNodes.contains(n)) {

            for (unsigned i = groupEnd; i < to; ++i)

                if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)

                    parentMatrix[i].swap(parentMatrix[groupEnd++]);

            if (groupEnd - previousGroupEnd > 1)

                sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);

            ASSERT(previousGroupEnd != groupEnd);

            previousGroupEnd = groupEnd;

#ifndef NDEBUG

            parentNodes.remove(n);

#endif

        }

    }

    ASSERT(parentNodes.isEmpty());

}

void NodeSet::sort() const

{

    if (m_isSorted)

        return;

    unsigned nodeCount = m_nodes.size();

    if (nodeCount < 2) {

        const_cast<bool&>(m_isSorted) = true;

        return;

    }

    bool containsAttributeNodes = false;

    Vector<Vector<Node*> > parentMatrix(nodeCount);

    for (unsigned i = 0; i < nodeCount; ++i) {

        Vector<Node*>& parentsVector = parentMatrix[i];

        Node* n = m_nodes[i].get();

        parentsVector.append(n);

        if (n->isAttributeNode()) {

            n = static_cast<Attr*>(n)->ownerElement();

            parentsVector.append(n);

            containsAttributeNodes = true;

        }

        while ((n = n->parent()))

            parentsVector.append(n);

    }

    sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);

    // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.

    Vector<RefPtr<Node> > sortedNodes;

    sortedNodes.reserveInitialCapacity(nodeCount);

    for (unsigned i = 0; i < nodeCount; ++i)

        sortedNodes.append(parentMatrix[i][0]);

    const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);

}

void NodeSet::reverse()

{

    if (m_nodes.isEmpty())

        return;

    unsigned from = 0;

    unsigned to = m_nodes.size() - 1;

    while (from < to) {

        m_nodes[from].swap(m_nodes[to]);

        ++from;

        --to;

    }

}

Node* NodeSet::firstNode() const

{

    if (isEmpty())

        return 0;

    sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.

    return m_nodes.at(0).get();

}

Node* NodeSet::anyNode() const

{

    if (isEmpty())

        return 0;

    return m_nodes.at(0).get();

}

}

}

#endif // ENABLE(XPATH)