Click here to Skip to main content
Click here to Skip to main content
Go to top

Generic Object Tree For Synapse Controlled Relations

, 10 Mar 2008
Rate this:
Please Sign up or sign in to vote.
A concept of building a tree and allowing each branch of the tree to associate to any object.

results

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 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 user's 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. 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. Why would we then force the user to visualize his photo as a file in order to categorize or organize it?

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 one 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 puts 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 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 lyrics on to the website, 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 be reminded of his friend's 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.

''' <span class="code-SummaryComment"><summary></span>
''' GenericObjectTree
''' <span class="code-SummaryComment"></summary></span>
''' <span class="code-SummaryComment"><remarks></span>
''' Generic Object Tree
''' Used to relate objects of any type to eachother in a tree object.
''' <span class="code-SummaryComment"></remarks></span>
<Serializable()> _
Public Class GenericObjectTree
    Inherits Generic.Dictionary(Of String, GenericObjectTree)
    Implements ISerializable

    ''' <span class="code-SummaryComment"><summary></span>
    ''' Data
    ''' <span class="code-SummaryComment"></summary></span>
    ''' <span class="code-SummaryComment"><remarks></span>
    ''' The actual data store of an object of your choice
    ''' <span class="code-SummaryComment"></remarks></span>
    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

    ''' <span class="code-SummaryComment"><summary></span>
    ''' New
    ''' <span class="code-SummaryComment"></summary></span>
    ''' <span class="code-SummaryComment"><remarks></span>
    ''' Default Constructor.
    ''' <span class="code-SummaryComment"></remarks></span>
    Public Sub New()
        MyBase.New()
    End Sub

    ''' <span class="code-SummaryComment"><summary></span>
    ''' New
    ''' <span class="code-SummaryComment"></summary></span>
    ''' <span class="code-SummaryComment"><param name="treeData"></param></span>
    ''' <span class="code-SummaryComment"><remarks></span>
    ''' Create Guid As Unique Node Identifier.
    ''' Assign First Key/Value Pair of current collection to Data Object.
    ''' <span class="code-SummaryComment"></remarks></span>
    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

    ''' <span class="code-SummaryComment"><summary></span>
    ''' New
    ''' <span class="code-SummaryComment"></summary></span>
    ''' <span class="code-SummaryComment"><param name="childData"></param></span>
    ''' <span class="code-SummaryComment"><param name="skipemptyroot"></param></span>
    ''' <span class="code-SummaryComment"><remarks></span>
    ''' Private Constructor, called from AddChild
    ''' <span class="code-SummaryComment"></remarks></span>
    Private Sub New(ByVal childData As Object, ByVal skipemptyroot As Boolean)
        MyBase.New()
        Me.Data = childData
    End Sub

    ''' <span class="code-SummaryComment"><summary></span>
    ''' AddChild
    ''' <span class="code-SummaryComment"></summary></span>
    ''' <span class="code-SummaryComment"><param name="childData"></param></span>
    ''' <span class="code-SummaryComment"><returns>Unique ID</returns></span>
    ''' <span class="code-SummaryComment"><remarks></span>
    ''' Create Guid As Unique Node Identifier.
    ''' Add Child Key/Value Pair with Data Onject.
    ''' <span class="code-SummaryComment"></remarks></span>
    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. 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, but 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:

''' <span class="code-SummaryComment"><summary></span>
''' FindNodeByUniqueIdentifier
''' <span class="code-SummaryComment"></summary></span>
''' <span class="code-SummaryComment"><param name="uniqueID">Unique ID</param></span>
''' <span class="code-SummaryComment"><returns>GenericObjectTree</returns></span>
''' <span class="code-SummaryComment"><remarks></span>
''' Return Your Tree Node By It's Assigned Unique Identifier.
''' This Method Will Recurse Itself.
''' <span class="code-SummaryComment"></remarks></span>
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 ever want to debug the code and understand what is happening. 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 calling 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.

''' <span class="code-SummaryComment"><summary></span>
''' SaveObject
''' <span class="code-SummaryComment"></summary></span>
''' <span class="code-SummaryComment"><param name="obj"></param></span>
''' <span class="code-SummaryComment"><param name="Filename"></param></span>
''' <span class="code-SummaryComment"><param name="skipTree"></param></span>
''' <span class="code-SummaryComment"><remarks></span>
''' Save a GenericObjectTree To Disk
''' <span class="code-SummaryComment"></remarks></span>
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 object's data, and removing objects.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jason Witty
Software Developer (Senior)
United States United States
For more articles please visit my website:
http://www.aprogrammersjournal.com
 
A Programmers Journal
RSS

Comments and Discussions

 
QuestionSource code? PinadminChris Maunder10-Mar-08 1:43 
AnswerRe: Source code? PinmemberJason Witty10-Mar-08 6:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140916.1 | Last Updated 10 Mar 2008
Article Copyright 2008 by Jason Witty
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid