C
C#•2w ago
HFrederick

How to filter for a specific object in a nested list and get the resulting object with parent items

I have a list of nested objects that looks like this: 
class Item
{
    List<Item> NestedItems;
    string Title;
}

List<Item> MyItems = new() { ... };
class Item
{
    List<Item> NestedItems;
    string Title;
}

List<Item> MyItems = new() { ... };
I know that I could find a specific nested object by value (ie get an Item with Title="some string") if I loop through the list and its nested items. I've written a recursive method extension that does this. But with such a method, I only get the specific child item: 
// Assuming this is a List<Item>...
Item 1
  Item 1-1
    Item 1-1-1
    Item 1-1-2
  Item 1-2
    Item 1-2-1
Item 2
  Item 2-1
  Item 2-2

MyItems.FindItemByString("Item 1-1-2"); 
// result: 
new Item() { Title: "Item 1-1-2" }
// Assuming this is a List<Item>...
Item 1
  Item 1-1
    Item 1-1-1
    Item 1-1-2
  Item 1-2
    Item 1-2-1
Item 2
  Item 2-1
  Item 2-2

MyItems.FindItemByString("Item 1-1-2"); 
// result: 
new Item() { Title: "Item 1-1-2" }
Is there a way I can also get the parent items as shown below? :ThonkAnime: Maybe I'm just missing out on some funky foreach algorithm or there's a linq method out there that does this already 
MyItems.FindItemByString("Item 1-1-2"); 
//result: 
new Item() 
{ 
  Title: "Item 1", 
  NestedItems: [
    new Item() 
    { 
      Title: "Item 1-1",
      NestedItems: [
         new Item() { Title: "Item 1-1-2" }
      ]
    }
  ]
}
MyItems.FindItemByString("Item 1-1-2"); 
//result: 
new Item() 
{ 
  Title: "Item 1", 
  NestedItems: [
    new Item() 
    { 
      Title: "Item 1-1",
      NestedItems: [
         new Item() { Title: "Item 1-1-2" }
      ]
    }
  ]
}
Trying to search this in google, the results just say to flatten the list with SelectMany, but that only works for a single level of nesting :xdd: Not even god knows which level of nesting I can expect to find my item at, so chaining selectmany's here is not possible.
6 Replies
canton7
canton7•2w ago
As you recurse, you can keep a stack of which parents you've recursed through Give me a min to throw together an example...
HFrederick
HFrederickOP•2w ago
Ah yes, this approach is what I'm looking for, though I'm worried how references are kept throughout each recursion loop :ThonkAnime: And mostly how to flag the parent objects that matched the child item :FeelsChromosomeMan:
canton7
canton7•2w ago
Here's a fairly simple (if perhaps slightly wasteful) way: https://lab.razor.fyi/#vVTBjtMwEBWCA0R7QHzBqCdHKpbg2k0lKALtqosqNRISVSW8ybQdNbUX29ndCuWIxGGv-3lcOfERyE5aktAse4E52Z6X954nMw5-HgXBRKulFhuemGffj3JDcgnTrbG4GQT1HR-pLMPEkpKGv0OJmpI7ECebTW7FeYYtzBsSS6mMpcR0Z_hIpfhKimxrqA0bk_zcOopXGkVKctl1zmNh1mYQBEkmjIHqxsGXAADAWGEpgUtFKZwJkiz0x2XSxaXQoJWyEIHEKzixuKkwTZyLmGyGEEHPoeBFr9_IvkdjMXUpAxHMGjkXB-gPy3TIPW8L3lf4HgbuNtJpqNNSh7V5N7ro_0_fL_-17_kfp0XjpMZYDIL9eqSkURnyD5osjkkiM1a7Hj9VJFmvD70-vCWZvt76OzHXuf3GvUI-RTen7BqiIVxzjwvDcOA1ilLqIj_PKNkNx5iMPXYUwwa3Jy0FShNgPdeBATJWJOtqgqZufbx_IaqtYx-yyoUL_wmf5GbFZk5kHtbKcLWiDIGVmFhvJ-qCqdx6rSTXGqUNu4bUYchZj3ZQPkFc17Vd0AKYg5UFgiiq3-4wswuNNtdyzxwrVzzW4q6qDFUslEaRrIB5-yvKUiDpPfJan_1NuVaw_b38xhHu_u9vBwe8VN5n810vFLs30xmoHsyqNWo9UfNYfrjvHt8Uvn6DoDh9qHP58cnjH19vvt0unj769OAX
HFrederick
HFrederickOP•2w ago
o7 this is massive help in the right direction, thanks
ティナ
ティナ•2w ago
normally you would have a dfs: 
void dfs(TreeNode* p, TreeNode*target){
    for(int i=0;i<p->children.size();++i){dfs(p->children[i],target)}
}
void dfs(TreeNode* p, TreeNode*target){
    for(int i=0;i<p->children.size();++i){dfs(p->children[i],target)}
}
then you will notice that there is an local variable i in the dfs, that means in your stack you capture the i 
struct StackLocalFrame{int i;TreeNode*p;}
struct StackLocalFrame{int i;TreeNode*p;}
so 
for(;true;){
   StackLocalFrame f=stack.top();
   if(++f.i>=p->children.size()) // always increment
   // check if p->children[i] is want you want
   // if yes then return,
   // else push a new StackLocalFrame with i=-1 an p=children to stack
}
for(;true;){
   StackLocalFrame f=stack.top();
   if(++f.i>=p->children.size()) // always increment
   // check if p->children[i] is want you want
   // if yes then return,
   // else push a new StackLocalFrame with i=-1 an p=children to stack
}
btw a much simpler way is to have an additional stack in dfs, push the parent when you enter and pop it before you leave
canton7
canton7•2w ago

Did you find this page helpful?