LINQ and recursion

Question

Consider the following:

public class Box
{
    public BoxSize Size { get; set; }

    public IEnumerable<Box> Contents { get; set; }
}

Box FindBoxBySize(Box box, BoxSize size)
{
    Box _foundBox = null;

    Action<IEnumerable<Box>> _recurse = null;

    _recurse = new Action<IEnumerable<Box>>(boxes =>
    {
        foreach (var _box in boxes)
        {
            if (_box.Size == size)
            {
                _foundBox = _box;

                return;
            }

            if (_box.Contents != null) _recurse(_box.Contents);
        }
    });

    _recurse(box.Contents);

    return _foundBox;
}

Is there any way that FindBoxBySize() can be compacted using LINQ? Also: comments on my code are welcome. I don't do much recursion, so I might have missed something in my implementation.

Enigmativity · Accepted Answer · 2010-11-24 02:46:51Z

5

I'd also take the extension method approach, but use an iterator method:

public static class BoxEx
{
    public static IEnumerable<Box> Flatten(this Box box)
    {
        yield return box;
        if (box.Contents != null)
        {
            foreach (var b in box.Contents.SelectMany(b2 => Flatten(b2)))
            {
                yield return b;
            }
        }
    }
}

Your FindBoxBySize method now becomes:

Box FindBoxBySize(Box box, BoxSize size)
{
    return (from b in box.Flatten()
            where b.Size == size
            select b).FirstOrDefault();
}

Your original calling code works without modification:

var small = FindBoxBySize(box, BoxSize.Small);

answered Nov 24, 2010 at 2:46

Enigmativity

117k12 gold badges101 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

abatishchev · Accepted Answer · 2010-11-24 06:58:51Z

2

Extension methods:

class Box
{
    public IEnumerable<Box> GetBoxes()
    {
        // avoid NullReferenceException
        var contents = this.Contents ?? Enumerable.Empty<Box>();

        // do the recursion
        return contents.SelectMany(b => b.GetBoxes()).Concat(contents);
    }

    public Box GetBox(int size)
    {
        return this.GetBoxes().FirstOrDefault(b => b.Size == size);
    }
}

Usage:

var box_with_box = new Box { Contents = new[] { new Box() { Size = 10 } } };
var box = new Box { Contents = new[] { box_with_box, box_with_box } };

Box box10 = box.GetBox(10);

edited Nov 24, 2010 at 6:58

answered Nov 23, 2010 at 14:44

abatishchev

101k88 gold badges303 silver badges443 bronze badges

6 Comments

cllpse Over a year ago

I think it does. But notice my break-statement; I'd really like there to be as little "looping" as possible, so whenever a match is found, I'd like to terminate.

Ani Over a year ago

This is still wrong. It blows up on null, which is clearly important to the OP. Secondly, it never actually yields a real box.

Ani Over a year ago

No. When is a real box reference actually being yielded?

abatishchev Over a year ago

@Ani: Yea, I see. But I haven't examined it, really. Indeed I was rewriting my own extension method (for ASP.NET, recursion for Control.FindControl()) but with lack of attention :)

AntonioR Over a year ago

Also, it is not a good pratice to write an extension method to your own classes. Why to use an EM when you could make it a public instance method of Box class? Object Oriented concepts as inheritance should not be easily replaced by EM. I really like EM and wrote a lot of then. It is a very usefull technique to be used when you want to extend a Type of an external library (including .net framework itself) and don't want (or can't) to create a derived Type. But overuse this technique leads to a model that just isn't object oriented, what is usually undesirable. Greetings.

|

Ani · Accepted Answer · 2010-11-23 19:00:40Z

1

If you want to use LINQ, you could do something like this (untested):

public static IEnumerable<Box> GetBoxesRecursive(this Box box)
{
  if(box == null)
      throw new ArgumentNullException("box");

  var children = box.Contents ?? Enumerable.Empty<Box>();

                           // use lambda in C# 3.0      
  var recursiveChildren = children.SelectMany(GetBoxesRecursive);  

  return new[] { box }.Concat(recursiveChildren);                                    
}

...    

Box desiredBox = myBox.GetBoxesRecursive()
                      .FirstOrDefault(b => b.Size == desiredSize);

edited Nov 23, 2010 at 19:00

answered Nov 23, 2010 at 14:49

Ani

114k27 gold badges269 silver badges313 bronze badges

Comments

Jens · Accepted Answer · 2010-11-23 14:52:54Z

0

You could make your recursion a little clearer (in my eyes) by writing

Box FindBoxBySize(Box box, BoxSize size)
{
    if (box.Size == size)
        return box;

    foreach (var child in box.Contents)
    {
        var foundBox = FindBoxBySize(child, size);
        if(foundBox != null)
            return foundBox;
    }

    return null;
}

As for LINQ: LINQ does not come with a good way to handle recursive data structures. Several different Extension methods to remedy that can be found by asking google for "LINQ recursion", but I am unsure if they add clarity in this case.

answered Nov 23, 2010 at 14:52

Jens

25.7k9 gold badges80 silver badges120 bronze badges

Collectives™ on Stack Overflow

LINQ and recursion

4 Answers 4

Comments

6 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

6 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related