Introduction
.NET contains several types of collections for storing elements - List, LinkedList, Dictionary, etc. A common question that comes up from many developers is, "Where is the Tree collection?" .NET doesn't include a Tree because there are too many variations to consider. However, I think we can create something that works for many hierarchical data structures.
This post is going to cover a lot of topics from generics to WPF to drag drop! You may see where I'm going with this already and you might have the correct assumption. WPF data binding is great for almost any collection - even a TreeView control is trivial to bind to. However, the trouble comes when you actually want to manipulate the data. TreeView doesn't even allow data binding to SelectedItem
. So begins the hours of googling and stringing together spaghetti code to get your TreeView control to manipulate your model.
Google no further. This is just about everything you'll need to get your TreeView drag and drop ready.
The Data Structure
Let's consider the desired behavior of a Tree data structure. Here are some obvious things we need to be able to do.
- Recursive tree nodes with children
- Nodes have a reference to parents
- Nodes are re-parented when moved to another node
Here are some less obvious things to consider.
- A node cannot be added to itself as a child
- A node cannot be added to any of it's descendants as a child
Let's jump right into the design. Here is the beginning of the SimpleTree class.
public class SimpleTree<T> where T : SimpleTree<T>
{
#region Member Variables
private readonly ObservableCollection<T> _children =
new ObservableCollection<T>();
#endregion
We use generics a little differently here. We place a constraint on T where T should be a SimpleTree. That means that our elements in our collection should extend SimpleTree. This is usually not a problem since we can create a ViewModel class for our view. Also notice that the children live in an ObservableCollection. We aren't beating around the bush here. We need good data binding support right off the bat.
#region Properties
private SimpleTree<T> _parent;
public SimpleTree<T> Parent
{
get { return _parent; }
private set { _parent = value; }
}
public ReadOnlyObservableCollection<T> Children
{
get { return new ReadOnlyObservableCollection<T>(_children); }
}
#endregion
We only have two properties Parent and Children. The setter on Parent is private and the Children are readonly. This is because we need to handle the adding and removing of the children explicitly. Now this is where some people might take a different design approach. You could create your own Collection that overrides ObservableCollection and manages the reparenting. This may be better in some cases since some WPF controls, like DataGrid, can instantiate a new ViewModel and add it to your collection for you.
Now let's take a look at our functions. This is where we handle all our Tree logic like reparenting and adding children. We also added some helper methods to find elements in a tree.
#region Functions
public T this[int i]
{
get { return _children[i]; }
}
public T AddChild(T node)
{
if (node == this)
{
throw new Exception("Cannot add self to children.");
}
if (this == node.Parent)
{
throw new Exception("Node already exists in children.");
}
T parent = (T)this.Parent;
while (parent != null)
{
if (parent == node)
{
throw new Exception("Node is an ancestor to this node.");
}
parent = (T)parent.Parent;
}
if (node.Parent != null)
{
node.Parent.RemoveChild(node);
}
node.Parent = this;
_children.Add(node);
return node;
}
public bool RemoveChild(T node)
{
if (_children.Remove(node))
{
node.Parent = null;
return true;
}
else
{
return false;
}
}
public void Traverse(Action<T> action)
{
action((T)this);
foreach (var c in _children)
{
c.Traverse(action);
}
}
public T Find(Predicate<T> predicate)
{
if (predicate((T)this))
{
return (T)this;
}
foreach (var c in _children)
{
var found = c.Find(predicate);
if (found != null)
{
return found;
}
}
return null;
}
public T Find(T tree)
{
if (tree == this)
{
return (T)this;
}
foreach (var c in _children)
{
var found = c.Find(tree);
if (found != null)
{
return found;
}
}
return null;
}
#endregion
Using
Using the simple tree is as simple as extending SimpleTree. Here is an example of the ubiquitous Person class, which is quite appropriate since people may have children.
public class Person : SimpleTree<Person>
{
public string Name { get; set; }
public override string ToString()
{
return Name;
}
}
WPF
Now, as I promised, let's discuss how we can make a Drag and Drop TreeView. I suppose this could be it's own blog post so I won't go into too much detail. I'll just post some code and touch on the main points.
Here is a TreeView in xaml showing how to bind our SimpleTree of Person's.
<TreeView x:Name="_tree"
ItemsSource="{Binding}"
AllowDrop="True"
MouseLeftButtonDown="OnBeginDrag"
Drop="OnDrop"
DragEnter="OnDragEnter"
MouseMove="OnDrag">
<TreeView.ItemTemplate>
<HierarchicalDataTemplate ItemsSource="{Binding Children}">
<TextBlock Text="{Binding Name}"/>
</HierarchicalDataTemplate>
</TreeView.ItemTemplate>
</TreeView>
You've probably noticed the Event handlers. Don't get scared! It's OK to have event handlers in WPF. The WPF police aren't going to get you. It does require the view to "know" about the ViewModel. This is where you could create an IPersonViewModel interface or something for extra credit. I've come to realize that at some point complex applications are coupled somewhere so refactor if you have to.
To begin dragging we need to capture the start point. Then when we start dragging we simple check if the left mouse button is down and that we aren't already dragging. Then we check to see if we've moved the minimum drag distance start the drag.
Point _startPoint;
bool _isDragging;
private void OnBeginDrag(object sender, MouseButtonEventArgs e)
{
_startPoint = e.GetPosition(_tree);
}
private void OnDrag(object sender, MouseEventArgs e)
{
if (e.LeftButton == MouseButtonState.Pressed && !_isDragging)
{
Point position = e.GetPosition(null);
if (Math.Abs(position.X - _startPoint.X) > SystemParameters.MinimumHorizontalDragDistance ||
Math.Abs(position.Y - _startPoint.Y) > SystemParameters.MinimumVerticalDragDistance)
{
StartDrag(e);
}
}
}
In the StartDrag method is where we start to get intimate with our ViewModel. Notice that it knows about the Person! At least WPF provides excellent support for this by getting the underlying object by calling SelectedItem.
private void StartDrag(MouseEventArgs e)
{
_isDragging = true;
Person person = <span style="font-size: 9pt;">e.Data.GetData(e.Data.GetFormats()[0])</span><span style="font-size: 9pt;"> as Person;</span>
if (person != null)
{
DragDropEffects de = DragDrop.DoDragDrop(_tree, person, DragDropEffects.Move);
}
_isDragging = false;
}
Here is the DragEnter method to set the effects. This also "helps" with making sure we are dealing with the correct data type.
private void OnDragEnter(object sender, DragEventArgs e)
{
var person = e.Data.GetData(e.Data.GetFormats()[0]) as Person;
if (person == null)
{
e.Effects = DragDropEffects.None;
}
}
The DROP! This is where the magic starts to happen. We already have a reference to the dragged object, but we need to get a reference to the target object. Once we have the target, we can call AddChild. Again, it feels like we know a little too much about the ViewModel, but it's OK!
private void OnDrop(object sender, DragEventArgs e)
{
var person = e.Data.GetData(e.Data.GetFormats()[0]) as Person;
if (person != null)
{
var target = GetItemAtLocation(e.GetPosition(_tree)) as Person;
if (target != null)
{
try
{
target.AddChild(person);
}
catch
{
}
}
}
}
We get the reference to the target object by using current location. This is also where we could check for Above or Below to allow reordering. But we are not doing that here.
private Person GetItemAtLocation
{
Person foundItem = default(Person);
HitTestResult hitTestResults = VisualTreeHelper.HitTest(_tree, location);
if (hitTestResults.VisualHit is FrameworkElement)
{
object dataObject = (hitTestResults.VisualHit as
FrameworkElement).DataContext;
if (dataObject is Person)
{
foundItem = (Person)dataObject;
}
}
return foundItem;
}
Unit Testing
Just to prove that our SimpleTree works, let's add some unit testing.
public class TestPerson : SimpleTree<TestPerson>
{
public string Name { get; set; }
}
[TestClass]
public class SimpleTree_UnitTest
{
[TestMethod]
public void Can_Create_Tree()
{
TestPerson tree = new TestPerson(){ Name = "Root" };
Assert.IsNotNull(tree);
Assert.AreEqual(0, tree.Children.Count);
}
[TestMethod]
public void Can_Add_Children()
{
TestPerson tree = new TestPerson(){ Name = "Root" };
TestPerson child1 = tree.AddChild(new TestPerson(){ Name = "Child 1" });
TestPerson child2 = tree.AddChild(new TestPerson(){ Name = "child 2" });
Assert.IsNotNull(tree);
Assert.AreEqual(2, tree.Children.Count);
Assert.AreEqual(tree, child1.Parent);
Assert.AreEqual(tree, child2.Parent);
}
[TestMethod]
public void Can_Find_Child()
{
TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
TestPerson tree2 = new TestPerson(){ Name = "Root 2" };
TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "Child 1" });
TestPerson child2 = tree2.AddChild(new TestPerson(){ Name = "child 2" });
TestPerson found = tree1.Find(x => x.Name.Equals("Child 1"));
Assert.AreEqual(child1, found);
Assert.AreEqual(1, tree1.Children.Count);
Assert.AreEqual(1, tree2.Children.Count);
}
[TestMethod]
public void Can_Move_Child()
{
TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
TestPerson tree2 = new TestPerson(){ Name = "Root 2" };
TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
TestPerson child2 = tree2.AddChild(new TestPerson(){ Name = "child 2" });
tree2.AddChild(child1);
Assert.AreEqual(tree2, child1.Parent);
Assert.AreEqual(0, tree1.Children.Count);
Assert.AreEqual(2, tree2.Children.Count);
}
[TestMethod]
public void Can_Remove_Child()
{
TestPerson tree1 = new TestPerson(){ Name = "Root 1" };
TestPerson tree2 = new TestPerson(){ Name = "Root 2" };
TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
tree1.RemoveChild(child1);
Assert.AreEqual(null, child1.Parent);
Assert.AreEqual(0, tree1.Children.Count);
}
[TestMethod]
public void Can_Find_Node()
{
TestPerson tree1 = new TestPerson() { Name = "Root 1" };
TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
TestPerson child2 = tree1.AddChild(new TestPerson(){ Name = "child 2" });
TestPerson found = tree1.Find(child1);
Assert.AreEqual(found, child1);
Assert.AreEqual(tree1, found.Parent);
Assert.AreEqual(2, tree1.Children.Count);
}
[TestMethod]
public void Cannot_Add_Self()
{
TestPerson tree1 = new TestPerson() { Name = "Root 1" };
TestPerson child1 = tree1.AddChild(new TestPerson(){ Name = "child 1" });
try
{
tree1.AddChild(tree1);
Assert.Fail();
}
catch (AssertFailedException ex)
{
Assert.Fail("Should thrown an exception.");
}
catch (Exception ex)
{
}
Assert.AreEqual(1, tree1.Children.Count);
}
[TestMethod]
public void Cannot_Add_Self_Children()
{
TestPerson tree1 = new TestPerson() { Name = "Root 1" };
TestPerson child = tree1.AddChild(new TestPerson() { Name = "child" });
TestPerson grandchild = child.AddChild(new TestPerson() { Name = "grandchild" });
try
{
tree1.AddChild(child);
Assert.Fail();
}
catch (AssertFailedException ex)
{
Assert.Fail("Should thrown an exception.");
}
catch (Exception ex)
{
}
Assert.AreEqual(1, tree1.Children.Count);
}
[TestMethod]
public void Can_Promote_Child()
{
TestPerson tree1 = new TestPerson() { Name = "Root 1" };
TestPerson child = tree1.AddChild(new TestPerson() { Name = "child" });
TestPerson grandchild = child.AddChild(new TestPerson() { Name = "grandchild" });
try
{
tree1.AddChild(grandchild);
}
catch (Exception ex)
{
Assert.Fail("Should not have thrown an exception promoting child.");
}
Assert.AreEqual(2, tree1.Children.Count);
}
}