Appropriate Data Structure for a TreeView?
BlitzMax Forums/BlitzMax Programming/Appropriate Data Structure for a TreeView?
| ||
| What would be the appropriate data structure in which to store the contents of a TreeView? I'm thinking of a TMap with the key being composed of each "branch" of the tree, delimited with another character of some kind. But I've never used TreeViews before, and this is one of the more complex data structures I've dealt with in general. So I'd appreciate opinions from more experienced programmers on the best way to store this. |
| ||
| To be honest, apart from tree structures, I dont see the point of Tmap. Obviously my lack of experiance showing ;) So I wont comment further, and will let the experts give a real answer. (However knowing this site, you will probably get two or three contraditory answers) |
| ||
| (However knowing this site, you will probably get two or three contraditory answers) Heh, for sure. And at least one person telling me that my entire methodology is wrong if I even use a TreeView. I haven't used TMaps much before. Just for things where I need quick random access, but an array isn't suitable ( something where the number of elements goes up and down a lot. ) Kinda seemed like they would suit a treeview, but like I say, this is new ground for me. |
| ||
| And at least one person telling me that my entire methodology is wrong if I even use a TreeView. And at least one person telling you that you could have used it before Mark changed it. But now it breaks some IEE standard laid down in 1972, and you need to roll back to Bmax 1.16 (and you should use a different version of the assembler) |
| ||
| Gabrial: The appropriate structure would be an own tree structure which saves all childs as linked list. A TMap or binary tree is useless for a treeview as each node can have more than 2 children ... |
| ||
| Gabrial: The appropriate structure would be an own tree structure which saves all childs as linked list. This is certainly something I've considered. I was just concerned about speed. A TMap or binary tree is useless for a treeview as each node can have more than 2 children ... Well it's restrictive, I'll give you that, but if I "encode" the branches of the tree into the key, then when it comes to parsing them out into the treeview gadget, I can simply iterate through the entire map, stripping the branches back out with a simple string parser. You see, I really need the speed when it comes to pulling objects out, but don't care the least about the speed of filling the treeview gadget. I guess a tree datastructure with TMap's for each node with just leaves and no further branches could be fast enough, but I'm not sure. I still have to negotiate my tree structure before I go there. Although in fairness, this makes searching the map faster as the maps are shorter. |
| ||
| That indeed would be a potential way as well. Doing the "dictionary way". Each treeview node is a typeinstance. This typeh as a "childs" list which uses TMap ... But this depends on the amount of childs there normally are. if log2(childs) isn't significantly smaller than childs (number of childs) then it doesn't make that much sense to use a TMap. but if you have 10+ childs on each treeview node it will start to make a significant difference when jumping down the tree. Another way is just 1 TMap ... and put all nodes in there with their node text as key. Thats very fast as well. don't know if the "encoding" would make it faster than one of the above solutions as decoding needs time as well |
| ||
| what you want is an exponential tree... for a simple listbox I just would use tmaps in tmaps. |
| ||
| Ok, well I tried searching for information and implementation guides for exponential trees and came up with next to nothing, apart from a little diagram which basically confirmed what you already told me, that it's suitable for a TreeView. So, being completely clueless on the subject, I decided to hack something together and open myself up to public humiliation in the hope of learning how I messed up. Here's what I've got. I've only tested adding a few categories and a couple of entries ( a category is a node on a treeview which has child nodes and an entry is a node with no children. In the context I'm using them, there is a clear distinction and I will never need to treat them the same. ) It seems to work ok in the little test, but there could well still be bugs, because I've only given it a cursory test since hacking it together. There is definitely no error checking. Well some, but not enough. That comes later. No sense making it bulletproof if it's a bad implementation and needs binning. I'm predominantly interested in speed. How does this look to the more experienced programmers? It's a module ( seemed best. )
Module glimmer.treemap
ModuleInfo "Framework: Tree-Based Map Data Structure"
ModuleInfo "Copyright: Glimmer Games"
ModuleInfo "Author: Phil Ings"
ModuleInfo "Version: 1.0"
Import brl.map
SuperStrict
' THIS IS YOUR TREE
Type tTreeMap
Field Root:tTreeMapNode
Method New()
Root=New tTreeMapNode
End Method
Method Delete()
Clear()
End Method
Method Clear()
Root.Clear()
End Method
Method InsertEntry(TreePath:String,Entry:String,Value:Object)
Local NewParent:tTreeMapNode=Root.FindPath(TreePath)
If NewParent<>Null
NewParent.InsertEntry(Entry,Value)
End If
End Method
Method InsertCategory:tTreeMapNode(TreePath:String,Category:String)
Local NewParent:tTreeMapNode=Root.FindPath(TreePath)
If NewParent<>Null
Return NewParent.InsertCategory(Category)
End If
End Method
Method RemoveEntry(TreePath:String,Entry:String)
Local NewParent:tTreeMapNode=Root.FindPath(TreePath)
If NewParent<>Null
NewParent.RemoveEntry(Entry)
End If
End Method
Method RemoveCategory(TreePath:String,Category:String)
Local NewParent:tTreeMapNode=Root.FindPath(TreePath)
If NewParent<>Null
NewParent.RemoveCategory(Category)
End If
End Method
Method FindEntry:Object(TreePath:String,Entry:String)
Local KeyParent:tTreeMapNode=Root.FindPath(TreePath)
If KeyParent=Null
Return Null
Else
Return KeyParent.FindEntry(Entry)
End If
End Method
Method FindCategory:tTreeMapNode(TreePath:String)
Return Root.FindPath(TreePath)
End Method
End Type
' NODES - THESE ARE YOUR CATEGORIES. THEY CONTAIN YOUR ACTUAL ENTRIES
Type tTreeMapNode
Field Children:tMap ' BINARY TREE OF ALL CHILD NODES - THESE ARE OTHER CATEGORIES
Field Leaves:TMap ' BINARY TREE OF ALL LEAF NODES - THESE ARE ENTRIES
Method Clear()
If Leaves<>Null
Leaves.Clear()
End If
For Local Node:tTreeMapNode=EachIn Children.Keys()
Node.Clear()
Next
End Method
Method InsertEntry(Entry:String,Value:Object)
If Leaves=Null
Leaves=New TMap
End If
Leaves.Insert(Entry,Value)
End Method
Method InsertCategory:tTreeMapNode(Category:String)
Local CategoryNode:tTreeMapNode=New tTreeMapNode
If Children=Null
Children=New TMap
End If
Children.Insert(Category,CategoryNode)
Return CategoryNode
End Method
Method RemoveEntry(Entry:String)
Leaves.Remove(Entry)
End Method
Method RemoveCategory(Category:String)
Local Node:tTreeMapNode=tTreeMapNode(Children.ValueForKey(Category))
Children.Remove(Category)
Node.Clear()
End Method
Method FindEntry:Object(Entry:String)
Return Leaves.ValueForKey(Entry)
End Method
Method FindPath:tTreeMapNode(Path:String)
Local NextNodeOnPath:tTreeMapNode
Local SlashPos:Int= Path.Find("\")
If SlashPos=-1
If Path<>""
If Children=Null
Return Null
Else
Return tTreeMapNode(Children.ValueForKey(Path))
End If
Else
Return Self
End If
Else
If SlashPos=Path.Length-1 ' IF THE SLASH IS ON THE END OF THE PATH, REMOVE IT AND DO AS ABOVE
Return tTreeMapNode(Children.ValueForKey(Path[..SlashPos-1]))
Else
NextNodeOnPath=tTreeMapNode(Children.ValueForKey(Path[..SlashPos]))
If NextNodeOnPath=Null
Return Null
Else
Return NextNodeOnPath.FindPath(Path[SlashPos+1..])
End If
End If
End If
End Method
End Type
|
| ||
| yeah, I don't know why I told you that.. it's really not a good choice anyway. |
| ||
| Anyone have any thoughts on this module then? |
| ||
| looks good to me... do you have a test program? I'd play with it a little then. |
   |