1[comment {-*- tcl -*-}] 2[manpage_begin {struct::tree v1} n 1.2.2] 3[copyright {2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>}] 4[moddesc {Tcl Data Structures}] 5[titledesc {Create and manipulate tree objects}] 6[category {Data structures}] 7[require Tcl 8.2] 8[require struct::tree [opt 1.2.2]] 9[description] 10[para] 11 12The [cmd ::struct::tree] command creates a new tree object with an 13associated global Tcl command whose name is [arg treeName]. This 14command may be used to invoke various operations on the tree. It has 15the following general form: 16 17[list_begin definitions] 18[call [cmd treeName] [method option] [opt [arg "arg arg ..."]]] 19 20[arg Option] and the [arg arg]s determine the exact behavior of the 21command. 22 23[list_end] 24 25[para] 26 27A tree is a collection of named elements, called nodes, one of which is 28distinguished as a root, along with a relation ("parenthood") that 29places a hierarchical structure on the nodes. (Data Structures and 30Algorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987). In 31addition to maintaining the node relationships, this tree 32implementation allows any number of keyed values to be associated with 33each node. 34 35[para] 36 37The element names can be arbitrary strings. 38 39[para][comment {This comparison (C) 2007 Lars Bergstrom, Bug 1687902}] 40 41A tree is thus similar to an array, but with three important 42differences: 43 44[list_begin enumerated] 45[enum] Trees are accessed through an object command, whereas arrays are 46accessed as variables. (This means trees cannot be local to a procedure.) 47 48[enum] Trees have a hierarchical structure, whereas an array is just an 49unordered collection. 50 51[enum] Each node of a tree has a separate collection of attributes and 52values. This is like an array where every value is a dictionary. 53 54[list_end] 55 56[para] 57 58 59The following commands are possible for tree objects: 60 61[list_begin definitions] 62 63[call [arg treeName] [method append] [arg node] [opt "-key [arg key]"] [arg value]] 64 65Appends a [arg value] to one of the keyed values associated with an 66node. If no [arg key] is specified, the key [const data] is assumed. 67 68 69[call [arg treeName] [method children] [arg node]] 70 71Return a list of the children of [arg node]. 72 73 74[call [arg treeName] [method cut] [arg node]] 75 76Removes the node specified by [arg node] from the tree, but not its 77children. The children of [arg node] are made children of the parent 78of the [arg node], at the index at which [arg node] was located. 79 80 81[call [arg treeName] [method delete] [arg node] [opt "[arg node] ..."]] 82 83Remove the specified nodes from the tree. All of the nodes' children 84will be removed as well to prevent orphaned nodes. 85 86 87[call [arg treeName] [method depth] [arg node]] 88 89Return the number of steps from node [arg node] to the root node. 90 91 92[call [arg treeName] [method destroy]] 93 94Destroy the tree, including its storage space and associated command. 95 96 97[call [arg treeName] [method exists] [arg node]] 98 99Remove true if the specified node exists in the tree. 100 101 102[call [arg treeName] [method get] [arg node] [opt "[option -key] [arg key]"]] 103 104Return the value associated with the key [arg key] for the node 105 106[arg node]. If no key is specified, the key [const data] is assumed. 107 108[call [arg treeName] [method getall] [arg node]] 109 110Returns a serialized list of key/value pairs (suitable for use with 111[lb][cmd {array set}][rb]) for the [arg node]. 112 113 114[call [arg treeName] [method keys] [arg node]] 115 116Returns a list of keys for the [arg node]. 117 118 119[call [arg treeName] [method keyexists] [arg node] [opt "-key [arg key]"]] 120 121Return true if the specified [arg key] exists for the [arg node]. If 122no [arg key] is specified, the key [const data] is assumed. 123 124 125[call [arg treeName] [method index] [arg node]] 126 127Returns the index of [arg node] in its parent's list of children. For 128example, if a node has [term nodeFoo], [term nodeBar], and 129 130[term nodeBaz] as children, in that order, the index of 131 132[term nodeBar] is 1. 133 134 135[call [arg treeName] [method insert] [arg parent] [arg index] [opt "[arg child] [opt "[arg child] ..."]"]] 136 137Insert one or more nodes into the tree as children of the node 138 139[arg parent]. The nodes will be added in the order they are given. If 140[arg parent] is [const root], it refers to the root of the tree. The 141new nodes will be added to the [arg parent] node's child list at the 142index given by [arg index]. The [arg index] can be [const end] in 143which case the new nodes will be added after the current last child. 144 145[para] 146 147If any of the specified children already exist in [arg treeName], 148those nodes will be moved from their original location to the new 149location indicated by this command. 150 151[para] 152 153If no [arg child] is specified, a single node will be added, and a 154name will be generated for the new node. The generated name is of the 155form [emph node][var x], where [var x] is a number. If names are 156specified they must neither contain whitespace nor colons (":"). 157 158[para] 159 160The return result from this command is a list of nodes added. 161 162 163[call [arg treeName] [method isleaf] [arg node]] 164 165Returns true if [arg node] is a leaf of the tree (if [arg node] has no 166children), false otherwise. 167 168 169[call [arg treeName] [method lappend] [arg node] [opt "-key [arg key]"] [arg value]] 170 171Appends a [arg value] (as a list) to one of the keyed values 172associated with an [arg node]. If no [arg key] is specified, the key 173[const data] is assumed. 174 175 176[call [arg treeName] [method move] [arg parent] [arg index] [arg node] [opt "[arg node] ..."]] 177 178Make the specified nodes children of [arg parent], inserting them into 179the parent's child list at the index given by [arg index]. Note that 180the command will take all nodes out of the tree before inserting them 181under the new parent, and that it determines the position to place 182them into after the removal, before the re-insertion. This behaviour 183is important when it comes to moving one or more nodes to a different 184index without changing their parent node. 185 186[call [arg treeName] [method next] [arg node] ] 187 188Return the right sibling of [arg node], or the empty string if 189 190[arg node] was the last child of its parent. 191 192 193[call [arg treeName] [method numchildren] [arg node]] 194 195Return the number of immediate children of [arg node]. 196 197 198[call [arg treeName] [method parent] [arg node]] 199 200Return the parent of [arg node]. 201 202 203[call [arg treeName] [method previous] [arg node] ] 204 205Return the left sibling of [arg node], or the empty string if 206 207[arg node] was the first child of its parent. 208 209 210[call [arg treeName] [method set] [arg node] [opt "[option -key] [arg key]"] [opt [arg value]]] 211 212Set or get one of the keyed values associated with a node. If no key 213is specified, the key [const data] is assumed. Each node that is 214added to a tree has the value "" assigned to the key [const data] 215automatically. A node may have any number of keyed values associated 216with it. If [arg value] is not specified, this command returns the 217current value assigned to the key; if [arg value] is specified, this 218command assigns that value to the key. 219 220 221[call [arg treeName] [method size] [opt [arg node]]] 222 223 224Return a count of the number of descendants of the node [arg node]; if 225no node is specified, [const root] is assumed. 226 227 228[call [arg treeName] [method splice] [arg parent] [arg from] [opt [arg to]] [opt [arg child]]] 229 230Insert a node named [arg child] into the tree as a child of the node 231[arg parent]. If [arg parent] is [const root], it refers to the root 232of the tree. The new node will be added to the parent node's child 233list at the index given by [arg from]. The children of [arg parent] 234which are in the range of the indices [arg from] and [arg to] are made 235children of [arg child]. If the value of [arg to] is not specified it 236defaults to [const end]. If no name is given for [arg child], a name 237will be generated for the new node. The generated name is of the form 238[emph node][var x], where [var x] is a number. The return result 239from this command is the name of the new node. 240 241 242[call [arg treeName] [method swap] [arg node1] [arg node2]] 243 244Swap the position of [arg node1] and [arg node2] in the tree. 245 246 247[call [arg treeName] [method unset] [arg node] [opt "[option -key] [arg key]"]] 248 249Remove a keyed value from the node [arg node]. If no key is 250specified, the key [const data] is assumed. 251 252 253[call [arg treeName] [method walk] [arg node] [opt "[option -order] [arg order]"] [opt "[option -type] [arg type]"] [option -command] [arg cmd]] 254 255Perform a breadth-first or depth-first walk of the tree starting at 256the node [arg node]. The type of walk, breadth-first or depth-first, 257is determined by the value of [arg type]; [const bfs] indicates 258breadth-first, [const dfs] indicates depth-first. Depth-first is the 259default. The order of the walk, pre-, post-, both- or in-order is 260determined by the value of [arg order]; [const pre] indicates 261pre-order, [const post] indicates post-order, [const both] indicates 262both-order and [const in] indicates in-order. Pre-order is the 263default. 264 265[para] 266 267Pre-order walking means that a parent node is visited before any of 268its children. For example, a breadth-first search starting from the 269root will visit the root, followed by all of the root's children, 270followed by all of the root's grandchildren. Post-order walking means 271that a parent node is visited after any of its children. Both-order 272walking means that a parent node is visited before [emph and] after 273any of its children. In-order walking means that a parent node is 274visited after its first child and before the second. This is a 275generalization of in-order walking for binary trees and will do the 276right thing if a binary is walked. The combination of a breadth-first 277walk with in-order is illegal. 278 279[para] 280 281As the walk progresses, the command [arg cmd] will be evaluated at 282each node. Percent substitution will be performed on [arg cmd] before 283evaluation, just as in a [cmd bind] script. The following 284substitutions are recognized: 285 286[list_begin definitions] 287 288[def [const %%]] 289 290Insert the literal % character. 291 292[def [const %t]] 293 294Name of the tree object. 295 296[def [const %n]] 297 298Name of the current node. 299 300[def [const %a]] 301 302Name of the action occurring; one of [const enter], [const leave], 303or [const visit]. [const enter] actions occur during pre-order 304walks; [const leave] actions occur during post-order walks; 305 306[const visit] actions occur during in-order walks. In a both-order 307walk, the command will be evaluated twice for each node; the action is 308[const enter] for the first evaluation, and [const leave] for the 309second. 310 311[list_end] 312[list_end] 313 314[section {BUGS, IDEAS, FEEDBACK}] 315 316This document, and the package it describes, will undoubtedly contain 317bugs and other problems. 318 319Please report such in the category [emph {struct :: tree}] of the 320[uri {http://sourceforge.net/tracker/?group_id=12883} {Tcllib SF Trackers}]. 321 322Please also report any ideas for enhancements you may have for either 323package and/or documentation. 324 325 326[keywords tree] 327[manpage_end] 328