7
\$\begingroup\$

Here is a search implementation for my tree. It searches each node in a breadth-first manner first, but it goes deeper in a depth-first manner, in the event it needs to go deeper. I know there may be multiple identical items in the tree (well, not my current use of it, but I still need to presume that), so it just returns the children for the first instance found. If I ever have duplicate items with different children, there will be other things needing change anyway.

For reference, this method is being implemented as part of my tree here: Trees and their uses

public IEnumerable<T> GetChildren(T item)
{
    IEnumerable<KeyValuePair<int, T>> itemSet = items.Where(x => item.Equals(x.Value));

    if (itemSet.Count() != 0)
    {
        int index = itemSet.ElementAt(0).Key;

        IEnumerable<KeyValuePair<int, Tree<T>>> branchSet = branches.Where(x => x.Key == index);
        
        if (branchSet.Count() != 0)
        {
            return branchSet.ElementAt(0).Value.GetChildren();
        }
    }

    foreach (KeyValuePair<int, Tree<T>> kvp in branches)
    {
        IEnumerable<T> coll = kvp.Value.GetChildren(item);

        if (coll != Enumerable.Empty<T>())
        {
            return coll;
        }
    }
    return Enumerable.Empty<T>();
}

I'm sure there are ways I can improve this, although it looks good to me.

Edit:

Some people asked me for clarification on how my search combined the breadth-first and depth-first searches in The 2nd Monitor. Here are some images showing how they each work (the first two taken from Wikipedia):

Breadth-first search:

Breadth First Search

Depth-first search:

enter image description here

My search:

enter image description here

\$\endgroup\$
4
\$\begingroup\$
  1. I would use First() instead of ElementAt(0) as it conveys the intention better.
  2. Instead of using something.Count() != 0 you should use something.Any(). This avoids having to iterate over the entire sequence just to find out if there are any items in it.
  3. Also you are not interested in the entire itemSet you're just interested in the first one if it exists so you should make use of FirstOrDefault which also provides a predicate overload.
  4. This foreach loop:

    foreach (KeyValuePair<int, Tree<T>> kvp in branches)
    {
         IEnumerable<T> coll = kvp.Value.GetChildren(item);
    
         if (coll != Enumerable.Empty<T>())
         {
             return coll;
         }
    }
    

    can be condensed to:

    var result = branches.Select(kvp => kvp.Value.GetChildren(item))
                         .FirstOrDefault(coll => coll != Enumerable.Empty<T>());
    return result ?? Enumerable.Empty<T>();
    

Update: Due to KeyValuePair being a value type to make it a bit neater a little helper is needed:

public static class Extensions
{
    public static bool EqualsDefault<T>(this T obj)
    {
        return EqualityComparer<T>.Default.Equals(obj, default(T));
    }
}

With this the method could be rewritten as:

public IEnumerable<T> GetChildren(T item)
{
    var firstMatch = items.FirstOrDefault(x => item.Equals(x.Value));

    if (!firstMatch.EqualsDefault())
    {
        var branch = branches.FirstOrDefault(x => x.Key == firstMatch.Key);
        if (!branch.EqualsDefault())
        {
            return branch.Value.GetChildren(item);
        }
    }

    var result = branches.Select(kvp => kvp.Value.GetChildren(item))
                         .FirstOrDefault(coll => coll != Enumerable.Empty<T>());
    return result ?? Enumerable.Empty<T>();
}
\$\endgroup\$
5
  • \$\begingroup\$ Ahh, so that's how it would be done. \$\endgroup\$
    – RubberDuck
    Apr 3 '15 at 2:03
  • \$\begingroup\$ Using FirstOrDefault will not work, because it defaults to the first element. Also, this wasn't stated in my question, but items is a Dictionary, and you cannot compare a KeyValuePair to null. \$\endgroup\$
    – user34073
    Apr 3 '15 at 3:16
  • \$\begingroup\$ The top 4 items are helpful, and I have made the changes. \$\endgroup\$
    – user34073
    Apr 3 '15 at 3:17
  • \$\begingroup\$ @Hosch: I fixed the KeyValuePair one. Regarding the FirstOrDefault - this is what your original code has been doing: First you filter with Where, then you check if you got any results and then you take the first one. Looks exactly like FirstOrDefault to me. \$\endgroup\$
    – ChrisWue
    Apr 8 '15 at 20:36
  • \$\begingroup\$ OK, I will check it again. \$\endgroup\$
    – user34073
    Apr 8 '15 at 20:50
4
\$\begingroup\$

Prefer positive boolean expressions over negations whenever possible.

if (branchSet.Count() != 0)

This can be stated positively like this.

if (brancheSet.Any())

I've got to admit that I don't understand what this line does.

IEnumerable<KeyValuePair<int, T>> itemSet = items.Where(x => item.Equals(x.Value));

You're returning the item that you passed in as an argument to begin with? I guess it also returns other items that match the arg as well. It's not as immediately obvious as it could be. Consider the Linq query here.

items.Where(x => item.Equals(x.Value));

It's a touch convoluted because I would expect item to be a member of items, but it's not. It's the method'd argument. I think some careful renaming and perhaps a comment will help here.


I'm convinced that your for each loop could be simplified with some Linq, but I've not quite worked out exactly how yet.

Something like this maybe.

return branches.Select(kvp => kvp.Value.GetChildren(item)).FirstOrDefault();
\$\endgroup\$
2
  • \$\begingroup\$ No, I am not returning item, I am returning all values in itemSet where x.Value == item. \$\endgroup\$
    – user34073
    Apr 3 '15 at 2:45
  • \$\begingroup\$ I know. I was exaggerating a bit to make a point. item and items differ by one letter, but they're unrelated really. It causes more confusion than is necessary. \$\endgroup\$
    – RubberDuck
    Apr 3 '15 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy