Marco Maggi - In this page I present the code for an experimental tree stucture. I don't like it at all because I Believe that complex data structures have to be implemented at the C level. But, I needed a tree structure in my Wiki pages so...
It's probably incorrect in some operations, I'll try to test it when I find time and will to do it.
proc tree_set_root { treevar node } {
upvar $treevar tree
array set tree [list root $node $node:dad {} $node:cld {}]
}
proc tree_get_root { treevar } {
upvar $treevar tree
return $tree(root)
}
proc tree_isroot { treevar node } {
upvar $treevar tree
return [expr {([string equal $tree(root) $node])? 1 : 0}]
}
proc tree_get_children { treevar node } {
upvar $treevar tree
return $tree($node:cld)
}
proc tree_get_father { treevar node } {
upvar $treevar tree
return $tree($node:dad)
}
proc tree_exists { treevar node} {
upvar $treevar tree
return [info exists tree($node:cld)]
}
proc tree_add_children { treevar node children } {
upvar $treevar tree
foreach child $children {
if { [info exists tree($child:dad)] } {
tree_remove_children tree($child:dad) $child
} else {
set tree($child:cld) {}
}
lappend tree($node:cld) $child
set tree($child:dad) $node
}
return
}
proc tree_remove { treevar node } {
upvar $treevar tree
if { [string equal $tree(root) $node] } {
set tree(root) {}
foreach child $tree($node:cld) {
tree_remove tree $child
}
} else {
set dad $tree($node:dad)
tree_remove_child tree $dad $node
}
unset tree($node:dad) tree($node:cld)
}
proc tree_remove_child { treevar node child } {
upvar $treevar tree
set idx [lsearch $tree($node:cld) $node]
set tree($node:cld) [lreplace $tree($node:cld) $idx $idx]
set tree($child:dad) {}
return
}
proc tree_path { treevar node } {
upvar $treevar tree
set path {}
while { ! [string equal $tree(root) $node] } {
set path [linsert $path 0 $node]
set node $tree($node:dad)
}
return [linsert $path 0 $node]
}To test it we can fill it with the following procedure.
proc fill_tree { treevar } {
upvar $treevar tree
tree_set_root tree 0
tree_add_children tree 0 { 1 2 3 4 5 6 7 8 9 }
for {set i 1} {$i < 10} {incr i} {
for {set j 1} {$j < 10} {incr j} {
tree_add_children tree $i $i.$j
for {set k 0} {$k < 10} {incr k} {
tree_add_children tree $i.$j $i.$j.$k
}
}
}
}RS: I wouldn't call trees data structures too complex for Tcl (which is implemented in C - our scripts just do the configuration :-) - nested lists are perfectly adequate, compact and efficient for representing tree structures, and easily navigable with multi-index lindex and lset...
Marco Maggi: I have to disagree. There are a lot of methods in a tree structure, and most of them require a set of 4/5 (or more) test cases. So if I have to spend time building a reliable structure of such a complexity, I prefer to do it with C, so that I can use the module with and without TCL.
I'm writing a C library of data structures, and it's not "fun" to make it reliable: I'm writing a lot of tests (handling them with the tcltest package of course) and spending a lot of hours. I want it to be as much reusable as possible, and C is the answer.
I like TCL, but what if tomorrow I get a job and my new boss tells me "Do this with python." ? Or "You have a week to build a C library that does this and that." and I need an AVL tree?
My C data structure library will be in my bag of tools "forever".
See also: