Tree Package for TCL

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

OBSOLETE
Alias for ::Tree::attributeAppend

::Tree::attributeExist tree attribute

Return true if the attribute exists for the specified tree, otherwise return false.

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?

Return a list of all the attribute names for the tree where the name matches the pattern. If the pattern is omitted then all of the attribute names are returned.

O(1)

::Tree::attributePairs tree ?pattern?

Return the array contents for all of the user assigned attributes that match the pattern. If the pattern is omitted, return data for all of the assigned attributes. This data is appropriate for a command of the form

array set MyArray [::Tree::attributePairs $someTree $myPattern]
        

O(1)

::Tree::attributeUnset tree attribute

Remove the attribute from the specified tree. Return the value of the attribute prior to the removal. If the attribute does not exist, an emtpy string is returned.

O(1)

::Tree::children tree ?pattern?
::Tree::children tree pattern ?options?

Return a list of all the children of the tree that match the glob style pattern. If the pattern is omitted, return all of the children. The order of the children is undefined. If a ::Tree::isLeaf tree returns 1, then this routine will return an empty list.

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

This option controls the order that children are returned Children that are present but not in the -order option are returned after children in the 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"

This command is used to order the names of the children that are returned. This routine is called using the form
command options nameList
The 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"

This only applies to depth traversals.
The command specified by this option is called on the first visit to the sub-tree. Stated differently, this is called on the downward traversal. The command is evaluated within the same scope (call level) as the code that invoked the ::Tree::walk routine.

command args tree depth

-inCall "command args"

Depth order traversal
The command specified by this option is called in between each of the children. The command is evaluated within the same scope (call level) as the code that invoked the ::Tree::walk routine. Unless the -order or <-sort> options are specified, there is no order of the children. For isLeaf trees the command is called once. For trees with only one child, this command is called after the child is traversed. For all other trees, the command is called exactly once between each of the children that are present. Also see the -singleCall option

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.

Level order traversal
The command specified by this option is called once for each of the trees in a level order traversal. The command is evaluated within the same scope (call level) as the code that invoked the ::Tree::walk routine. Unless the -order option is specified, there is no order of the children.

command args tree depth

-postCall "command args"

This only applies to depth traversals.
The command specified by this option is called on the last visit to the sub-tree. Stated differently, this is called on the backtrack traversal. The command is evaluated within the same scope (call level) as the code that invoked the ::Tree::walk routine.

command args tree depth

-singleInCall boolean

This only applies to depth traversals.
This option controls how often the -inCall command is called. If -singleInCall is 0, then the -inCall command is called as specified in the -inCall option. If -singleInCall is 1, the -inCall command is called only once.

-order names

This option controls the order that children are traversed. Children that are present but not in the -order option are traversed after children in the -order list.

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"

This command is used to order the names of the children during the walk. This routine is called using the form
command options nameList
The 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"

This command is used to order the names of the children during the walk. This routine is called using the form
command options tree
The 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 default is 1. When using the -order, -sort or -arrange options the resulting node name list may not be complete. If -authoritative is zero (0) then any remaining nodes will be appended in no defined manner to the list of nodes that will be processed for the tree being visited. if -authoritative is one (1) then only the node names returned by the -order, -sort or -arrange routines is traversed.

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
}


Known limitations


Revision History

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

Timings
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