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