'\"
'\" Generated from file 'struct_tree1\&.man' by tcllib/doctools with format 'nroff'
'\" Copyright (c) 2002 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>
'\"
.TH "struct::tree_v1" n 1\&.2\&.3 tcllib "Tcl Data Structures"
.\" The -*- nroff -*- definitions below are for supplemental macros used
.\" in Tcl/Tk manual entries.
.\"
.\" .AP type name in/out ?indent?
.\"	Start paragraph describing an argument to a library procedure.
.\"	type is type of argument (int, etc.), in/out is either "in", "out",
.\"	or "in/out" to describe whether procedure reads or modifies arg,
.\"	and indent is equivalent to second arg of .IP (shouldn't ever be
.\"	needed;  use .AS below instead)
.\"
.\" .AS ?type? ?name?
.\"	Give maximum sizes of arguments for setting tab stops.  Type and
.\"	name are examples of largest possible arguments that will be passed
.\"	to .AP later.  If args are omitted, default tab stops are used.
.\"
.\" .BS
.\"	Start box enclosure.  From here until next .BE, everything will be
.\"	enclosed in one large box.
.\"
.\" .BE
.\"	End of box enclosure.
.\"
.\" .CS
.\"	Begin code excerpt.
.\"
.\" .CE
.\"	End code excerpt.
.\"
.\" .VS ?version? ?br?
.\"	Begin vertical sidebar, for use in marking newly-changed parts
.\"	of man pages.  The first argument is ignored and used for recording
.\"	the version when the .VS was added, so that the sidebars can be
.\"	found and removed when they reach a certain age.  If another argument
.\"	is present, then a line break is forced before starting the sidebar.
.\"
.\" .VE
.\"	End of vertical sidebar.
.\"
.\" .DS
.\"	Begin an indented unfilled display.
.\"
.\" .DE
.\"	End of indented unfilled display.
.\"
.\" .SO ?manpage?
.\"	Start of list of standard options for a Tk widget. The manpage
.\"	argument defines where to look up the standard options; if
.\"	omitted, defaults to "options". The options follow on successive
.\"	lines, in three columns separated by tabs.
.\"
.\" .SE
.\"	End of list of standard options for a Tk widget.
.\"
.\" .OP cmdName dbName dbClass
.\"	Start of description of a specific option.  cmdName gives the
.\"	option's name as specified in the class command, dbName gives
.\"	the option's name in the option database, and dbClass gives
.\"	the option's class in the option database.
.\"
.\" .UL arg1 arg2
.\"	Print arg1 underlined, then print arg2 normally.
.\"
.\" .QW arg1 ?arg2?
.\"	Print arg1 in quotes, then arg2 normally (for trailing punctuation).
.\"
.\" .PQ arg1 ?arg2?
.\"	Print an open parenthesis, arg1 in quotes, then arg2 normally
.\"	(for trailing punctuation) and then a closing parenthesis.
.\"
.\"	# Set up traps and other miscellaneous stuff for Tcl/Tk man pages.
.if t .wh -1.3i ^B
.nr ^l \n(.l
.ad b
.\"	# Start an argument description
.de AP
.ie !"\\$4"" .TP \\$4
.el \{\
.   ie !"\\$2"" .TP \\n()Cu
.   el          .TP 15
.\}
.ta \\n()Au \\n()Bu
.ie !"\\$3"" \{\
\&\\$1 \\fI\\$2\\fP (\\$3)
.\".b
.\}
.el \{\
.br
.ie !"\\$2"" \{\
\&\\$1	\\fI\\$2\\fP
.\}
.el \{\
\&\\fI\\$1\\fP
.\}
.\}
..
.\"	# define tabbing values for .AP
.de AS
.nr )A 10n
.if !"\\$1"" .nr )A \\w'\\$1'u+3n
.nr )B \\n()Au+15n
.\"
.if !"\\$2"" .nr )B \\w'\\$2'u+\\n()Au+3n
.nr )C \\n()Bu+\\w'(in/out)'u+2n
..
.AS Tcl_Interp Tcl_CreateInterp in/out
.\"	# BS - start boxed text
.\"	# ^y = starting y location
.\"	# ^b = 1
.de BS
.br
.mk ^y
.nr ^b 1u
.if n .nf
.if n .ti 0
.if n \l'\\n(.lu\(ul'
.if n .fi
..
.\"	# BE - end boxed text (draw box now)
.de BE
.nf
.ti 0
.mk ^t
.ie n \l'\\n(^lu\(ul'
.el \{\
.\"	Draw four-sided box normally, but don't draw top of
.\"	box if the box started on an earlier page.
.ie !\\n(^b-1 \{\
\h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.el \}\
\h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\l'|0u-1.5n\(ul'
.\}
.\}
.fi
.br
.nr ^b 0
..
.\"	# VS - start vertical sidebar
.\"	# ^Y = starting y location
.\"	# ^v = 1 (for troff;  for nroff this doesn't matter)
.de VS
.if !"\\$2"" .br
.mk ^Y
.ie n 'mc \s12\(br\s0
.el .nr ^v 1u
..
.\"	# VE - end of vertical sidebar
.de VE
.ie n 'mc
.el \{\
.ev 2
.nf
.ti 0
.mk ^t
\h'|\\n(^lu+3n'\L'|\\n(^Yu-1v\(bv'\v'\\n(^tu+1v-\\n(^Yu'\h'-|\\n(^lu+3n'
.sp -1
.fi
.ev
.\}
.nr ^v 0
..
.\"	# Special macro to handle page bottom:  finish off current
.\"	# box/sidebar if in box/sidebar mode, then invoked standard
.\"	# page bottom macro.
.de ^B
.ev 2
'ti 0
'nf
.mk ^t
.if \\n(^b \{\
.\"	Draw three-sided box if this is the box's first page,
.\"	draw two sides but no top otherwise.
.ie !\\n(^b-1 \h'-1.5n'\L'|\\n(^yu-1v'\l'\\n(^lu+3n\(ul'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.el \h'-1.5n'\L'|\\n(^yu-1v'\h'\\n(^lu+3n'\L'\\n(^tu+1v-\\n(^yu'\h'|0u'\c
.\}
.if \\n(^v \{\
.nr ^x \\n(^tu+1v-\\n(^Yu
\kx\h'-\\nxu'\h'|\\n(^lu+3n'\ky\L'-\\n(^xu'\v'\\n(^xu'\h'|0u'\c
.\}
.bp
'fi
.ev
.if \\n(^b \{\
.mk ^y
.nr ^b 2
.\}
.if \\n(^v \{\
.mk ^Y
.\}
..
.\"	# DS - begin display
.de DS
.RS
.nf
.sp
..
.\"	# DE - end display
.de DE
.fi
.RE
.sp
..
.\"	# SO - start of list of standard options
.de SO
'ie '\\$1'' .ds So \\fBoptions\\fR
'el .ds So \\fB\\$1\\fR
.SH "STANDARD OPTIONS"
.LP
.nf
.ta 5.5c 11c
.ft B
..
.\"	# SE - end of list of standard options
.de SE
.fi
.ft R
.LP
See the \\*(So manual entry for details on the standard options.
..
.\"	# OP - start of full description for a single option
.de OP
.LP
.nf
.ta 4c
Command-Line Name:	\\fB\\$1\\fR
Database Name:	\\fB\\$2\\fR
Database Class:	\\fB\\$3\\fR
.fi
.IP
..
.\"	# CS - begin code excerpt
.de CS
.RS
.nf
.ta .25i .5i .75i 1i
..
.\"	# CE - end code excerpt
.de CE
.fi
.RE
..
.\"	# UL - underline word
.de UL
\\$1\l'|0\(ul'\\$2
..
.\"	# QW - apply quotation marks to word
.de QW
.ie '\\*(lq'"' ``\\$1''\\$2
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\$2
..
.\"	# PQ - apply parens and quotation marks to word
.de PQ
.ie '\\*(lq'"' (``\\$1''\\$2)\\$3
.\"" fix emacs highlighting
.el (\\*(lq\\$1\\*(rq\\$2)\\$3
..
.\"	# QR - quoted range
.de QR
.ie '\\*(lq'"' ``\\$1''\\-``\\$2''\\$3
.\"" fix emacs highlighting
.el \\*(lq\\$1\\*(rq\\-\\*(lq\\$2\\*(rq\\$3
..
.\"	# MT - "empty" string
.de MT
.QW ""
..
.BS
.SH NAME
struct::tree_v1 \- Create and manipulate tree objects
.SH SYNOPSIS
package require \fBTcl 8\&.5 9\fR
.sp
package require \fBstruct::tree ?1\&.2\&.3?\fR
.sp
\fBtreeName\fR \fBoption\fR ?\fIarg arg \&.\&.\&.\fR?
.sp
\fItreeName\fR \fBappend\fR \fInode\fR ?-key \fIkey\fR? \fIvalue\fR
.sp
\fItreeName\fR \fBchildren\fR \fInode\fR
.sp
\fItreeName\fR \fBcut\fR \fInode\fR
.sp
\fItreeName\fR \fBdelete\fR \fInode\fR ?\fInode\fR \&.\&.\&.?
.sp
\fItreeName\fR \fBdepth\fR \fInode\fR
.sp
\fItreeName\fR \fBdestroy\fR
.sp
\fItreeName\fR \fBexists\fR \fInode\fR
.sp
\fItreeName\fR \fBget\fR \fInode\fR ?\fB-key\fR \fIkey\fR?
.sp
\fItreeName\fR \fBgetall\fR \fInode\fR
.sp
\fItreeName\fR \fBkeys\fR \fInode\fR
.sp
\fItreeName\fR \fBkeyexists\fR \fInode\fR ?-key \fIkey\fR?
.sp
\fItreeName\fR \fBindex\fR \fInode\fR
.sp
\fItreeName\fR \fBinsert\fR \fIparent\fR \fIindex\fR ?\fIchild\fR ?\fIchild\fR \&.\&.\&.??
.sp
\fItreeName\fR \fBisleaf\fR \fInode\fR
.sp
\fItreeName\fR \fBlappend\fR \fInode\fR ?-key \fIkey\fR? \fIvalue\fR
.sp
\fItreeName\fR \fBmove\fR \fIparent\fR \fIindex\fR \fInode\fR ?\fInode\fR \&.\&.\&.?
.sp
\fItreeName\fR \fBnext\fR \fInode\fR
.sp
\fItreeName\fR \fBnumchildren\fR \fInode\fR
.sp
\fItreeName\fR \fBparent\fR \fInode\fR
.sp
\fItreeName\fR \fBprevious\fR \fInode\fR
.sp
\fItreeName\fR \fBset\fR \fInode\fR ?\fB-key\fR \fIkey\fR? ?\fIvalue\fR?
.sp
\fItreeName\fR \fBsize\fR ?\fInode\fR?
.sp
\fItreeName\fR \fBsplice\fR \fIparent\fR \fIfrom\fR ?\fIto\fR? ?\fIchild\fR?
.sp
\fItreeName\fR \fBswap\fR \fInode1\fR \fInode2\fR
.sp
\fItreeName\fR \fBunset\fR \fInode\fR ?\fB-key\fR \fIkey\fR?
.sp
\fItreeName\fR \fBwalk\fR \fInode\fR ?\fB-order\fR \fIorder\fR? ?\fB-type\fR \fItype\fR? \fB-command\fR \fIcmd\fR
.sp
.BE
.SH DESCRIPTION
.PP
The \fB::struct::tree\fR command creates a new tree object with an
associated global Tcl command whose name is \fItreeName\fR\&. This
command may be used to invoke various operations on the tree\&. It has
the following general form:
.TP
\fBtreeName\fR \fBoption\fR ?\fIarg arg \&.\&.\&.\fR?
\fIOption\fR and the \fIarg\fRs determine the exact behavior of the
command\&.
.PP
.PP
A tree is a collection of named elements, called nodes, one of which is
distinguished as a root, along with a relation ("parenthood") that
places a hierarchical structure on the nodes\&. (Data Structures and
Algorithms; Aho, Hopcroft and Ullman; Addison-Wesley, 1987)\&.  In
addition to maintaining the node relationships, this tree
implementation allows any number of keyed values to be associated with
each node\&.
.PP
The element names can be arbitrary strings\&.
.PP
A tree is thus similar to an array, but with three important
differences:
.IP [1]
Trees are accessed through an object command, whereas arrays are
accessed as variables\&. (This means trees cannot be local to a procedure\&.)
.IP [2]
Trees have a hierarchical structure, whereas an array is just an
unordered collection\&.
.IP [3]
Each node of a tree has a separate collection of attributes and
values\&. This is like an array where every value is a dictionary\&.
.PP
.PP
The following commands are possible for tree objects:
.TP
\fItreeName\fR \fBappend\fR \fInode\fR ?-key \fIkey\fR? \fIvalue\fR
Appends a \fIvalue\fR to one of the keyed values associated with an
node\&. If no \fIkey\fR is specified, the key \fBdata\fR is assumed\&.
.TP
\fItreeName\fR \fBchildren\fR \fInode\fR
Return a list of the children of \fInode\fR\&.
.TP
\fItreeName\fR \fBcut\fR \fInode\fR
Removes the node specified by \fInode\fR from the tree, but not its
children\&.  The children of \fInode\fR are made children of the parent
of the \fInode\fR, at the index at which \fInode\fR was located\&.
.TP
\fItreeName\fR \fBdelete\fR \fInode\fR ?\fInode\fR \&.\&.\&.?
Removes the specified nodes from the tree\&.  All of the nodes' children
will be removed as well to prevent orphaned nodes\&.
.TP
\fItreeName\fR \fBdepth\fR \fInode\fR
Return the number of steps from node \fInode\fR to the root node\&.
.TP
\fItreeName\fR \fBdestroy\fR
Destroy the tree, including its storage space and associated command\&.
.TP
\fItreeName\fR \fBexists\fR \fInode\fR
Returns true if the specified node exists in the tree\&.
.TP
\fItreeName\fR \fBget\fR \fInode\fR ?\fB-key\fR \fIkey\fR?
Return the value associated with the key \fIkey\fR for the node
\fInode\fR\&. If no key is specified, the key \fBdata\fR is assumed\&.
.TP
\fItreeName\fR \fBgetall\fR \fInode\fR
Returns a serialized list of key/value pairs (suitable for use with
[\fBarray set\fR]) for the \fInode\fR\&.
.TP
\fItreeName\fR \fBkeys\fR \fInode\fR
Returns a list of keys for the \fInode\fR\&.
.TP
\fItreeName\fR \fBkeyexists\fR \fInode\fR ?-key \fIkey\fR?
Return true if the specified \fIkey\fR exists for the \fInode\fR\&. If
no \fIkey\fR is specified, the key \fBdata\fR is assumed\&.
.TP
\fItreeName\fR \fBindex\fR \fInode\fR
Returns the index of \fInode\fR in its parent's list of children\&.  For
example, if a node has \fInodeFoo\fR, \fInodeBar\fR, and
\fInodeBaz\fR as children, in that order, the index of
\fInodeBar\fR is 1\&.
.TP
\fItreeName\fR \fBinsert\fR \fIparent\fR \fIindex\fR ?\fIchild\fR ?\fIchild\fR \&.\&.\&.??
Insert one or more nodes into the tree as children of the node
\fIparent\fR\&. The nodes will be added in the order they are given\&. If
\fIparent\fR is \fBroot\fR, it refers to the root of the tree\&. The
new nodes will be added to the \fIparent\fR node's child list at the
index given by \fIindex\fR\&. The \fIindex\fR can be \fBend\fR in
which case the new nodes will be added after the current last child\&.
.sp
If any of the specified children already exist in \fItreeName\fR,
those nodes will be moved from their original location to the new
location indicated by this command\&.
.sp
If no \fIchild\fR is specified, a single node will be added, and a
name will be generated for the new node\&. The generated name is of the
form \fInode\fR\fBx\fR, where \fBx\fR is a number\&. If names are
specified they must neither contain whitespace nor colons (":")\&.
.sp
The return result from this command is a list of nodes added\&.
.TP
\fItreeName\fR \fBisleaf\fR \fInode\fR
Returns true if \fInode\fR is a leaf of the tree (if \fInode\fR has no
children), false otherwise\&.
.TP
\fItreeName\fR \fBlappend\fR \fInode\fR ?-key \fIkey\fR? \fIvalue\fR
Appends a \fIvalue\fR (as a list) to one of the keyed values
associated with an \fInode\fR\&. If no \fIkey\fR is specified, the key
\fBdata\fR is assumed\&.
.TP
\fItreeName\fR \fBmove\fR \fIparent\fR \fIindex\fR \fInode\fR ?\fInode\fR \&.\&.\&.?
Make the specified nodes children of \fIparent\fR, inserting them into
the parent's child list at the index given by \fIindex\fR\&. Note that
the command will take all nodes out of the tree before inserting them
under the new parent, and that it determines the position to place
them into after the removal, before the re-insertion\&. This behaviour
is important when it comes to moving one or more nodes to a different
index without changing their parent node\&.
.TP
\fItreeName\fR \fBnext\fR \fInode\fR
Return the right sibling of \fInode\fR, or the empty string if
\fInode\fR was the last child of its parent\&.
.TP
\fItreeName\fR \fBnumchildren\fR \fInode\fR
Return the number of immediate children of \fInode\fR\&.
.TP
\fItreeName\fR \fBparent\fR \fInode\fR
Return the parent of \fInode\fR\&.
.TP
\fItreeName\fR \fBprevious\fR \fInode\fR
Return the left sibling of \fInode\fR, or the empty string if
\fInode\fR was the first child of its parent\&.
.TP
\fItreeName\fR \fBset\fR \fInode\fR ?\fB-key\fR \fIkey\fR? ?\fIvalue\fR?
Set or get one of the keyed values associated with a node\&. If no key
is specified, the key \fBdata\fR is assumed\&.  Each node that is
added to a tree has the value "" assigned to the key \fBdata\fR
automatically\&.  A node may have any number of keyed values associated
with it\&.  If \fIvalue\fR is not specified, this command returns the
current value assigned to the key; if \fIvalue\fR is specified, this
command assigns that value to the key\&.
.TP
\fItreeName\fR \fBsize\fR ?\fInode\fR?
Return a count of the number of descendants of the node \fInode\fR; if
no node is specified, \fBroot\fR is assumed\&.
.TP
\fItreeName\fR \fBsplice\fR \fIparent\fR \fIfrom\fR ?\fIto\fR? ?\fIchild\fR?
Insert a node named \fIchild\fR into the tree as a child of the node
\fIparent\fR\&. If \fIparent\fR is \fBroot\fR, it refers to the root
of the tree\&. The new node will be added to the parent node's child
list at the index given by \fIfrom\fR\&.  The children of \fIparent\fR
which are in the range of the indices \fIfrom\fR and \fIto\fR are made
children of \fIchild\fR\&.  If the value of \fIto\fR is not specified it
defaults to \fBend\fR\&.  If no name is given for \fIchild\fR, a name
will be generated for the new node\&.  The generated name is of the form
\fInode\fR\fBx\fR, where \fBx\fR is a number\&.  The return result
from this command is the name of the new node\&.
.TP
\fItreeName\fR \fBswap\fR \fInode1\fR \fInode2\fR
Swap the position of \fInode1\fR and \fInode2\fR in the tree\&.
.TP
\fItreeName\fR \fBunset\fR \fInode\fR ?\fB-key\fR \fIkey\fR?
Removes a keyed value from the node \fInode\fR\&.  If no key is
specified, the key \fBdata\fR is assumed\&.
.TP
\fItreeName\fR \fBwalk\fR \fInode\fR ?\fB-order\fR \fIorder\fR? ?\fB-type\fR \fItype\fR? \fB-command\fR \fIcmd\fR
Perform a breadth-first or depth-first walk of the tree starting at
the node \fInode\fR\&.  The type of walk, breadth-first or depth-first,
is determined by the value of \fItype\fR; \fBbfs\fR indicates
breadth-first, \fBdfs\fR indicates depth-first\&.  Depth-first is the
default\&. The order of the walk, pre-, post-, both- or in-order is
determined by the value of \fIorder\fR; \fBpre\fR indicates
pre-order, \fBpost\fR indicates post-order, \fBboth\fR indicates
both-order and \fBin\fR indicates in-order\&. Pre-order is the
default\&.
.sp
Pre-order walking means that a parent node is visited before any of
its children\&.  For example, a breadth-first search starting from the
root will visit the root, followed by all of the root's children,
followed by all of the root's grandchildren\&. Post-order walking means
that a parent node is visited after any of its children\&. Both-order
walking means that a parent node is visited before \fIand\fR after
any of its children\&. In-order walking means that a parent node is
visited after its first child and before the second\&. This is a
generalization of in-order walking for binary trees and will do the
right thing if a binary is walked\&. The combination of a breadth-first
walk with in-order is illegal\&.
.sp
As the walk progresses, the command \fIcmd\fR will be evaluated at
each node\&.  Percent substitution will be performed on \fIcmd\fR before
evaluation, just as in a \fBbind\fR script\&.  The following
substitutions are recognized:
.RS
.TP
\fB%%\fR
Insert the literal % character\&.
.TP
\fB%t\fR
Name of the tree object\&.
.TP
\fB%n\fR
Name of the current node\&.
.TP
\fB%a\fR
Name of the action occurring; one of \fBenter\fR, \fBleave\fR,
or \fBvisit\fR\&.  \fBenter\fR actions occur during pre-order
walks; \fBleave\fR actions occur during post-order walks;
\fBvisit\fR actions occur during in-order walks\&.  In a both-order
walk, the command will be evaluated twice for each node; the action is
\fBenter\fR for the first evaluation, and \fBleave\fR for the
second\&.
.RE
.PP
.SH "BUGS, IDEAS, FEEDBACK"
This document, and the package it describes, will undoubtedly contain
bugs and other problems\&.
Please report such in the category \fIstruct :: tree\fR of the
\fITcllib Trackers\fR [http://core\&.tcl\&.tk/tcllib/reportlist]\&.
Please also report any ideas for enhancements you may have for either
package and/or documentation\&.
.PP
When proposing code changes, please provide \fIunified diffs\fR,
i\&.e the output of \fBdiff -u\fR\&.
.PP
Note further that \fIattachments\fR are strongly preferred over
inlined patches\&. Attachments can be made by going to the \fBEdit\fR
form of the ticket immediately after its creation, and then using the
left-most button in the secondary navigation bar\&.
.SH KEYWORDS
tree
.SH CATEGORY
Data structures
.SH COPYRIGHT
.nf
Copyright (c) 2002 Andreas Kupries <andreas_kupries@users\&.sourceforge\&.net>

.fi