1

I have levels of tables (Level1, Level2, Level3, ...) For simplicity, we'll say I have 3 levels.

The rows in the higher level tables are parents of lower level table rows. The relationship does not skip levels however. E.g. Row1Level1 is parent of Row3Level2, Row2Level2 is parent of Row4Level3. Level(n-1)'s parent is always be in Level(n).

Given these tables with data, I need to come up with a recursive function that generates an XML file to represent the relationship and the data. E.g.

<data>
  <level levelid = 1 rowid=1>
    <level levelid = 2 rowid=3 />
  </level>
  <level levelid = 2 rowid=2>
    <level levelid = 3 rowid=4 />
  </level>
</data>  

I would like help with coming up with a pseudo-code for this setup. This is what I have so far:

Edited/Updated code:

XElement GetXML(ArrayList list, XElement xml)
        {
            XElement xElement = xml;
            // Get the rows of the current list into xmlData format
            ArrayList childList = GetChildList(list);

            if (childList != null)
            {
                foreach (Row r in list)
                {
                    // Convert the rows to xml
                    xElement = new XElement(xml);
                    xElement.AddFirst(new XElement("Row"));
                    xElement.Add(new XAttribute("RowId", r.RowId));

                    // Get the children as xml
                    if (childList != null)
                    {
                        ArrayList childRows = GetChildRows(list);
                        XElement childXml = GetXML(childRows, xElement);
                        if (childXml != null)
                        {
                            xElement.Add(childXml);
                        }
                    }
                }
            }
            return xElement;
       }

This is the main function. I can add the rest of the test program if needed. Thank you.

static void Main(string[] args)
        {
            Program p = new Program();

            // Initialize datasets
            p.InitializeLists();

            // Create xml map of the datasets
            XElement x = p.GetXML(p.level1, new XElement("Row"));

            Console.WriteLine(x.ToString());
            Console.ReadLine();
        }
  • See also: dba.stackexchange.com/questions/39365/… – Dave Jarvis Oct 28 '13 at 16:54
  • Hi Dave, Thank you for your suggestion. The link you posted is related to tables in a database. In this example, Table is just an example datatype. I want to keep this generic. I am more interested in seeing how recursion plays out in this scenario. Thank you again. – Tom Oct 28 '13 at 18:15
1

First and foremost, this should probably be moved to the Code Review site.

I would prefer to come at the problem from a different angle, using objects to handle the behavior rather than a recursive method which knows how to traverse everything. Doing so seems to map your domain better, with a bonus that it eliminates the need for a ListID value stored on each row, making it scale better.

public class Row
{
   public ICollection<Row> ChildRows { get; private set; }
   public int RowId { get; private set; }
   public int ParentRowId { get; private set; }

   public Row(int rowId, int parentRowId)
   {
      RowId = rowId;
      ParentRowId = parentRowId;
      ChildRows = new List<Row> ();
   }

   public XElement BuildXML(int level)
   {
      var element = new XElement("level",
                                 new XAttribute("levelid", level),
                                 new XAttribute("rowid", RowId));
      if (ChildRows.Any())
         element.Add(ChildRows.Select(r => r.BuildXML(level + 1)));

      return element;
   }
}

I would then build my object hierarchy as a tree structure. To do so easily, I would initialize with two collections - one a list of the top-level items, and the other a dictionary of all items:

void InitializeLists()
{
   var allRows = new List<Row>
                 {
                    new Row(1, 0),
                    new Row(2, 0),
                    new Row(3, 0),
                    new Row(1, 1),
                    new Row(2, 2),
                    new Row(3, 2),
                    new Row(4, 3),
                    new Row(5, 1),
                    new Row(6, 1),
                    new Row(1, 3),
                    new Row(2, 3),
                    new Row(3, 4),
                    new Row(4, 6),
                    new Row(5, 6),
                    new Row(6, 6),
                 }; 
   var rowTable = allRows.ToDictionary(r => r.RowId);

   var rootRows = new List<Row>();
   foreach(var row in allRows)
   {
      if(row.RowId == 0)
         rootRows.Add(row);
      else
      {
         Row parentRow;

         if(rowTable.TryGetValue(row.ParentRowId, out parentRow))
         {
            parentRow.ChildRows.Add(row);
         }
         else
         {
            // throw or log an appropriate error
         }
      }
   }

   _rootRows = rootRows;
}

With that done, your XML building becomes rather trivial:

public static void Main(string[] args)
{
   var p = new Program();

   // Initialize datasets
   p.InitializeLists();

   // Create xml map of the datasets
   XElement x = p.GetXML();

   Console.WriteLine(x.ToString());
   Console.ReadLine();
}

public XElement GetXML()
{
   var xElement = new XElement("Rows");
   foreach(var row in _rootRows)
      xElement.Add(row.BuildXML(1));

   return xElement;
}

Update

I failed to notice on my first attempt that the row IDs were non-unique. There are two basic options to address this:

  • Make the IDs unique
  • Make a composite key for lookup which will be unique. The easiest option here is to re-introduce the list IDs and build a key as a combination of ID and list ID.

Since the above examples handle cases with unique row IDs, I will add some tweaks for the second option. First, we re-introduce ListId to the Row. This lets us remove the parameter from BuildXML:

public class Row
{
   public ICollection<Row> ChildRows { get; private set; }
   public int RowId { get; private set; }
   public int ListId { get; private set; }
   public int ParentRowId { get; private set; }

   public Row(int rowId, int listId, int parentRowId)
   {
      RowId = rowId;
      ListId = listId;
      ParentRowId = parentRowId;
      ChildRows = new List<Row> ();
   }

   public XElement BuildXML()
   {
      var element = new XElement("level",
                                 new XAttribute("levelid", ListId),
                                 new XAttribute("rowid", RowId));
      if (ChildRows.Any())
         element.Add(ChildRows.Select(r => r.BuildXML()));

      return element;
   }
}

Then, we re-do how we initialize:

void InitializeLists()
{
   var allRows = new List<Row>
                 {
                    new Row(1, 1, 0),
                    new Row(2, 1, 0),
                    new Row(3, 1, 0),
                    new Row(1, 2, 1),
                    new Row(2, 2, 2),
                    new Row(3, 2, 2),
                    new Row(4, 2, 3),
                    new Row(5, 2, 1),
                    new Row(6, 2, 1),
                    new Row(1, 3, 3),
                    new Row(2, 3, 3),
                    new Row(3, 3, 4),
                    new Row(4, 3, 6),
                    new Row(5, 3, 6),
                    new Row(6, 3, 6),
                 };

   const string FMT = "{0}:{1}";

   var rowTable = allRows.ToDictionary(r => string.Format(FMT, r.ListId, r.RowId));

   var rootRows = new List<Row>();
   foreach(var row in allRows)
   {
      if(row.ListId == 1)
         rootRows.Add(row);
      else
      {
         Row parentRow;

         var parentKey = string.Format(FMT, row.ListId-1, row.ParentRowId);

         if(rowTable.TryGetValue(parentKey, out parentRow))
         {
            parentRow.ChildRows.Add(row);
         }
      }
   }

   _rootRows = rootRows;
}

Finally, we fix the GetXML function so it does not pass in a starting level:

XElement GetXML()
{
   XElement xElement = new XElement("Rows");
   foreach(var row in _rootRows)
      xElement.Add(row.BuildXML());

   return xElement;
}
  • Hey Dan, Thank you for your detailed reply. It looks like this only prints out the rootRow though. Also, this line: var rowTable = allRows.ToDictionary(r => r.RowId); throws error because its trying to add duplicate keys. – Tom Oct 30 '13 at 15:53
  • @Tom oops, my fault for not noticing the row IDs were not unique. That's what I get for rushing through an answer over a lunch break :) I shall update the answer with some options to address that. – Dan Lyons Oct 30 '13 at 17:21
  • It should print the entire XML structure, as we are recursively building it through the Row.BuildXML functions. The difference in how it is done here versus the original code is that we handle the recursion within the Row object, since it now acts as a tree. – Dan Lyons Oct 30 '13 at 17:40
  • Dan, This works perfectly. I did try with composite key with rowId*10 + parentRowId for the key, but the issue then came when getting the parent back using the 'reverse' of this 'key'. Thank you again for your time. I wanted to vote your solution up, but it requires 15 reputation points. I will get there :) – Tom Oct 30 '13 at 18:40
0

Here is the whole solution. This worked. Thanks for looking :)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Xml.Linq;

namespace RecursiveExcursion
{
    class Program
    {
        ArrayList level1 = new ArrayList();
        ArrayList level2 = new ArrayList();
        ArrayList level3 = new ArrayList();

        static void Main(string[] args)
        {
            Program p = new Program();

            // Initialize datasets
            p.InitializeLists();

            // Create xml map of the datasets
            XElement x = p.GetXML(p.level1, new XElement("Rows"));

            Console.WriteLine(x.ToString());
            Console.ReadLine();
        }

        void InitializeLists()
        {
            // Add rows to the first list
            level1.Add(new Row(1, 1, 0));
            level1.Add(new Row(1, 2, 0));
            level1.Add(new Row(1, 3, 0));

            // Add rows to the second list
            level2.Add(new Row(2, 1, 1));
            level2.Add(new Row(2, 2, 2));
            level2.Add(new Row(2, 3, 2));
            level2.Add(new Row(2, 4, 3));
            level2.Add(new Row(2, 5, 1));
            level2.Add(new Row(2, 6, 1));

            // Add rows to the third list
            level3.Add(new Row(3, 1, 3));
            level3.Add(new Row(3, 2, 3));
            level3.Add(new Row(3, 3, 4));
            level3.Add(new Row(3, 4, 6));
            level3.Add(new Row(3, 5, 6));
            level3.Add(new Row(3, 6, 6));
        }

        XElement GetXML(ArrayList list, XElement xml)
        {
            XElement xElement = xml;

            // Get the rows of the current list into xmlData format
            ArrayList childList = GetChildList(list);

            if (childList != null)
            {
                foreach (Row r in list)
                {
                    // Convert the rows to xml
                    XElement xElementRow = new XElement("Row");
                    xElementRow.Add(new XAttribute("RowId", r.RowId));

                    // Get the children as xml
                    ArrayList childRows = GetChildRows(list, r);
                    xElement.Add(GetXML(childRows, xElementRow));
                }
            }
            else
            {
                foreach (Row r in list)
                {
                    XElement xElementRow = new XElement("Row");
                    xElementRow.Add(new XAttribute("RowId", r.RowId));
                    xElement.Add(xElementRow);
                }
            }
            return xElement;
        }

        private ArrayList GetChildRows(ArrayList list, Row r)
        {
            ArrayList childList = GetChildList(list);
            ArrayList childRows = new ArrayList();

            if (childList != null)
            {
                foreach (Row childRow in childList)
                {
                    if (childRow.ParentRowId == r.RowId)
                    {
                        childRows.Add(childRow);
                    }
                }
                return childRows;
            }
            else
            {
                return null;
            }
        }

        private ArrayList GetChildList(ArrayList list)
        {
            if (list.Count > 0)
            {
                int listName = 0;

                Row firstRow = (Row)list[0];
                listName = firstRow.ListId;

                switch (listName)
                {
                    case 1:
                        {
                            return this.level2;
                        }
                    case 2:
                        {
                            return this.level3;
                        }
                    case 3:

                    default:
                        {
                            return null;
                        }
                }

            }
            return null;

        }

        bool IsLastLevel(int listId)
        {
            return listId == 3;
        }
    }

    class Row
    {
        public int ListId { get; set; }
        public int RowId { get; set; }
        public int ParentRowId { get; set; }

        public Row()
        {
        }

        public Row(int listId, int rowId, int parentRowId)
        {
            ListId = listId;
            RowId = rowId;
            ParentRowId = parentRowId;
        }
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.