Страницы справочника OS X

Эта страница руководства для  версии 10.9 Mac OS X

Читать страницы руководства

struct::tree(n)                              Tcl Data Structures                             struct::tree(n)



____________________________________________________________________________________________________________

NAME
       struct::tree - Create and manipulate tree objects

SYNOPSIS
       package require Tcl  8.2

       package require struct::tree  ?2.1.1?

       package require struct::list  ?1.5?

       ::struct::tree ?treeName? ?=|:=|as|deserialize source?

       treeName option ?arg arg ...?

       ::struct::tree::prune

       treeName = sourcetree

       treeName --> desttree

       treeName ancestors node

       treeName append node key value

       treeName attr key

       treeName attr key -nodes list

       treeName attr key -glob globpattern

       treeName attr key -regexp repattern

       treeName children ?-all? node ?filter cmdprefix?

       treeName cut node

       treeName delete node ?node ...?

       treeName depth node

       treeName descendants node ?filter cmdprefix?

       treeName deserialize serialization

       treeName destroy

       treeName exists node

       treeName get node key

       treeName getall node ?pattern?

       treeName keys node ?pattern?

       treeName keyexists node key

       treeName index node

       treeName insert parent index ?child ?child ...??

       treeName isleaf node

       treeName lappend node key value

       treeName leaves

       treeName move parent index node ?node ...?

       treeName next node

       treeName numchildren node

       treeName nodes

       treeName parent node

       treeName previous node

       treeName rename node newname

       treeName rootname

       treeName serialize ?node?

       treeName set node key ?value?

       treeName size ?node?

       treeName splice parent from ?to? ?child?

       treeName swap node1 node2

       treeName unset node key

       treeName walk node ?-order order? ?-type type? loopvar script

       treeName walkproc node ?-order order? ?-type type? cmdprefix

____________________________________________________________________________________________________________

DESCRIPTION
       A  tree  is  a  collection  of named elements, called nodes, one of which is distinguished as a root,
       along with a relation ("parenthood") that places a hierarchical structure on the nodes. (Data  Struc-tures Structures
       tures  and  Algorithms;  Aho, Hopcroft and Ullman; Addison-Wesley, 1987).  In addition to maintaining
       the node relationships, this tree implementation allows any number of keyed values to  be  associated
       with each node.

       The element names can be arbitrary strings.

       A tree is thus similar to an array, but with three important differences:

       [1]    Trees  are accessed through an object command, whereas arrays are accessed as variables. (This
              means trees cannot be local to a procedure.)

       [2]    Trees have a hierarchical structure, whereas an array is just an unordered collection.

       [3]    Each node of a tree has a separate collection of attributes and values. This is like an  array
              where every value is a dictionary.


       Note: The major version of the package struct has been changed to version 2.0, due to backward incom-patible incompatible
       patible changes in the API of this module. Please read the section Changes for 2.0 for a full list of
       all changes, incompatible and otherwise.


API
   TREE CLASS API
       The main commands of the package are:

       ::struct::tree ?treeName? ?=|:=|as|deserialize source?
              The  command  creates  a  new  tree object with an associated global Tcl command whose name is
              treeName. This command may be used to invoke various operations on the tree.  It has the  fol-lowing following
              lowing general form:

              treeName option ?arg arg ...?
                     Option and the args determine the exact behavior of the command.

       If  treeName  is  not specified a unique name will be generated by the package itself. If a source is
       specified the new tree will be initialized to it. For the operators =, :=, and as  source  is  inter-preted interpreted
       preted  as the name of another tree object, and the assignment operator = will be executed. For dese-rialize deserialize
       rialize the source is a serialized tree object and deserialize will be executed.

       In other words


           ::struct::tree mytree = b


       is equivalent to


           ::struct::tree mytree
           mytree = b


       and


           ::struct::tree mytree deserialize $b


       is equivalent to


           ::struct::tree mytree
           mytree deserialize $b


       ::struct::tree::prune
              This command is provided outside of the tree methods, as it is not a tree method  per  se.  It
              however  interacts  tightly  with  the method walk. When used in the walk script it causes the
              traversal to ignore the children of the node we are currently at.  This command cannot be used
              with  the  traversal  modes  which look at children before their parent, i.e. post and in. The
              only applicable orders of traversal are pre and both. An error is thrown if  the  command  and
              chosen order of traversal do not fit.



   TREE OBJECT API
       Two general observations beforehand:

       [1]    The  root  node  of the tree can be used in most places where a node is asked for. The default
              name of the rootnode is "root", but this can be changed with the method  rename  (see  below).
              Whatever the current name for the root node of the tree is, it can be retrieved by calling the
              method rootname.

       [2]    The method insert is the only way to create new nodes, and they are automatically added  to  a
              parent. A tree object cannot have nodes without a parent, save the root node.


       And now the methods supported by tree objects created by this package:

       treeName = sourcetree
              This  is  the  assignment  operator for tree objects. It copies the tree contained in the tree
              object sourcetree over the tree data in treeName. The old contents of treeName are deleted  by
              this operation.

              This operation is in effect equivalent to


                  treeName deserialize [sourcetree serialize]


       treeName --> desttree
              This  is the reverse assignment operator for tree objects. It copies the tree contained in the
              tree object treeName over the tree data in the object desttree. The old contents  of  desttree
              are deleted by this operation.

              This operation is in effect equivalent to


                  desttree deserialize [treeName serialize]


       treeName ancestors node
              This  method extends the method parent and returns a list containing all ancestor nodes to the
              specified node. The immediate ancestor, in other words, parent node, is the first  element  in
              that  list, its parent the second element, and so on until the root node is reached, making it
              the last element of the returned list.

       treeName append node key value
              Appends a value to one of the keyed values associated with an  node.  Returns  the  new  value
              given to the attribute key.

       treeName attr key

       treeName attr key -nodes list

       treeName attr key -glob globpattern

       treeName attr key -regexp repattern
              This  method retrieves the value of the attribute named key, for all nodes in the tree (match-ing (matching
              ing the restriction specified via one of  the  possible  options)  and  having  the  specified
              attribute.

              The result is a dictionary mapping from node names to the value of attribute key at that node.
              Nodes not having the attribute key, or not passing a specified restriction, are not listed  in
              the result.

              The possible restrictions are:

              -nodes The  value  is  a list of nodes. Only the nodes mentioned in this list are searched for
                     the attribute.

              -glob  The value is a glob pattern. Only the nodes in the tree whose names match this  pattern
                     are searched for the attribute.

              -regexp
                     The  value  is  a regular expression. Only the nodes in the tree whose names match this
                     pattern are searched for the attribute.


       treeName children ?-all? node ?filter cmdprefix?
              Return a list of the children of node.  If the option -all is specified,  then  not  only  the
              direct  children,  but their children, and so on are returned in the result.  If a filter com-mand command
              mand is specified only those nodes are listed in the final result which  pass  the  test.  The
              command  in  cmdprefix is called with two arguments, the name of the tree object, and the name
              of the node in question. It is executed in the context of the  caller  and  has  to  return  a
              boolean  value.  Nodes  for  which  the command returns false are removed from the result list
              before it is returned to the caller.

              Some examples:


                  mytree insert root end 0 ; mytree set 0 volume 30
                  mytree insert root end 1
                  mytree insert root end 2
                  mytree insert 0    end 3
                  mytree insert 0    end 4
                  mytree insert 4    end 5 ; mytree set 5 volume 50
                  mytree insert 4    end 6

                  proc vol {t n} {
                   $t keyexists $n volume
                  }
                  proc vgt40 {t n} {
                   if {![$t keyexists $n volume]} {return 0}
                   expr {[$t get $n volume] > 40}
                  }

                  tclsh> lsort [mytree children -all root filter vol]
                  0 5

                  tclsh> lsort [mytree children -all root filter vgt40]
                  5

                  tclsh> lsort [mytree children root filter vol]
                  0

                  tclsh> puts ([lsort [mytree children root filter vgt40]])
                  ()


       treeName cut node
              Removes the node specified by node from the tree, but not its children.  The children of  node
              are made children of the parent of the node, at the index at which node was located.

       treeName delete node ?node ...?
              Remove  the specified nodes from the tree.  All of the nodes' children will be removed as well
              to prevent orphaned nodes.

       treeName depth node
              Return the number of steps from node node to the root node.

       treeName descendants node ?filter cmdprefix?
              This method extends the method children and returns a list  containing  all  nodes  descending
              from node, and passing the filter, if such was specified.

              This  is  actually  the same as "treeName children -all".  descendants should be prefered, and
              "children -all" will be deprecated sometime in the future.

       treeName deserialize serialization
              This is the complement to serialize. It replaces tree data in treeName with the tree described
              by the serialization value. The old contents of treeName are deleted by this operation.

       treeName destroy
              Destroy the tree, including its storage space and associated command.

       treeName exists node
              Remove true if the specified node exists in the tree.

       treeName get node key
              Returns the value associated with the key key for the node node.

       treeName getall node ?pattern?
              Returns a dictionary (suitable for use with [array set]) containing the attribute data for the
              node.  If the glob pattern is specified only the attributes whose names match the pattern will
              be part of the dictionary.

       treeName keys node ?pattern?
              Returns  a  list  of keys for the node.  If the pattern is specified only the attributes whose
              names match the pattern will be part of the returned list. The pattern is a glob pattern.

       treeName keyexists node key
              Return true if the specified key exists for the node.

       treeName index node
              Returns the index of node in its parent's list of children.  For example, if a node has  node-Foo, nodeFoo,
              Foo, nodeBar, and nodeBaz as children, in that order, the index of nodeBar is 1.

       treeName insert parent index ?child ?child ...??
              Insert one or more nodes into the tree as children of the node parent. The nodes will be added
              in the order they are given. If parent is root, it refers to the root of  the  tree.  The  new
              nodes will be added to the parent node's child list at the index given by index. The index can
              be end in which case the new nodes will be added after the current last child.  Indices of the
              form "end-n" are accepted as well.

              If  any  of  the  specified children already exist in treeName, those nodes will be moved from
              their original location to the new location indicated by this command.

              If no child is specified, a single node will be added, and a name will be  generated  for  the
              new node. The generated name is of the form nodex, where x is a number. If names are specified
              they must neither contain whitespace nor colons (":").

              The return result from this command is a list of nodes added.

       treeName isleaf node
              Returns true if node is a leaf of the tree (if node has no children), false otherwise.

       treeName lappend node key value
              Appends a value (as a list) to one of the keyed values associated with an  node.  Returns  the
              new value given to the attribute key.

       treeName leaves
              Return a list containing all leaf nodes known to the tree.

       treeName move parent index node ?node ...?
              Make  the  specified  nodes children of parent, inserting them into the parent's child list at
              the index given by index. Note that the command will take all nodes out  of  the  tree  before
              inserting  them  under  the new parent, and that it determines the position to place them into
              after the removal, before the re-insertion. This behaviour is important when it comes to  mov-ing moving
              ing one or more nodes to a different index without changing their parent node.

       treeName next node
              Return  the  right sibling of node, or the empty string if node was the last child of its par-ent. parent.
              ent.

       treeName numchildren node
              Return the number of immediate children of node.

       treeName nodes
              Return a list containing all nodes known to the tree.

       treeName parent node
              Return the parent of node.

       treeName previous node
              Return the left sibling of node, or the empty string if node was the first child of  its  par-ent. parent.
              ent.

       treeName rename node newname
              Renames  the  node node to newname. An error is thrown if either the node does not exist, or a
              node with name newname does exist. The result of the command is the new name of the node.

       treeName rootname
              Returns the name of the root node of the tree.

       treeName serialize ?node?
              This method serializes the sub-tree starting at node. In other words it returns  a  tcl  value
              completely  describing  the  tree starting at node.  This allows, for example, the transfer of
              tree objects (or parts thereof) over arbitrary channels, persistence,  etc.   This  method  is
              also the basis for both the copy constructor and the assignment operator.

              The  result  of  this  method has to be semantically identical over all implementations of the
              tree interface. This is what will enable us to copy tree data  between  different  implementa-tions implementations
              tions of the same interface.

              The  result is a list containing containing a multiple of three elements. It is like a serial-ized serialized
              ized array except that there are two values following each key. They  are  the  names  of  the
              nodes  in  the  serialized  tree.  The  two  values are a reference to the parent node and the
              attribute data, in this order.

              The reference to the parent node is the empty string for the root node of the  tree.  For  all
              other nodes it is the index of the parent node in the list. This means that they are integers,
              greater than or equal to zero, less than the length of the list, and multiples of three.   The
              order  of the nodes in the list is important insofar as it is used to reconstruct the lists of
              children for each node. The children of a node have to be listed in the serialization  in  the
              same order as they are listed in their parent in the tree.

              The  attribute data of a node is a dictionary, i.e. a list of even length containing a serial-ized serialized
              ized array. For a node without attribute data the dictionary is the empty list.

              Note: While the current implementation returns the root node as the first element of the list,
              followed by its children and their children in a depth-first traversal this is not necessarily
              true for other implementations.  The only information a reader of the serialized data can rely
              on for the structure of the tree is that the root node is signaled by the empty string for the
              parent reference, that all other nodes refer to their parent through the index  in  the  list,
              and that children occur in the same order as in their parent.


               A possible serialization for the tree structure

                           +- d
                     +- a -+
               root -+- b  +- e
                     +- c
               is

               {root {} {} a 0 {} d 3 {} e 3 {} b 0 {} c 0 {}}

               The above assumes that none of the nodes have attributes.


       treeName set node key ?value?
              Set or get one of the keyed values associated with a node. A node may have any number of keyed
              values associated with it.  If value is not specified, this command returns the current  value
              assigned  to  the  key; if value is specified, this command assigns that value to the key, and
              returns it.

       treeName size ?node?
              Return a count of the number of descendants of the node node; if no node is specified, root is
              assumed.

       treeName splice parent from ?to? ?child?
              Insert  a  node named child into the tree as a child of the node parent. If parent is root, it
              refers to the root of the tree. The new node will be added to the parent node's child list  at
              the  index  given  by from.  The children of parent which are in the range of the indices from
              and to are made children of child.  If the value of to is not specified it  defaults  to  end.
              If  no name is given for child, a name will be generated for the new node.  The generated name
              is of the form nodex, where x is a number.  The return result from this command is the name of
              the new node.

              The  arguments  from  and  to  are regular list indices, i.e.  the form "end-n" is accepted as
              well.

       treeName swap node1 node2
              Swap the position of node1 and node2 in the tree.

       treeName unset node key
              Remove a keyed value from the node node. The method will do nothing if the key does not exist.

       treeName walk node ?-order order? ?-type type? loopvar script
              Perform  a  breadth-first or depth-first walk of the tree starting at the node node.  The type
              of walk, breadth-first or depth-first, is determined by  the  value  of  type;  bfs  indicates
              breadth-first,  dfs indicates depth-first.  Depth-first is the default. The order of the walk,
              pre-, post-, both- or in-order is determined by the value of order; pre  indicates  pre-order,
              post  indicates  post-order, both indicates both-order and in indicates in-order. Pre-order is
              the default.

              Pre-order walking means that a parent node is visited before any of its children.   For  exam-ple, example,
              ple, a breadth-first search starting from the root will visit the root, followed by all of the
              root's children, followed by all of the root's grandchildren. Post-order walking means that  a
              parent  node is visited after any of its children. Both-order walking means that a parent node
              is visited before and after any of its children. In-order walking means that a parent node  is
              visited  after  its  first  child  and before the second. This is a generalization of in-order
              walking for binary trees and will do the right thing if a binary tree is walked. The  combina-tion combination
              tion of a breadth-first walk with in-order is illegal.

              As  the walk progresses, the script will be evaluated at each node. The evaluation takes place
              in the context of the caller of the method.  Regarding loop variables,  these  are  listed  in
              loopvar.  If one only one variable is specified it will be set to the id of the node. When two
              variables are specified, i.e. loopvar is a true list, then the first variable will be  set  to
              the  action performed at the node, and the other to the id of the node itself.  All loop vari-ables variables
              ables are created in the context of the caller.

              There are three possible actions: enter, leave, or visit.  enter  actions  occur  during  pre-order preorder
              order  walks; leave actions occur during post-order walks; visit actions occur during in-order
              walks.  In a both-order walk, the command will be evaluated twice for each node; the action is
              enter for the first evaluation, and leave for the second.

              Note: The enter action for a node is always performed before the walker will look at the chil-dren children
              dren of that node. This means that changes made by the script to the children of the node will
              immediately influence the walker and the steps it will take.

              Any other manipulation, for example of nodes higher in the tree (i.e already visited), or upon
              leaving will have undefined results. They may succeed, error out, silently compute  the  wrong
              result, or anything in between.

              At  last  a  small table showing the relationship between the various options and the possible
              actions.


               order       type    actions         notes
               -----       ----    -----           -----pre ----pre
               pre         dfs     enter           parent before children
               post        dfs     leave           parent after children
               in          dfs     visit           parent between first and second child.
               both        dfs     enter, leave    parent before and after children
               -----       ----    -----           -----pre ----pre
               pre         bfs     enter           parent before children
               post        bfs     leave           parent after children
               in          bfs             -- illegal --both -both
               both        bfs     enter, leave    parent before and after children
               -----       ----    -----           -----Note ----Note


              Note the command ::struct::tree::prune. This command can be used in the walk script  to  force
              the  command to ignore the children of the node we are currently at. It will throw an error if
              the order of traversal is either post or in as these modes visit  the  children  before  their
              parent, making pruning non-sensical.

       treeName walkproc node ?-order order? ?-type type? cmdprefix
              This method is like method walk in all essentials, except the interface to the user code. This
              method invokes a command prefix with three additional  arguments  (tree,  node,  and  action),
              instead of evaluating a script and passing the node via a loop variable.


   CHANGES FOR 2.0
       The following noteworthy changes have occurred:

       [1]    The API for accessing attributes and their values has been simplified.

              All  functionality  regarding  the  default  attribute  "data"  has been removed. This default
              attribute does not exist anymore. All accesses to attributes have to specify the name  of  the
              attribute  in question. This backward incompatible change allowed us to simplify the signature
              of all methods handling attributes.

              Especially the flag -key is not required anymore, even more, its use is now forbidden.  Please
              read the documentation for the methods set, get, getall, unset, append, lappend, keyexists and
              keys for a description of the new API's.

       [2]    The methods keys and getall now take  an  optional  pattern  argument  and  will  return  only
              attribute data for keys matching this pattern.

       [3]    Nodes can now be renamed. See the documentation for the method rename.

       [4]    The  structure  has been extended with API's for the serialization and deserialization of tree
              objects, and a number of operations based on them (tree assignment, copy construction).

              Please read the documentation for the methods serialize, deserialize, =, and -->, and the doc-umentation documentation
              umentation on the construction of tree objects.

              Beyond  the  copying  of  whole  tree objects these new API's also enable the transfer of tree
              objects over arbitrary channels and for easy persistence.

       [5]    The walker API has been streamlined and made more similar to the command foreach. In detail:

              •      The superfluous option -command has been removed.

              •      Ditto for the place holders. Instead of the placeholders two loop variables have to  be
                     specified to contain node and action information.

              •      The  old command argument has been documented as a script now, which it was in the past
                     too.

              •      The fact that enter actions are called before the walker looks at  the  children  of  a
                     node has been documented now. In other words it is now officially allowed to manipulate
                     the list of children for a node under these circumstances. It has been made clear  that
                     changes  under  any other circumstances will have undefined results, from silently com-puting computing
                     puting the wrong result to erroring out.

       [6]    A new method, attr, was added allowing the query  and  retrieval  of  attribute  data  without
              regard to the node relationship.

       [7]    The method children has been extended with the ability to select from the children of the node
              based on an arbitrary filtering criterium. Another extension is the ability to look  not  only
              at the immediate children of the node, but the whole tree below it.


EXAMPLES
       The following example demonstrates the creation of new nodes:

           mytree insert root end 0   ; # Create node 0, as child of the root
           mytree insert root end 1 2 ; # Ditto nodes 1 & 2
           mytree insert 0    end 3   ; # Now create node 3 as child of node 0
           mytree insert 0    end     ; # Create another child of 0, with a
           #                              generated name. The name is returned
           #                              as the result of the command.


BUGS, IDEAS, FEEDBACK
       This  document,  and  the  package  it  describes,  will undoubtedly contain bugs and other problems.
       Please report such in the  category  struct  ::  tree  of  the  Tcllib  SF  Trackers  [http://source -
       forge.net/tracker/? group_id=12883].   Please  also report any ideas for enhancements you may have for
       either package and/or documentation.

KEYWORDS
       breadth-first, depth-first, in-order, node, post-order, pre-order, serialization, tree

CATEGORY
       Data structures

COPYRIGHT
       Copyright (c) 2002-2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>




struct                                              2.1.1                                    struct::tree(n)