XMLLib for PUGXML with XPath

//**************************************************************************************************************************
//* Blue Xml Extension
//* Copyright (c) 2002-2003 Josh Harler
//*
//* Blue - General Purpose C++ Library
//* Copyright (c) 2002-2003 Josh Harler
//*
//* This software is provided 'as-is', without any express or implied warranty. In no event
//* will the authors be held liable for any damages arising from the use of this software.
//*
//* Permission is granted to anyone to use this software for any purpose, including commercial
//* applications, and to alter it and redistribute it freely, subject to the following restrictions:
//*
//*     1. The origin of this software must not be misrepresented; you must not claim that you
//*     wrote the original software. If you use this software in a product, an acknowledgment in the
//*     product documentation would be appreciated but is not required.
//*
//*     2. Altered source versions must be plainly marked as such, and must not be misrepresented as
//*     being the original software.
//*
//*     3. This notice may not be removed or altered from any source distribution.
//*
//* Modified by JCrane2 to support PugXML parser:
//* http://www.codeproject.com/soap/pugxml.asp
//* http://www.codeproject.com/soap/JCraneArticle.asp
//*
//* file   PugXpathExpression.cpp
//**
//
//////////////////////////////////////////////////////////////////////


// Private Headers =========================================================================================================
#define _CRT_SECURE_NO_WARNINGS 1


// matching header
#include "PugXPathExpression.h"

// Blue library headers
#include "StringTokenizer.h"

// Extension headers
#include "PugXPathPredicate.h"


// Private Defines/Enums/Typedefs/Etc ======================================================================================

using namespace blue;
using namespace blue::common;
using namespace blue::util;


// Private Classes/Structs =================================================================================================

// Private Global Variables ================================================================================================

namespace
{
    const BString AXIS_CHILD               = "child";
    const BString AXIS_DESCENDANT          = "descendant";
    const BString AXIS_PARENT              = "parent";
    const BString AXIS_ANCESTOR            = "ancestor";
    const BString AXIS_FOLLOWING_SIBLING   = "following-sibling";
    const BString AXIS_PRECEDING_SIBLING   = "preceding-sibling";
    const BString AXIS_FOLLOWING           = "following";
    const BString AXIS_PRECEDING           = "preceding";
    const BString AXIS_DESCENDANT_OR_SELF  = "descendant-or-self";
    const BString AXIS_ANCESTOR_OR_SELF    = "ancestor-or-self";
    const BString AXIS_SELF                = "self";
    const BString AXIS_ATTRIBUTE           = "attribute";
}


// External Global Variables ===============================================================================================

// Private Functions =======================================================================================================

namespace
{
    using namespace blue::ext;
    using namespace blue::ext::xml;


    Array<xml_node_struct*> getSubNodes(xml_node_struct* node, bool bAttribsOnly)
    {
        Array<xml_node_struct*> subNodes;

        xml_node wrapper(node);

        if (wrapper.has_child_nodes())
        {
            for (unsigned int i = 0; i < node->children; i++)
            {
                if (!bAttribsOnly)
                {
                    subNodes.append(node->child[i]);
                }
                else
                {
                    if (wrapper.child(i).type() == node_attribute)
                        subNodes.append(node->child[i]);
                }
            }
        }

        return subNodes;
    }

    Array<xml_node_struct*> getSiblingElementNodes(xml_node_struct* node)
    {
        Array<xml_node_struct*> siblings;

        xml_node wrapper(node);
        if (wrapper.has_siblings())
        {
            siblings = getSubNodes(node->parent, FALSE);
        }
        return siblings;
    }

    Array<int> priv_sortGetIDs(xml_node_struct* node)
    {
        Array<int> id;
        Array<xml_node_struct*> siblings;

        xml_node_struct* parent = node->parent;
        xml_node wrapper(parent);
        if (!wrapper.empty() && !wrapper.type_document())
        {
            siblings = getSubNodes(parent, FALSE);
            id = priv_sortGetIDs(parent);
        }
        else
        {
            siblings = Array<xml_node_struct*>(1);
            siblings[0] = node;
        }

        for (int i = 0; i < siblings.getSize(); ++i)
        {
            if (siblings[i] == node)
            {
                id.append(i);
                break;
            }
        }

        return (id);
    }


    int priv_sortCompareIDs(Array<int> one, Array<int> two)
    {
        int oneSize = one.getSize();
        int twoSize = two.getSize();
        int maxSize = min(oneSize, twoSize);

        for (int i = 0; i < maxSize; ++i)
        {
            if (one[i] < two[i])
            {
                return (-1);
            }
            if (one[i] > two[i])
            {
                return (1);
            }
        }

        if (oneSize < twoSize)
        {
            return (-1);
        }
        if (oneSize > twoSize)
        {
            return (1);
        }

        return (0);
    }


    Array<xml_node_struct*> priv_sortDocumentOrder(Array<xml_node_struct*> nodes)
    {
        if (nodes.getSize() <= 1)
            return nodes;
        Array<xml_node_struct*> wrkNodes = nodes.copy();
        Array< Array<int> > wrkIDs(wrkNodes.getSize());
        int idx;

        for (idx = 0; idx < wrkNodes.getSize(); ++idx)
        {
            wrkIDs[idx] = priv_sortGetIDs(wrkNodes[idx]);
        }

        Array<xml_node_struct*> srtNodes(wrkNodes.getSize());
        int srtIdx = 0;

        while (srtIdx < srtNodes.getSize())
        {
            int idxLow = -1;

            for (idx = 0; idx < wrkIDs.getSize(); ++idx)
            {
                if (wrkIDs[idx].getSize() > 0)
                {
                    if (idxLow == -1)
                    {
                        idxLow = idx;
                    }
                    else
                    {
                        int compare = priv_sortCompareIDs(wrkIDs[idx], wrkIDs[idxLow]);
                        if (compare < 0)
                        {
                            idxLow = idx;
                        }
                        if (compare == 0)
                        {
                            // remove any duplicates
                            wrkIDs[idx].clear();
                        }
                    }
                }
            }

            if (idxLow == -1)
            {
                break;
            }

            srtNodes[srtIdx++] = wrkNodes[idxLow];
            wrkIDs[idxLow].clear();
        }

        if (srtIdx != srtNodes.getSize())
        {
            srtNodes.resize(srtIdx);
        }

        return (srtNodes);
    }

}


// Functions ===============================================================================================================

namespace blue
{
    namespace ext
    {
        namespace xml
        {
    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathExpression::PugXPathExpression() :m_root(0), m_predicate(0)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathExpression::PugXPathExpression(xml_node_struct* root) :m_root(root), m_predicate(0)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathExpression::~PugXPathExpression()
    {
        if (m_predicate != 0)
        {
            delete m_predicate;
        }
    }

    // ---------------------------------------------------------------------------------------------------------------------

    xml_node_struct* PugXPathExpression::getRootNode()
    {
        return (m_root);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    const xml_node_struct* PugXPathExpression::getRootNode() const
    {
        return (m_root);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathFunction* PugXPathExpression::getFunction(BString function)
    {
        if (m_predicate != 0)
        {
            return m_predicate->getFunction(function);
        }

        return (0);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    const PugXPathFunction* PugXPathExpression::getFunction(BString function) const
    {
        return ((PugXPathExpression*)this)->getFunction(function);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::findNodes(BString xpathExpr)
    {
        Array< Array<xp_path_item> > info;
        extractInfo(xpathExpr, info);

        Array<xml_node_struct*> matches;
        for (int i = 0; i < info.getSize(); ++i)
        {
            Array<xp_path_item>& items = info[i];

            Array<xml_node_struct*> search(1);
            search[0] = m_root;

            for (int iPi = 0; iPi < items.getSize(); ++iPi)
            {
                Array<xml_node_struct*> results = processPass(search, items[iPi]);
                search = results;
            }

            matches += search;
        }

        matches = priv_sortDocumentOrder(matches);
        return (matches);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    const Array<xml_node_struct*> PugXPathExpression::findNodes(BString xpathExpr) const
    {
        return ((PugXPathExpression*)this)->findNodes(xpathExpr);
    }


    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::findNodes(const char* xpathExpr)
    {
        return ((PugXPathExpression*)this)->findNodes(BString(xpathExpr));
    }

    // ---------------------------------------------------------------------------------------------------------------------

    const Array<xml_node_struct*> PugXPathExpression::findNodes(const char* xpathExpr) const
    {
        return ((PugXPathExpression*)this)->findNodes(xpathExpr);
    }

    // ---------------------------------------------------------------------------------------------------------------------
    Array<BString> PugXPathExpression::findValues(BString xpathExpr) const
    {
        const Array<xml_node_struct*> nodes = findNodes(xpathExpr);
        Array<BString> results(nodes.getSize());

        for (int i = 0; i < nodes.getSize(); ++i)
        {
            xml_node node = nodes[i];
            results[i] = node.child(0).value();
        }

        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    xml_node_struct* PugXPathExpression::findNode(BString xpathExpr)
    {
        Array<xml_node_struct*> nodes = findNodes(xpathExpr);
        if (nodes.getSize() > 0)
        {
            return (nodes[0]);
        }

        return (0);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    const xml_node_struct* PugXPathExpression::findNode(BString xpathExpr) const
    {
        return ((PugXPathExpression*)this)->findNode(xpathExpr);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    BString PugXPathExpression::findValue(BString xpathExpr) const
    {
        Array<BString> values = findValues(xpathExpr);
        if (values.getSize() > 0)
        {
            return (values[0]);
        }

        return (BString::null);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    void PugXPathExpression::setRootNode(xml_node_struct* root)
    {
        m_root = root;
    }

    // ---------------------------------------------------------------------------------------------------------------------

    void PugXPathExpression::addFunction(PugXPathFunction* function)
    {
        if (m_predicate == 0)
        {
            m_predicate = new PugXPathPredicate();
        }
        m_predicate->addFunction(function);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    void PugXPathExpression::removeFunction(BString function)
    {
        if (m_predicate != 0)
        {
            m_predicate->removeFunction(function);
        }
    }

    // ---------------------------------------------------------------------------------------------------------------------

    void PugXPathExpression::extractInfo(BString xpathExpr, Array< Array<xp_path_item> >& info)
    {
        StringTokenizer toker;
        toker.addContainer("\"", "\"", StringTokenizer::EXCLUSIVE);
        toker.addContainer("\'", "\'", StringTokenizer::EXCLUSIVE);
        toker.addContainer("[" , "]",  StringTokenizer::NORMAL);
        flags32_t tokerFlags = StringTokenizer::KEEP_DELIMITERS | StringTokenizer::TRIM_RESULTS | StringTokenizer::NO_WHITESPACE;

        Array<BString> tokens = toker.tokenize(xpathExpr, "/|", tokerFlags);

        Array<xp_path_item> curInfo;

        int idx = 0;
        while (idx < tokens.getSize())
        {
            if (tokens[idx] == "|")
            {
                if (++idx == tokens.getSize())
                {
                    break;
                }

                info.append(curInfo);
                curInfo.clear();
            }

            if (tokens[idx] != "/" || ++idx == tokens.getSize())
            {
                throw PugXPathException("Invalid PugXPath expression: '" + xpathExpr + "'");
            }

            // check for "//" shortcut
            if (tokens[idx] == "/")
            {
                tokens[idx] = AXIS_DESCENDANT_OR_SELF + "::node()";
                tokens.insert("/", idx + 1);
            }
            // check for "." shortcut
            else if (tokens[idx] == ".")
            {
                tokens[idx] = AXIS_SELF + "::node()";
            }
            // check for ".." shortcut
            else if (tokens[idx] == "..")
            {
                tokens[idx] = AXIS_PARENT + "::node()";
            }

            BString section = tokens[idx];
            xp_path_item item;

            // locate predicate
            int begBrack = section.findPos("[");
            if (begBrack != BString::npos)
            {
                StringTokenizer toker;
                toker.addContainer("\"", "\"", StringTokenizer::EXCLUSIVE);
                toker.addContainer("\'", "\'", StringTokenizer::EXCLUSIVE);
                toker.addContainer("[" , "]",  StringTokenizer::NORMAL);
                flags32_t tokerFlags = StringTokenizer::TRIM_RESULTS | StringTokenizer::NO_WHITESPACE;

                Array<BString> predicates = toker.tokenize(section.subString(begBrack), "[]", tokerFlags);

                if (predicates.getSize() > 0)
                {
                    if (m_predicate == 0)
                    {
                        m_predicate = new PugXPathPredicate();
                    }
                    for (int i = 0; i < predicates.getSize(); ++i)
                    {
                        Array<PugXPathToken> predTokens = m_predicate->parsePredicate(predicates[i]);
                        item.m_predicates.append(predTokens);
                    }
                }

                section = section.left(begBrack).trim();
            }

            // get axis
            int posColon = section.findPos("::");
            if (posColon != BString::npos)
            {
                item.m_axis = section.left(posColon);
                section = section.stripFromLeft(posColon + 2);
            }
            else
            {
                item.m_axis = AXIS_CHILD;
            }

            // get node name
            // pugXML does not support nodes as attributes
            /**/
            if (section.beginsWith("@"))
            {
                item.m_axis = AXIS_ATTRIBUTE;
                section = section.stripFromLeft(1);
            }
            /**/

            item.m_node = section;

            curInfo.append(item);

            ++idx;
        }

        if (curInfo.getSize() > 0)
        {
            info.append(curInfo);
        }
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processPass(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        results = processPassAxis(search, item);
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processPassAxis(Array<xml_node_struct*> search, xp_path_item& item)
    {
        BString axis = item.m_axis;

        if (axis == AXIS_CHILD)
        {
            return processAxisChild(search, item);
        }
        if (axis == AXIS_DESCENDANT)
        {
            return processAxisDescendant(search, item);
        }
        if (axis == AXIS_PARENT)
        {
            return processAxisParent(search, item);
        }
        if (axis == AXIS_ANCESTOR)
        {
            return processAxisAncestor(search, item);
        }
        if (axis == AXIS_FOLLOWING_SIBLING)
        {
            return processAxisFollowingSibling(search, item);
        }
        if (axis == AXIS_PRECEDING_SIBLING)
        {
            return processAxisPrecedingSibling(search, item);
        }
        if (axis == AXIS_FOLLOWING)
        {
            return processAxisFollowing(search, item);
        }
        if (axis == AXIS_PRECEDING)
        {
            return processAxisPreceding(search, item);
        }
        if (axis == AXIS_DESCENDANT_OR_SELF)
        {
            return processAxisDescendantOrSelf(search, item);
        }
        if (axis == AXIS_ANCESTOR_OR_SELF)
        {
            return processAxisAncestorOrSelf(search, item);
        }
        if (axis == AXIS_SELF)
        {
            return processAxisSelf(search, item);
        }
        if (axis == AXIS_ATTRIBUTE)
        {
            return processAxisAttribute(search, item);
        }

        throw PugXPathException("Invalid axis specified: '" + axis + "'");
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processRecursiveMatch(xml_node_struct* node, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        if (checkForMatch(node, item))
        {
            results.append(node);
        }

        Array<xml_node_struct*> nodes = getSubNodes(node, FALSE);
        for (int iN = 0; iN < nodes.getSize(); ++iN)
        {
            results += processRecursiveMatch(nodes[iN], item);
        }

        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisChild(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            Array<xml_node_struct*> nodes = getSubNodes(search[i], FALSE);
            Array<xml_node_struct*> nodeResults;
            for (int iN = 0; iN < nodes.getSize(); ++iN)
            {
                if (checkForMatch(nodes[iN], item))
                {
                    nodeResults.append(nodes[iN]);
                }
            }

            nodeResults = processPredicates(nodeResults, item);
            results += nodeResults;
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisDescendant(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            Array<xml_node_struct*> nodes = getSubNodes(search[i], FALSE);
            for (int iN = 0; iN < nodes.getSize(); ++iN)
            {
                results += processRecursiveMatch(nodes[iN], item);
            }
        }
        results = processPredicates(results, item);
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisParent(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            xml_node_struct* parent = search[i]->parent;
            if (parent != 0 && parent->type == node_element)
            {
                if (checkForMatch(parent, item))
                {
                    Array<xml_node_struct*> matches(1);
                    matches[0] = parent;
                    matches = processPredicates(matches, item);
                    if (matches.getSize() > 0)
                    {
                        results.append(parent);
                    }
                }
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisAncestor(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            xml_node_struct* parent = search[i]->parent;
            while (parent != 0 && parent->type == node_element)
            {
                if (checkForMatch(parent, item))
                {
                    Array<xml_node_struct*> matches(1);
                    matches[0] = parent;
                    matches = processPredicates(matches, item);
                    if (matches.getSize() > 0)
                    {
                        results.append(parent);
                    }
                }
                parent = parent->parent;
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisFollowingSibling(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            if (search[i]->type == node_element)
            {
                xml_node_struct* element = (xml_node_struct*)search[i];
                Array<xml_node_struct*> siblings = getSiblingElementNodes(element);
                int idx = 0;
                for (; idx < siblings.getSize() && siblings[idx] != element; ++idx)
                {
                    ; // empty loop
                }

                Array<xml_node_struct*> nodeResults;
                for (++idx; idx < siblings.getSize(); ++idx)
                {
                    if (checkForMatch(siblings[idx], item))
                    {
                        nodeResults.append(siblings[idx]);
                    }
                }
                nodeResults = processPredicates(nodeResults, item);
                results += nodeResults;
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisPrecedingSibling(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            if (search[i]->type == node_element)
            {
                xml_node_struct* element = (xml_node_struct*)search[i];
                Array<xml_node_struct*> siblings = getSiblingElementNodes(element);

                Array<xml_node_struct*> nodeResults;
                for (int idx = 0; idx < siblings.getSize(); ++idx)
                {
                    if (siblings[idx] == element)
                    {
                        break;
                    }
                    if (checkForMatch(siblings[idx], item))
                    {
                        nodeResults.append(siblings[idx]);
                    }
                }
                nodeResults = processPredicates(nodeResults, item);
                results += nodeResults;
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisFollowing(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            if (search[i]->type == node_element)
            {
                xml_node_struct* element = (xml_node_struct*)search[i];
                Array<xml_node_struct*> siblings = getSiblingElementNodes(element);
                int idx = 0;
                for (; idx < siblings.getSize() && siblings[idx] != element; ++idx)
                {
                    ; // empty loop
                }

                Array<xml_node_struct*> nodeResults;
                for (++idx; idx < siblings.getSize(); ++idx)
                {
                    nodeResults += processRecursiveMatch(siblings[idx], item);
                }
                nodeResults = processPredicates(nodeResults, item);
                results += nodeResults;

                xml_node_struct* parent = search[i]->parent;
                while (parent != 0 && parent->type == node_element)
                {
                    xml_node_struct* element = (xml_node_struct*)parent;
                    Array<xml_node_struct*> siblings = getSiblingElementNodes(element);

                    int idx = 0;
                    for (; idx < siblings.getSize() && siblings[idx] != element; ++idx)
                    {
                        ; // empty loop
                    }

                    Array<xml_node_struct*> nodeResults;
                    for (++idx; idx < siblings.getSize(); ++idx)
                    {
                        nodeResults += processRecursiveMatch(siblings[idx], item);
                    }
                    nodeResults = processPredicates(nodeResults, item);
                    results += nodeResults;

                    parent = parent->parent;
                }
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisPreceding(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            if (search[i]->type == node_element)
            {
                xml_node_struct* element = (xml_node_struct*)search[i];
                Array<xml_node_struct*> siblings = getSiblingElementNodes(element);
                Array<xml_node_struct*> nodeResults;
                for (int iS = 0; iS < siblings.getSize(); ++iS)
                {
                    if (siblings[iS] == element)
                    {
                        break;
                    }
                    nodeResults += processRecursiveMatch(siblings[iS], item);
                }
                nodeResults = processPredicates(nodeResults, item);
                results += nodeResults;

                xml_node_struct* parent = search[i]->parent;
                while (parent != 0 && parent->type == node_element)
                {
                    xml_node_struct* element = (xml_node_struct*)parent;
                    Array<xml_node_struct*> siblings = getSiblingElementNodes(element);

                    Array<xml_node_struct*> nodeResults;
                    for (int iS = 0; iS < siblings.getSize(); ++iS)
                    {
                        if (siblings[iS] == element)
                        {
                            break;
                        }
                        nodeResults += processRecursiveMatch(siblings[iS], item);
                    }
                    nodeResults = processPredicates(nodeResults, item);
                    results += nodeResults;

                    parent = parent->parent;
                }
            }
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisDescendantOrSelf(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            results += processRecursiveMatch(search[i], item);
        }
        results = processPredicates(results, item);
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisAncestorOrSelf(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            if (checkForMatch(search[i], item) /*match == "*" || match == search[i]->getName()*/)
            {
                results.append(search[i]);
            }

            Array<xml_node_struct*> nodeResults;
            xml_node_struct* parent = search[i]->parent;
            while (parent != 0 && parent->type == node_element)
            {
                if (checkForMatch(parent, item))
                {
                    nodeResults.append(parent);
                }
                parent = parent->parent;
            }

            nodeResults = processPredicates(nodeResults, item);
            results += nodeResults;
        }
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processAxisSelf(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results = processPredicates(search, item);
        return (results);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    /**/
    // Commented out because pugXML does not put attributes in a does
    Array<xml_node_struct*> PugXPathExpression::processAxisAttribute(Array<xml_node_struct*> search, xp_path_item& item)
    {
        Array<xml_node_struct*> results;
        for (int i = 0; i < search.getSize(); ++i)
        {
            Array<xml_node_struct*> attribs = getSubNodes(search[i], TRUE);
            xml_node wrapper = xml_node(search[i]);

            if (item.m_node == "*")
            {
                results += attribs;
            }
            else
            {
                for (int iA = 0; iA < attribs.getSize(); ++iA)
                {
                    if (item.m_node == attribs[iA]->name)
                    {
                        results.append(attribs[iA]);
                        break;
                    }
                }
            }
        }
        results = processPredicates(results, item);
        return (results);
    }
    /**/

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathExpression::processPredicates(Array<xml_node_struct*> search, xp_path_item& item)
    {
        if (item.m_predicates.getSize() == 0)
        {
            return search;
        }

        //Array<xml_node_struct*> results;
        Array<xml_node_struct*> wrkSearch = search.copy();
        Array<xml_node_struct*> nxtSearch;

        for (int iP = 0; iP < item.m_predicates.getSize(); ++iP)
        {
            for (int i = 0; i < wrkSearch.getSize(); ++i)
            {
                PugXPathToken token = m_predicate->evaluate(item.m_predicates[iP], wrkSearch, wrkSearch[i]);
                if (token.getType() == PugXPathToken::NUMBER_INT || token.getType() == PugXPathToken::NUMBER_DBL)
                {
                    int idx = token.getValueNumberInt();
                    if (idx ==(i + 1))
                    {
                        nxtSearch.append(wrkSearch[i]);
                    }
                }
                else
                {
                    if (token.getType() == PugXPathToken::NODESET)
                    {
                        Array<xml_node_struct*> nodes;
                        if (token.getValueString().beginsWith("/"))
                        {
                            nodes = token.getValueNodeSet(m_root);
                        }
                        else
                        {
                            nodes = token.getValueNodeSet(wrkSearch[i]);
                        }
                        if (nodes.getSize() > 0)
                        {
                            nxtSearch.append(wrkSearch[i]);
                        }
                    }
                    else
                    {
                        if (token.isCompatibleWith(PugXPathToken::BOOLEAN))
                        {
                            if (token.getValueBool())
                            {
                                nxtSearch.append(wrkSearch[i]);
                            }
                        }
                        else
                        {
                            return Array<xml_node_struct*>();
                        }
                    }
                }
            }
            wrkSearch = nxtSearch;
            nxtSearch.clear();
        }

        return (wrkSearch);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    bool PugXPathExpression::checkForMatch(xml_node_struct* node, xp_path_item& item)
    {
        if (item.m_node == "node()")
        {
            return (true);
        }

        /**/
        // pugXML does not support attributes as a node type
        if (node->type == node_element && item.m_axis == AXIS_ATTRIBUTE)
        {
            if (item.m_node == "*")
            {
                return (true);
            }
            xml_node wrapper = xml_node(node);
            if (wrapper.has_attribute((char *) item.m_node.getAsCStr()))
            {
                return (true);
            }
        }
        /**/
        else if (node->type == node_element)
        {
            if (item.m_node == "*" || item.m_node == node->name)
            {
                return (true);
            }
        }
        else
        {
            if (item.m_node == "text()")
            {
                if (node->type == node_pcdata || node->type == node_cdata)
                {
                    return (true);
                }
            }
            else if (item.m_node == "comment()")
            {
                if (node->type == node_comment)
                {
                    return (true);
                }
            }
            else if (item.m_node == "processing-instruction()")
            {
                if (node->type == node_pi)
                {
                    return (true);
                }
            }
        }
        return (false);
    }

    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken() :m_type(STRING)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken(BString value, type_e type) :m_value(value), m_type(type)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken(BString value) :m_value(value), m_type(STRING)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken(bool value) :m_value(value? "true":"false"), m_type(BOOLEAN)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken(int value) :m_value(BString(value)), m_type(NUMBER_INT)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::PugXPathToken(double value) :m_value(BString(value)), m_type(NUMBER_DBL)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    BString PugXPathToken::getValue(xml_node_struct* context) const
    {
        if (m_type == NODESET || (m_type == OPERATOR && m_value == "*"))
        {
            Array<xml_node_struct*> nodeset = getValueNodeSet(context);
            if (nodeset.getSize() > 0)
            {
                return BString(nodeset[0]->value);
            }
            return (BString::null);
        }

        return (m_value);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathToken::type_e PugXPathToken::getType() const
    {
        return (m_type);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    BString PugXPathToken::getValueString() const
    {
        return (m_value);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    bool PugXPathToken::getValueBool() const
    {
        switch (m_type)
        {
            case BOOLEAN:
                return (m_value == "true");

            case STRING:
                return (m_value != BString::null);

            case NUMBER_INT:
            case NUMBER_DBL:
                return (m_value.getAsDouble() != 0.0);
        }

        throw PugXPathException("Cannot convert value to boolean");
    }

    // ---------------------------------------------------------------------------------------------------------------------

    int PugXPathToken::getValueNumberInt() const
    {
        switch (m_type)
        {
            case NUMBER_INT:
            case NUMBER_DBL:
            case STRING:
                return ((int)m_value.getAsDouble());

            case BOOLEAN:
                return (m_value == "true" ? 1 : 0);
        }

        throw PugXPathException("Cannot convert value to integer");
    }

    // ---------------------------------------------------------------------------------------------------------------------

    double PugXPathToken::getValueNumberDouble() const
    {
        switch (m_type)
        {
            case NUMBER_INT:
            case NUMBER_DBL:
            case STRING:
                return ((double)m_value.getAsDouble());

            case BOOLEAN:
                return (m_value == "true" ? 1.0 : 0.0);
        }

        throw PugXPathException("Cannot convert value to double");
    }

    // ---------------------------------------------------------------------------------------------------------------------

    Array<xml_node_struct*> PugXPathToken::getValueNodeSet(xml_node_struct* context) const
    {
        if (m_type == NODESET || (m_type == OPERATOR&&m_value == "*"))
        {
            PugXPathExpression expr;
            expr.setRootNode(context);
            return expr.findNodes(m_value.beginsWith("/") ? m_value : "/" + m_value);
        }

        throw PugXPathException("Cannot convert value to nodeset");
    }

    // ---------------------------------------------------------------------------------------------------------------------

    bool PugXPathToken::isCompatibleWith(type_e type) const
    {
        if (type == m_type)
        {
            return (true);
        }

        switch (type)
        {
            case STRING:
                return (true);

            case NUMBER_INT:
            case NUMBER_DBL:
                return m_value.isValidDouble();

            case BOOLEAN:
                switch (m_type)
                {
                case NUMBER_INT:
                case NUMBER_DBL:
                case NODESET:
                    return (true);

                case STRING:
                    return (m_value == "true" || m_value == "false");
                }
                break;

                case NODESET:
                    return (m_type == BOOLEAN || m_type == STRING || (m_type == OPERATOR&&m_value == "*"));
        }

        return (false);
    }

    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------
    // ---------------------------------------------------------------------------------------------------------------------

    PugXPathFunction::PugXPathFunction(BString name, int parmCount) :m_name(name), m_parmCount(parmCount)
    {
    }

    // ---------------------------------------------------------------------------------------------------------------------

    BString PugXPathFunction::getName() const
    {
        return (m_name);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    int PugXPathFunction::getParmCount() const
    {
        return (m_parmCount);
    }

    // ---------------------------------------------------------------------------------------------------------------------

    void PugXPathFunction::validateParm(PugXPathToken& parm, PugXPathToken::type_e type)
    {
        if (!parm.isCompatibleWith(type))
        {
            throw PugXPathException("Invalid parameter passed to " + m_name + ": '" + parm.getValueString() + "'");
        }
    }
}
}
}   // namespaces