Introduction
We are investigating advanced WPF tree view implementations. The 1st and 2nd part of this series compared virtualized and non-virtualized implementations, and the third was focused on traversing tree structures.
 | A general understanding of tree traversal was required to implement the efficient tree view filter application in the 3rd [3] article. But this is also required to save and load data from and to a WPF tree view. And while the last article [3] briefly touched the subject of saving and loading data, I felt some need to detail this with an article of its own. this article also covers storing and retrieving tree view based data in a relational database system (here SQLite), as it is not trivial, but often required, and not well documented elsewhere. |
The article is structured around 2 demo applications, where the first SQLite Demo application is focused on storing tree structured data in a relational database backend system. This part of the article should also be interesting for anyone wishing to store and retrieve tree structured data from non-WPF technologies, such as, Winform based TreeViews, Java Tree Structures etc.) in a relational database system.
The second part of the article combines the basics learned from the SQLite Demo and revisits the WPF 00_InplaceEditBoxLib.zip demo from the first article to integrate a save/load backend data system.
A solution to the task of storing and retrieving tree based data in a relational database system is not trivial, because relational data is constrained to tables, while tree structures can come in manner different forms and shapes. A solution to this problem is the Adjacency List Model [5], which requires us to store tree nodes in dependence of their level within the tree. This solution is not difficult (anymore) since we can use the Level-Order traversal [3] algorithm to visit and store nodes with respect to their level.
Then when we have stored tree nodes with their level - we can retrieve them ordered by their level - rebuilding the tree from its root to its leaves. Retrieving nodes from a database table requires us to store their:
- Level (0, 1, 2, 3, ... n) and
- A link to the parent node (id to parent of current node)
So, 1. is required to rebuild the tree in order from root to leaf, while 2. is required to insert each item retrieved from the database in its correct spot. Lets explore that idea with the SQLite_Demo attached to this article. This demo implements 2 projects:
- SolutionModelsLib (DLL project)
- SQLite_Demo (MS-DOS Console project)
The SolutionModelsLib implements a simplified tree structured model using 3 classes:
where the SolutionModel represents the container of the tree model, while the SolutionRootItemModel is the first visible item in the collection, and the SolutionItemModel implements all other items that can be visible in the tree structure (File, Folder, Project).
The second part of the SolutionModelsLib project contains the SQLIteDatabase class [4] that wraps the SQLite database system, and the SolutionDB class that implements the specific storage and retrieval methods for this demo.
The Write database model region in the SolutionDB class contains a ReCreateDBTables method that creates the empty tables: itemtype and solution. The itemtype table is used to store the enumeration from the SolutionItemType enum, while the solution table contains the adjacency list (the data of the tree) of the solution.
CREATE TABLE IF NOT EXISTS
[itemtype] (
[id] INTEGER NOT NULL PRIMARY KEY,
[name] VARCHAR(256) NOT NULL
)
CREATE TABLE IF NOT EXISTS
[solution] (
[id] INTEGER NOT NULL PRIMARY KEY,
[parent] INTEGER NOT NULL,
[level] INTEGER NOT NULL,
[name] VARCHAR(256) NOT NULL,
[itemtypeid] INTEGER NOT NULL,
FOREIGN KEY (itemtypeid) REFERENCES itemtype(id)
)
The InsertItemTypeEnumeration method writes the itemtype enumeration values into its table and the InsertSolutionData method persists the tree structured data:
private int WriteToFile(SolutionModel solutionRoot
, SQLiteCommand cmd)
{
int result = 0;
int iKey = 0;
Queue<Tuple<int, SolutionItemModel>> queue = new Queue<Tuple<int, SolutionItemModel>>();
if (solutionRoot.Root != null)
queue.Enqueue(new Tuple<int, SolutionItemModel>(0, solutionRoot.Root));
while (queue.Count() > 0)
{
var queueItem = queue.Dequeue();
int iLevel = queueItem.Item1;
SolutionItemModel current = queueItem.Item2;
current.Id = iKey++;
int parentId = (current.Parent == null ? -1 : current.Parent.Id);
cmd.Parameters.AddWithValue("@id", current.Id);
cmd.Parameters.AddWithValue("@parent", parentId);
cmd.Parameters.AddWithValue("@level", iLevel);
cmd.Parameters.AddWithValue("@name", current.DisplayName);
cmd.Parameters.AddWithValue("@itemtypeid", (int)(current.ItemType));
result += cmd.ExecuteNonQuery();
foreach (var item in current.Children)
queue.Enqueue(new Tuple<int, SolutionItemModel>(iLevel + 1, item));
}
return result;
}
Private Function WriteToFile(ByVal solutionRoot As SolutionModel, ByVal cmd As SQLiteCommand) As Integer
Dim result As Integer = 0
Dim iKey As Integer = 0
Dim queue As Queue(Of Tuple(Of Integer, SolutionItemModel)) = New Queue(Of Tuple(Of Integer, SolutionItemModel))()
If solutionRoot.Root IsNot Nothing Then queue.Enqueue(New Tuple(Of Integer, SolutionItemModel)(0, solutionRoot.Root))
While queue.Count() > 0
Dim queueItem = queue.Dequeue()
Dim iLevel As Integer = queueItem.Item1
Dim current As SolutionItemModel = queueItem.Item2
current.Id = iKey
iKey = iKey + 1
Dim parentId As Integer = (If(current.Parent Is Nothing, -1, current.Parent.Id))
If cmd IsNot Nothing Then
cmd.Parameters.AddWithValue("@id", current.Id)
cmd.Parameters.AddWithValue("@parent", parentId)
cmd.Parameters.AddWithValue("@level", iLevel)
cmd.Parameters.AddWithValue("@name", current.DisplayName)
cmd.Parameters.AddWithValue("@itemtypeid", CInt((current.ItemType)))
result += cmd.ExecuteNonQuery()
Else
Console.WriteLine(String.Format("{0,4} - {1} ({2})", iLevel, current.GetStackPath(), current.ItemType.ToString()))
End If
For Each item In current.Children
queue.Enqueue(New Tuple(Of Integer, SolutionItemModel)(iLevel + 1, item))
Next
End While
Return result
End Function
We recognize this code pattern from the previous article and know that the code implements the Level-Order traversal algorithm, -and only the bold marked parts operate on each traversed tree node (storing tree node data in the SQLite table is the operation here).
We can see that the iKey table Id is computed on the fly and the iLevel information falls practically out of the algorithm.
So, this is, how we can store tree structured data in a relational table structure. Let's now switch gears and see how loading this data can work.
Retrieving the data stored in the previous section to re-build the tree on load is surprisingly easy since we've done all the heavy lifting when writing the data. All we really need is a select statement to get the tree data from the solution table:
SELECT * FROM solution ORDER BY level, id
The important part here is the ORDER BY level - this makes sure that we retrieve the tree nodes from top to bottom as we have written them. The Order BY id part is not really required but I like to have things in order when I can.
So, the above statement gives us an id of each tree view node, the id of it's parent, the level of the node, and some application dependent data like name and type of the node. Now, we can retrieve these nodes from top to bottom and we can insert each node in its correct spot (underneath its parent) if we keep a log of the previously retrieved nodes and their ids. This idea is implemented in the ReadSolutionData method of the SolutionDB class.
And while the code in the ReadSolutionData method may seem long its actually less complicated than any of the traversal methods we have seen previously. The first part of the algorithm inserts the root item if the query has any results at all - we can do it like this since the root is expected to be first (it was written first) and this tree view implementation allows only one root item (so all other items are non-root items by definition).
public int ReadSolutionData(SolutionModel solutionRoot
, SQLiteDatabase db = null)
{
int recordCount = 0;
var query = "SELECT * FROM solution ORDER BY level, id";
using (SQLiteCommand cmd = new SQLiteCommand(query, db.Connection))
{
using (SQLiteDataReader selectResult = cmd.ExecuteReader())
{
Dictionary<int, SolutionItemModel> mapKeyToItem = new Dictionary<int, SolutionItemModel>();
if (selectResult.HasRows == true)
{
if (selectResult.Read() == true)
{
var root = solutionRoot.AddSolutionRootItem(selectResult["name"].ToString());
mapKeyToItem.Add(selectResult.GetInt32(0), root);
recordCount++;
}
while (selectResult.Read() == true)
{
int iParentKey = selectResult.GetInt32(1);
SolutionItemModel parent = null;
if (mapKeyToItem.TryGetValue(iParentKey, out parent) == true)
{
var itemTypeId = (long)selectResult["itemtypeid"];
var item = parent.AddChild(parent
, selectResult["name"].ToString()
, itemTypeId);
mapKeyToItem.Add(selectResult.GetInt32(0), item);
recordCount++;
}
else
{
throw new Exception("Data written is corrupted.");
}
}
}
}
}
return recordCount;
}
Public Function ReadSolutionData(ByVal solutionRoot As SolutionModel, ByVal Optional db As SQLiteDatabase = Nothing) As Integer
If db Is Nothing Then db = Me
Dim recordCount As Integer = 0
Dim query = "SELECT * FROM solution ORDER BY level, id"
Using cmd As SQLiteCommand = New SQLiteCommand(query, db.Connection)
Using selectResult As SQLiteDataReader = cmd.ExecuteReader()
Dim mapKeyToItem As Dictionary(Of Integer, SolutionItemModel) = New Dictionary(Of Integer, SolutionItemModel)()
If selectResult.HasRows = True Then
If selectResult.Read() = True Then
Dim root = solutionRoot.AddSolutionRootItem(selectResult("name").ToString())
mapKeyToItem.Add(selectResult.GetInt32(0), root)
recordCount += 1
End If
While selectResult.Read() = True
Dim iParentKey As Integer = selectResult.GetInt32(1)
Dim parent As SolutionItemModel = Nothing
If mapKeyToItem.TryGetValue(iParentKey, parent) = True Then
Dim itemTypeId = CLng(selectResult("itemtypeid"))
Dim item = parent.AddChild(parent, selectResult("name").ToString(), itemTypeId)
mapKeyToItem.Add(selectResult.GetInt32(0), item)
recordCount += 1
Else
Throw New Exception("Data written is corrupted.")
End If
End While
End If
End Using
End Using
Return recordCount
End Function
The 2nd mapKeyToItem.Add(...) statement in the above code can be optimized further if we recognize that we need to store only objects that can actually have Children themselves (Folder, Project, RootItem), while File objects cannot have children and, therefore, require no storage for later lookup in the dictionary.
The flat file database system was covered in a recent article [4]. The article developed a SQLite database wrapper class called SQLiteDatabase - this class is reused here and extended with custom functorialities.
We are now able to run the attached SQLite_Demo understanding the concept - be sure to set some breackpoints with the debugger, if something is in doubt or use the forum below the article to ask questions...
So, the concept does work with a simple Console application, but how do we do this with WPF? Should we have the database class consume the data and spit out ViewModel items or is there a better way for this?
The attached WPF demo sample application is a further development of the 00_InplaceEditBoxLib.zip project attached to the 1st article. The application is now multi-threaded and virtualized. There are also some editing functions that can be used to edit, add, or remove items as the user wishes:
The Context-Menu in the above window is implemented in the TreeItemContentPresenter of the MainWIndow.xaml in the InPlaceEditBoxDemo project. Most of these commands bind directly to an object of the:
SolutionLib.ViewModels.Browser.SolutionViewModel
class, which is the root ViewModel of the solution tree view (ViewModel part).
All ViewModel classes that represent an item (node) in the tree view are either used on the ItemViewModel class or the ItemChildrenViewModel class. This design turned out to be adventegious, because we can clearly distinguish between items that can have items below themselves (Project, Folder, RootItem) and other items that cannot have children (Files).
The Save and Load commands are not implemented in the SolutionViewModel class. Why? Because it turns out that it does make sense to convert a viewmodel representation into a model representation before saving it. There are various arguments for doing so, the most important ones are:
- The view and the viewmodel should not directly depend on the underlying data layer - this means we should be able to exchange different storage technologies (eg.: XML, relational database etc) without having to re-write the entire application
- A viewmodel usually contains items that are useful when the UI is alive, such as, the currently selected node. Most of this UI and state relevant data is not required for persistence.
Now, we could argue that it could be required to know what the last selected item was in order to re-establish that state on re-load of the tree view. And thats a valid point - but if we consider to re-establish the state of a tree view after reloading its data we should do so based on 2 files (one configuration file for the tree structured data and one session file for its last states) rather than writing everything in one file.
This seperation of configuration and state is a good practice, because users may wish to store the settings file in GitHUB (or elsewhere), while the last session may not always be that interesting for everyone else...
So, these are only 2 important points that lead us to the conclusion that a viewmodel should almost always be converted into a model before being stored - and the retrieval will then require us to retrieve the model, convert it into a viewmodel to display it's data in the bound view.
The SaveSolutionCommand and the LoadSolutionCommand are implemented in the AppViewModel class of the InPlaceEditBoxDemo project. Both commands accepts an ISolution object as parameter and call a method in turn. Here is the method called by the SaveSolutionCommand:
private async Task SaveSolutionCommand_ExecutedAsync(ISolution solutionRoot)
{
var explorer = ServiceLocator.ServiceContainer.Instance.GetService<IExplorer>();
var filepath = explorer.SaveDocumentFile(UserDocDir + "\\" + "New Solution",
UserDocDir, true, solutionRoot.SolutionFileFilter);
if (string.IsNullOrEmpty(filepath) == true)
return;
var solutionModel = new ViewModelModelConverter().ToModel(solutionRoot);
var result = await SaveSolutionFileAsync(filepath, solutionModel);
}
Private Async Function SaveSolutionCommand_ExecutedAsync(ByVal solutionRoot As ISolution) As Task
Dim explorer = ServiceLocator.ServiceLocator.ServiceContainer.Instance.GetService(Of IExplorer)()
Dim filepath = explorer.SaveDocumentFile(UserDocDir & "\" & "New Solution",
UserDocDir,
True,
solutionRoot.SolutionFileFilter)
If String.IsNullOrEmpty(filepath) = True Then Return
Dim solutionModel = New ViewModelModelConverter().ToModel(solutionRoot)
Dim result = Await SaveSolutionFileAsync(filepath, solutionModel)
End Function
The last 2 lines in the above code snippet show how the Model for the Solution is obtained from the ViewModelModelConverter().ToModel() call. This Model (and not the ViewModel) is then saved through an extra call to SaveSolutionFileAsync(....). So, let us review these in the next sections.
There is this Level-Order Conversion section in the previous article that gave hints towards converting a Model to a ViewModel (on Load) and claimed this should also be possible in the opposite direction (on Save). This conversion is implemented in both directions in the
InPlaceEditBoxDemo.ViewModels.ViewModelModelConverter
class. The conversion methods ToModel() and ToViewModel() are used within the SaveSolutionCommand and the LoadSolutionCommand in the AppViewModel class. The ToModel() method is called before the Save operation takes place.
The conversion is based on the Level-Order algorithm of the TreeLib library project. The foreach loop below does the actual conversion, also based on an Id that is computed on the fly in itemId.
public SolutionModelsLib.Models.SolutionModel ToModel(ISolution solutionRoot)
{
IItem treeRootVM = solutionRoot.GetRootItem();
long itemId = 0;
var items = TreeLib.BreadthFirst.Traverse.LevelOrder(treeRootVM
, (i) =>
{
var it = i as IItemChildren;
if (it != null)
return it.Children;
return new List<IItemChildren>();
});
var dstIdItems = new Dictionary<long, IItemChildrenModel>();
var solutionModel = new SolutionModel();
foreach (var item in items.Select(i => i.Node))
{
item.SetId(itemId++);
if (item.Parent == null)
{
solutionModel.AddSolutionRootItem(item.DisplayName, item.GetId());
dstIdItems.Add(solutionModel.Root.Id, solutionModel.Root);
}
else
{
IItemChildrenModel modelParentItem;
IItemModel modelNewChild;
dstIdItems.TryGetValue(item.Parent.GetId(), out modelParentItem);
modelNewChild = ConvertToModel(solutionModel, modelParentItem, item);
modelNewChild.Id = item.GetId();
if (modelNewChild is IItemChildrenModel)
dstIdItems.Add(modelNewChild.Id, modelNewChild as IItemChildrenModel);
}
}
return solutionModel;
}
Public Function ToModel(ByVal solutionRoot As ISolution) As SolutionModelsLib.Models.SolutionModel
Dim treeRootVM As IItem = solutionRoot.GetRootItem()
Dim itemId As Long = 0
Dim items = TreeLib.BreadthFirst.Traverse.LevelOrder(treeRootVM, Function(i)
Dim it = TryCast(i, IItemChildren)
If it IsNot Nothing Then Return it.Children
Return New List(Of IItemChildren)()
End Function)
Dim dstIdItems = New Dictionary(Of Long, IItemChildrenModel)()
Dim solutionModel = New SolutionModel()
For Each item In items.[Select](Function(i) i.Node)
item.SetId(Math.Min(System.Threading.Interlocked.Increment(itemId), itemId - 1))
If item.Parent Is Nothing Then
solutionModel.AddSolutionRootItem(item.DisplayName, item.GetId())
dstIdItems.Add(solutionModel.Root.Id, solutionModel.Root)
Else
Dim modelParentItem As IItemChildrenModel = Nothing
Dim modelNewChild As IItemModel = Nothing
dstIdItems.TryGetValue(item.Parent.GetId(), modelParentItem)
modelNewChild = ConvertToModel(solutionModel, modelParentItem, item)
modelNewChild.Id = item.GetId()
If TypeOf modelNewChild Is IItemChildrenModel Then dstIdItems.Add(modelNewChild.Id, TryCast(modelNewChild, IItemChildrenModel))
End If
Next
Return solutionModel
End Function
The above code converts the ViewModel objects in the SolutionLib project (using one more helper method) into a collection of model objects defined in the SolutionModelsLib project. The model definitions in the SolutionModelsLib project are defined in a very similar structure to the viewmodels in the SolutionLib project. This similarity is mainly there, because it makes the conversion much easier. Note, however that both, model and viewmodel structure could also be very different depending on the requirements of the UI and the storage technology used.
The previous section explained the conversion from the ViewModel into the Model. This section explains how the model is stored via the AppViewModel.SaveSolutionFileAsync() method call. The SaveSolutionFileAsync() method calls the SaveSolutionFile() method, which in turn calls the SQLite specific methods that implement the backend. The interesting line here is this statement:
recordCount = db.InsertSolutionData(solutionRoot);
which leads us to the WriteToFile Method in the SolutionModelsLib.SQLite.SolutionDB class:
private int WriteToFile(SolutionModel solutionRoot
, SQLiteCommand cmd)
{
int result = 0;
int iKey = 0;
var items = TreeLib.BreadthFirst.Traverse.LevelOrder<IItemModel>(solutionRoot.Root
, (i) =>
{
var it = i as IItemChildrenModel;
if (it != null)
return it.Children;
return new List<IItemChildrenModel>();
});
foreach (var item in items)
{
int iLevel = item.Level;
IItemModel current = item.Node;
current.Id = iKey++;
long parentId = (current.Parent == null ? -1 : current.Parent.Id);
if (cmd != null)
{
cmd.Parameters.AddWithValue("@id", current.Id);
cmd.Parameters.AddWithValue("@parent", parentId);
cmd.Parameters.AddWithValue("@level", iLevel);
cmd.Parameters.AddWithValue("@name", current.DisplayName);
cmd.Parameters.AddWithValue("@itemtypeid", (int)(current.ItemType));
result += cmd.ExecuteNonQuery();
}
else
{
Console.WriteLine(string.Format("{0,4} - {1} ({2})"
, iLevel, current.GetStackPath(), current.ItemType.ToString()));
}
}
return result;
}
Private Function WriteToFile(ByVal solutionRoot As SolutionModel,
ByVal cmd As SQLiteCommand) As Integer
Dim result As Integer = 0
Dim iKey As Integer = 0
Dim items = TreeLib.BreadthFirst.Traverse.LevelOrder(Of IItemModel)(solutionRoot.Root,
Function(i)
Dim it = TryCast(i, IItemChildrenModel)
If it IsNot Nothing Then Return it.Children
Return New List(Of IItemChildrenModel)()
End Function)
For Each item In items
Dim iLevel As Integer = item.Level
Dim current As IItemModel = item.Node
current.Id = Math.Min(System.Threading.Interlocked.Increment(iKey), iKey - 1)
Dim parentId As Long = (If(current.Parent Is Nothing, -1, current.Parent.Id))
If cmd IsNot Nothing Then
cmd.Parameters.AddWithValue("@id", current.Id)
cmd.Parameters.AddWithValue("@parent", parentId)
cmd.Parameters.AddWithValue("@level", iLevel)
cmd.Parameters.AddWithValue("@name", current.DisplayName)
cmd.Parameters.AddWithValue("@itemtypeid", CInt((current.ItemType)))
result += cmd.ExecuteNonQuery()
Else
Console.WriteLine(String.Format("{0,4} - {1} ({2})", iLevel, current.GetStackPath(), current.ItemType.ToString()))
End If
Next
Return result
End Function
This method looks very similar to the converter method shown in the previous section. Here, we are using the same traversal method from the TreeLib library project. The foreach loop is (again) the part that does the actual operation on each tree node - the operation here being data storage in the SQLite database file.
Many beginners in programming have problems manipulating tree structured data items, which makes their WPF tree view implementation limited to some degree. This article and the previous article are published in the hope that traversal methods can shed some warm light here. The usage of the IEnumerable/Yield method, described in the last article and re-used here for conversion and load/save, shows that an application of these traversal methods can be trivial, while still yielding outstanding performance.
The extra conversion between model and viewmodel seems to be extra work without any real immediate advantage. But one should draw a benefit from this design when working in a larger team. This design approach will also yield more flexability when future changes need to be included. Change something significant, like the UI control suite, or the storage backend, or just developing things further should be easy if you stick to working with Models and ViewModels with a proper seperation.
- 2017-12-08 all code samples available VB.Net also
