Unable to get my basic tree structure working

Question

Sometimes you get one of those days no matter how much you batter your head around a wall, even the simplest task alludes you (this is one of those days!).

So what I have is a list of categories

CategoryID, CategoryName, ParentID, Lineage
1           Root Category,  NULL,   /1/
2           Child Category, 1,      /1/2/
3           Grandchild,     2,      /1/2/3 
4           Second Root,    NULL,   /4/
5           Second Child    2,      /1/2/5/

I've created a class to hold this where it contains all the values above, plus

ICollection<Category> Children;

This should create the tree

Root Category 
`-- Child category
|   `-- Grandchild
`-- Second Child
Second Root

So I'm trying to add a new category to the tree given the Lineage and the element, I convert the lineage to a queue and throw it into this function.

public void AddToTree(ref Category parentCategory, Category newCategory, Queue<Guid>lineage)
    {

        Guid lastNode = lineage.Dequeue();

        if(lastNode == newCategory.CategoryId)
        {
            parentCategory.Children.Add(newCategory);
            return;
        }

        foreach (var category in parentCategory.Children)
        {
            if(category.CategoryId == lastNode)
            {
                this.AddToTree(ref category, newCategory, lineage);
            }
        }
    }

Now two problems I'm getting

The self referencing isn't too worrying (its designed to be recursive) but since the category in the foreach loop is a locally instantiated variable I can't make it by reference and use it as a pointer.
I'm sure there has to be an easier way than this!

Any pointers would be greatly received.

What's lineage? That's not a tree structure. The simplest tree structure you can get is:`class Node { public string Id {get;set;} public List Children {get;set;} }`. Then you don't need a AddToTree function, since you can do: `currentNode.Children.Add(newNode)` — edeboursetty, Aug 01 '12 at 12:02
Sorry, the data held on my data-source is lineage. The class itself (category) has no concept of linage, lineage is just a way to point to the correct node in the tree. — John Mitchell, Aug 01 '12 at 12:03
@JohnMitchell: Do you store the parent ID in your data source too? — Florian Greinacher, Aug 01 '12 at 12:06
Lineage contains integers, and CategoryID is an integer as well. Then how is that possible that `AddToTree` works with guids? — Andrei, Aug 01 '12 at 12:16
Sorry I was simplifying the data store slightly :) It really contains guids, but its far far easier to type integer values than guid values on a demonstration. — John Mitchell, Aug 01 '12 at 12:17
I'm trying to pass it by ref since I don't want to multiple copies to be made of the tree, although it appears small here it can grow to be a very large tree, so the less internal copying values I can make the better. — John Mitchell, Aug 01 '12 at 12:19
As Enigmativity pointed out, why are you passing by ref? You only need to use `ref` or `out` if you actually plan on setting `category` to a new object. For more info, see the note at the top of http://msdn.microsoft.com/en-us/library/14akc2c7.aspx — Jon Senchyna, Aug 01 '12 at 12:25
As far as making multiple copies, that only happens for value types. For reference types (i.e. classes), only the reference is copied to the parameter. See http://stackoverflow.com/questions/900903/c-sharp-ref-keyword-performance for a similar question. — Jon Senchyna, Aug 01 '12 at 12:34
You need to remove the `ref` - when passing reference types by `ref` you're asking for bugs in your code. :-) — Enigmativity, Aug 01 '12 at 22:05

Andrei · Accepted Answer · 2012-08-01T12:37:15.283

This code seems to be what you are looking for, but without any self references and recursions - it goes through the tree along the given lineage and in the end of the lineage inserts the given category. Several assumptions:

Tree is stored as a list of its roots

lineage is a string

void AddCategory(List<Category> roots, Category categoryToAdd, string lineage)
{
    List<Guid> categoryIdList = lineage.Split('/').Select(id => new Guid(id)).ToList();

    List<Category> currentNodes = roots;
    Category parentNode = null;

    foreach (Guid categoryId in categoryIdList)
    {
        parentNode = currentNodes.Where(category => category.CategoryId == categoryId).Single();
        currentNodes = parentNode.Children;
    }

    parentNode.Children.Add(categoryToAdd);
}

Thanks! I used this and changed a few items (basically to account for the fact lineage is self referencing) and supporting adding categories at a root element. — John Mitchell, Aug 01 '12 at 12:55

Les · Answer 2 · 2012-08-01T12:40:58.187

0

You dont appear to need the "ref" at all. You are not modifying the object reference, just its state.

EDIT: If you must use ref, then use a temporary variable, for example...

        foreach (var temp in parentCategory.Children)
        {
            Category category = temp;
            if (category.CategoryId == lastNode)
            {
                this.AddToTree(ref category, newCategory, lineage);
            }
        }

But even with this, the ref is about useless. AddToTree does not modify the reference value. It modifies the referenced objects state. Maybe you have more code involved that we need to see.

If your intent is to modify the child reference in the parent, you will have an issue with ICollection Children object. You cannot use "ref" on an element in the ICollection to in effect replace the reference. You would have to remove the child reference and add a new one.

edited Aug 01 '12 at 12:40

answered Aug 01 '12 at 12:15

Les

10,335
4
40
60

The problem with passing a by value though is two fold. One is that there's a lot of copying around of data (especially for a large tree). The second is that I'm just trying to modify the root parent node and add values to it, by doing a copy I'd need to return all the way back up the tree and replace the original copy. – John Mitchell Aug 01 '12 at 12:18
1

@JohnMitchell This is only true if `Category` was a `struct`. – Florian Greinacher Aug 01 '12 at 12:19
Let me re-phrase the comment :D If I removed the ref value how would I get the instance of the tree with the new "child" nodes? – John Mitchell Aug 01 '12 at 12:21
1

In C# variables of reference types (classes) are (by default) passed reference-by-value. So if you pass your root category to the method and from within the method alter the state of it the calling method will also see this new state. – Florian Greinacher Aug 01 '12 at 12:26
you can use a temp variable if you do not modify the enumerator, if you need to the child node, you will need to use a for loop, otherwise, see the EDIT – Les Aug 01 '12 at 12:26
@JohnMitchell to get the instance of the tree with the new "child" nodes?" you will need to pass that as a parameter as well. But then "foreach" will be a problem. Modifying the ICollection in a foreach would throw a run-time error. You can use an array, but adding would be less efficient. – Les Aug 01 '12 at 12:58
Sorry, its been a long morning :) my brain just wasn't working. Sorry for the stupid questions/comments :D – John Mitchell Aug 01 '12 at 12:59

Unable to get my basic tree structure working

2 Answers2