1struct::tree(n)               Tcl Data Structures              struct::tree(n)
2
3
4
5______________________________________________________________________________
6

NAME

8       struct::tree - Create and manipulate tree objects
9

SYNOPSIS

11       package require Tcl  8.2
12
13       package require struct::tree  ?2.1.1?
14
15       package require struct::list  ?1.5?
16
17       ::struct::tree ?treeName? ?=|:=|as|deserialize source?
18
19       treeName option ?arg arg ...?
20
21       ::struct::tree::prune
22
23       treeName = sourcetree
24
25       treeName --> desttree
26
27       treeName ancestors node
28
29       treeName append node key value
30
31       treeName attr key
32
33       treeName attr key -nodes list
34
35       treeName attr key -glob globpattern
36
37       treeName attr key -regexp repattern
38
39       treeName children ?-all? node ?filter cmdprefix?
40
41       treeName cut node
42
43       treeName delete node ?node ...?
44
45       treeName depth node
46
47       treeName descendants node ?filter cmdprefix?
48
49       treeName deserialize serialization
50
51       treeName destroy
52
53       treeName exists node
54
55       treeName get node key
56
57       treeName getall node ?pattern?
58
59       treeName keys node ?pattern?
60
61       treeName keyexists node key
62
63       treeName index node
64
65       treeName insert parent index ?child ?child ...??
66
67       treeName isleaf node
68
69       treeName lappend node key value
70
71       treeName leaves
72
73       treeName move parent index node ?node ...?
74
75       treeName next node
76
77       treeName numchildren node
78
79       treeName nodes
80
81       treeName parent node
82
83       treeName previous node
84
85       treeName rename node newname
86
87       treeName rootname
88
89       treeName serialize ?node?
90
91       treeName set node key ?value?
92
93       treeName size ?node?
94
95       treeName splice parent from ?to? ?child?
96
97       treeName swap node1 node2
98
99       treeName unset node key
100
101       treeName walk node ?-order order? ?-type type? loopvar script
102
103       treeName walkproc node ?-order order? ?-type type? cmdprefix
104
105______________________________________________________________________________
106

DESCRIPTION

108       A tree is a collection of named elements, called nodes, one of which is
109       distinguished as a root, along  with  a  relation  ("parenthood")  that
110       places  a hierarchical structure on the nodes. (Data Structures and Al‐
111       gorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987).  In addition
112       to  maintaining the node relationships, this tree implementation allows
113       any number of keyed values to be associated with each node.
114
115       The element names can be arbitrary strings.
116
117       A tree is thus similar to an array, but with  three  important  differ‐
118       ences:
119
120       [1]    Trees are accessed through an object command, whereas arrays are
121              accessed as variables. (This means trees cannot be  local  to  a
122              procedure.)
123
124       [2]    Trees have a hierarchical structure, whereas an array is just an
125              unordered collection.
126
127       [3]    Each node of a tree has a separate collection of attributes  and
128              values. This is like an array where every value is a dictionary.
129
130       Note:  The major version of the package struct has been changed to ver‐
131       sion 2.0, due to backward incompatible changes in the API of this  mod‐
132       ule.  Please  read  the  section Changes for 2.0 for a full list of all
133       changes, incompatible and otherwise.
134

API

136   TREE CLASS API
137       The main commands of the package are:
138
139       ::struct::tree ?treeName? ?=|:=|as|deserialize source?
140              The command creates a new tree object with an associated  global
141              Tcl  command whose name is treeName. This command may be used to
142              invoke various operations on the tree.   It  has  the  following
143              general form:
144
145              treeName option ?arg arg ...?
146                     Option  and  the args determine the exact behavior of the
147                     command.
148
149       If treeName is not specified a unique name will  be  generated  by  the
150       package  itself. If a source is specified the new tree will be initial‐
151       ized to it. For the operators =, :=, and as source  is  interpreted  as
152       the  name of another tree object, and the assignment operator = will be
153       executed. For deserialize the source is a serialized  tree  object  and
154       deserialize will be executed.
155
156       In other words
157
158
159
160                  ::struct::tree mytree = b
161
162
163       is equivalent to
164
165
166
167                  ::struct::tree mytree
168                  mytree = b
169
170
171       and
172
173
174
175                  ::struct::tree mytree deserialize $b
176
177
178       is equivalent to
179
180
181
182                  ::struct::tree mytree
183                  mytree deserialize $b
184
185
186       ::struct::tree::prune
187              This  command  is provided outside of the tree methods, as it is
188              not a tree method per se. It however interacts tightly with  the
189              method  walk. When used in the walk script it causes the traver‐
190              sal to ignore the children of the  node  we  are  currently  at.
191              This  command cannot be used with the traversal modes which look
192              at children before their parent, i.e. post and in. The only  ap‐
193              plicable  orders  of  traversal  are  pre  and both. An error is
194              thrown if the command and chosen order of traversal do not fit.
195
196   TREE OBJECT API
197       Two general observations beforehand:
198
199       [1]    The root node of the tree can be used in  most  places  where  a
200              node  is  asked for. The default name of the rootnode is "root",
201              but this can be changed with  the  method  rename  (see  below).
202              Whatever  the  current name for the root node of the tree is, it
203              can be retrieved by calling the method rootname.
204
205       [2]    The method insert is the only way to create new nodes, and  they
206              are  automatically  added to a parent. A tree object cannot have
207              nodes without a parent, save the root node.
208
209       And now the methods supported by tree objects created by this package:
210
211       treeName = sourcetree
212              This is the assignment operator for tree objects. It copies  the
213              tree  contained in the tree object sourcetree over the tree data
214              in treeName. The old contents of treeName are  deleted  by  this
215              operation.
216
217              This operation is in effect equivalent to
218
219
220
221                  treeName deserialize [sourcetree serialize]
222
223
224       treeName --> desttree
225              This  is  the  reverse  assignment operator for tree objects. It
226              copies the tree contained in the tree object treeName  over  the
227              tree  data  in the object desttree. The old contents of desttree
228              are deleted by this operation.
229
230              This operation is in effect equivalent to
231
232
233
234                  desttree deserialize [treeName serialize]
235
236
237       treeName ancestors node
238              This method extends the method parent and returns  a  list  con‐
239              taining  all ancestor nodes to the specified node. The immediate
240              ancestor, in other words, parent node, is the first  element  in
241              that  list,  its  parent the second element, and so on until the
242              root node is reached, making it the last element of the returned
243              list.
244
245       treeName append node key value
246              Appends  a  value  to one of the keyed values associated with an
247              node. Returns the new value given to the attribute key.
248
249       treeName attr key
250
251       treeName attr key -nodes list
252
253       treeName attr key -glob globpattern
254
255       treeName attr key -regexp repattern
256              This method retrieves the value of the attribute named key,  for
257              all  nodes  in  the tree (matching the restriction specified via
258              one of the possible options) and having the specified attribute.
259
260              The result is a dictionary mapping from node names to the  value
261              of  attribute  key at that node.  Nodes not having the attribute
262              key, or not passing a specified restriction, are not  listed  in
263              the result.
264
265              The possible restrictions are:
266
267              -nodes The value is a list of nodes. Only the nodes mentioned in
268                     this list are searched for the attribute.
269
270              -glob  The value is a glob pattern. Only the nodes in  the  tree
271                     whose  names  match this pattern are searched for the at‐
272                     tribute.
273
274              -regexp
275                     The value is a regular expression. Only the nodes in  the
276                     tree  whose names match this pattern are searched for the
277                     attribute.
278
279
280       treeName children ?-all? node ?filter cmdprefix?
281              Return a list of the children of node.  If the  option  -all  is
282              specified,  then  not  only the direct children, but their chil‐
283              dren, and so on are returned in the result.  If a filter command
284              is  specified  only  those  nodes are listed in the final result
285              which pass the test. The command in cmdprefix is called with two
286              arguments, the name of the tree object, and the name of the node
287              in question. It is executed in the context of the caller and has
288              to  return  a boolean value. Nodes for which the command returns
289              false are removed from the result list before it is returned  to
290              the caller.
291
292              Some examples:
293
294
295
296                  mytree insert root end 0 ; mytree set 0 volume 30
297                  mytree insert root end 1
298                  mytree insert root end 2
299                  mytree insert 0    end 3
300                  mytree insert 0    end 4
301                  mytree insert 4    end 5 ; mytree set 5 volume 50
302                  mytree insert 4    end 6
303
304                  proc vol {t n} {
305                $t keyexists $n volume
306                  }
307                  proc vgt40 {t n} {
308                if {![$t keyexists $n volume]} {return 0}
309                expr {[$t get $n volume] > 40}
310                  }
311
312                  tclsh> lsort [mytree children -all root filter vol]
313                  0 5
314
315                  tclsh> lsort [mytree children -all root filter vgt40]
316                  5
317
318                  tclsh> lsort [mytree children root filter vol]
319                  0
320
321                  tclsh> puts ([lsort [mytree children root filter vgt40]])
322                  ()
323
324
325       treeName cut node
326              Removes  the  node  specified by node from the tree, but not its
327              children.  The children of node are made children of the  parent
328              of the node, at the index at which node was located.
329
330       treeName delete node ?node ...?
331              Removes  the  specified  nodes from the tree.  All of the nodes'
332              children will be removed as well to prevent orphaned nodes.
333
334       treeName depth node
335              Return the number of steps from node node to the root node.
336
337       treeName descendants node ?filter cmdprefix?
338              This method extends the method children and returns a list  con‐
339              taining  all nodes descending from node, and passing the filter,
340              if such was specified.
341
342              This is actually the same as "treeName children -all".   descen‐
343              dants should be prefered, and "children -all" will be deprecated
344              sometime in the future.
345
346       treeName deserialize serialization
347              This is the complement to serialize. It replaces  tree  data  in
348              treeName with the tree described by the serialization value. The
349              old contents of treeName are deleted by this operation.
350
351       treeName destroy
352              Destroy the tree, including its  storage  space  and  associated
353              command.
354
355       treeName exists node
356              Returns true if the specified node exists in the tree.
357
358       treeName get node key
359              Returns the value associated with the key key for the node node.
360
361       treeName getall node ?pattern?
362              Returns  a  dictionary  (suitable for use with [array set]) con‐
363              taining the attribute data for the node.  If the glob pattern is
364              specified only the attributes whose names match the pattern will
365              be part of the dictionary.
366
367       treeName keys node ?pattern?
368              Returns a list of keys for the node.  If the pattern  is  speci‐
369              fied  only  the attributes whose names match the pattern will be
370              part of the returned list. The pattern is a glob pattern.
371
372       treeName keyexists node key
373              Return true if the specified key exists for the node.
374
375       treeName index node
376              Returns the index of node in its parent's list of children.  For
377              example,  if  a  node has nodeFoo, nodeBar, and nodeBaz as chil‐
378              dren, in that order, the index of nodeBar is 1.
379
380       treeName insert parent index ?child ?child ...??
381              Insert one or more nodes into the tree as children of  the  node
382              parent.  The nodes will be added in the order they are given. If
383              parent is root, it refers to the root of the tree. The new nodes
384              will be added to the parent node's child list at the index given
385              by index. The index can be end in which case the new nodes  will
386              be  added  after  the  current  last child.  Indices of the form
387              "end-n" are accepted as well.
388
389              If any of the specified  children  already  exist  in  treeName,
390              those  nodes  will  be moved from their original location to the
391              new location indicated by this command.
392
393              If no child is specified, a single node will  be  added,  and  a
394              name  will  be generated for the new node. The generated name is
395              of the form nodex, where x is a number. If names  are  specified
396              they must neither contain whitespace nor colons (":").
397
398              The return result from this command is a list of nodes added.
399
400       treeName isleaf node
401              Returns true if node is a leaf of the tree (if node has no chil‐
402              dren), false otherwise.
403
404       treeName lappend node key value
405              Appends a value (as a list) to one of the keyed  values  associ‐
406              ated  with an node. Returns the new value given to the attribute
407              key.
408
409       treeName leaves
410              Return a list containing all leaf nodes known to the tree.
411
412       treeName move parent index node ?node ...?
413              Make the specified nodes children of parent, inserting them into
414              the  parent's  child list at the index given by index. Note that
415              the command will take all nodes out of the tree before inserting
416              them  under  the new parent, and that it determines the position
417              to place them into after the removal, before  the  re-insertion.
418              This  behaviour is important when it comes to moving one or more
419              nodes to a different index without changing their parent node.
420
421       treeName next node
422              Return the right sibling of node, or the empty  string  if  node
423              was the last child of its parent.
424
425       treeName numchildren node
426              Return the number of immediate children of node.
427
428       treeName nodes
429              Return a list containing all nodes known to the tree.
430
431       treeName parent node
432              Return the parent of node.
433
434       treeName previous node
435              Return the left sibling of node, or the empty string if node was
436              the first child of its parent.
437
438       treeName rename node newname
439              Renames the node node to newname. An error is thrown  if  either
440              the node does not exist, or a node with name newname does exist.
441              The result of the command is the new name of the node.
442
443       treeName rootname
444              Returns the name of the root node of the tree.
445
446       treeName serialize ?node?
447              This method serializes the sub-tree starting at node.  In  other
448              words  it  returns  a  tcl  value completely describing the tree
449              starting at node.  This allows, for  example,  the  transfer  of
450              tree objects (or parts thereof) over arbitrary channels, persis‐
451              tence, etc.  This method is also the basis  for  both  the  copy
452              constructor and the assignment operator.
453
454              The  result of this method has to be semantically identical over
455              all implementations of the tree interface. This is what will en‐
456              able  us  to copy tree data between different implementations of
457              the same interface.
458
459              The result is a list containing containing a multiple  of  three
460              elements.  It  is  like a serialized array except that there are
461              two values following each key. They are the names of  the  nodes
462              in  the  serialized  tree. The two values are a reference to the
463              parent node and the attribute data, in this order.
464
465              The reference to the parent node is the  empty  string  for  the
466              root  node  of  the tree. For all other nodes it is the index of
467              the parent node in the list. This means that they are  integers,
468              greater than or equal to zero, less than the length of the list,
469              and multiples of three.  The order of the nodes in the  list  is
470              important  insofar  as  it  is  used to reconstruct the lists of
471              children for each node. The children of a node have to be listed
472              in  the  serialization  in  the same order as they are listed in
473              their parent in the tree.
474
475              The attribute data of a node is a dictionary,  i.e.  a  list  of
476              even  length  containing  a serialized array. For a node without
477              attribute data the dictionary is the empty list.
478
479              Note: While the current implementation returns the root node  as
480              the  first  element  of  the  list, followed by its children and
481              their children in a depth-first traversal this is not  necessar‐
482              ily  true  for  other  implementations.   The only information a
483              reader of the serialized data can rely on for the  structure  of
484              the  tree  is that the root node is signaled by the empty string
485              for the parent reference, that all other nodes  refer  to  their
486              parent through the index in the list, and that children occur in
487              the same order as in their parent.
488
489
490
491               A possible serialization for the tree structure
492
493                           +- d
494                     +- a -+
495               root -+- b  +- e
496                     +- c
497               is
498
499               {root {} {} a 0 {} d 3 {} e 3 {} b 0 {} c 0 {}}
500
501               The above assumes that none of the nodes have attributes.
502
503
504       treeName set node key ?value?
505              Set or get one of the keyed values associated  with  a  node.  A
506              node may have any number of keyed values associated with it.  If
507              value is not specified, this command returns the  current  value
508              assigned to the key; if value is specified, this command assigns
509              that value to the key, and returns it.
510
511       treeName size ?node?
512              Return a count of the number of descendants of the node node; if
513              no node is specified, root is assumed.
514
515       treeName splice parent from ?to? ?child?
516              Insert  a  node named child into the tree as a child of the node
517              parent. If parent is root, it refers to the root  of  the  tree.
518              The  new  node  will be added to the parent node's child list at
519              the index given by from.  The children of parent  which  are  in
520              the range of the indices from and to are made children of child.
521              If the value of to is not specified it defaults to end.   If  no
522              name  is  given  for child, a name will be generated for the new
523              node.  The generated name is of the form nodex,  where  x  is  a
524              number.   The return result from this command is the name of the
525              new node.
526
527              The arguments from and to are regular list  indices,  i.e.   the
528              form "end-n" is accepted as well.
529
530       treeName swap node1 node2
531              Swap the position of node1 and node2 in the tree.
532
533       treeName unset node key
534              Removes  a  keyed  value  from the node node. The method will do
535              nothing if the key does not exist.
536
537       treeName walk node ?-order order? ?-type type? loopvar script
538              Perform a breadth-first or depth-first walk of the tree starting
539              at  the  node  node.   The type of walk, breadth-first or depth-
540              first, is  determined  by  the  value  of  type;  bfs  indicates
541              breadth-first,  dfs  indicates  depth-first.  Depth-first is the
542              default. The order of the walk, pre-, post-, both-  or  in-order
543              is  determined  by  the value of order; pre indicates pre-order,
544              post indicates post-order, both indicates both-order and in  in‐
545              dicates in-order. Pre-order is the default.
546
547              Pre-order walking means that a parent node is visited before any
548              of its children.  For example, a breadth-first  search  starting
549              from the root will visit the root, followed by all of the root's
550              children, followed by all of the root's grandchildren.  Post-or‐
551              der walking means that a parent node is visited after any of its
552              children. Both-order walking means that a parent node is visited
553              before  and  after  any  of its children. In-order walking means
554              that a parent node is visited after its first child  and  before
555              the second. This is a generalization of in-order walking for bi‐
556              nary trees and will do the right  thing  if  a  binary  tree  is
557              walked. The combination of a breadth-first walk with in-order is
558              illegal.
559
560              As the walk progresses, the script will  be  evaluated  at  each
561              node. The evaluation takes place in the context of the caller of
562              the method.  Regarding loop variables, these are listed in loop‐
563              var. If one only one variable is specified it will be set to the
564              id of the node. When two variables are specified,  i.e.  loopvar
565              is  a  true list, then the first variable will be set to the ac‐
566              tion performed at the node, and the other to the id of the  node
567              itself.   All  loop  variables are created in the context of the
568              caller.
569
570              There are three possible actions: enter, leave, or visit.  enter
571              actions occur during pre-order walks; leave actions occur during
572              post-order walks; visit actions occur during in-order walks.  In
573              a  both-order walk, the command will be evaluated twice for each
574              node; the action is enter for the first  evaluation,  and  leave
575              for the second.
576
577              Note: The enter action for a node is always performed before the
578              walker will look at the children of that node. This  means  that
579              changes  made by the script to the children of the node will im‐
580              mediately influence the walker and the steps it will take.
581
582              Any other manipulation, for example of nodes higher in the  tree
583              (i.e  already  visited), or upon leaving will have undefined re‐
584              sults. They may succeed, error out, silently compute  the  wrong
585              result, or anything in between.
586
587              At last a small table showing the relationship between the vari‐
588              ous options and the possible actions.
589
590
591
592               order       type    actions         notes
593               -----       ----    -----           -----
594               pre         dfs     enter           parent before children
595               post        dfs     leave           parent after children
596               in          dfs     visit           parent between first and second child.
597               both        dfs     enter, leave    parent before and after children
598               -----       ----    -----           -----
599               pre         bfs     enter           parent before children
600               post        bfs     leave           parent after children
601               in          bfs             -- illegal --
602               both        bfs     enter, leave    parent before and after children
603               -----       ----    -----           -----
604
605
606       Note the command ::struct::tree::prune. This command can be used in the
607       walk  script to force the command to ignore the children of the node we
608       are currently at. It will throw an error if the order of  traversal  is
609       either  post  or in as these modes visit the children before their par‐
610       ent, making pruning non-sensical.
611
612       treeName walkproc node ?-order order? ?-type type? cmdprefix
613              This method is like method walk in all  essentials,  except  the
614              interface to the user code. This method invokes a command prefix
615              with three additional arguments (tree, node,  and  action),  in‐
616              stead  of  evaluating  a  script and passing the node via a loop
617              variable.
618
619   CHANGES FOR 2.0
620       The following noteworthy changes have occurred:
621
622       [1]    The API for accessing attributes and their values has been  sim‐
623              plified.
624
625              All  functionality  regarding  the  default attribute "data" has
626              been removed. This default attribute does not exist anymore. All
627              accesses to attributes have to specify the name of the attribute
628              in question. This backward incompatible  change  allowed  us  to
629              simplify the signature of all methods handling attributes.
630
631              Especially the flag -key is not required anymore, even more, its
632              use is now forbidden. Please  read  the  documentation  for  the
633              methods  set, get, getall, unset, append, lappend, keyexists and
634              keys for a description of the new API's.
635
636       [2]    The methods keys and getall now take an optional  pattern  argu‐
637              ment  and will return only attribute data for keys matching this
638              pattern.
639
640       [3]    Nodes can now be renamed. See the documentation for  the  method
641              rename.
642
643       [4]    The structure has been extended with API's for the serialization
644              and deserialization of tree objects, and a number of  operations
645              based on them (tree assignment, copy construction).
646
647              Please read the documentation for the methods serialize, deseri‐
648              alize, =, and -->, and the documentation on the construction  of
649              tree objects.
650
651              Beyond  the  copying  of whole tree objects these new API's also
652              enable the transfer of tree objects over arbitrary channels  and
653              for easy persistence.
654
655       [5]    The walker API has been streamlined and made more similar to the
656              command foreach. In detail:
657
658              •      The superfluous option -command has been removed.
659
660              •      Ditto for the place holders. Instead of the  placeholders
661                     two  loop  variables have to be specified to contain node
662                     and action information.
663
664              •      The old command argument has been documented as a  script
665                     now, which it was in the past too.
666
667              •      The  fact that enter actions are called before the walker
668                     looks at the children of a node has been documented  now.
669                     In other words it is now officially allowed to manipulate
670                     the list of children  for  a  node  under  these  circum‐
671                     stances.  It  has  been made clear that changes under any
672                     other circumstances will  have  undefined  results,  from
673                     silently computing the wrong result to erroring out.
674
675       [6]    A  new  method, attr, was added allowing the query and retrieval
676              of attribute data without regard to the node relationship.
677
678       [7]    The method children has been extended with the ability to select
679              from  the  children  of the node based on an arbitrary filtering
680              criterium. Another extension is the ability to look not only  at
681              the immediate children of the node, but the whole tree below it.
682

EXAMPLES

684       The following example demonstrates the creation of new nodes:
685
686
687                  mytree insert root end 0   ; # Create node 0, as child of the root
688                  mytree insert root end 1 2 ; # Ditto nodes 1 & 2
689                  mytree insert 0    end 3   ; # Now create node 3 as child of node 0
690                  mytree insert 0    end     ; # Create another child of 0, with a
691                  #                              generated name. The name is returned
692                  #                              as the result of the command.
693
694

BUGS, IDEAS, FEEDBACK

696       This  document,  and the package it describes, will undoubtedly contain
697       bugs and other problems.  Please report such in the category struct  ::
698       tree  of  the  Tcllib  Trackers [http://core.tcl.tk/tcllib/reportlist].
699       Please also report any ideas for enhancements you may have  for  either
700       package and/or documentation.
701
702       When proposing code changes, please provide unified diffs, i.e the out‐
703       put of diff -u.
704
705       Note further that  attachments  are  strongly  preferred  over  inlined
706       patches.  Attachments  can  be  made  by  going to the Edit form of the
707       ticket immediately after its creation, and  then  using  the  left-most
708       button in the secondary navigation bar.
709

KEYWORDS

711       breadth-first,  depth-first, in-order, node, post-order, pre-order, se‐
712       rialization, tree
713

CATEGORY

715       Data structures
716
718       Copyright (c) 2002-2004,2012 Andreas Kupries <andreas_kupries@users.sourceforge.net>
719
720
721
722
723tcllib                               2.1.1                     struct::tree(n)
Impressum