1struct::tree(n) Tcl Data Structures struct::tree(n)
2______________________________________________________________________________
6
8 struct::tree - Create and manipulate tree objects
9
11 package require Tcl 8.2
12 package require struct::tree ?2.1.1?
14 package require struct::list ?1.5?
16 ::struct::tree ?treeName? ?=|:=|as|deserialize source?
18 treeName option ?arg arg ...?
20 ::struct::tree::prune
22 treeName = sourcetree
24 treeName --> desttree
26 treeName ancestors node
28 treeName append node key value
30 treeName attr key
32 treeName attr key -nodes list
34 treeName attr key -glob globpattern
36 treeName attr key -regexp repattern
38 treeName children ?-all? node ?filter cmdprefix?
40 treeName cut node
42 treeName delete node ?node ...?
44 treeName depth node
46 treeName descendants node ?filter cmdprefix?
48 treeName deserialize serialization
50 treeName destroy
52 treeName exists node
54 treeName get node key
56 treeName getall node ?pattern?
58 treeName keys node ?pattern?
60 treeName keyexists node key
62 treeName index node
64 treeName insert parent index ?child ?child ...??
66 treeName isleaf node
68 treeName lappend node key value
70 treeName leaves
72 treeName move parent index node ?node ...?
74 treeName next node
76 treeName numchildren node
78 treeName nodes
80 treeName parent node
82 treeName previous node
84 treeName rename node newname
86 treeName rootname
88 treeName serialize ?node?
90 treeName set node key ?value?
92 treeName size ?node?
94 treeName splice parent from ?to? ?child?
96 treeName swap node1 node2
98 treeName unset node key
100 treeName walk node ?-order order? ?-type type? loopvar script
102 treeName walkproc node ?-order order? ?-type type? cmdprefix
104_________________________________________________________________
106
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
111 Algorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987). In addi‐
112 tion to maintaining the node relationships, this tree implementation
113 allows any number of keyed values to be associated with each node.
114 The element names can be arbitrary strings.
116 A tree is thus similar to an array, but with three important differ‐
118 ences:
119 [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 [2] Trees have a hierarchical structure, whereas an array is just an
125 unordered collection.
126 [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 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
136 TREE CLASS API
137 The main commands of the package are:
138 ::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 treeName option ?arg arg ...?
146 Option and the args determine the exact behavior of the
147 command.
148 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 In other words
157 ::struct::tree mytree = b
160 is equivalent to
163 ::struct::tree mytree
166 mytree = b
167 and
170 ::struct::tree mytree deserialize $b
173 is equivalent to
176 ::struct::tree mytree
179 mytree deserialize $b
180 ::struct::tree::prune
183 This command is provided outside of the tree methods, as it is
184 not a tree method per se. It however interacts tightly with the
185 method walk. When used in the walk script it causes the traver‐
186 sal to ignore the children of the node we are currently at.
187 This command cannot be used with the traversal modes which look
188 at children before their parent, i.e. post and in. The only
189 applicable orders of traversal are pre and both. An error is
190 thrown if the command and chosen order of traversal do not fit.
191 TREE OBJECT API
193 Two general observations beforehand:
194 [1] The root node of the tree can be used in most places where a
196 node is asked for. The default name of the rootnode is "root",
197 but this can be changed with the method rename (see below).
198 Whatever the current name for the root node of the tree is, it
199 can be retrieved by calling the method rootname.
200 [2] The method insert is the only way to create new nodes, and they
202 are automatically added to a parent. A tree object cannot have
203 nodes without a parent, save the root node.
204 And now the methods supported by tree objects created by this package:
206 treeName = sourcetree
208 This is the assignment operator for tree objects. It copies the
209 tree contained in the tree object sourcetree over the tree data
210 in treeName. The old contents of treeName are deleted by this
211 operation.
212 This operation is in effect equivalent to
214 treeName deserialize [sourcetree serialize]
217 treeName --> desttree
220 This is the reverse assignment operator for tree objects. It
221 copies the tree contained in the tree object treeName over the
222 tree data in the object desttree. The old contents of desttree
223 are deleted by this operation.
224 This operation is in effect equivalent to
226 desttree deserialize [treeName serialize]
229 treeName ancestors node
232 This method extends the method parent and returns a list con‐
233 taining all ancestor nodes to the specified node. The immediate
234 ancestor, in other words, parent node, is the first element in
235 that list, its parent the second element, and so on until the
236 root node is reached, making it the last element of the returned
237 list.
238 treeName append node key value
240 Appends a value to one of the keyed values associated with an
241 node. Returns the new value given to the attribute key.
242 treeName attr key
244 treeName attr key -nodes list
246 treeName attr key -glob globpattern
248 treeName attr key -regexp repattern
250 This method retrieves the value of the attribute named key, for
251 all nodes in the tree (matching the restriction specified via
252 one of the possible options) and having the specified attribute.
253 The result is a dictionary mapping from node names to the value
255 of attribute key at that node. Nodes not having the attribute
256 key, or not passing a specified restriction, are not listed in
257 the result.
258 The possible restrictions are:
260 -nodes The value is a list of nodes. Only the nodes mentioned in
262 this list are searched for the attribute.
263 -glob The value is a glob pattern. Only the nodes in the tree
265 whose names match this pattern are searched for the
266 attribute.
267 -regexp
269 The value is a regular expression. Only the nodes in the
270 tree whose names match this pattern are searched for the
271 attribute.
272 treeName children ?-all? node ?filter cmdprefix?
275 Return a list of the children of node. If the option -all is
276 specified, then not only the direct children, but their chil‐
277 dren, and so on are returned in the result. If a filter command
278 is specified only those nodes are listed in the final result
279 which pass the test. The command in cmdprefix is called with two
280 arguments, the name of the tree object, and the name of the node
281 in question. It is executed in the context of the caller and has
282 to return a boolean value. Nodes for which the command returns
283 false are removed from the result list before it is returned to
284 the caller.
285 Some examples:
287 mytree insert root end 0 ; mytree set 0 volume 30
290 mytree insert root end 1
291 mytree insert root end 2
292 mytree insert 0 end 3
293 mytree insert 0 end 4
294 mytree insert 4 end 5 ; mytree set 5 volume 50
295 mytree insert 4 end 6
296 proc vol {t n} {
298 $t keyexists $n volume
299 }
300 proc vgt40 {t n} {
301 if {![$t keyexists $n volume]} {return 0}
302 expr {[$t get $n volume] > 40}
303 }
304 tclsh> lsort [mytree children -all root filter vol]
306 0 5
307 tclsh> lsort [mytree children -all root filter vgt40]
309 5
310 tclsh> lsort [mytree children root filter vol]
312 0
313 tclsh> puts ([lsort [mytree children root filter vgt40]])
315 ()
316 treeName cut node
319 Removes the node specified by node from the tree, but not its
320 children. The children of node are made children of the parent
321 of the node, at the index at which node was located.
322 treeName delete node ?node ...?
324 Remove the specified nodes from the tree. All of the nodes'
325 children will be removed as well to prevent orphaned nodes.
326 treeName depth node
328 Return the number of steps from node node to the root node.
329 treeName descendants node ?filter cmdprefix?
331 This method extends the method children and returns a list con‐
332 taining all nodes descending from node, and passing the filter,
333 if such was specified.
334 This is actually the same as "treeName children -all". descen‐
336 dants should be prefered, and "children -all" will be deprecated
337 sometime in the future.
338 treeName deserialize serialization
340 This is the complement to serialize. It replaces tree data in
341 treeName with the tree described by the serialization value. The
342 old contents of treeName are deleted by this operation.
343 treeName destroy
345 Destroy the tree, including its storage space and associated
346 command.
347 treeName exists node
349 Remove true if the specified node exists in the tree.
350 treeName get node key
352 Returns the value associated with the key key for the node node.
353 treeName getall node ?pattern?
355 Returns a dictionary (suitable for use with [array set]) con‐
356 taining the attribute data for the node. If the glob pattern is
357 specified only the attributes whose names match the pattern will
358 be part of the dictionary.
359 treeName keys node ?pattern?
361 Returns a list of keys for the node. If the pattern is speci‐
362 fied only the attributes whose names match the pattern will be
363 part of the returned list. The pattern is a glob pattern.
364 treeName keyexists node key
366 Return true if the specified key exists for the node.
367 treeName index node
369 Returns the index of node in its parent's list of children. For
370 example, if a node has nodeFoo, nodeBar, and nodeBaz as chil‐
371 dren, in that order, the index of nodeBar is 1.
372 treeName insert parent index ?child ?child ...??
374 Insert one or more nodes into the tree as children of the node
375 parent. The nodes will be added in the order they are given. If
376 parent is root, it refers to the root of the tree. The new nodes
377 will be added to the parent node's child list at the index given
378 by index. The index can be end in which case the new nodes will
379 be added after the current last child. Indices of the form
380 "end-n" are accepted as well.
381 If any of the specified children already exist in treeName,
383 those nodes will be moved from their original location to the
384 new location indicated by this command.
385 If no child is specified, a single node will be added, and a
387 name will be generated for the new node. The generated name is
388 of the form nodex, where x is a number. If names are specified
389 they must neither contain whitespace nor colons (":").
390 The return result from this command is a list of nodes added.
392 treeName isleaf node
394 Returns true if node is a leaf of the tree (if node has no chil‐
395 dren), false otherwise.
396 treeName lappend node key value
398 Appends a value (as a list) to one of the keyed values associ‐
399 ated with an node. Returns the new value given to the attribute
400 key.
401 treeName leaves
403 Return a list containing all leaf nodes known to the tree.
404 treeName move parent index node ?node ...?
406 Make the specified nodes children of parent, inserting them into
407 the parent's child list at the index given by index. Note that
408 the command will take all nodes out of the tree before inserting
409 them under the new parent, and that it determines the position
410 to place them into after the removal, before the re-insertion.
411 This behaviour is important when it comes to moving one or more
412 nodes to a different index without changing their parent node.
413 treeName next node
415 Return the right sibling of node, or the empty string if node
416 was the last child of its parent.
417 treeName numchildren node
419 Return the number of immediate children of node.
420 treeName nodes
422 Return a list containing all nodes known to the tree.
423 treeName parent node
425 Return the parent of node.
426 treeName previous node
428 Return the left sibling of node, or the empty string if node was
429 the first child of its parent.
430 treeName rename node newname
432 Renames the node node to newname. An error is thrown if either
433 the node does not exist, or a node with name newname does exist.
434 The result of the command is the new name of the node.
435 treeName rootname
437 Returns the name of the root node of the tree.
438 treeName serialize ?node?
440 This method serializes the sub-tree starting at node. In other
441 words it returns a tcl value completely describing the tree
442 starting at node. This allows, for example, the transfer of
443 tree objects (or parts thereof) over arbitrary channels, persis‐
444 tence, etc. This method is also the basis for both the copy
445 constructor and the assignment operator.
446 The result of this method has to be semantically identical over
448 all implementations of the tree interface. This is what will
449 enable us to copy tree data between different implementations of
450 the same interface.
451 The result is a list containing containing a multiple of three
453 elements. It is like a serialized array except that there are
454 two values following each key. They are the names of the nodes
455 in the serialized tree. The two values are a reference to the
456 parent node and the attribute data, in this order.
457 The reference to the parent node is the empty string for the
459 root node of the tree. For all other nodes it is the index of
460 the parent node in the list. This means that they are integers,
461 greater than or equal to zero, less than the length of the list,
462 and multiples of three. The order of the nodes in the list is
463 important insofar as it is used to reconstruct the lists of
464 children for each node. The children of a node have to be listed
465 in the serialization in the same order as they are listed in
466 their parent in the tree.
467 The attribute data of a node is a dictionary, i.e. a list of
469 even length containing a serialized array. For a node without
470 attribute data the dictionary is the empty list.
471 Note: While the current implementation returns the root node as
473 the first element of the list, followed by its children and
474 their children in a depth-first traversal this is not necessar‐
475 ily true for other implementations. The only information a
476 reader of the serialized data can rely on for the structure of
477 the tree is that the root node is signaled by the empty string
478 for the parent reference, that all other nodes refer to their
479 parent through the index in the list, and that children occur in
480 the same order as in their parent.
481 A possible serialization for the tree structure
484 +- d
486 +- a -+
487 root -+- b +- e
488 +- c
489 is
490 {root {} {} a 0 {} d 3 {} e 3 {} b 0 {} c 0 {}}
492 The above assumes that none of the nodes have attributes.
494 treeName set node key ?value?
497 Set or get one of the keyed values associated with a node. A
498 node may have any number of keyed values associated with it. If
499 value is not specified, this command returns the current value
500 assigned to the key; if value is specified, this command assigns
501 that value to the key, and returns it.
502 treeName size ?node?
504 Return a count of the number of descendants of the node node; if
505 no node is specified, root is assumed.
506 treeName splice parent from ?to? ?child?
508 Insert a node named child into the tree as a child of the node
509 parent. If parent is root, it refers to the root of the tree.
510 The new node will be added to the parent node's child list at
511 the index given by from. The children of parent which are in
512 the range of the indices from and to are made children of child.
513 If the value of to is not specified it defaults to end. If no
514 name is given for child, a name will be generated for the new
515 node. The generated name is of the form nodex, where x is a
516 number. The return result from this command is the name of the
517 new node.
518 The arguments from and to are regular list indices, i.e. the
520 form "end-n" is accepted as well.
521 treeName swap node1 node2
523 Swap the position of node1 and node2 in the tree.
524 treeName unset node key
526 Remove a keyed value from the node node. The method will do
527 nothing if the key does not exist.
528 treeName walk node ?-order order? ?-type type? loopvar script
530 Perform a breadth-first or depth-first walk of the tree starting
531 at the node node. The type of walk, breadth-first or depth-
532 first, is determined by the value of type; bfs indicates
533 breadth-first, dfs indicates depth-first. Depth-first is the
534 default. The order of the walk, pre-, post-, both- or in-order
535 is determined by the value of order; pre indicates pre-order,
536 post indicates post-order, both indicates both-order and in
537 indicates in-order. Pre-order is the default.
538 Pre-order walking means that a parent node is visited before any
540 of its children. For example, a breadth-first search starting
541 from the root will visit the root, followed by all of the root's
542 children, followed by all of the root's grandchildren. Post-
543 order walking means that a parent node is visited after any of
544 its children. Both-order walking means that a parent node is
545 visited before and after any of its children. In-order walking
546 means that a parent node is visited after its first child and
547 before the second. This is a generalization of in-order walking
548 for binary trees and will do the right thing if a binary tree is
549 walked. The combination of a breadth-first walk with in-order is
550 illegal.
551 As the walk progresses, the script will be evaluated at each
553 node. The evaluation takes place in the context of the caller of
554 the method. Regarding loop variables, these are listed in loop‐
555 var. If one only one variable is specified it will be set to the
556 id of the node. When two variables are specified, i.e. loopvar
557 is a true list, then the first variable will be set to the
558 action performed at the node, and the other to the id of the
559 node itself. All loop variables are created in the context of
560 the caller.
561 There are three possible actions: enter, leave, or visit. enter
563 actions occur during pre-order walks; leave actions occur during
564 post-order walks; visit actions occur during in-order walks. In
565 a both-order walk, the command will be evaluated twice for each
566 node; the action is enter for the first evaluation, and leave
567 for the second.
568 Note: The enter action for a node is always performed before the
570 walker will look at the children of that node. This means that
571 changes made by the script to the children of the node will
572 immediately influence the walker and the steps it will take.
573 Any other manipulation, for example of nodes higher in the tree
575 (i.e already visited), or upon leaving will have undefined
576 results. They may succeed, error out, silently compute the wrong
577 result, or anything in between.
578 At last a small table showing the relationship between the vari‐
580 ous options and the possible actions.
581 order type actions notes
584 ----- ---- ----- -----
585 pre dfs enter parent before children
586 post dfs leave parent after children
587 in dfs visit parent between first and second child.
588 both dfs enter, leave parent before and after children
589 ----- ---- ----- -----
590 pre bfs enter parent before children
591 post bfs leave parent after children
592 in bfs -- illegal --
593 both bfs enter, leave parent before and after children
594 ----- ---- ----- -----
595 Note the command ::struct::tree::prune. This command can be used
598 in the walk script to force the command to ignore the children
599 of the node we are currently at. It will throw an error if the
600 order of traversal is either post or in as these modes visit the
601 children before their parent, making pruning non-sensical.
602 treeName walkproc node ?-order order? ?-type type? cmdprefix
604 This method is like method walk in all essentials, except the
605 interface to the user code. This method invokes a command prefix
606 with three additional arguments (tree, node, and action),
607 instead of evaluating a script and passing the node via a loop
608 variable.
609 CHANGES FOR 2.0
611 The following noteworthy changes have occurred:
612 [1] The API for accessing attributes and their values has been sim‐
614 plified.
615 All functionality regarding the default attribute "data" has
617 been removed. This default attribute does not exist anymore. All
618 accesses to attributes have to specify the name of the attribute
619 in question. This backward incompatible change allowed us to
620 simplify the signature of all methods handling attributes.
621 Especially the flag -key is not required anymore, even more, its
623 use is now forbidden. Please read the documentation for the
624 methods set, get, getall, unset, append, lappend, keyexists and
625 keys for a description of the new API's.
626 [2] The methods keys and getall now take an optional pattern argu‐
628 ment and will return only attribute data for keys matching this
629 pattern.
630 [3] Nodes can now be renamed. See the documentation for the method
632 rename.
633 [4] The structure has been extended with API's for the serialization
635 and deserialization of tree objects, and a number of operations
636 based on them (tree assignment, copy construction).
637 Please read the documentation for the methods serialize, deseri‐
639 alize, =, and -->, and the documentation on the construction of
640 tree objects.
641 Beyond the copying of whole tree objects these new API's also
643 enable the transfer of tree objects over arbitrary channels and
644 for easy persistence.
645 [5] The walker API has been streamlined and made more similar to the
647 command foreach. In detail:
648 · The superfluous option -command has been removed.
650 · Ditto for the place holders. Instead of the placeholders
652 two loop variables have to be specified to contain node
653 and action infromation.
654 · The old command argument has been documented as a script
656 now, which it was in the past too.
657 · The fact that enter actions are called before the walker
659 looks at the children of a node has been documented now.
660 In other words it is now officially allowed to manipulate
661 the list of children for a node under these circum‐
662 stances. It has been made clear that changes under any
663 other circumstances will have undefined results, from
664 silently computing the wrong result to erroring out.
665 [6] A new method, attr, was added allowing the query and retrieval
667 of attribute data without regard to the node relationship.
668 [7] The method children has been extended with the ability to select
670 from the children of the node based on an arbitrary filtering
671 criterium. Another extension is the ability to look not only at
672 the immediate children of the node, but the whole tree below it.
673
675 The following example demonstrates the creation of new nodes:
676 mytree insert root end 0 ; # Create node 0, as child of the root
678 mytree insert root end 1 2 ; # Ditto nodes 1 & 2
679 mytree insert 0 end 3 ; # Now create node 3 as child of node 0
680 mytree insert 0 end ; # Create another child of 0, with a
681 # generated name. The name is returned
682 # as the result of the command.
683
686 This document, and the package it describes, will undoubtedly contain
687 bugs and other problems. Please report such in the category struct ::
688 tree of the Tcllib SF Trackers [http://source‐
689 forge.net/tracker/?group_id=12883]. Please also report any ideas for
690 enhancements you may have for either package and/or documentation.
691
693 breadth-first, depth-first, in-order, node, post-order, pre-order,
694 serialization, tree
695
697 Copyright (c) 2002-2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>
698struct 2.1.1 struct::tree(n)