src/xalanc/XSLT/NodeSorter.cpp

/*
 * 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.
 */

// Class header file.
#include "NodeSorter.hpp"



#include <xalanc/PlatformSupport/DOMStringHelper.hpp>
#include <xalanc/PlatformSupport/DoubleSupport.hpp>



#include <xalanc/XPath/XObjectFactory.hpp>
#include <xalanc/XPath/XPath.hpp>



#include "StylesheetExecutionContext.hpp"



namespace XALAN_CPP_NAMESPACE {



NodeSorter::NodeSorter(MemoryManager& theManager) :
    m_numberResultsCache(theManager),
    m_stringResultsCache(theManager),
    m_keys(theManager),
    m_scratchVector(theManager)
{
}



NodeSorter::~NodeSorter()
{
}



void
NodeSorter::sort(StylesheetExecutionContext&    executionContext)
{
    assert(m_scratchVector.empty() == false);

    // Make sure the caches are cleared when we're done...
    const CollectionClearGuard<NumberResultsCacheType>  guard1(m_numberResultsCache);
    const CollectionClearGuard<StringResultsCacheType>  guard2(m_stringResultsCache);

    NodeSortKeyCompare  theComparer(
                    executionContext,
                    *this,
                    m_scratchVector,
                    m_keys);

    using std::stable_sort;

    // Use the stl sort algorithm, which will use our compare functor,
    // which returns true if first less than second
    stable_sort(
            m_scratchVector.begin(),
            m_scratchVector.end(),
            theComparer);
}



void
NodeSorter::sort(
            StylesheetExecutionContext&     executionContext,
            MutableNodeRefList&             theList)
{
    if (m_keys.empty() == false)
    {
        const NodeRefListBase::size_type    theLength = theList.getLength();

        // Copy the nodes to a vector...
        assert(m_scratchVector.empty() == true);

        // Make sure the scratch vector is cleared when we're done...
        CollectionClearGuard<NodeVectorType>    guard(m_scratchVector);

        m_scratchVector.reserve(theLength);

        NodeRefListBase::size_type  i = 0;

        for (; i < theLength; ++i)
        {
            m_scratchVector.push_back(NodeVectorType::value_type(theList.item(i), i));
        }

        // Do the sort...
        sort(executionContext);
        assert(m_scratchVector.size() == NodeVectorType::size_type(theLength));

        // Copy the nodes back to the list in sorted order.
        theList.clear();

        for (i = 0; i < theLength; ++i)
        {
            theList.addNode(m_scratchVector[i].m_node);
        }

        assert(theList.getLength() == theLength);
    }
}



static inline int
doCollationCompare(
            StylesheetExecutionContext&         executionContext,
            const XalanDOMString&               theLHS,
            const XalanDOMString&               theRHS,
            const XalanDOMString&               theLanguage,
            XalanCollationServices::eCaseOrder  theCaseOrder)
{
    if (theLanguage.empty() == true)
    {
        return executionContext.collationCompare(
                theLHS,
                theRHS,
                theCaseOrder);
    }
    else
    {
        return executionContext.collationCompare(
                theLHS,
                theRHS,
                theLanguage,
                theCaseOrder);
    }
}



int
NodeSorter::NodeSortKeyCompare::compare(
                const NodeVectorType::value_type&    theLHS,
                const NodeVectorType::value_type&    theRHS,
                XalanSize_t                          theKeyIndex) const
{
    assert(theLHS.m_node != 0 && theRHS.m_node != 0);
    assert(theKeyIndex < m_nodeSortKeys.size());

    int                 theResult = 0;

    const NodeSortKey&  theKey = m_nodeSortKeys[theKeyIndex];

    // Compare as numbers
    if(theKey.getTreatAsNumbers() == false)
    {
        // Compare as strings...
        const XalanDOMString&   theLHSString =
            getStringResult(theKey, theKeyIndex, theLHS);

        const XalanDOMString&   theRHSString =
            getStringResult(theKey, theKeyIndex, theRHS);

        theResult = doCollationCompare(
                m_executionContext,
                theLHSString,
                theRHSString,
                theKey.getLanguageString(),
                theKey.getCaseOrder());
    }
    else
    {
        const double    n1Num = getNumberResult(theKey, theKeyIndex, theLHS);
        const double    n2Num = getNumberResult(theKey, theKeyIndex, theRHS);

        // Always order NaN before anything else...
        if (DoubleSupport::isNaN(n1Num) == true)
        {
            if (DoubleSupport::isNaN(n2Num) == false)
            {
                theResult = -1;
            }
        }
        else if (DoubleSupport::isNaN(n2Num) == true)
        {
            theResult = 1;
        }
        else if (DoubleSupport::lessThan(n1Num, n2Num) == true)
        {
            theResult = -1;
        }
        else if (DoubleSupport::greaterThan(n1Num, n2Num) == true)
        {
            theResult = 1;
        }
    }

    // If they're not equal, the flip things if the
    // order is descending...
    if (theResult != 0)
    {
        if (theKey.getDescending() == true)
        {
            theResult = -theResult;
        }
    }
    else if(theKeyIndex + 1 < m_nodeSortKeys.size())
    {
        // They're equal, so process the next key, if any...
        theResult = compare(theLHS, theRHS, theKeyIndex + 1);
    }

    return theResult;
}



inline double
getResult(
            const XPath*            theXPath,
            XalanNode*              theNode,
            const PrefixResolver&   thePrefixResolver,
            XPathExecutionContext&  theExecutionContext)
{
    typedef XPathExecutionContext::GetCachedString  GetCachedString;

    if (theXPath == 0)
    {
        assert(theNode != 0);

        const GetCachedString   temp(theExecutionContext);

        DOMServices::getNodeData(*theNode, theExecutionContext, temp.get());

        return DoubleSupport::toDouble(temp.get(), theExecutionContext.getMemoryManager());
    }
    else
    {
        double  theResult;

        theXPath->execute(
                theNode,
                thePrefixResolver,
                theExecutionContext,
                theResult);

        return theResult;
    }
}



double
NodeSorter::NodeSortKeyCompare::getNumberResult(
                const NodeSortKey&                   theKey,
                XalanSize_t                          theKeyIndex,
                const NodeVectorType::value_type&    theEntry) const
{
    assert(theKey.getPrefixResolver() != 0);

    const XPath* const  xpath = theKey.getSelectPattern();

    typedef NodeSorter::NumberResultsCacheType  NumberResultsCacheType;

    NumberResultsCacheType&     theCache =
            m_sorter.m_numberResultsCache;

    if (theCache.empty() == true)
    {
        theCache.resize(m_nodeSortKeys.size());
    }

    // We need a dummy value to indicate that a slot has
    // never been evaluated.  0 is probably a bad idea,
    // as is NaN, since that would be fairly common with
    // values that are not convertible to a number.  This
    // is just a not-so-random number...
    const double    theDummyValue = 135792468.0L;

    if (theCache[theKeyIndex].empty() == false)
    {
        if (DoubleSupport::equal(theCache[theKeyIndex][theEntry.m_position], theDummyValue) == true)
        {
            theCache[theKeyIndex][theEntry.m_position] =
                getResult(
                    xpath,
                    theEntry.m_node,
                    *theKey.getPrefixResolver(),
                    m_executionContext);
        }
    }
    else
    {
        theCache[theKeyIndex].resize(m_nodes.size(), 0);

        using std::fill;

        // Fill with the dummy value...
        fill(
            theCache[theKeyIndex].begin(),
            theCache[theKeyIndex].end(),
            theDummyValue);

        theCache[theKeyIndex][theEntry.m_position] =
            getResult(
                xpath,
                theEntry.m_node,
                *theKey.getPrefixResolver(),
                m_executionContext);
    }

    return theCache[theKeyIndex][theEntry.m_position];
}



#if defined(XALAN_NODESORTER_CACHE_XOBJECTS)

inline void
getResult(
            const XPath*            theXPath,
            XalanNode*              theNode,
            const PrefixResolver&   thePrefixResolver,
            XPathExecutionContext&  theExecutionContext,
            XObjectPtr&             theResult)
{
    if (theXPath == 0)
    {
        assert(theNode != 0);

        theResult = theExecutionContext.getXObjectFactory().createNodeSet(theNode);     
    }
    else
    {
        theResult = theXPath->execute(
                theNode,
                thePrefixResolver,
                theExecutionContext);
    }
}

inline bool
notCached(const XObjectPtr&     theEntry)
{
    return theEntry.null();
}

inline bool
isCached(const XObjectPtr&  theEntry)
{
    return !theEntry.null();
}

inline const XalanDOMString&
cacheValue(const XObjectPtr&    theEntry)
{
    return theEntry->str();
}

#else

inline void
getResult(
            const XPath*            theXPath,
            XalanNode*              theNode,
            const PrefixResolver&   thePrefixResolver,
            XPathExecutionContext&  theExecutionContext,
            XalanDOMString&         theResult)
{
    if (theXPath == 0)
    {
        assert(theNode != 0);

        DOMServices::getNodeData(
                *theNode,
                theExecutionContext,
                theResult);
    }
    else
    {
        theXPath->execute(
                theNode,
                thePrefixResolver,
                theExecutionContext,
                theResult);
    }
}

inline bool
notCached(const XalanDOMString&     theEntry)
{
    return theEntry.empty();
}

inline bool
isCached(const XalanDOMString&  /* theEntry */)
{
    return true;
}

inline const XalanDOMString&
cacheValue(const XalanDOMString&    theEntry)
{
    return theEntry;
}

#endif



const XalanDOMString&
NodeSorter::NodeSortKeyCompare::getStringResult(
                const NodeSortKey&                   theKey,
                XalanSize_t                          theKeyIndex,
                const NodeVectorType::value_type&    theEntry) const
{
    assert(theKey.getPrefixResolver() != 0);

    const XPath* const  xpath = theKey.getSelectPattern();

    typedef NodeSorter::StringResultsCacheType  StringResultsCacheType;

    StringResultsCacheType&     theCache =
            m_sorter.m_stringResultsCache;

    if (theCache.empty() == true)
    {
        theCache.resize(m_nodeSortKeys.size());
    }

    if (theCache[theKeyIndex].empty() == false)
    {
        if (notCached(theCache[theKeyIndex][theEntry.m_position]) == true)
        {
            getResult(
                xpath,
                theEntry.m_node,
                *theKey.getPrefixResolver(),
                m_executionContext,
                theCache[theKeyIndex][theEntry.m_position]);
        }
    }
    else
    {

        theCache[theKeyIndex].resize(m_nodes.size());

        getResult(
            xpath,
            theEntry.m_node,
            *theKey.getPrefixResolver(),
            m_executionContext,
            theCache[theKeyIndex][theEntry.m_position]);
    }

    assert(isCached(theCache[theKeyIndex][theEntry.m_position]) == true);

    return cacheValue(theCache[theKeyIndex][theEntry.m_position]);
}



}