Download Demo Project | View Demo Project
Introduction
I have recently been paying a lot of attention to many of the new multi touch concept screens that are being demonstrated, such as Microsoft Surface. In this type of interface you may very likely to have many different types of objects on your surface, such as some pictures, a video, shortcuts to web sites and documents containing information that you had jotted down. So now the problem in my mind is that if a product like this were to ever become more than a novelty it will need a good way of storing a users information so it can be swept clean and recalled later. The traditional method of today would be a series of folders and files stored on a hard drive, but there is a flaw in this setup in my mind. When visualizing objects on a screen like this pictures appear as pictures, videos appear as videos, etc. You have to actually make a giant paradigm leap to understand that the object you are viewing as a picture is actually a file made up of ones and zeros and should be organized as such. So I started thinking about the fact that we store information such as a picture in a file and display it like a photo because our brain understands the rendered photo, not the file. So why would we then force the user to visualize his photo as a file in order to categorize or organize it.
So I came up with a concept of building a tree and allowing each branch of the tree to associate to any object, a user could build trees by dragging and dropping on item onto another or the operating system could build trees based on certain things a user had done. For instance if a user dropped his camera phone onto the surface and pulled some photos off of the camera, then shoved the pictures off of the screen picked up his camera and walked away the operating system could have created a tree which had his camera as an object and all of the photos as children. So the next time he put his camera phone on the screen the operating system could recall all of the objects associated with that camera and make a recommendation that he take a look at them. The more exciting concept is the second part, allowing users to relate any objects to each other by dragging and dropping them onto each other.
This allows users to store their objects more like how our mind organizes memories. For instance maybe someone in a photo always reminds you of a certain song that you heard for the first time when you met that person, and maybe you have the lyrics to that song in a document and maybe you have a video that was also sent to you by the same person who gave you the lyrics to that song who also has a personal web site. Now in the past, relations for the most part have been determined by some arbitrary set of rules, this can relate to that because of this. My concept is to break down that need for a computer to understand why things are related, they are related simply because the user said they are related. In my example above if a user were to drag the music object onto the picture, the lyrics onto the song, the video onto the lyrics and the favorite onto the onto the video the next time any of those objects were recalled the operating system could remind you of the objects that are related to it. So for example if the user opened the photo of his friend he could then be reminded of the song that he also has or if he opened the video he could be then reminded of his friends web site.
The Project
To accomplish a proof of concept for this method of storing information I have put together a demonstration project which consists of a generic object tree class, a collection of arbitrary objects, a web UI for creating and associating objects together and a serialization class for storing and recalling generic object trees exactly as they are displayed.
This project is written in vb.net in Visual Studio 2008 and requires the .net 3.5 framework. Please note that if you are looking for a library for building a recursive navigation or family tree, then I would advise you to search for "generic tree", though it may look from the demo that this is exactly what you need; this demonstration is an example of storing unrelated objects in a tree not objects of all the same type in a tree.
The Tree
For this tree to work correctly, I knew I would need to inherit from a generic collection object and I also knew that I would run into a semaphore problem if we ever wanted to actually retrieve a specific item from a tree. I chose to inherit from the generic dictionary object which provides me not only with the ability to store objects in a collection, but also the ability to assign a unique key to each object and the ability to look up objects by key very quickly and efficiently.
''' <summary>
''' GenericObjectTree
''' </summary>
''' <remarks>
''' Generic Object Tree
''' Used to relate objects of any type to eachother in a tree object.
''' </remarks>
<Serializable()> _
Public Class GenericObjectTree
Inherits Generic.Dictionary(Of String, GenericObjectTree)
Implements ISerializable
''' <summary>
''' Data
''' </summary>
''' <remarks>
''' The actual data store of an object of your choice
''' </remarks>
Private m_Data As Object
Public Property Data() As Object
Get
Return m_Data
End Get
Set(ByVal value As Object)
m_Data = value
End Set
End Property
''' <summary>
''' New
''' </summary>
''' <remarks>
''' Default Constructor.
''' </remarks>
Public Sub New()
MyBase.New()
End Sub
''' <summary>
''' New
''' </summary>
''' <param name="treeData"></param>
''' <remarks>
''' Create Guid As Unique Node Identifier.
''' Assign First Key/Value Pair of current collection to Data Object.
''' </remarks>
Public Sub New(ByVal treeData As Object)
MyBase.New()
Dim newID As String = Guid.NewGuid().ToString()
Me.Add(newID, New GenericObjectTree())
Me(newID).Data = treeData
End Sub
''' <summary>
''' New
''' </summary>
''' <param name="childData"></param>
''' <param name="skipemptyroot"></param>
''' <remarks>
''' Private Constructor, called from AddChild
''' </remarks>
Private Sub New(ByVal childData As Object, ByVal skipemptyroot As Boolean)
MyBase.New()
Me.Data = childData
End Sub
''' <summary>
''' AddChild
''' </summary>
''' <param name="childData"></param>
''' <returns>Unique ID</returns>
''' <remarks>
''' Create Guid As Unique Node Identifier.
''' Add Child Key/Value Pair with Data Onject.
''' </remarks>
Public Overridable Function AddChild(ByVal childData As Object) As String
Dim newID As String = Guid.NewGuid().ToString()
Me.Add(newID, New GenericObjectTree(childData, True))
Return newID
End Function
End Class
Now the first thing you will notice is that the object inherits from a Generic.Dictionary of itself. Now I realize that it makes absolutely no logical sense for an object to inherit itself, but does it make sense that an object can inherit from a collection of itself? Sure why not, the inheritance states that the object inherits all of the properties of a generic dictionary and itself while at the same time allowing you to create children of the same type. You will see there is an additional property of type object to store the arbitrary object on each tree node.
One other thing to note is the existence of the private/public constructors. This is because of a simple chicken and egg problem which arises, to be able to access the data stored in each node you will need a key, since the initial instance of the object is not a child of any other dictionary it cannot be assigned a key. To address this problem we always need to create an initial instance that does not store any data only references to its child objects. This action is taken in the public constructor. Once a tree has been created this empty node is no longer required and the private constructor is called via AddChild.
Recursing The Tree
Recursing the tree is fairly simple if you have a good understanding of recursion. It simply consists of taking action on the current tree node, checking if that tree node has any children, if so taking the same action on the children, then checking to see if that node has any siblings and taking the same action on each sibling. This continues until you have recursed the entire tree or until you have found what you are looking for. The following example is one of the recursive methods contained in the project.
''' <summary>
''' FindNodeByUniqueIdentifier
''' </summary>
''' <param name="uniqueID">Unique ID</param>
''' <returns>GenericObjectTree</returns>
''' <remarks>
''' Return Your Tree Node By It's Assigned Unique Identifier.
''' This Method Will Recurse Itself.
''' </remarks>
Public Overridable Function FindNodeByUniqueIdentifier(ByVal uniqueID As String) As GenericObjectTree
'check if key is a child currently.
If Me.ContainsKey(uniqueID) Then
'key found return tree node
Return Me(uniqueID)
End If
'loop through collection to recurse branches
For Each key As String In Me.Keys
'recurse grandchild.
Dim childtree As GenericObjectTree = Me(key).FindNodeByUniqueIdentifier(uniqueID)
'if found return tree node.
If childtree IsNot Nothing Then Return childtree
Next
'if not found return nothing.
Return Nothing
End Function
One thing I do have to mention. It is arguable that the function above is not truly recursive, though it is recursive in nature. It is important to understand this if you want to ever want to debug the code and understand what is happenning. When the method above is called it does in fact call a function with the same name and does follow the design pattern of a standard recursive function. But the method it is actually calling is a method by the same name in a child instance of itself, so it could be argued that it is not technically caling itself.
Displaying the tree data
Displaying the tree data simply consists of recursing the tree. Deciding what type of data is stored in the current tree node and displaying the correct visual representation for that specific object.
Protected Sub DisplayCurrentFileTree(ByVal FileBranch As GenericObjectTree, _
ByVal UniqueID As String, _
Optional ByVal removeOther As Boolean = True)
...
'Check type of data on this tree node and display appropriate box type.
Select Case True
Case TypeOf (FileBranch.Data) Is Files.MusicFile
'Display a music box
DisplayMusicBox(DirectCast(FileBranch.Data, Files.MusicFile), UniqueID)
Case TypeOf (FileBranch.Data) Is Files.Picture
'display a picture box
DisplayPictureBox(DirectCast(FileBranch.Data, Files.Picture), UniqueID)
Case TypeOf (FileBranch.Data) Is Files.Favorite
'display a favortie box
DisplayFavoriteBox(DirectCast(FileBranch.Data, Files.Favorite), UniqueID)
Case TypeOf (FileBranch.Data) Is Files.Video
'display a video box
DisplayVideoBox(DirectCast(FileBranch.Data, Files.Video), UniqueID)
Case TypeOf (FileBranch.Data) Is Files.WordDocument
'display a word document box
DisplayWordDocumentBox(DirectCast(FileBranch.Data, Files.WordDocument), UniqueID)
Case Else
'do nothing
End Select
...
'If sibling keys exists then loop through each key.
For Each key As String In FileBranch.Keys
...
'Recurse each found key.
'Specify false do tree display is not truncated.
DisplayCurrentFileTree(FileBranch(key), key, False)
...
Next
Storing The Tree
In this system my goal was to store the object exactly how it is displayed so I chose to store each tree serialized as binary as well as each object serialized as binary. The objects are stored and organized just as they are displayed. There is no need to deconstruct and reconstruct the objects in and out of flat tables. Since Generic.Dictionary will not serialize correctly by default I had to first implement ISerializable as well as add a custom constructor and method to my generic dictionary object. When storing the GenericObject Tree I had to first serialize the object according to its myBase method. Since the base method does not have the concept of the arbitrary object data and since each object will be serialized differently I need to recurse the tree and store each object as its own file named by its key. When recalling the object first the tree is deserialized and then recursed to load each arbitrary object by its key. The nice thing about this is that each arbitrary object is then stored as a stand alone object and can exist in many trees.
''' <summary>
''' SaveObject
''' </summary>
''' <param name="obj"></param>
''' <param name="Filename"></param>
''' <param name="skipTree"></param>
''' <remarks>
''' Save a GenericObjectTree To Disk
''' </remarks>
Public Shared Sub SaveObject(ByVal obj As GenericObjectTree, ByVal Filename As String, Optional ByVal skipTree As Boolean = False)
If Not skipTree Then
'open a file strem
Using s As Stream = File.Open(Filename, FileMode.Create, FileAccess.ReadWrite)
'serialize dictionary to disk in binary
Dim b As New BinaryFormatter
b.Serialize(s, obj)
End Using
End If
'serialize all data objects to disk
For Each key As String In obj.Keys
Dim dataObj As Object = obj(key).Data
If dataObj IsNot Nothing Then
'write data object to disk, use unique key for filename.
Using s As Stream = File.Open(Path.GetDirectoryName(Filename) & "\" & key & ".sf", FileMode.Create, FileAccess.ReadWrite)
'serialize data to disk in binary
Dim b As New BinaryFormatter
b.Serialize(s, dataObj)
End Using
End If
'recurse.
SaveObject(obj(key), Filename, True)
Next
End Sub
Conclusion
Though the web UI interface is far from a multi touch display I believe that it effectively examples how the process of associating arbitrary objects to each other is possible and effective. As you can see in the example the rendering is extremely efficient when building, loading and saving extremely large trees.
In the next version of this project I hope to implement an interface where objects are created outside of the tree itself and stored on a surface until associated by dragging and dropping. In addition I hope to implement moving of objects within the tree, disassociating objects with the tree, editing an objects data and removing objects.