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

NAME

       struct::tree_v1 - Create and manipulate tree objects

SYNOPSIS

       package require Tcl  8.2

       package require struct::tree  ?1.2.2?

       treeName option ?arg arg ...?

       treeName append node ?-key key? value

       treeName children node

       treeName cut node

       treeName delete node ?node ...?

       treeName depth node

       treeName destroy

       treeName exists node

       treeName get node ?-key key?

       treeName getall node

       treeName keys node

       treeName keyexists node ?-key key?

       treeName index node

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

       treeName isleaf node

       treeName lappend node ?-key key? value

       treeName move parent index node ?node ...?

       treeName next node

       treeName numchildren node

       treeName parent node

       treeName previous node

       treeName set node ?-key key? ?value?

       treeName size ?node?

       treeName splice parent from ?to? ?child?

       treeName swap node1 node2

       treeName unset node ?-key key?

       treeName walk node ?-order order? ?-type type? -command cmd

_________________________________________________________________________________________________

DESCRIPTION

       The ::struct::tree 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.

       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.

       The following commands are possible for tree objects:

       treeName append node ?-key key? value
              Appends a value to one of the keyed values associated with an node. If  no  key  is
              specified, the key data is assumed.

       treeName children node
              Return a list of the children of node.

       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 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 key?
              Return the value associated with the key key for  the  node  node.  If  no  key  is
              specified, the key data is assumed.

       treeName getall node
              Returns  a  serialized  list of key/value pairs (suitable for use with [array set])
              for the node.

       treeName keys node
              Returns a list of keys for the node.

       treeName keyexists node ?-key key?
              Return true if the specified key exists for the node. If no key is  specified,  the
              key data is assumed.

       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.

              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 key? value
              Appends  a value (as a list) to one of the keyed values associated with an node. If
              no key is specified, the key data is assumed.

       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 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 set node ?-key key? ?value?
              Set  or get one of the keyed values associated with a node. If no key is specified,
              the key data is assumed.  Each node that is added  to  a  tree  has  the  value  ""
              assigned to the key data automatically.  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.

       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.

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

       treeName unset node ?-key key?
              Removes  a keyed value from the node node.  If no key is specified, the key data is
              assumed.

       treeName walk node ?-order order? ?-type type? -command cmd
              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  is  walked.  The
              combination of a breadth-first walk with in-order is illegal.

              As  the  walk  progresses, the command cmd will be evaluated at each node.  Percent
              substitution will be performed on cmd before evaluation, just as in a bind  script.
              The following substitutions are recognized:

              %%     Insert the literal % character.

              %t     Name of the tree object.

              %n     Name of the current node.

              %a     Name  of the action occurring; one of 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.

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

       tree

CATEGORY

       Data structures

COPYRIGHT

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