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.

Answer 3

You could significantly narrow your search down with a lambda expression something like:

var foundHighScore = myList.FirstOrDefault(IE => IE.HighScore or (IE.SubEntries != null && IE.SubEntries.Any(IES => IES.HighScore));

var indexEntry = foundHighScore;
if (!indexEntry.HighScore)
{
    indexEntry = indexEntry.SubEntries.FirstOrDefault(IE => IE.HighScore);
}

// do something with indexEntry

Update

Actually the first solution won't traverse through properly. I don't think there is a lambda-only solution to this, you will have to do some form of recursive function. Off the top of my head the following would work, how it would cope performance wise I am unsure:

public IndexEntry FindHighScore(List<IndexEntry> entries)
{
    var highScore = GetHighScore(entries);
    if (highScore == null)
    {
        // give me only entries that contain sub-entries
        var entriesWithSub = entries.Where(e => e.SubEntries != null);
        foreach (var e in entriesWithSub)
        {
            highScore = FindHighScore(e.SubEntries);
            if (highScore != null)
                return highScore;
        }
    }
    return highScore;
}

private IndexEntry GetHighScore(List<IndexEntry> entries)
{
    return entries.FirstOrDefault(IE => IE.HighScore);
}