CODEWITHSUNDEEP
c#linqrecursion
John Ohara
John Ohara

Reputation: 2901

Traverse up a list using Linq

I have a class as follows:

public class SiloNode
{
    public string Key { get; private set; }
    public string ParentKey { get; private set; }
    public string Text { get; private set; }
    public string Url { get; private set; }
}

All nodes are contained in a list:

List<SiloNode> nodes = new List<SiloNode>();

As you can see, the class contains a ParentKey property, so it's possible to find the item's parent, grandparent etc, until the top of the list is hit.

At present, I need to traverse up 2 levels, and you can see from the code below, it's already looking quite clunky. Now I need to modify the code to traverse up 3 levels and I'm concerned it's getting messy.

Is there a cleaner way to achieve what I want?

    string GetStartGroup(string currentUrl)
    {
        string startGroup = null;

        var currentNode = Silos.Silo.SingleOrDefault(x => x.Url == currentUrl);

        if (currentNode != null)
        {
            var parentNode = Silos.Silo.SingleOrDefault(x => x.Key == currentNode.ParentKey);
            if (parentNode != null) startGroup = parentNode.ParentKey;
        }

        return startGroup;
    }

Upvotes: 1

Views: 218

Answers (4)

Derrick Moeller
Derrick Moeller

Reputation: 4960

You can do this with recursion.

string GetStartGroup(string currentUrl)
{
    var node = nodes.Single(x => x.Url == currentUrl);
    if (node.ParentKey == null)
        return node.Key;

    return GetStartGroup(nodes.Single(x => x.Key == node.ParentKey).Url);
}

Alternatively:

string GetStartGroup(string currentUrl)
{
    return GetStartNode(nodes.Single(x => x.Url == currentUrl)).Key;
}

SiloNode GetStartNode(SiloNode node)
{
    if (node.ParentKey == null)
        return node;

    return GetStartNode(nodes.Single(x => x.Key == node.ParentKey));
}

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

Repeatedly using SingleOrDefault on a list makes the algorithm rather slow: finding parents for n nodes requires an O(n2) time.

You should make a Dictionary<string,SiloNode> first, and then traverse up the hierarchy through the dictionary:

var lookup= nodes.ToDictionary(n => n.Key);
...
SiloNode FindParent(SiloNode node, int levelsUp, IDictionary<string,SiloNode> lookup) {
    while (node != null && levelsUp != 0) {
        if (node.ParentKey == null || !lookup.TryGetValue(node.ParentKey, out var parent)) {
            return node;
        }
        node = parent;
        levelsUp--;
    }
    return node;
}

This will look up a parent up to levelsUp levels up. If you are looking for the last possible parent, modify the code as follows:

SiloNode FindParent(SiloNode node, IDictionary<string,SiloNode> lookup) {
    while (true) {
        if (node?.ParentKey == null || !lookup.TryGetValue(node.ParentKey, out var parent)) {
            return node;
        }
        node = parent;
    }
}

or recursively

SiloNode FindParent(SiloNode node, IDictionary<string,SiloNode> lookup) {
    return node?.ParentKey != null && lookup.TryGetValue(node.ParentKey, out var parent)
         ? FindParent(parent, lookup)
         : node;
}

Upvotes: 1

X39
X39

Reputation: 827

just put it into a method:

public static Silo Up(Silo current, IEnumerable<Silo> collection)
{
    return collection.FirstOrDefault((it) => it.ParentKey == it.Key);
}

or as Extension method:

public static SiloExtensions
{
    public static Silo Up(this Silo current, IEnumerable<Silo> collection)
    {
        return collection.FirstOrDefault((it) => it.ParentKey == it.Key);
    }
}

so you can just do silo.Up()?.Up()

Please note that this is rather slow. Depending on what you actually do, you may want to introduce actual Parent-Object as a field or a wrapper object providing access to it.

Such a wrapper object might look like this:

public class SiloWrapper
{
    public Silo Wrapped { get; }
    public Silo Parent { get; }
    private SiloWrapper(Silo silo, Silo parent)
    {
        this.Wrapped = silo;
        this.Parent = parent;
    }
    public IEnumerable<SiloWrapper> Map(IEnumerable<Silo> silos)
    {
        var dict = silos.ToDictionary((s) => s.Key);
        foreach(var s in silos)
        {
            yield return new SiloWrapped(s, s.ParentKey == null ? null : dict[s.ParentKey]);
        }
    }
}

to then traverse up and down, you just would need to call SiloWrapped.Map(<methodToGetSiloCollection>) and have all wrapped silos ready for usage.

If GarbageCollection may be a concern, you also can use WeakReference<Silo> ParentWeak instead

Upvotes: 0

Lajos Arpad
Lajos Arpad

Reputation: 76717

You can change

if (parentNode != null) startGroup = parentNode.ParentKey;

to

if (parentNode != null) startGroup = GetStartGroup(currentNode.parentUrl /*or something similar*/);

However, it would be better to use an iterative loop. I do not know about your problem enough to give you a hint, but the pseudocode would look like this:

while (parentNode != null) {
    currentNode = currentNode.parentNode;
    parentNode = currentNode.parentNode;
}

You might need to call SingleOrDefault, but if you have a direct reference, you should use that instead.

Upvotes: 0

Related Questions