Convert Recursive Method Group in LINQ Select to iterative method

Question

I've got a class that looks like this:

public class SourceObject
{
    public string Id { get; set; }
    public List<SourceObject> Children { get; set; }

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

As you can see, it has a property that contains a list of further instances of this same class. The data I'm dealing with for this class means that the number of children is unknown until runtime and the overall "depth" of the resulting object graph is also unknown.

I need to create a "mapping" from the object graph of SourceObject to a similarly shaped graph of DestinationObject's (similar to how AutoMapper might map from one object to another).

I've got a method that will map from my Source graph to my Destination graph, however, this method uses recursion:

// Recursive way of mapping each Source object to Destination
public static DestinationObject MapSourceToDestination(SourceObject source)
{
    var result = new DestinationObject();
    result.Id = source.Id;
    result.Children = source.Children.Select(MapSourceToDestination).ToList();
    return result;
}

This works fine when the size of the source object graph isn't too large or deep, however, when the source object graph is very large, this method will throw a StackOverflow exception.

I have managed to create an alternative version of this function that removes the recursion and replaces it with a Queue/Stack using a technique similar to that described in this answer) however, I've noticed that the Queue/Stack can also grow very large and I'm not sure that my implementation is the most efficient.

Is it possible to convert the recursive function to one that purely uses iteration over the source object graph (i.e. removing recursion and ideally, the use of a Queue/Stack)?

Answer 1

I still believe the stack with size the max depth of the tree is the optimal general solution.

But interestingly, the data structure and the concrete process contain all the necessary information to implement the conversion without explicit stack just based on Children.Count. Let see what we need:

(1) Are there more source children to process: source.Children.Count != target.Children.Count)

(2) Which is the next source child to process: source.Children[target.Children.Count]

(3) What is the current processing child index: target.Children.Count - 1

Note that the above rules apply for any level during the processing.

Here is the implementation:

public static DestinationObject MapSourceToDestination(SourceObject source)
{
    // Map everything except childen
    Func<SourceObject, DestinationObject> primaryMap = s => new DestinationObject
    {
        Id = s.Id,
        // ...
        Children = new List<DestinationObject>(s.Children.Count) // Empty list with specified capacity
    };

    var target = primaryMap(source);

    var currentSource = source;
    var currentTarget = target;
    int depth = 0;
    while (true)
    {
        if (currentTarget.Children.Count != currentSource.Children.Count)
        {
            // Process next child
            var sourceChild = currentSource.Children[currentTarget.Children.Count];
            var targetChild = primaryMap(sourceChild);
            currentTarget.Children.Add(targetChild);
            if (sourceChild.Children.Count > 0)
            {
                // Move one level down
                currentSource = sourceChild;
                currentTarget = targetChild;
                depth++;
            }
        }
        else
        {
            // Move one level up
            if (depth == 0) break;
            depth--;
            currentSource = source;
            currentTarget = target;
            for (int i = 0; i < depth; i++)
            {
                int index = currentTarget.Children.Count - 1;
                currentSource = currentSource.Children[index];
                currentTarget = currentTarget.Children[index];
            }
        }
    }

    return target;
}

The only tricky (and partially inefficient) part is the moving up step (which is why the general solution requires stack). If the objects had Parent property, it would have been simply:

currentSource = currentSource.Parent;
currentTarget = currentTarget.Parent;

With the lack of such properties, to find the parents of the current source and target items, we start from root items and move down through currently processing index (see (3)) until we hit the desired depth.