CODEWITHSUNDEEP
linqrecursion
petko_stankoski
petko_stankoski

Reputation: 10723

Linq query recursion

I work in C# and Entity framework. I have a table in my database named Genre. Here are its attributes: idGenre, name, idParentGenre.

For example. the values would be:

(idGenre = 1, name = "acoustic", idParentGenre=2)

(idGenre = 2, name = "rock", idParentGenre=2)

(idGenre = 3, name = "country", idParentGenre=4)

(idGenre = 4, name = "folk", idParentGenre=5)

(idGenre = 5, name = "someOtherGenre", idParentGenre=5)

As you can see, it's kind of a tree.

Now, I have a method for searching through this table. The input parameter is idGenre and idParentGenre. I should return if the genre (idGenre) is a son/grandchild/grandgrandchild/... of idParentGenre.

For example, I get idGenre=3, idParentGenre=5, I should return true.

However, there isn't recursion in Linq. Is there a way I can do this?

Upvotes: 3

Views: 7975

Answers (3)

Reed Copsey
Reed Copsey

Reputation: 564851

I would make a method to handle this instead of using LINQ:

bool HasParent(int genre, int parent)
{
    Genre item = db.Genres.FirstOrDefault(g => g.IdGenre == genre);
    if (item == null)
        return false;

    // If there is no parent, return false, 
    // this is assuming it's defined as int?
    if (!item.idParentGenre.HasValue)
        return false;

    if (item.idParentGenre.Value == parent)
        return true;

    return HasParent(item.idParentGenre, parent);
}

This lets you handle this in a single recursive function.

Upvotes: 4

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727027

Bring the table of genres in the memory (it cannot be that big), and recursively traverse it to create a mapping between an idGenre and a transitive closure of its descendents, like this:

1: {1, 2}
2: {2}
3: {3, 4, 5}
4: {4, 5}
5: {5}

The data above stays only in memory. You recompute it every time on start-up, and on updates to the genres table.

When it is time to query for all songs in a specific genre, use the pre-calculated table in an idGenre in ... query, like this:

IEnumerable<Song> SongsWithGenreId(int idGenre) {
    var idClosure = idToIdClosure[idGenre];
    return context.Songs.Where(song => idClosure.Contains(song.idGenre));
}

Upvotes: 1

Jesse Smith
Jesse Smith

Reputation: 963

It looks like you're trying to implement a tree without using a tree.

Have you considered...using a tree? Here's a great question and some answers you could build off (including one with code:

delegate void TreeVisitor<T>(T nodeData);

class NTree<T>
{
    T data;
    LinkedList<NTree<T>> children;

    public NTree(T data)
    {
        this.data = data;
        children = new LinkedList<NTree<T>>();
    }

    public void addChild(T data)
    {
        children.AddFirst(new NTree<T>(data));
    }

    public NTree<T> getChild(int i)
    {
        foreach (NTree<T> n in children)
            if (--i == 0) return n;
        return null;
    }

    public void traverse(NTree<T> node, TreeVisitor<T> visitor)
    {
        visitor(node.data);
        foreach (NTree<T> kid in node.children)
            traverse(kid, visitor);
    }        
}

Upvotes: 2

Related Questions