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