XML tree generation

Question

I've got a "flat" XML menu that I need to structure.

Current XML tree:

<root>
    <nodes>
        <node>
            <id>5</id>
            <parent>1</parent>
        </node>
        <node>
            <id>8</id>
            <parent>5</parent>
        </node>
        <node>
            <id>14</id>
            <parent>8</parent>
        </node>
        <node>
            <id>26</id>
            <parent>1</parent>
        </node>
    </nodes>    
</root>

This XML tree need to be reodered to have correct relations between ID:s and ParentID:S

<root>
    <nodes>
        <node>
            <id>5</id>
            <parent>1</parent>
            <node>
                <id>8</id>
                <parent>5</parent>
                <node>
                    <id>14</id>
                    <parent>8</parent>
                </node>
            </node>
        </node>            
        <node>
            <id>26</id>
            <parent>1</parent>
        </node>
    </nodes>    
</root>

Iv got the following code to try to accomplish this:

public XmlDocument SortXmlNodeTree(XmlDocument udoc)
{
    XmlDocument sortedDoc = new XmlDocument();
    sortedDoc.LoadXml(xmlStartString);

    //select top nodes
    //top node -> find all siblings. For each sibling add sibling.siblings. ->loop            
    XmlNode nodes = udoc.DocumentElement.LastChild;
    foreach(XmlNode n in nodes)
    {
        //get top nodes and check if they are folders
        if (n["parent"].InnerText.Equals("1") && n["type"].InnerText.Equals("2"))
        {
            XmlNode newNode = sortedDoc.ImportNode(n, true);                        
            GetNodeSiblings(ref nodes, newNode, ref sortedDoc);       
            SortedDoc.DocumentElement.FirstChild.AppendChild(newNode);                    
        }
    }
    return sortedDoc;
}

public XmlNode GetNodeSiblings(ref XmlNode nodes, XmlNode currentNode, ref XmlDocument tree)
{
    if (!nodes.HasChildNodes)
    {
        return null;
    }

    foreach (XmlNode n in nodes)
    {
        // if we have a folder and parent is currentNode, go deeper
        if (n["type"].InnerText.Equals("2") && n["parent"].InnerText.Equals(currentNode["id"].InnerText))
        {
            XmlNode newNode = tree.ImportNode(n, true);                    
            GetNodeSiblings(ref nodes, newNode, ref tree);
            currentNode.AppendChild(newNode);
        }
        // if we have a product that has currentNode as parent, add it.
        else if (!n["type"].InnerText.Equals("2") && n["parent"].InnerText.Equals(currentNode["id"].InnerText))
        {
            XmlNode newNode = tree.ImportNode(n, true);
            nodes.RemoveChild(n);
            currentNode.AppendChild(newNode);
        }
    }
    return null;
}

As you can see my nodes also contain "type" and "name". Types are used to determine if a nodes is a "folder" or a "product".

My problem is that this dosn't return the correct XML. If I remove the nodes.RemoveChild(n) in the last section then it works great but I whant to remove the children (products, type=1) that I know haven't got any children.

If this code is run. I only get a few nodes.

Answer 1

Here's some code that gets all the nodes with the name 'node':

    public static IEnumerable<XmlNode> GetNodes(XmlDocument xdoc)
    {
        var nodes = new List<XmlNode>();

        Queue<XmlNode> toProcess = new Queue<XmlNode>();

        if (xdoc != null)
        {
            foreach (var node in GetChildElements(xdoc))
            {
                toProcess.Enqueue(node);
            }
        }

        do
        {
            //get a node to process
            var node = toProcess.Dequeue();

            // add node to found list if name matches
            if (node.Name == "node")
            {
                nodes.Add(node);
            }

            // get the node's children
            var children = GetChildElements(node);

            // add children to queue.
            foreach (var n in children)
            {
                toProcess.Enqueue(n);
            }

            // continue while queue contains items.
        } while (toProcess.Count > 0);


        return nodes;
    }

    private static IEnumerable<XmlNode> GetChildElements(XmlNode node)
    {
        if (node == null || node.ChildNodes == null) return new List<XmlNode>();

        return node.ChildNodes.Cast<XmlNode>().Where(n=>n.NodeType == XmlNodeType.Element);
    }

Then you'll need to move the nodes around based on parent-child rel'ships. See @PierrOz's answer.

Answer 2

this code does the job. Hope it's clear enough

public class Node
{
    public Node()
    {
        Children = new List<Node>();
    }

    public int Id;

    public int ParentId;

    public List<Node> Children;

    public Node Parent;

    public static Node Deserialize(XmlElement xNode)
    {
        Node n = new Node();
        XmlElement xId = xNode.SelectSingleNode("id") as XmlElement;
        n.Id = int.Parse(xId.InnerText);
        XmlElement xParent = xNode.SelectSingleNode("parent") as XmlElement;
        n.ParentId = int.Parse(xParent.InnerText);
        return n;
    }

    public void AddChild(Node child)
    {
        Children.Add(child);
        child.Parent = this;
    }

    public void Serialize(XmlElement xParent)
    {
        XmlElement xNode = xParent.OwnerDocument.CreateElement("node");
        XmlElement xId = xParent.OwnerDocument.CreateElement("id");
        xId.InnerText = Id.ToString();
        xNode.AppendChild(xId);
        XmlElement xParentId = xParent.OwnerDocument.CreateElement("parent");
        xParentId.InnerText = ParentId.ToString();
        xNode.AppendChild(xParentId);
        foreach (Node child in Children)
            child.Serialize(xNode);
        xParent.AppendChild(xNode);
    }
}

public static XmlDocument DeserializeAndReserialize(XmlDocument flatDoc)
{
    Dictionary<int, Node> nodes = new Dictionary<int, Node>();
    foreach (XmlElement x in flatDoc.SelectNodes("//node"))
    {
        Node n = Node.Deserialize(x);
        nodes[n.Id] = n;
    }

    // at the end, retrieve parents for each node
    foreach (Node n in nodes.Values)
    {
        Node parent;
        if (nodes.TryGetValue(n.ParentId, out parent))
        {
           parent.AddChild(n);
        }
    }

    XmlDocument orderedDoc = new XmlDocument();
    XmlElement root = orderedDoc.CreateElement("root");
    orderedDoc.AppendChild(root);
    XmlElement xnodes = orderedDoc.CreateElement("nodes");
    foreach (Node n in nodes.Values)
    {
        if (n.Parent == null)
            n.Serialize(xnodes);
    }
    root.AppendChild(xnodes);
    return orderedDoc;
}

Answer 3

I would take a different approach to the problem. You are now trying to modify an existing document by moving nodes around which is rather complex. I would parse the original document, store it in some data structure and write it again to another location.

Your data structure would look something like this:

public class Node
{
    public SomeClass NodeData { get ; set; }
    public List<Node> Children { get; }
}

where SomeClass is a typed object that holds the relevant data for a single node. And then your code should look like this:

Node rootNode = ParseXml(...);
WriteStructuredXml(rootNode);

Both of these methods are not hard to write. This way you divide the problem into two smaller, easier problems.