Trees and their uses

Question

I was getting sicker and sicker of using an ordinary collection to do a tree's work, so I built a tree. A requirement of the tree are that it needs to contain a key to sort the tree by, so I used a Dictionary<int, T> to store the items. Here is the Tree<T>:

public class Tree<T>
{
    public Tree<T> AddItem(int key, T value)
    {
        if (TreeItems.ContainsKey(key))
        {
            throw new ArgumentException("Tree already contains value at that location.");
        }

        TreeItems.Add(key, value);
        return this;
    }

    public Tree<T> AddDirectory(int key, T item, Tree<T> value)
    {
        this.AddItem(key, item);

        if (TreeMenus.ContainsKey(key))
        {
            throw new ArgumentException("Tree already contains directory at that location.");
        }
        TreeMenus.Add(key, value);
        return this;
    }

    public IEnumerable<T> GetChildren()
    {
        return TreeItems.OrderBy(k => k.Key).Select(v => v.Value);
    }

    public IEnumerable<Tree<T>> GetChildrenDirectories()
    {
        return TreeMenus.OrderBy(k => k.Key).Select(v => v.Value);
    }

    private Dictionary<int, Tree<T>> TreeMenus = new Dictionary<int, Tree<T>>();
    private Dictionary<int, T> TreeItems = new Dictionary<int, T>();
}

Now, I like that part good enough, the trouble is getting the values from higher up the tree. I am defining a tree like this in my MenuItemManager class:

public MenuItemManager()
{
    Fill();
}

private Tree<MenuItem> dataTree = new Tree<MenuItem>();
private void Fill()
{
    dataTree.AddDirectory(0, new MenuItem(string.Empty, typeof(Nullable), Menus.OneNote2013, AppVersion.OneNoteDesktop2013), new Tree<MenuItem>()

        .AddDirectory(0, new MenuItem(resourceFile.GetString("OneNote"), typeof(Tutorials.Desktop2013Data.Menus.OneNote), Menus.OneNote2013, AppVersion.OneNoteDesktop2013), new Tree<MenuItem>()
        )

        .AddDirectory(1, new MenuItem(resourceFile.GetString("File2013"), typeof(Tutorials.Desktop2013Data.Menus.FileTab), Menus.File2013, AppVersion.OneNoteDesktop2013), new Tree<MenuItem>()
        )

        .AddDirectory(2, new MenuItem(resourceFile.GetString("Home2013"), typeof(Tutorials.Desktop2013Data.Menus.HomeTab), Menus.Home2013, AppVersion.OneNoteDesktop2013), new Tree<MenuItem>()
            .AddItem(0, new MenuItem(resourceFile.GetString("ClipboardGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.ClipboardGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
            .AddItem(1, new MenuItem(resourceFile.GetString("BasicTextGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.BasicTextGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
            .AddItem(2, new MenuItem(resourceFile.GetString("StylesGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.StylesGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
            .AddItem(3, new MenuItem(resourceFile.GetString("TagsGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.TagsGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
            .AddItem(4, new MenuItem(resourceFile.GetString("EmailGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.EmailGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
            .AddItem(5, new MenuItem(resourceFile.GetString("MeetingsGroup2013"), typeof(Tutorials.Desktop2013Data.HomeTab.MeetingsGroup), Menus.Home2013, AppVersion.OneNoteDesktop2013))
        )
    );
}

The top node(s) are the nodes that separate the nodes by OneNote tutorial version. The next level of nodes are my menus, and the third level are my items. The reason I set the two top nodes as directories, not items, is because I am not fully done with those sections, but they are directories that will be filled with items later.

I have many of these nodes, but this is the deepest I am going to nest my values for UI reasons. So, I wrote these three methods to get the values of the tree, also hosted in MenuItemManager:

private IEnumerable<Tree<MenuItem>> GetMenus(AppVersion version)
{
    IEnumerable<Tree<MenuItem>> treeDirectories = dataTree.GetChildrenDirectories();
    IEnumerable<MenuItem> treeItems = dataTree.GetChildren();

    for (int i = 0; i < treeDirectories.Count(); i++)
    {
        if (treeItems.ElementAt(i).Version == version)
        {
             return treeDirectories.ElementAt(i).GetChildrenDirectories();
        }
    }
    return new List<Tree<MenuItem>>();
}

public IEnumerable<MenuItem> GetMenuItems(AppVersion version)
{
    IEnumerable<Tree<MenuItem>> treeDirectories = dataTree.GetChildrenDirectories();
    IEnumerable<MenuItem> treeItems = dataTree.GetChildren();

    for (int i = 0; i < treeDirectories.Count(); i++)
    {
        if (treeItems.ElementAt(i).Version == version)
        {
             return treeDirectories.ElementAt(i).GetChildren();
        }
    }
    return new List<MenuItem>();
}

public IEnumerable<MenuItem> GetMenuItems(AppVersion version, Menus menu)
{
    IEnumerable<Tree<MenuItem>> treeDirectories = GetMenus(version);
    IEnumerable<MenuItem> treeItems = GetMenuItems(version);

    for (int i = 0; i < treeItems.Count(); i++)
    {
        if (treeItems.ElementAt(i).Menu == menu)
        {
            if (i < treeDirectories.Count())
            {
                return treeDirectories.ElementAt(i).GetChildren().Reverse();
            }
            else
            {
                break;
            }
        }
    }
    return new List<MenuItem>();
}

GetMenus is private by design, as I only need to be able to access the MenuItems out of this class. This method gets the trees stored in the second level so I can get the items in the third level. GetMenuItems(AppVersion) returns the menus stored in the top node(s) based on which version of tutorial the user wants. GetMenuItems(Appversion, Menus) gets the MenuItems stored in the deepest levels of the tree based on which version the user is in and which menu they just opened. These methods are the part I do not like, partially because there is no easy way to search the tree for a value.

P.S.

I'm not sure if this is more of a tree or a file structure as I need it to be able to have multiple nodes at any level, with the true "root" being the variable holding it all together.

Answer 1

private Dictionary<int, T> TreeItems = new Dictionary<int, T>();

private fields are lowerCamelCase or _lowerCamelCase with the latter receiving my (and most others') preference.

---

public Tree<T> AddDirectory(int key, T item, Tree<T> value)
{
    this.AddItem(key, item);

    if (TreeMenus.ContainsKey(key))
    {
        throw new ArgumentException("Tree already contains directory at that location.");
    }
    TreeMenus.Add(key, value);
    return this;
}

Do you really want to insert the item when there might be argument exceptions possible? If you catch the exception, you will have a partially executed method; if you don't catch the exception your program will have crashed anyway.

---

What is the key exactly? It seems like it conveys an ordering position; name it as such.

---

Tutorials.Desktop2013Data.Menus.HomeTab

Do these all have to use a fully qualified name? It would read a lot easier if you'd drop all the unnecessary namespaces and used a using directive instead.

---

I already know the branches and items are part of the tree so I'd just name them directories and items.

---

for (int i = 0; i < treeDirectories.Count(); i++)
{
    if (treeItems.ElementAt(i).Version == version)
    {
         return treeDirectories.ElementAt(i).GetChildrenDirectories();
    }
}

This can be shortened to

return treeDirectories.SkipWhile((dir, index) => treeItems.ElementAt(index).Version != version).FirstOrDefault().GetChildrenDirectories();

Notice the use of FirstOrDefault(). This indicates that there might be multiple entries that satisfy your query criterium since that is how your for-loop will be interpreted. If you instead want to distinguish between multiple-but-one and one-and-one-only, consider using SingleOrDefault().

This same approach goes for GetMenuItems().

In retrospect I'm not so sure if I prefer this over a loop but at least you know about the option.

---

return new List<Tree<MenuItem>>();

Use return Enumerable.Empty<List<Tree<MenuItem>>>(); to properly convey your intent.

Answer 2

I'm not sure if this is more of a tree or a file structure as I need it to be able to have multiple nodes at any level, with the true "root" being the variable holding it all together.

What's the difference? Is there one? According to Wikipedia a tree is

a way of representing the hierarchical nature of a structure in a graphical form. It is named a "tree structure" because the classic representation resembles a tree, even though the chart is generally upside down compared to an actual tree, with the "root" at the top and the "leaves" at the bottom.

So, a file structure (at the level of abstraction that we tend to think of them on) is a tree structure.

Now, I think your tree implementation is really pretty good, except you've gotten the reason you built it and what it is all mixed up. You've botched the abstraction and that is why you're confused about it.

public Tree<T> AddDirectory(int key, T item, Tree<T> value)

You're not adding a directory here. You're adding a branch. A more appropriate name would be AddBranch or AddChild. Then, you've separated the concept of a file directory from that of a tree branch. The reason you built the data structure no longer taints the data structure itself.

You've a similar problem here.

public IEnumerable<Tree<T>> GetChildrenDirectories()

and here

private Dictionary<int, Tree<T>> TreeMenus = new Dictionary<int, Tree<T>>();

Trees don't have Directories and Menus.

---

Side Note: The methods you wrote to traverse and search the tree look like they could be cleaned up with some Linq.