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