X'mas tree implementation

Question

With the festive season mood and the new year coming, I thought I would make my first question this year, a tree implementation. Blame me because it doesn't have anything to do about Christmas.

public interface ITreeITem
{
    object Key { get;  }
    object ParentKey { get; set; }
}

public class Tree<T> : IEnumerable<T>
    where T: ITreeITem
{
    private readonly IDictionary<object, Tree<T>> _items = new Dictionary<object, Tree<T>>(7);
    public T Item { get; set; }
    public Tree()
    {
    }  

    public Tree(IEnumerable<T> values)
    {
        foreach (var value in values)
        {
            if (value.ParentKey == null)
            {
                AddAsSubTree(value);
            }
            else
            {
                Parent(value)?.AddAsSubTree(value);
            }
        }
    }

    public IEnumerable<Tree<T>> Children
    {
        get { return _items.Values; }
    }

    public Tree<T> Parent(T item)
    {
        if (item.ParentKey == null)
        {
            return this;
        }
        if(_items.Count == 0)
        {
            return null;
        }
        var child = _items.TryGetOrValue(item.ParentKey, null);
        if (child == null)
        {
            return _items.Values
                .Select(v => v.Parent(item))
                .FirstOrDefault(v => v != null);
        }
        else
        {
            return child;
        }
    }

    public Tree<T> Parent(T item, int level)
    {
        if (level == 1)
        {
            return this;
        }
        return ChildrenInLevel(level - 1)
            .FirstOrDefault(t => t._items.ContainsKey(item.ParentKey));
    } 

    protected Tree<T> AddAsSubTree(T item)
    {
        var tree = new Tree<T>
        {
            Item = item
        };
        _items.Add(item.Key, tree);
        return tree;
    }

    protected IEnumerable<T> AllChildren(Tree<T> root)
    {
        foreach (var item in root._items.Values)
        {
            yield return item.Item;
            foreach (var aux in AllChildren(item))
            {
                yield return aux;
            }
        }
    }

    protected IEnumerable<Tree<T>> ChildrenInLevel(int level)
    {
        var children = Children;
        while (--level > 0)
        {
            children = children.SelectMany(t => t._items.Values);
        }
        return children;
    }

    public Tree<T> Add(T item)
    {
        return Parent(item).AddAsSubTree(item);
    }

    public Tree<T> Add(T item, int level)
    {
        return Parent(item, level).AddAsSubTree(item);
    }

    public bool RemoveItemAndChildren(T item)
    {
        if (Parent(item)._items.Remove(item.Key))
        {
            item.ParentKey = null;
            return true;
        }
        return false;
    }

    public bool RemoveItemAndChildren(T item, int level)
    {
        if (Parent(item, level)._items.Remove(item.Key))
        {
            item.ParentKey = null;
            return true;
        }
        return false;
    }

    public class Family
    {
        public Family(Tree<T> tree, T item)
        {
            Parent = tree.Parent(item);
            Children = Parent._items[item.Key].Children;
        }

        public Family(Tree<T> tree, T item, int level)
        {
            Parent = tree.Parent(item, level);
            Children = Parent._items[item.Key].Children;
        }

        public Tree<T> Parent { get; set; }
        public IEnumerable<Tree<T>> Children { get; set; }

        public IEnumerable<T> Remove(T item)
        {
            Parent._items.Remove(item.Key);
            yield return item;
            foreach (var child in Children)
            {
                Parent._items.Add(child.Item.Key, child);
                child.Item.ParentKey = item.ParentKey;
                yield return child.Item;
            }
        } 
    }

    public IEnumerable<T> Remove(T item)
    {
        var family = new Family(this, item);
        return family.Remove(item).ToList();
    }

    public IEnumerable<T> Remove(T item, int level)
    {
        var family = new Family(this, item, level);
        return family.Remove(item).ToList();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return AllChildren(this).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

I also tested it a bit so you can also run the tests and fiddle with it.

public class Model : ITreeITem
{
    public int ID { get; set; }
    public int? ParentID { get; set; }
    public string Text { get; set; }
    public object Key
    {
        get { return ID; }
    }

    public object ParentKey
    {
        get { return ParentID; }
        set { ParentID = (int?)value; }
    }
}

public class TestTree
{
    private Tree<Model> _tree;
    private List<Model> _list; 

    [SetUp]
    public void Init()
    {
        _list = new List<Model>(8)
        {
            new Model() {ID = 1, Text = "Item 1"},
            new Model() {ID = 2, Text = "Item 2"},
            new Model() {ID = 3, Text = "Item 1.1", ParentID = 1},
            new Model() {ID = 4, Text = "Item 1.2", ParentID = 1},
            new Model() {ID = 7, Text = "Item 1.2.1", ParentID = 4},
            new Model() {ID = 5, Text = "Item 2.1", ParentID = 2},
            new Model() {ID = 6, Text = "Item 1.2.2", ParentID = 4},
            new Model() {ID = 8, Text = "Item 1.2.1.1", ParentID = 7}
        };
        _tree = new Tree<Model>(_list);
    }

    [Test]
    public void AsSameCount()
    {
        Assert.AreEqual(_list.Count, _tree.Count());
    }

    [Test]
    public void HasParentElements()
    {
        var parents = _tree.Children;
        Assert.AreEqual(2, parents.Count());
        Assert.AreEqual(3, parents.Sum(p => p.Item.ID));
    }

    [Test]
    public void HasChildren()
    {
        var children = _tree.Children.SelectMany(t => t.Children);
        Assert.AreEqual(3, children.Count());
        Assert.AreEqual(12, children.Sum(p => p.Item.ID));

        children = children.SelectMany(t => t.Children);
        Assert.AreEqual(2, children.Count());
        Assert.AreEqual(13, children.Sum(p => p.Item.ID));
    }

    [Test]
    public void TestAdd()
    {
        _tree = new Tree<Model>();
        foreach (var item in _list)
        {
            _tree.Add(item);
        }
        AsSameCount();
        HasParentElements();
        HasChildren();
    }

    [Test]
    public void TestRemoveAll()
    {
        foreach (var item in _list)
        {
            _tree.Remove(item);
        }
        Assert.AreEqual(0, _tree.Count());
    }

    [Test]
    public void TestRemoveLast()
    {
        var last = _list.Last();
        var removed = _tree.Remove(last);
        Assert.AreEqual(1, removed.Count());
        Assert.AreSame(removed.FirstOrDefault(), last);
    }

    [Test]
    public void TestRemoveItemAndChildren()
    {
        var item = _list[3];
        Assert.IsTrue(_tree.RemoveItemAndChildren(item));
        Assert.AreEqual(_list.Count - 4, _tree.Count());
    }
}

Aprreciate any criticism you might have about this implementation.

Answer 1

1. The Tree constructor silently discards items where the parent can't be found. This is usually a bad idea since it means the caller has no real idea why items are missing and why the created tree is incomplete (from the callers point of view) - debugging ensues and wastes some time. If you throw an ArgumentException instead stating the the parent can't be found - it's immediately clear what's wrong.

2. This is probably a bug: If you call Parent on an empty tree passing in an item with ParentKey == null then you will get the current tree as the parent even though the tree contains no items at all (the first two if blocks should probably be swapped around).

3. In Parent the the local variable is called child even through you're looking for the parent.

4. In generally if I call a data structure to remove an item the I do expect the data structure to be modified (i.e. the item removed) if the call is valid but not the item to be changed. RemoveItemAndChildren changes the passed in item which violates that expectation which is probably not a good thing.

5. The code in the Remove methods will throw a NullReferenceException when being passed in an invalid item since Parent may return null. It would be better to detect this and ignore the Remove call (the general expectation usually is that Remove just does nothing if being called with an item which is not in the structure).

6. Documentation for the public interface of the Tree class is missing (see point 2 above plus your comment - documentation would have made clear what the exact purpose of the method was)

Answer 2

The familyclass isn't that useful, actually it may confuse the logic a little bit because now we don't know in which class where to place the methods. Should we always use the familyclass to support every method and make every tree method just simply instantiate a family object and call the respective method, this sounds silly, but with my approach this would be what the implementation would degenerate to. That said the familyclass is easly replaced with a auxiliary method.

private bool RemoveItemAndChildren(Tree<T> parent, T item)
{
    if (parent._items.Remove(item.Key))
    {
        item.ParentKey = null;
        return true;
    }
    return false;
}

public bool RemoveItemAndChildren(T item)
{
    return RemoveItemAndChildren(Parent(item), item);
}

public bool RemoveItemAndChildren(T item, int level)
{
    return RemoveItemAndChildren(Parent(item, level), item);
}

And with this the family class is no longer needed. I should also have applied the same logic into the remove method, because there is some duplicated code there.

private IEnumerable<T> Remove(Tree<T> parent, T item)
{
    var children = parent._items[item.Key].Children;
    parent._items.Remove(item.Key);
    item.ParentKey = null;
    yield return item;
    foreach (var child in children)
    {
        parent._items.Add(child.Item.Key, child);
        child.Item.ParentKey = item.ParentKey;
        yield return child.Item;
    }
} 

public IEnumerable<T> Remove(T item)
{
    return Remove(Parent(item), item).ToList();
}

public IEnumerable<T> Remove(T item, int level)
{
    return Remove(Parent(item, level), item).ToList();
}

Comming back to my tree once again, because I am needing it once again. I can see space for two further improvements.

In order to Address the point 4 provided by @ChrisWue I thought of having a bool AutoUpdateParentKeyOnRemove property, so users could specify the desired behaviour. I still agree though that the best option would be to not update object parameter state at all.

When I implemented the methods that receive a int level on them I did so with performance in mind (although I never compared them with the versions without the parameter). Looking back at it I guess I could support them on a derived implementation of tree, so I don't pollute the public API with methods that can be rarely used. I guess the common use case should be to just to retrieve an item while not knowing which level of the tree.