Searching Hierarchical List

Question

I've got a simple class defined as:

public class IndexEntry
{
   public bool HighScore { get; set; }
   public List<IndexEntry> SubEntries { get; set; }
   //Other properties, etc...
}

I now need to search through a List to find the one item that has its HighScore Property set to true. Since it isn't a flat list, but a Hierarchy which can be an unknown number of levels deep and since the item I'm looking for might be contained in any one of the SubEnties lists, I can't do a simple Lambda like this:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore == true);

Here's the code I have. I know it's ugly (at least it seems that way to me). It works, but is slow as sin on an even remotely large list and I'm sure there must be a better way.

private IndexEntry GetHighScoreEntry(IEnumerable<IndexEntry> entryList)
{
    IndexEntry result = null;
    IndexEntry recursiveResult = null;
    foreach (IndexEntry currentEntry in entryList)
    {
        if (currentEntry.HighScore)
        {
            result = currentEntry;
            break;  //Don't need to look anymore, we found our highscore.;
        }
        else
        {
            if ((currentEntry.SubEntries == null) || (currentEntry.SubEntries.Count < 1))
            {
                continue;
            }
            else
            {
                recursiveResult = GetHighScoreEntry(currentEntry.SubEntries);
                if (recursiveResult == null)
                    continue;
                    result = recursiveResult;
                break;
            }
        }
    }
    return result;
}

I've got believe that there's a better way using a slightly more complex lambda or with LINQ to clean up this code and make it more performant.

Thanks in advance for your help.

Answer 1

Recursion is your friend here.

public IndexEntry FindHighScore(IEnumerable<IndexEntry> entries)
{
  foreach (IndexEntry entry in entries)
  {
    IndexEntry highScore = FindHighScore(entry);
    if (highScore != null)
    {
      return highScore;
    }
  }
  return null;
}

private IndexEntry FindHighScore(IndexEntry entry)
{
  return entry.HighScore ? entry : FindHighScore(entry.SubEntries);
}

Answer 2

All the solutions posted so far are specialized - they are not generic or general, and thus, the next time you have a hierarchical list, you'll have to code up a new solution. Yuck.

Here's a general, generic solution that will work for all your hierarchical needs:

public static IEnumerable<T> Flatten<T>(this IEnumerable<T> sequence, Func<T, IEnumerable<T>> childFetcher)
{
    var itemsToYield = new Queue<T>(sequence);
    while (itemsToYield.Count > 0)
    {
        var item = itemsToYield.Dequeue();
        yield return item;

        var children = childFetcher(item);
        if (children != null)
        { 
            foreach (var child in children) 
            {
                itemsToYield.Enqueue(child);
            }
        }
    }
}

Here's how you'd use it:

myList.Flatten(i => i.SubEntries).FirstOrDefault(i => i.HighScore);

Easy as cheese.

This extension method can be used to turn any hierarchical data into a flat list, which can them be searched using LINQ.

Another great thing about this solution is that is uses lazy evaluation, thus it only does as much work as the caller demands. For example, in the above code, Flatten will stop churning out items as soon as a HighScore is found.

This solution also avoids recursion, which can be a costly operation for deeply nested hierarchies, avoiding the many stack allocations that recursive solutions incur.