C # - XML ​​- Удаление узлов без использования рекурсии

Question

У меня есть следующий рекурсивный метод, который берет документ XHTML и помечает узлы на основе определенных условий и вызывается, как показано ниже, для ряда HTML-содержимого: -

XmlDocument document = new XmlDocument();
document.LoadXml(xmlAsString);
PrepNodesForDeletion(document.DocumentElement, document.DocumentElement);

Определение метода ниже

/// <summary>
/// Recursive function to identify and mark all unnecessary nodes so that they can be removed from the document.
/// </summary>
/// <param name="nodeToCompareAgainst">The node that we are recursively comparing all of its descendant nodes against</param>
/// <param name="nodeInQuestion">The node whose children we are comparing against the "nodeToCompareAgainst" node</param>
static void PrepNodesForDeletion(XmlNode nodeToCompareAgainst, XmlNode nodeInQuestion)
{
    if (infinityIndex++ > 100000)
    {
        throw;
    }
    foreach (XmlNode childNode in nodeInQuestion.ChildNodes)
    {
        // make sure we compare all of the childNodes descendants to the nodeToCompareAgainst
        PrepNodesForDeletion(nodeToCompareAgainst, childNode);

        if (AreNamesSame(nodeToCompareAgainst, childNode) && AllAttributesPresent(nodeToCompareAgainst, childNode))
        {
            // the function AnyAttributesWithDifferingValues assumes that all attributes are present between the two nodes
            if (AnyAttributesWithDifferingValues(nodeToCompareAgainst, childNode) && InnerTextIsSame(nodeToCompareAgainst, childNode))
            {
                MarkNodeForDeletion(nodeToCompareAgainst);
            }
            else if (!AnyAttributesWithDifferingValues(nodeToCompareAgainst, childNode))
            {
                MarkNodeForDeletion(childNode);
            }
        }

        // make sure we compare all of the childNodes descendants to the childNode
        PrepNodesForDeletion(childNode, childNode);
    }
}

А затем следующий метод, который удалит отмеченный узел: -

static void RemoveMarkedNodes(XmlDocument document)
{
    // in order for us to make sure we remove everything we meant to remove, we need to do this in a while loop
    // for instance, if the original xml is = <a><a><b><a/></b></a><a/></a>
    // this should result in the xml being passed into this function as:
    // <a><b><a DeleteNode="TRUE" /></b><a DeleteNode="TRUE"><b><a DeleteNode="TRUE" /></b></a><a DeleteNode="TRUE" /></a>
    // then this function (without the while) will not delete the last <a/>, even though it is marked for deletion
    // if we incorporate a while loop, then we can insure all nodes marked for deletion are removed
    // TODO: understand the reason for this -- see http://groups.google.com/group/microsoft.public.dotnet.xml/browse_thread/thread/25df058a4efb5698/7dd0a8b71739216c?lnk=st&q=xmlnode+removechild+recursive&rnum=2&hl=en#7dd0a8b71739216c
    XmlNodeList nodesToDelete = document.SelectNodes("//*[@DeleteNode='TRUE']");

    while (nodesToDelete.Count > 0)
    {
        foreach (XmlNode nodeToDelete in nodesToDelete)
        {
            nodeToDelete.ParentNode.RemoveChild(nodeToDelete);
        }

        nodesToDelete = document.SelectNodes("//*[@DeleteNode='TRUE']");
    }
}

Когда я использую метод PrepNodesForDeletion без счетчика infinityIndex, я получаю OutOfMemoryException для небольшого количества содержимого HTML. Однако, если я использую счетчик infinityIndex, он может не удалять узлы для некоторого содержимого HTML.

Может кто-нибудь предложить какой-либо способ удалить рекурсию. Также я не знаком с пакетом HtmlAgility. Итак, если это можно сделать с помощью этого, может кто-нибудь предоставить пример кода.

Answer 1

Хорошо, если я правильно понимаю ваш алгоритм, вы хотите сделать следующее: Для каждого узла в дереве сравните его со всеми дочерними узлами нерекурсивным способом, верно?

    // walk the tree in DFS
    public void XmlTreeWalk(XmlNode root, Action<XmlNode, XmlNode> action)
    {
        var nodesToCompare = new Stack<XmlNode>();
        foreach (XmlNode child in root.ChildNodes)
        {
            nodesToCompare.Push(child);
        }
        while (nodesToCompare.Count > 0)
        {
            var top = nodesToCompare.Pop();
            action(root, top);
            foreach (XmlNode child in top.ChildNodes)
            {
                nodesToCompare.Push(child);
            }
        }
    }

    // for each node: prepare all its children for deletion
    public void PrepareForDeletion(XmlNode root)
    {
        XmlTreeWalk(root, (r, c) => PrepareSubtreeForDeletion(r, c));
    }

    // for each node, compare all its children against the toCompare node
    private void PrepareSubtreeForDeletion(XmlNode toCompare, XmlNode root)
    {
        XmlTreeWalk(root, (unused, current) => MarkNodeForDeletion(toCompare, current));
    }

    // your delete logic
    public void MarkNodeForDeletion(XmlNode toCompare, XmlNode toCompareAgains)
    {
       ...
    }

Что этоЧто нужно сделать: пройтись по дереву сверху вниз, и для каждого узла пройти по поддереву этого узла, сравнивая все дочерние элементы с этим узлом.

Я не проверял его, поэтому он может содержать ошибки, но идея должна быть ясной,По-видимому, этот алгоритм O (n ^ 2).

Answer 2

Ваша проблема в том, что у вас плохо сформированный XML, и в результате ваш DOM является беспорядком. Я думаю, что вам нужно будет использовать синтаксический анализатор SAX (который должен существовать для .net) и реализовать логику для самостоятельного исправления DOM, что, по-видимому, является тем, что вы пытаетесь сделать.

Этот метод не является рекурсивным, но потребует от вас выполнения некоторой работы, которую вы не понимали, что вам нужно было сделать.

также обратите внимание, что вы получаете исключение нехватки памяти, а не исключение переполнения стека, что подтверждает идею о том, что слишком большая рекурсия сама по себе не является вашей проблемой.

Answer 3

Чтобы удалить рекурсию, дети и родители должны знать друг о друге.

Затем вы можете пройти, скажем, вниз по правой ноге от корневого родителя, пока не достигнете самой правой нижней ноги.

А затем оттуда поднимитесь на один, затем вниз на левую, а затем вниз вправо до низа. Повторяйте один раз вверх, вниз влево, а затем вправо, насколько это возможно, и т. Д., Пока не пройдете по всей древовидной структуре.

Я не уверен в том, что вы пытаетесь сделать, чтобы предложить, как использовать этот метод в вашей проблеме.