You are here

Tree Package for TCL

admin의 아바타

홈페이지 :
http://web.uvic.ca/%7Eerempel/tcl/tree/tree.html

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::isTree treeToken

Return 1 if treeToken represents a valid tree, otherwise return 0.

O(1)

::Tree::isRoot treeToken

Return 1 if treeToken has no parents.

O(1)

::Tree::isLeaf treeToken

Return 1 if treeToken has no children.

O(1)

::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 set the user attribute value of the tree to be "". See ::Tree::attribute

O(1)

::Tree::destroy treeToken

Destroy the tree represented by the treeToken. See also ::Tree::prune.

O(n)

::Tree::root treeToken

Return the tree token in the parent path of the treeToken that has no parents. Stated differently, return the tree token for the root of the entire tree that contains the treeToken

O(log n) for balanced trees. The degenerative case is O(n).

::Tree::prune treeToken

Remove the tree specified by treeToken from any tree that it is a child of. Return the treeToken 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::graft parentToken childToken

Make the tree represented by childToken a child of the tree represented by parentToken. If childToken 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 perform the prune or graft, and will return an empty string. Return childToken.

O(log n) for balanced trees. The degenerative case is O(n).

::Tree::parent treeToken

Return the tree token for the tree that treeToken is a child of. If treeToken does not have a parent, then an invalid tree token is returned. This means that ::Tree::isTree will return 0.

O(1)

::Tree::child treeToken name

Obsolete - use ::Tree::children instead.
Return the list of children of treeToken that are named name. Wild cards are not supported.

O(1)

::Tree::children treeToken ?options?
::Tree::children treeToken ?-pattern? pattern ?options?

Return a list of all the children of the token treeToken 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 treeToken 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.

-pattern pattern

The -pattern key word is only necessary is the pattern begins with a hyphen.
-order names

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 -order list.
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::exist treeToken name ?childVar?

Return 1 if the tree treeToken has a child named name. If the childVar is included, then it is assigned the list of children with name. This saves the extra call to ::Tree::children treeToken name.

O(1)

The followig two segments of code are equivilent;

if {[::Tree::exist $myTree childName]} then {
  set childList [::Tree::children $myTree childName]
  ... some code ...
}

and

if {[::Tree::exist $myTree childName childList]} then {
  ... some code ...
}

::Tree::name treeToken
::Tree::name treeToken ?name?

In the first form, return the name of the tree represented by treeToken.

In the second form, set the name of the treeToken to name. Return the name of the tree prior to the change.

O(1)

::Tree::attribute tree
::Tree::attribute tree ?attribute?
::Tree::attribute tree attribute ?value?

In the first form, return 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.

In the third form, set the value of the of the tree attribute to be value. Return the value of the tree attribute prior to the change.

O(1)

::Tree::attributeExist tree attribute

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

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::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] {
    lappend myList [::Tree::attribute $child $attribute]
  }
  return $myList
}

::Tree::appendAttribute tree attribute value

Append value onto the value of attribute of tree. Return the new value of tree attribute.

O(1)

::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::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. The degenerative case is O(n).

::Tree::format treeToken

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::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-zero, the traverse is canceled and the tree that the non-zero return was performed on 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.

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. Any children that 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 were not present in the nameList. This will affect the traversal the same way that non-existant names in the -order option do. Any children that 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.

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 0
  }
 
  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 0
  }
 
  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 0
  }
 
  set answer ""
  ::Tree::walk $tree depth -inCall "InOrder answer" -preCall "PreOrder answer" -postCall "PostOrder answer" -singleInCall 0
  return $answer
}

첨부 파일파일 크기
Package icon tree212.zip36.06 KB
Binary Data tree212.tar.gz33.42 KB