Current Version 3.1
zip
tar gzip
Previous Version 2.12
zip
tar gzip
Author: Evan Rempel erempel@UVic.CA
This package is intended to be a building block for any and all hierachical structures. It has a slightly different interface than most programmers are used to, but I believe it to be functionally complete.
By definition, a tree is a single element, with zero or more trees as children. Using this definition, there is no NULL tree.
As examples I will produe an XML parser that will produce trees, and a binary search tree package.
For those that are working on large trees, I have included a BigO classification for each of the routines. I was recently bitten by a O(n2) tree operation in a perl library :-( and wanted to save others of this problem.
::Tree::attribute tree
::Tree::attribute tree attribute ?value?
The first form is now obsolete (see ::Tree::attributePairs)
This form returns the array contents for all of the user
assigned attributes. This data is appropriate for a command of the form
array set MyArray [::Tree::attribute $someTree]
In the second form, return the value of the user attribute specified. The attribute named value is the default attribute used in the ::Tree::create routine and the walk routine. If value is included, set the attribute to value.
O(1)
::Tree::attributeAppend tree attribute value
Append value onto the value of attribute of tree. Return the new value of tree attribute.
O(1)
::Tree::appendAttribute tree attribute value
::Tree::attributeExist tree attribute
O(1)
::Tree::attributeLappend tree attribute value
Append value as a list onto the value of attribute of tree. Return the new value of tree attribute.
O(1)
::Tree::attributeNames tree ?pattern?
O(1)
::Tree::attributePairs tree ?pattern?
array set MyArray [::Tree::attributePairs $someTree $myPattern]
O(1)
::Tree::attributeUnset tree attribute
O(1)
::Tree::children tree ?pattern?
::Tree::children tree pattern ?options?
O(1) unless -order or -sort are used, then O(n) plus the O(sort/order) where n is the number of children.
-order nameList
There is no order defined for children that have the same names.
The -order and -sort options may not both be specified.
-sort "command options"
command options nameListThe sort command specified may return names that were not present in the nameList. This will cause null children to be returned in the place of the non-existant names.
There is no order defined for children that have the same names.
The -order and -sort options may not both be specified.
::Tree::create name ?value?
Return a new tree named name, with no children. If value is present, set the user attribute value of the tree to be it, otherwise do not set the user attribute value of the tree. See ::Tree::attribute
O(1)
::Tree::depth tree
Return the depth within the parent tree that tree resides. The depth of a newly created tree (::Tree::isRoot is 1) is zero, and a tree the is the child of such a tree has depth 1, etc. The depth of a non-tree is the empty string.
O(log n) for balanced trees where n is the number of nodes in the tree. The degenerative case is O(n).
::Tree::deserialize treeString
Return a new tree that is represented by the treeString. Typically this will be a string produced by the ::Tree::serialize routine. If the string is not a valid serialized tree then return an empty string.
O(n) where n is the number of nodes in the tree.
::Tree::destroy tree
Destroy the tree represented by the tree. See also ::Tree::prune.
O(n)
::Tree::exist tree pattern ?childVar?
Return 1 if the tree tree has a child whos name matches pattern. If the childVar is included, then it is assigned the list of children with name. This saves the extra call to ::Tree::children tree name.
O(1)
The followig two segments of code are equivilent;
if {[::Tree::exist $myTree $pattern]} then { set childList [::Tree::children $myTree -pattern $pattern] ... some code ... }and
if {[::Tree::exist $myTree $pattern childList]} then { ... some code ... }
::Tree::format tree
Return a nested representation of a tree, similar to XML. The data presented in the output is based on the user attribute value. See ::Tree::attribute
O(n)
The following code will produce the output below.
set myTree [::Tree::create employee]
set birthday [::Tree::graft $myTree [::Tree::create birthday happy]]
::Tree::attribute $birthday type julian
::Tree::graft $birthday [::Tree::create year 1971]
::Tree::graft $birthday [::Tree::create month March]
::Tree::graft $birthday [::Tree::create day 17]
::Tree::graft $myTree [::Tree::create name "Sam Smith"]
::Tree::graft $myTree [::Tree::create empNumber "12345"]
puts [::Tree::format $myTree]
Would produce the output;
<employee>
<birthday type="julian">happy
<year>1971</year>
<month>March</month>
<day>17</day>
</birthday>
<name>Sam Smith</name>
<empNumber>12345</empNumber>
</employee>
::Tree::graft parentTree childTree
Make the tree represented by childTree a child of the tree represented by parentTree. If childTree is the child of a tree when this routine is called, it is first pruned from its location prior to being grafted into its new location. Grafting an ancestor onto a decendent is illegal and will not perform the prune or graft, and will return an empty string. Return childTree.
O(log n) for balanced trees. The degenerative case is O(n).
::Tree::height tree
Return the height of the tree. The height of a newly created tree (::Tree::isLeaf is 1) is zero, a tree with one child that is a leaf, has height of 1 etc. The height of a non-tree is the empty string.
O(n)
::Tree::isLeaf tree
Return 1 if tree has no children.
O(1)
::Tree::isRoot tree
Return 1 if tree has no parents.
O(1)
::Tree::isTree tree
Return 1 if tree represents a valid tree, otherwise return 0.
O(1)
::Tree::list tree pattern
::Tree::list tree pattern ?attribute?
Return a list of of the attribute values of the children of tree that have a name that matches the glob style pattern. If attribute is omitted, then the default attribute value is used. See ::Tree::create
O(n) where n is the number of children.
This is equivilent to the following code segment;
proc ::Tree::list {tree childName attribute} {
set myList {}
foreach child [::Tree::children $myTree $childName] {
if {[::Tree::attributeExist $child $attribute]} then {
lappend myList [::Tree::attribute $child $attribute]
}
}
return $myList
}
::Tree::name tree
::Tree::name tree ?name?
In the first form, return the name of the tree.
In the second form, set the name of the tree to name. Return the name of the tree prior to the change.
O(1)
::Tree::parent tree
Return the tree that tree is a child of. If tree does not have a parent, then an invalid tree is returned. This means that ::Tree::isTree will return 0.
O(1)
::Tree::prune tree
Remove the tree from any tree that it is a child of. Return the tree of the tree that has been removed. This routine does not destroy any data. See also ::Tree::destroy.
O(n) where n is the number of siblings.
::Tree::root tree
Return the tree in the parent path of the tree that has no parents. Stated differently, return the tree for the root of the entire tree that contains the tree
O(log n) for balanced trees. The degenerative case is O(n).
::Tree::serialize tree
Return the string suitable for use with ::Tree::deserialize that represents the tree. This provides a mechanism to easily save and load trees.
O(n) where n is the number of nodes in the tree.
::Tree::walk tree depth options
::Tree::walk tree level options
By for the most complex of all the Tree routines. Traverse the tree, calling user specified routines for each visit to a tree.
This routine will walk through the tree, following a depth order,
or a level order traversal, calling the specified commands for
each tree that is visited.
If any of the -preCall, -inCall or -postCall commands returns a non-null value, the traverse is canceled and the non-null value is returned.
O(n) * ( O(preCall/inCall/postCall) + O(sort/order/arrange) )
-preCall "command args"
command args tree depth
-inCall "command args"
command args tree depth inCallIndex
Note: If the -order option is specified, the command is called once between each of the children in the -order list, regardless of whether or not the child actually exists. This could result in multiple back to back calls to command.
command args tree depth
-postCall "command args"
command args tree depth
-singleInCall boolean
-order names
Generally, the -order option is only useful if the names of the immediate children are unique within the immediate tree, but common to all trees and sub-trees. Also see the -InCall option. A common usage for this option is to binary trees to ensure that an in-order traversal visits the parent of a right node first, even if the left node is not present. If -authoritative is 0 any names that exist but are not returned by this routine are appended to the list that the order command returns.
There is no order defined for children that have the same names.
The -order and -sort options may not both be specified.
-sort "command options"
command options nameListThe sort command specified may return names that were not present in the nameList. This will affect the traversal the same way that non-existant names in the -order option do. If -authoritative is 0 any names that exist but are not returned by this routine are appended to the list that the sort command returns.
-arrange "command options"
command options treeThe arrange command specified may return names that are not children of the tree. This will affect the traversal the same way that non-existant names in the -order option do. If -authoritative is 0 any names that exist but are not returned by this routine are appended to the list that the arrange command returns.
There is no order defined for children that have the same names.
Only one of the -order, -sort or -arrange options may be specified.
-authoritative 0/1
The ::Tree::format routine could be written as the following, however, using ::Tree::format is an order of magnitude faster;
proc MyFormat { tree } {
proc InOrder { collect tree depth count} {
upvar $collect output
if {[::Tree::isLeaf $tree]} then {
set offsetString "[string repeat " " $depth][string repeat " " $depth]"
array set attributes [::Tree::attribute $tree]
set attribString ""
foreach attributeName [array names attributes] {
if {$attributeName != "value"} then {
append attribString " $attributeName=\"$attributes($attributeName)\""
}
}
append output "${offsetString}<[::Tree::name $tree]$attribString>[::Tree::attribute $tree value]</[::Tree::name $tree]>\n"
}
return ""
}
proc PostOrder { collect tree depth } {
upvar $collect output
if {![::Tree::isLeaf $tree]} then {
set offsetString "[string repeat " " $depth][string repeat " " $depth]"
append output "${offsetString}</[::Tree::name $tree]>\n"
}
return ""
}
proc PreOrder { collect tree depth } {
upvar $collect output
if {![::Tree::isLeaf $tree]} then {
set offsetString "[string repeat " " $depth][string repeat " " $depth]"
array set attributes [::Tree::attribute $tree]
set attribString ""
foreach attributeName [array names attributes] {
if {$attributeName != "value"} then {
append attribString " $attributeName=\"$attributes($attributeName)\""
}
}
append output "${offsetString}<[::Tree::name $tree]$attribString>[::Tree::attribute $tree value]\n"
}
return ""
}
set answer ""
::Tree::walk $tree depth -inCall "InOrder answer" -preCall "PreOrder answer" -postCall "PostOrder answer" -singleInCall 0
return $answer
}
Version 3.1 - Sep 15, 2004
Version 3.0 - Sep 8, 2004
Version 2.12 - Apr 10, 2003
Version 2.11 - Feb 13, 2003
Version 2.10 - Oct 29, 2002
Version 2.9.1 - July 27, 2002
Version 2.9 - June 9, 2002
Version 2.8 - Mar 12, 2002
Version 2.7 - Feb 9, 2002
Version 2.6 - Jan 30, 2002
Version 2.5 - Jan 22, 2002
Version 2.4 - October 21, 2001
Version 2.3.1 - Aug 24, 2001
Version 2.3 - July 3, 2001
Version 2.2 - June 18, 2001
Tested with TCL 8.4.4 Version 3.1 Create: 22 microseconds per iteration Destroy: 37 microseconds per iteration Destroy with children: 153 microseconds per iteration isTree: 7 microseconds per iteration isRoot: 12 microseconds per iteration isLeaf: 12 microseconds per iteration root: 26 microseconds per iteration Graft: 64 microseconds per iteration Graft (10000 wide): 57 microseconds per iteration Prune (10000 wide): 759 microseconds per iteration Prune: 54 microseconds per iteration parent: 11 microseconds per iteration children all: 14 microseconds per iteration children static: 25 microseconds per iteration children wild card all: 14 microseconds per iteration children wild card: 36 microseconds per iteration children all with sort: 66 microseconds per iteration children all with order: 75 microseconds per iteration exist: 20 microseconds per iteration exist return: 42 microseconds per iteration name: 16 microseconds per iteration Attribute set: 25 microseconds per iteration All attributes: 30 microseconds per iteration Wildcard attributes: 24 microseconds per iteration Single attribute: 23 microseconds per iteration Unset attribute: 11 microseconds per iteration attributeAppend: 15 microseconds per iteration appendAttribute: 15 microseconds per iteration attributeExist: 8 microseconds per iteration attributeNames all: 13 microseconds per iteration attributeNames wildcard: 12 microseconds per iteration attributeNames static: 11 microseconds per iteration attributePairs all: 24 microseconds per iteration attributePairs wildcard: 19 microseconds per iteration attributePairs static: 16 microseconds per iteration list static: 25 microseconds per iteration list wild card: 44 microseconds per iteration list unknown value: 44 microseconds per iteration height: 68 microseconds per iteration depth: 27 microseconds per iteration format: 679 microseconds per iteration walk - none: 307 microseconds per iteration walk - pre: 549 microseconds per iteration walk - in: 566 microseconds per iteration walk - post: 549 microseconds per iteration walk - pre, in, post: 1002 microseconds per iteration walk - pre, post: 755 microseconds per iteration walk - pre, in, post with sort: 1205 microseconds per iteration walk level: 531 microseconds per iteration walk level - sort: 730 microseconds per iteration walk level - sort: 651 microseconds per iteration Version 3.0 Create: 26 microseconds per iteration Destroy: 39 microseconds per iteration Destroy with children: 153 microseconds per iteration isTree: 7 microseconds per iteration isRoot: 14 microseconds per iteration isLeaf: 12 microseconds per iteration root: 34 microseconds per iteration Prune (10000 wide): 772 microseconds per iteration Prune: 54 microseconds per iteration parent: 14 microseconds per iteration children all: 16 microseconds per iteration children static: 25 microseconds per iteration children wild card all: 17 microseconds per iteration children wild card: 35 microseconds per iteration children all with sort: 66 microseconds per iteration children all with order: 75 microseconds per iteration exist: 21 microseconds per iteration exist return: 43 microseconds per iteration name: 17 microseconds per iteration Attribute set: 22 microseconds per iteration All attributes: 30 microseconds per iteration Wildcard attributes: 22 microseconds per iteration Single attribute: 21 microseconds per iteration Unset attribute: 11 microseconds per iteration attributeAppend: 15 microseconds per iteration appendAttribute: 15 microseconds per iteration attributeExist: 8 microseconds per iteration attributeNames all: 13 microseconds per iteration attributeNames wildcard: 12 microseconds per iteration attributeNames static: 11 microseconds per iteration attributePairs all: 24 microseconds per iteration attributePairs wildcard: 19 microseconds per iteration attributePairs static: 16 microseconds per iteration list static: 25 microseconds per iteration list wild card: 44 microseconds per iteration list unknown value: 44 microseconds per iteration height: 95 microseconds per iteration depth: 36 microseconds per iteration format: 681 microseconds per iteration walk - none: 350 microseconds per iteration walk - pre: 596 microseconds per iteration walk - in: 609 microseconds per iteration walk - post: 599 microseconds per iteration walk - pre, in, post: 1055 microseconds per iteration walk - pre, post: 818 microseconds per iteration walk - pre, in, post with sort: 1240 microseconds per iteration walk level: 618 microseconds per iteration walk level - sort: 753 microseconds per iteration walk level - sort: 666 microseconds per iteration Version 2.12 Create: 33 microseconds per iteration Destroy: 34 microseconds per iteration Destroy with children: 121 microseconds per iteration isTree: 5 microseconds per iteration isRoot: 11 microseconds per iteration isLeaf: 11 microseconds per iteration root: 29 microseconds per iteration Prune (10000 wide): 784 microseconds per iteration Prune: 62 microseconds per iteration parent: 11 microseconds per iteration child: 14 microseconds per iteration children all: 20 microseconds per iteration children static: 34 microseconds per iteration children wild card all: 24 microseconds per iteration children wild card: 42 microseconds per iteration children all with sort: 93 microseconds per iteration children all with order: 93 microseconds per iteration exist: 29 microseconds per iteration exist return: 49 microseconds per iteration name: 17 microseconds per iteration Attribute set: 23 microseconds per iteration All attributes: 57 microseconds per iteration Single attribute: 21 microseconds per iteration Unset attribute: 16 microseconds per iteration appendAttribute: 13 microseconds per iteration attributeExist: 10 microseconds per iteration list static: 33 microseconds per iteration list wild card: 53 microseconds per iteration list unknown value: 54 microseconds per iteration height: 141 microseconds per iteration depth: 49 microseconds per iteration format: 998 microseconds per iteration walk - none: 520 microseconds per iteration walk - pre: 789 microseconds per iteration walk - in: 805 microseconds per iteration walk - post: 791 microseconds per iteration walk - pre, in, post: 1301 microseconds per iteration walk - pre, post: 1038 microseconds per iteration walk - pre, in, post with sort: 1561 microseconds per iteration walk level: 838 microseconds per iteration walk level - sort: 953 microseconds per iteration walk level - sort: 911 microseconds per iteration