struct::tree_v1(3tcl) Tcl Data Structures struct::tree_v1(3tcl)
______________________________________________________________________________
NAME
struct::tree_v1 - Create and manipulate tree objects
SYNOPSIS
package require Tcl 8.2
package require struct::tree ?1.2.2?
treeName option ?arg arg ...?
treeName append node ?-key key? value
treeName children node
treeName cut node
treeName delete node ?node ...?
treeName depth node
treeName destroy
treeName exists node
treeName get node ?-key key?
treeName getall node
treeName keys node
treeName keyexists node ?-key key?
treeName index node
treeName insert parent index ?child ?child ...??
treeName isleaf node
treeName lappend node ?-key key? value
treeName move parent index node ?node ...?
treeName next node
treeName numchildren node
treeName parent node
treeName previous node
treeName set node ?-key key? ?value?
treeName size ?node?
treeName splice parent from ?to? ?child?
treeName swap node1 node2
treeName unset node ?-key key?
treeName walk node ?-order order? ?-type type? -command cmd
______________________________________________________________________________
DESCRIPTION
The ::struct::tree command creates a new tree object with an associated
global Tcl command whose name is treeName. This command may be used to
invoke various operations on the tree. It has the following general
form:
treeName option ?arg arg ...?
Option and the args determine the exact behavior of the command.
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 Al-
gorithms; 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.
The element names can be arbitrary strings.
A tree is thus similar to an array, but with three important differ-
ences:
[1] Trees are accessed through an object command, whereas arrays are
accessed as variables. (This means trees cannot be local to a
procedure.)
[2] Trees have a hierarchical structure, whereas an array is just an
unordered collection.
[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.
The following commands are possible for tree objects:
treeName append node ?-key key? value
Appends a value to one of the keyed values associated with an
node. If no key is specified, the key data is assumed.
treeName children node
Return a list of the children of node.
treeName cut node
Removes the node specified by node from the tree, but not its
children. The children of node are made children of the parent
of the node, at the index at which node was located.
treeName delete node ?node ...?
Removes the specified nodes from the tree. All of the nodes'
children will be removed as well to prevent orphaned nodes.
treeName depth node
Return the number of steps from node node to the root node.
treeName destroy
Destroy the tree, including its storage space and associated
command.
treeName exists node
Returns true if the specified node exists in the tree.
treeName get node ?-key key?
Return the value associated with the key key for the node node.
If no key is specified, the key data is assumed.
treeName getall node
Returns a serialized list of key/value pairs (suitable for use
with [array set]) for the node.
treeName keys node
Returns a list of keys for the node.
treeName keyexists node ?-key key?
Return true if the specified key exists for the node. If no key
is specified, the key data is assumed.
treeName index node
Returns the index of node in its parent's list of children. For
example, if a node has nodeFoo, nodeBar, and nodeBaz as chil-
dren, in that order, the index of nodeBar is 1.
treeName insert parent index ?child ?child ...??
Insert one or more nodes into the tree as children of the node
parent. The nodes will be added in the order they are given. If
parent is root, it refers to the root of the tree. The new nodes
will be added to the parent node's child list at the index given
by index. The index can be end in which case the new nodes will
be added after the current last child.
If any of the specified children already exist in treeName,
those nodes will be moved from their original location to the
new location indicated by this command.
If no child 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 nodex, where x is a number. If names are specified
they must neither contain whitespace nor colons (":").
The return result from this command is a list of nodes added.
treeName isleaf node
Returns true if node is a leaf of the tree (if node has no chil-
dren), false otherwise.
treeName lappend node ?-key key? value
Appends a value (as a list) to one of the keyed values associ-
ated with an node. If no key is specified, the key data is as-
sumed.
treeName move parent index node ?node ...?
Make the specified nodes children of parent, inserting them into
the parent's child list at the index given by index. 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.
treeName next node
Return the right sibling of node, or the empty string if node
was the last child of its parent.
treeName numchildren node
Return the number of immediate children of node.
treeName parent node
Return the parent of node.
treeName previous node
Return the left sibling of node, or the empty string if node was
the first child of its parent.
treeName set node ?-key key? ?value?
Set or get one of the keyed values associated with a node. If no
key is specified, the key data is assumed. Each node that is
added to a tree has the value "" assigned to the key data auto-
matically. A node may have any number of keyed values associ-
ated with it. If value is not specified, this command returns
the current value assigned to the key; if value is specified,
this command assigns that value to the key.
treeName size ?node?
Return a count of the number of descendants of the node node; if
no node is specified, root is assumed.
treeName splice parent from ?to? ?child?
Insert a node named child into the tree as a child of the node
parent. If parent is root, 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 from. The children of parent which are in
the range of the indices from and to are made children of child.
If the value of to is not specified it defaults to end. If no
name is given for child, a name will be generated for the new
node. The generated name is of the form nodex, where x is a
number. The return result from this command is the name of the
new node.
treeName swap node1 node2
Swap the position of node1 and node2 in the tree.
treeName unset node ?-key key?
Removes a keyed value from the node node. If no key is speci-
fied, the key data is assumed.
treeName walk node ?-order order? ?-type type? -command cmd
Perform a breadth-first or depth-first walk of the tree starting
at the node node. The type of walk, breadth-first or depth-
first, is determined by the value of type; bfs indicates
breadth-first, dfs 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 order; pre indicates pre-order,
post indicates post-order, both indicates both-order and in in-
dicates in-order. Pre-order is the default.
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-or-
der walking means that a parent node is visited after any of its
children. Both-order walking means that a parent node is visited
before and 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 bi-
nary trees and will do the right thing if a binary is walked.
The combination of a breadth-first walk with in-order is ille-
gal.
As the walk progresses, the command cmd will be evaluated at
each node. Percent substitution will be performed on cmd before
evaluation, just as in a bind script. The following substitu-
tions are recognized:
%% Insert the literal % character.
%t Name of the tree object.
%n Name of the current node.
%a Name of the action occurring; one of enter, leave, or
visit. enter actions occur during pre-order walks; leave
actions occur during post-order walks; visit actions oc-
cur during in-order walks. In a both-order walk, the
command will be evaluated twice for each node; the action
is enter for the first evaluation, and leave for the sec-
ond.
BUGS, IDEAS, FEEDBACK
This document, and the package it describes, will undoubtedly contain
bugs and other problems. Please report such in the category struct ::
tree of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist].
Please also report any ideas for enhancements you may have for either
package and/or documentation.
When proposing code changes, please provide unified diffs, i.e the out-
put of diff -u.
Note further that attachments are strongly preferred over inlined
patches. Attachments can be made by going to the Edit form of the
ticket immediately after its creation, and then using the left-most
button in the secondary navigation bar.
KEYWORDS
tree
CATEGORY
Data structures
COPYRIGHT
Copyright (c) 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>
tcllib 1.2.2 struct::tree_v1(3tcl)