Keep track of parents in recursive call

Question

I am trying to keep track of parents in a recursive call, and flag the correct occurrence of parent-child relationships.

There are 4 classes (don't mind the names, this is dummycode for an example):

1. Root
2. ChildBlock
3. ChildFinally
4. ChildDisposable

All 3 childclasses inherit from one abstract class: Child.

Root is obviously the top-class that holds all children, Root does not have a parent. But, in some way, neither do the other classes. Root has children, and each of the children has children; but NOT visa-versa. ChildBlock (and all others) does not have a parent stored, only a list of children. See code:

internal abstract class Child
{
    public string name;
    public List<Child> children;

    public Child()
    {
        name = "Child";
        children = new List<Child>();
    }       

    public virtual void AddChild(Child child)
    {
        children.Add(child);
    }
}

internal class ChildFinally : Child
{
    public ChildFinally(string level)
    {
        name = level + ": ChildFinally";
        children = new List<Child>();
    }
}

Say you have a Root(level 1) with one child: ChildBlock(level 2). ChildBlock, on it's own has two children: ChildFinally(level 3) and ChildBlock(level 3). Both ChildFinally(level 3) and ChildBlock(level 3) have one child: ChildDisposable(level 4).

So in a hierarchical way (I colored them to show the levels more accurately):

What I am trying to achieve is this: I want to know if ChildDisposable(level 4) has a parent, in any level above him, which is of type ChildFinally.

The problem here, is that ChildDisposable is not aware of it's parent(s), but the parent is aware of his children (through a list of children).

Right now I am looping through each list of children in a recursive call:

private static void DisplayChildren(Child child)
{
    foreach (Child c in child.children)
    {
        Console.WriteLine(c.name);
        DisplayChildren(c);
    }
}

This recursive call has to stay that way. Also, I can not let the children be aware of their parent(s).

Is there any way for me to track if a child of type ChildDisposable has a parent (in any level) of type ChildFinally?

Edit: I can supply the full (reproduceable) dummycode if required.

Answer 1

How about this:

internal abstract class Child
{
    public string name;
    public List<Child> children;

    public Child Parent {get;set;}

    public Child()
    {
        name = "Child";
        children = new List<Child>();
    }       

    public virtual void AddChild(Child child)
    {
        children.Add(child);
        child.Parent = this;
    }
}

public static class ChildHelpers
{
    public static Child[] GetAncestors(this Child self)
    {
        var path = new List<Child>();
        var current = self;
        while (current.Parent != null)
        {
            path.Add(current.Parent);
            current = current.Parent;
        }
        return path.ToArray(); // maybe reverse first...
    }
}

This would add a reference to a parent to each child of course...

Alternatively you have to pass a "parent locating service" to a child when creating/being added as a child that can determine your parent maybe by traversing the tree top-down until it finds the child and note the ancestors during the traverse. This may be costly if the tree is deep and you have to do this several times...

If the structure is somehow globally accessible and static (not preferable!) you can do without by simple calling a static "parent locating service".

If you don't want to modify the Childs you can also build up wrappers for each, that contains the parent reference and passes it down to own children:

internal class ChildHolder
{
    public Child TheChild {get; private set;} // get the payload child
    public ChildHolder Parent {get;set;} // store information about parent

    public ChildHolder(Child child)
    {        
       TheChild = child;
    }

    public virtual void AddChild(ChildHolder childHolder)
    {
        TheChild.Add(childHolder.TheChild); // store children in original child object
        childHolder.Parent = this; // and pass my parent information to childs holder
    }

}

Answer 2

I was thinking a dictionary

var parents = new Dictionary<Child, Child>();

void SetParent(Child parent)
{
    foreach (Child c in parent.children)
    {
       parents[c] = parent;
       SetParent(c);
    }
}

You just have to call this once with SetParent(root)

Answer 3

It's hard to tell based on what we know but I think I can guess a bit.

Anyway if I'm right you will walk your tree in some way so my suggestion would be to remember some kind of path information while you walk your tree (should be trivial - it's just another argument to your walker) - there you can easily store things like the last ChildFinally

That would be for your example:

private static void DisplayChildren(Child child)
{
    DisplayChildren(child, new []{child});
}

private static void DisplayChildren(Child child, Child[] path)
{
    foreach (Child c in child.children)
    {
        Console.WriteLine(c.name);
        var newPath = new List<Child>(path);
        newPath.Add(c);
        DisplayChildren(c, newPath.ToArray());
    }
}

of course I don't know what really need so this example gives you just the path to the current child (including it) - it should be easy to find what you need:

static bool HasFinalParent(Child[] path)
{
   return path.Any(c => c is ChildFinally);
}

or easier (only remember the parent if any):

private static void DisplayChildren(Child child)
{
    DisplayChildren(child, null);
}

private static void DisplayChildren(Child child, ChildFinally lastFinalParent)
{
    if (child is ChildFinally)
       lastFinalParent = (ChildFinally)child;

    foreach (Child c in child.children)
    {
        Console.WriteLine(c.name);
        DisplayChildren(c, lastFinalParent);
    }
}