Provided by: tcllib_1.21+dfsg-1_all bug

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  Structures 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  incompatible  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 following 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 interpreted as the name of another tree object, and the assignment operator =
       will  be  executed. For deserialize 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 (matching 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 command 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 ...?
              Removes  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
              Returns 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  nodeFoo, 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 moving 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 parent.

       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 parent.

       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 implementations of the same interface.

              The result is a list containing containing a multiple of three elements. It is like
              a serialized 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  serialized  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
              Removes  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 example, 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 combination 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  variables  are  created  in  the
              context of the caller.

              There  are  three  possible  actions:  enter, leave, or visit.  enter actions occur
              during pre-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 children 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         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         bfs     enter           parent before children
               post        bfs     leave           parent after children
               in          bfs             -- illegal --
               both        bfs     enter, leave    parent before and after children
               -----       ----    -----           -----

       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 documentation 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 computing 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  Trackers
       [http://core.tcl.tk/tcllib/reportlist].  Please also report any ideas for enhancements you
       may have for either package and/or documentation.

       When proposing code changes, please provide unified diffs, i.e the output of diff -u.

       Note further that attachments are strongly preferred over inlined patches. Attachments can
       be  made  by going to the Edit form of the ticket immediately after its creation, and then
       using the left-most button in the secondary navigation bar.

KEYWORDS

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

CATEGORY

       Data structures

COPYRIGHT

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