How to filter a recursive object?

Question

In my current project, a method I don't control sends me an object of this type:

public class SampleClass
{
    public SampleClass();

    public int ID { get; set; }
    public List<SampleClass> Items { get; set; }
    public string Name { get; set; }
    public SampleType Type { get; set; }
}

public enum SampleType
{
    type1,
    type2,
    type3
}

I display those data in a TreeView, but I would like to display only the path ending with SampleClass objects having their Type property set to type3, no matter the depth of this leaf.

I have absolutely no clue on how to do that, can someone help me ?

Thanks in advance !

Edit

To explain the problem I meet with the solutions proposed by Shahrooz Jefri and dasblinkenlight, here is a picture. The left column is the original data, without filtering, and the right one is the data filtered. Both methods provide the same result. In red is the problem.

enter image description here

What should happen if there is a type2 node on the path to a type3 lief? — Sergey Kalinichenko, Feb 08 '13 at 19:05
I must have the full path, so it would give something like `type1 > type2 > ... > type3` — Shimrod, Feb 08 '13 at 19:12

david.s · Answer 1 · 2013-02-08T20:58:16.210

2

Use this Filter method:

public void Filter(List<SampleClass> items)
{
    if (items != null)
    {
        List<SampleClass> itemsToRemove = new List<SampleClass>();

        foreach (SampleClass item in items)
        {
            Filter(item.Items);
            if (item.Items == null || item.Items.Count == 0)
                if (item.Type != SampleType.type3)
                    itemsToRemove.Add(item);
        }

        foreach (SampleClass item in itemsToRemove)
        {
            items.Remove(item);
        }
    }
}

edited Feb 08 '13 at 20:58

answered Feb 08 '13 at 19:55

david.s

11,283
6
50
82

I tried your method, and I've got the same problem as with the others. – Shimrod Feb 08 '13 at 20:03
@Shimrod What problem would that be? I've tested with multiple children and it only returns the paths which end in a leaf with `type3` exactly as you want. Can you post a sample where my code doesn't work? – david.s Feb 08 '13 at 20:12
Hi David. The problem is the one I described in the edit in my question. Not only the leaf with the type3 is returned, but also its parent's siblings. – Shimrod Feb 08 '13 at 20:28

score 1 · Answer 2 · answered Feb 08 '13 at 19:37

1

In addition to initially determining which items to show, if the datasize is substantial and you expect users to frequently collapse and expand sections then filtering after every click my result in slow ui response.

Consider the Decorator pattern or some other way of tagging each node with relevant info so that the filtering is not required after every click.

answered Feb 08 '13 at 19:37

Miserable Variable

28,432
15
72
133

This won't be the problem, the idea is to filter only once, the data don't change after the tree is displayed. And also there will not be that much data, it just needs to be displayed hierarchically, I have no power over that. – Shimrod Feb 08 '13 at 19:42
The data won't change but every time a user expands a node you will have to traverse it to filter. If the data size is not too large as you say then it may not be an issue – Miserable Variable Feb 08 '13 at 19:47

Sergey Kalinichenko · Accepted Answer · 2013-02-08T20:54:36.377

0

Try this approach:

static bool ShouldKeep(SampleClass item) {
    return (item.Type == SampleType.type3 && item.Items.Count == 0)
        || item.Items.Any(ShouldKeep);
}

static SampleClass Filter(SampleClass item) {
    if (!ShouldKeep(item)) return null;
    return new SampleClass {
        Id = item.Id
    ,   Name = item.Name
    ,   Type = item.Type
    ,   Items = item.Items.Where(ShouldKeep).Select(x=>Filter(x)).ToList()
    };
}

The above code assumes that Items of leaves are empty lists, rather than nulls.

edited Feb 08 '13 at 20:54

answered Feb 08 '13 at 19:12

Sergey Kalinichenko

714,442
84
1,110
1,523

I get the same problem as the answer above, http://stackoverflow.com/questions/14779487/how-to-filter-a-recursive-object#comment20692674_14779539 – Shimrod Feb 08 '13 at 19:19
@Shimrod I did not realize that by "path ending" you meant that `type3` must be at the end of the chain. Take a look at the edit. – Sergey Kalinichenko Feb 08 '13 at 19:22
The problem is still there, I guess it comes from the way the Items collection is rebuilt. I made an edit to my questionto explain it – Shimrod Feb 08 '13 at 19:32
@Shimrod OK, this should fix it. – Sergey Kalinichenko Feb 08 '13 at 19:55
@dasblinkenlight This code doesn't even compile and if you get it to compile it still doesn't work. Please fix it! – david.s Feb 08 '13 at 20:05
@david.s It looks like it has both compiled and worked for the OP. Did you spot a syntax error that I do not see? – Sergey Kalinichenko Feb 08 '13 at 20:08
@dasblinkenlight `return res = new SampleClass` should be `return new SampleClass` and another problem at `|| Items.Any(ShouldKeep);` – david.s Feb 08 '13 at 20:10
@david.s Thanks! I started with a `var res =`, and then converted to `return`. The [method group syntax](http://stackoverflow.com/q/886822/335858) for `Items.Any(ShouldKeep)` should compile, though. – Sergey Kalinichenko Feb 08 '13 at 20:14
@dasblinkenlight The error at `Items.Any(ShouldKeep)` is `An object reference is required for the non-static field, method, or property`. The method group syntax is ok. – david.s Feb 08 '13 at 20:34
Of course, I did some changes, as the name of the class was just a sample for the site, so I corrected those errors... – Shimrod Feb 08 '13 at 20:41
@dasblinkenlight , it's ` || item.Items.Any(ShouldKeep);` – Shimrod Feb 08 '13 at 20:42
1

@Shimrod This is now fixed. – Sergey Kalinichenko Feb 08 '13 at 21:18
@downvoter it's silly to downvote an essentially correct answer, wouldn't you agree? – Sergey Kalinichenko Feb 08 '13 at 21:18
@dasblinkenlight Your answer still doesn't work when the `Items` list is `null` and it's very inefficient (it checks the same items multiple times). So it's not silly to downvote it. – david.s Feb 08 '13 at 21:38
@david.s The assumption that `Items` is not `null` is stated explicitly in the answer. As far as the efficiency is concerned, premature optimization is responsible for the majority of bugs out there. Besides, with threes that are four to six levels deep, there's nothing to talk about. – Sergey Kalinichenko Feb 08 '13 at 21:44
@dasblinkenlight Yes, but my reasons for downvoting are still valid. Another such reason would be readability. – david.s Feb 08 '13 at 21:47
@david.s Readability? Now, c'mon: that's absurd! How "unreadable" could be a solution of essentially three statements? It's hard to get it to be much simpler that that. You certainly not talking about my formatting, right? – Sergey Kalinichenko Feb 08 '13 at 21:56
@david.s Generally, you downvote an accepted answer only if it is demonstrably factually wrong. All other cases are simply your disagreements with the author of the answer. – Sergey Kalinichenko Feb 08 '13 at 21:58
Well I fiund this solution to be easily readable, I don't know how you can pretend the opposite... Ok, my grand-ma will not be able to understand it... – Shimrod Feb 12 '13 at 16:24

How to filter a recursive object?

Edit

3 Answers3