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
161 is equivalent to
164 ::struct::tree mytree
168 mytree = b
169 and
172 ::struct::tree mytree deserialize $b
176 is equivalent to
179 ::struct::tree mytree
183 mytree deserialize $b
184 ::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
193 applicable orders of traversal are pre and both. An error is
194 thrown if the command and chosen order of traversal do not fit.
195 TREE OBJECT API
197 Two general observations beforehand:
198 [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 [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 And now the methods supported by tree objects created by this package:
210 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 This operation is in effect equivalent to
218 treeName deserialize [sourcetree serialize]
222 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 This operation is in effect equivalent to
231 desttree deserialize [treeName serialize]
235 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 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 treeName attr key
250 treeName attr key -nodes list
252 treeName attr key -glob globpattern
254 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 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 The possible restrictions are:
266 -nodes The value is a list of nodes. Only the nodes mentioned in
268 this list are searched for the attribute.
269 -glob The value is a glob pattern. Only the nodes in the tree
271 whose names match this pattern are searched for the
272 attribute.
273 -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 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 Some examples:
293 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 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 tclsh> lsort [mytree children -all root filter vol]
313 0 5
314 tclsh> lsort [mytree children -all root filter vgt40]
316 5
317 tclsh> lsort [mytree children root filter vol]
319 0
320 tclsh> puts ([lsort [mytree children root filter vgt40]])
322 ()
323 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 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 treeName depth node
335 Return the number of steps from node node to the root node.
336 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 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 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 treeName destroy
352 Destroy the tree, including its storage space and associated
353 command.
354 treeName exists node
356 Returns true if the specified node exists in the tree.
357 treeName get node key
359 Returns the value associated with the key key for the node node.
360 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 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 treeName keyexists node key
373 Return true if the specified key exists for the node.
374 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 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 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 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 The return result from this command is a list of nodes added.
399 treeName isleaf node
401 Returns true if node is a leaf of the tree (if node has no chil‐
402 dren), false otherwise.
403 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 treeName leaves
410 Return a list containing all leaf nodes known to the tree.
411 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 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 treeName numchildren node
426 Return the number of immediate children of node.
427 treeName nodes
429 Return a list containing all nodes known to the tree.
430 treeName parent node
432 Return the parent of node.
433 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 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 treeName rootname
444 Returns the name of the root node of the tree.
445 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 The result of this method has to be semantically identical over
455 all implementations of the tree interface. This is what will
456 enable us to copy tree data between different implementations of
457 the same interface.
458 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 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 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 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 A possible serialization for the tree structure
492 +- d
494 +- a -+
495 root -+- b +- e
496 +- c
497 is
498 {root {} {} a 0 {} d 3 {} e 3 {} b 0 {} c 0 {}}
500 The above assumes that none of the nodes have attributes.
502 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 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 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 The arguments from and to are regular list indices, i.e. the
528 form "end-n" is accepted as well.
529 treeName swap node1 node2
531 Swap the position of node1 and node2 in the tree.
532 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 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
545 indicates in-order. Pre-order is the default.
546 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-
551 order walking means that a parent node is visited after any of
552 its children. Both-order walking means that a parent node is
553 visited before and after any of its children. In-order walking
554 means that a parent node is visited after its first child and
555 before the second. This is a generalization of in-order walking
556 for binary 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 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
566 action performed at the node, and the other to the id of the
567 node itself. All loop variables are created in the context of
568 the caller.
569 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 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
580 immediately influence the walker and the steps it will take.
581 Any other manipulation, for example of nodes higher in the tree
583 (i.e already visited), or upon leaving will have undefined
584 results. They may succeed, error out, silently compute the wrong
585 result, or anything in between.
586 At last a small table showing the relationship between the vari‐
588 ous options and the possible actions.
589 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 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 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),
616 instead of evaluating a script and passing the node via a loop
617 variable.
618 CHANGES FOR 2.0
620 The following noteworthy changes have occurred:
621 [1] The API for accessing attributes and their values has been sim‐
623 plified.
624 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 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 [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 [3] Nodes can now be renamed. See the documentation for the method
641 rename.
642 [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 Please read the documentation for the methods serialize, deseri‐
648 alize, =, and -->, and the documentation on the construction of
649 tree objects.
650 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 [5] The walker API has been streamlined and made more similar to the
656 command foreach. In detail:
657 · The superfluous option -command has been removed.
659 · 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 · The old command argument has been documented as a script
665 now, which it was in the past too.
666 · 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 [6] A new method, attr, was added allowing the query and retrieval
676 of attribute data without regard to the node relationship.
677 [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
684 The following example demonstrates the creation of new nodes:
685 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
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 When proposing code changes, please provide unified diffs, i.e the out‐
703 put of diff -u.
704 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
711 breadth-first, depth-first, in-order, node, post-order, pre-order,
712 serialization, tree
713
715 Data structures
716
718 Copyright (c) 2002-2004,2012 Andreas Kupries <andreas_kupries@users.sourceforge.net>
719tcllib 2.1.1 struct::tree(n)