LinqTraversal

CSharp · Console

/Program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public static class LinqExtension
{
  public static IEnumerable<T> Traverse<T>(this T item, Func<T,T> childSelector)
  {
    var stack = new Stack<T>(new T[]{item});
    
    while (stack.Any ())
    {
      var next = stack.Pop();
      if(next != null)
      {
        yield return next;
        stack.Push(childSelector(next));
      }
    }
  }
  
  public static IEnumerable<T> Traverse<T>(this T item, Func<T,IEnumerable<T>> childSelector)
  {
    var stack = new Stack<T>(new T[]{item});
    
    while (stack.Any ())
    {
      var next = stack.Pop();
      //if(next != null)
      //{
        yield return next;
        foreach (var child in childSelector(next))
        {
          stack.Push(child);
        }
      //}
    }
  }
  
  public static IEnumerable<T> Traverse<T>(this IEnumerable<T> items, 
    Func<T, IEnumerable<T>> childSelector)
  {
      var stack = new Stack<T>(items);
      while(stack.Any())
      {
          var next = stack.Pop();
          yield return next;
          foreach(var child in childSelector(next))
              stack.Push(child);
      }
  }
}
					
public class Program
{
	public static void Main()
	{
		UnitTest unitTest = new UnitTest();
		unitTest.Assert(false, "Test Failure {0}", new object[]{-1});
		unitTest.TestSameType();
		unitTest.TestDescendantType();
		unitTest.TestEnumerableSelector();
		unitTest.TestEnumerable();
		unitTest.TestReverseTraversal();
	}
}

public class UnitTest
{
  public void Assert(bool Assertion, string details = "", object[] args = null)
  {
    if(args == null)
    {
      args = new object[]{};
    }
    var caller = new StackFrame(1, true).GetMethod().Name;
    if(!Assertion)
    {
      Debug.Assert(Assertion, caller, details, args);
      Console.WriteLine("Fail: {0} - {1}", caller, string.Format(details, args));
    }
  }
	
  public void TestSameType()
  {
    // Test Case 1 Same Types
    var innerException = new Exception("Root Exception");
    innerException.Data["Error Code"] = -1;
    var exception = new Exception("oh no", innerException);
    //exception.Dump();
    
    var allExceptions = exception.Traverse(ex => ex.InnerException);//.Dump();
    
    Assert(allExceptions.Count () == 2);
    
    // This is what got me started down this rabbit hole. If anyone knows a simpler way, let me know.
    var lookingForKey = "Error Code";
    Assert(
      allExceptions.Where (e => e.Data != null 
        && e.Data.Contains(lookingForKey) 
        && e.Data[lookingForKey] is int
        && (int)e.Data[lookingForKey] == -1
        ).Any (),
      "Exception Exists");
  }
  
  public void TestDescendantType()
  {
    var innerException = new Exception("root error");
    var exception = new ApplicationException("oh no", innerException);
    
    // Need to specify the base type here.  I was hoping to get it to work
    // with a where T:TAncestor on the helper function, but I could not.
    var allExceptions = exception.Traverse<Exception>(ex => ex.InnerException);//.Dump();
    
    Assert(allExceptions.Count () == 2);
  }
  
  public void TestEnumerableSelector()
  {
    var folder = new Folder(2, 2) {Name = "Root"};
    //folder.Dump();
    
    var allFolders = folder.Traverse(f => f.SubFolders);//.Dump();
    
    Assert(allFolders.Count () == 7, System.Reflection.MethodInfo.GetCurrentMethod().Name);
    // Example requested by Keith to not include parent.  Could modify the function, but it's not
    // what I need so instead have this.
    //allFolders.Where (f => f != folder).Dump();
    Assert(allFolders.Where (f => f != folder).Count () == 6,
      "Exclude Parent");
    // Or you could also do it like this, as int TestEnumerable()
    Assert(folder.SubFolders.Traverse(f => f.SubFolders).Count () == 6,
      "Exclude Parent Example 2");
  }
  
  public void TestEnumerable()
  {
    var folder = new Folder(2,2){Name = "Root"};
    
    var allSubFolders = folder.SubFolders.Traverse(f => f.SubFolders);//.Dump();
    
    Assert(allSubFolders.Count () == 6);
  }
  
  public void TestReverseTraversal()
  {
    var folder = new Folder(2,2){Name = "Root"};//.Dump();
    var subFolder = folder.SubFolders.Last ().SubFolders.Last ();//.Dump();
    var allParents = subFolder.Traverse(f => f.Parent);//.Dump();
    
    Assert(allParents.Count () == 3);
  }
  
    // Test Data
  public class Folder
  {
    // Curtesy of http://www.generatedata.com/
    private static string[] TestNames = {"Samson","Mohammad","Grant","Ross","Sean","Oscar","Edan","Ryder","Arden","Raphael",
      "Dolan","Dillon","Burton","Hunter","Lewis","Rooney","Gareth","Vladimir","Uriah","Xavier",
      "Plato","Lance","Baxter","Aristotle","Brian","Ralph","Dillon","Cullen","Joel","Matthew",
      "Thomas","Kenyon","Gregory","Francis","Odysseus","Samuel","Peter","Conan","Jarrod",
      "Ezekiel","Tarik","Odysseus","Adam","Fulton","Callum","Gage","Gannon","Silas","Allen",
      "Avram","Kenneth","Dieter","Ishmael","Josiah","Sebastian","Acton","Elijah","Nehru",
      "Upton","Ferdinand","Brendan","Edan","Carter","Erasmus","Zeph","Colin","Noble","Chase",
      "Colin","Gray","Micah","Amos","Kasimir","Armand","Upton","Dane","Carter","Zephania","Aladdin",
      "Keith","Malcolm","Marshall","Norman","Jerry","Bevis","Connor","Fulton","Colby","Eaton",
      "Ivan","Zane","Abel","Ryder","Benedict","Austin","Garrett","Dexter","Cain","Yuli","Theodore",};
    private static IEnumerable<string> AvailableNames = new List<string>();
    public Folder(int subFolderCount, int levels)
    {
      if(AvailableNames.Count () == 0)
      {
        AvailableNames = new List<String>(TestNames);
      }
      SubFolders = new List<Folder>(subFolderCount);
      if(levels > 0)
      {
        for(int i = 0; i < subFolderCount; i++)
        {
          SubFolders.Add(new Folder(subFolderCount, levels -1)
            {
              Name = AvailableNames.First (),
              Parent = this
            });
          AvailableNames = new List<string>(AvailableNames.Skip(1));
        }
      }
    }
    
    public string Name{get;set;}
    public IList<Folder> SubFolders{get;set;}
    public Folder Parent{get;set;}
  }
}