Recursively find all objects of type System.Web.UI.Pair in an object array

Review

Here's the method I came up with, but it feels inelegant and incomplete. Any improvements, especially ones that can leverage LINQ are welcome.

You could write it more elegantly by using recursion for your pair members.

 if (pair.First is IEnumerable)
 {
      Flatten((root as Pair).First, list);
 }
 else if (pair.First is Pair)
 {
      list.Add(pair.First as Pair);
 }
 if (pair.Second is IEnumerable)
 {
      Flatten((root as Pair).Second, list);
 }
 else if (pair.Second is Pair)
 {
      list.Add(pair.Second as Pair);
 }

if (root is Pair)
{   
    var pair = root as Pair;
    list.Add(pair);      
    Flatten(pair.First, list);
    Flatten(pair.Second, list);
}

You are right that it is incomplete. You are missing:

• pairs in dictionaries KeyValuePair<T, Pair>
• pairs in complex objects Tuple<T, Pair>, MyPairWrapper
• pairs in anonymous objects

code

public class MyPairWrapper {
    public Pair Value { get; }
    // ..
}

Your search strategy expects a tree structure, not a graph. In the following example you will get an infinite cycle.

var pair = new Pair();
pair.First = pair;

Proposed Solution

I suggest to make a graph traversal walker that is able to deal with:

• cyclic graphs as well as trees
• any reference type you want to flatten
• any kind of sequence (Array, IEnumerable, IQueryable, IDictionary, ..)
• anonymous types
• common structs and classes (Tuple<T1,T2,..>, KeyValuePair<TKey,TValue>, ..)
• complex types (traverse public fields and readable properties)

Let's start..

I adapted the method signature of the extension method and redirected the implementation to ObjectGraphWalker.

public static class LinqExtension
{
    public static IEnumerable<T> Flatten<T>(this object root) where T : class {
        return ObjectGraphWalker.Flatten<T>(root);
    }
}

The graph walker ObjectGraphWalker traverses any graph (tree, acyclic or cyclic) and keeps track of visited objects to avoid infinite loops. Recursion is used to traverse sequences and complex objects.

public static class ObjectGraphWalker
{
    public static IEnumerable<T> Flatten<T>(object root) where T : class {
        var results = new List<T>();
        var visited = new ArrayList();
        FlattenWalk(root, results, visited);
        return results.ToArray();
    }

    private static void FlattenWalk<T>(object source, IList<T> results, IList visited) 
        where T : class 
    {
        if (source == null) return;
        if (visited.Contains(source)) return;
        visited.Add(source);

        // source is instance of T or any derived class
        if (typeof(T).IsInstanceOfType(source)) {
            results.Add((T)source);
        }

        // source is a sequence of objects
        if (source is IEnumerable) {
            // includes Array, IDictionary, IList, IQueryable
            FlattenWalkSequence((IEnumerable)source, results, visited);
        }

        // dive into the object's properties
        FlattenWalkComplexObject(source, results, visited);
    }

    private static void FlattenWalkSequence<T>(IEnumerable source, 
        IList<T> results, IList visited) 
        where T : class 
    {
        if (source == null) return;
        foreach (var element in source) {
            FlattenWalk(element, results, visited);
        }
    }

    private static void FlattenWalkComplexObject<T>(object source, 
        IList<T> results, IList visited) 
        where T : class 
    {
        if (source == null) return;
        var type = source.GetType();
        var properties = type.GetProperties(BindingFlags.Public | BindingFlags.Instance)
            .Where(x => x.CanRead && !x.GetIndexParameters().Any());
        var fields = type.GetFields(BindingFlags.Public | BindingFlags.Instance);
        // search its public fields and properties
        foreach (var field in fields) {
            FlattenWalk(field.GetValue(source), results, visited);
        }
        foreach (var property in properties) {
            FlattenWalk(property.GetValue(source), results, visited);
        }
    }
}

Test Case

Let's create a derived class Triad and a complex object PairProvider that has a Pair as property.

public class PairProvider
{
    public Pair Value;
}

public class Triad : Pair
{
    public object Third;
}

public class Pair
{
    public object First;
    public object Second;
}

Test method:

public static void Main() {

        var pair1 = new Pair { First = 1, Second = 2 }; // 1
        var pair2 = new Pair { First = 3, Second = pair1 }; // 2
        var triad = new Triad { First = "John", Second = "Doe" }; // 3
        triad.Third = triad;

        var dynamicObject = new {
            pair = new Pair { // 4
                First = pair1,
                Second = new[] { pair1, pair2 }
            },
            adapter = new PairProvider { Value = triad },
            items = new Dictionary<int, IEnumerable> {
                { 1, new object[] { 1, 2, new Pair { First = 1, Second = triad } } }, // 5
                { 2, new int[] { 1, 2, 3 } },
                { 3, new object[] { Tuple.Create<Pair, Pair>(pair2, new Pair()) } } // 6
            }
        };

        var flattened = dynamicObject.Flatten<Pair>();
        var count = flattened.Count(); // = 6

        Console.ReadKey();
    }

1. You don't need to return anything. The list you initially pass in is a reference, which you can use after the function returns. The function can be of type void.

2. You can recurse on First and Second.

3. root.GetType().IsArray isn't needed

new code:

public static void Flatten(this object root, List<Pair> list)
{
    if (root == null)
    {
        return;
    }
    if (root is Pair)
    {
        var pair = root as Pair;
        list.Add(pair);
        Flatten(pair.First, list);
        Flatten(pair.Second, list);
        return;
    }
    if (root is IEnumerable)
    {
        foreach (object o in (IEnumerable) root)
        {
            Flatten(o, list);
        }
    }
}