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\$
  • \$\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\$ – Hosch250 Apr 3 '15 at 3:16
  • \$\begingroup\$ The top 4 items are helpful, and I have made the changes. \$\endgroup\$ – Hosch250 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\$ – Hosch250 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\$
  • \$\begingroup\$ No, I am not returning item, I am returning all values in itemSet where x.Value == item. \$\endgroup\$ – Hosch250 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.