tree(n) 2.0 struct "Tcl Data Structures"
tree - Create and manipulate tree objects
package require Tcl 8.2
package require struct ?2.0?
A tree is a collection of 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.
Note: The major version of the package struct has
been changed to version 2.0, due to backward incompatible changes in
the API of this module. Please read the section
Changes for 2.0 for a full list of all changes,
incompatible and otherwise.
The main command of the package is:
- ::struct::tree ?treeName? ?=|:=|as|deserialize source?
-
The 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.
If treeName is not specified a unique name will be generated by
the package itself. If a source is specified the new tree will
be initialized to it. For the operators =, :=, and
as source is interpreted as the name of another tree
object, and the assignment operator = will be executed. For
deserialize the source is a serialized tree object and
deserialize will be executed.
In other words
| |
::struct::tree mytree = b
|
is equivalent to
| |
::struct::tree mytree
mytree = b
|
and
| |
::struct::tree mytree deserialize $b
|
is equivalent to
| |
::struct::tree mytree
mytree deserialize $b
|
A general observation: The root node of the tree can be used in most
places where a node is asked for. The default name of the rootnode is
"root", but this can be changed with the method rename (see
below). Whatever the current name for the root node of the tree is, it
can be retrieved by calling the method rootname.
The following commands are possible for tree objects:
- treeName = sourcetree
-
This is the assignment operator for tree objects. It copies the tree
contained in the tree object sourcetree over the tree data in
treeName. The old contents of treeName are deleted by this
operation.
This operation is in effect equivalent to
| |
treeName deserialize [sourcetree serialize]
|
- treeName --> desttree
-
This is the reverse assignment operator for tree objects. It copies the tree
contained in the tree object treeName over the tree data in the object
desttree. The old contents of desttree are deleted by this
operation.
This operation is in effect equivalent to
| |
desttree deserialize [treeName serialize]
|
- treeName append node key value
-
Appends a value to one of the keyed values associated with an
node. Returns the new value given to the attribute key.
- 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 ...?
-
Remove 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 deserialize serialization
-
This is the complement to serialize. It replaces tree data in
treeName with the tree described by the serialization
value. The old contents of treeName are deleted by this
operation.
- treeName destroy
-
Destroy the tree, including its storage space and associated command.
- treeName exists node
-
Remove true if the specified node exists in the tree.
- treeName get node key
-
Returns the value associated with the key key for the node
node.
- treeName getall node ?pattern?
-
Returns a dictionary (suitable for use with [array set])
containing the attribute data for the node.
If the glob pattern is specified only the attributes whose names
match the pattern will be part of the dictionary.
- treeName keys node ?pattern?
-
Returns a list of keys for the node.
If the pattern is specified only the attributes whose names
match the pattern will be part of the returned list. The pattern is a
glob pattern.
- treeName keyexists node key
-
Return true if the specified key exists for the node.
- 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 children, 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
children), false otherwise.
- treeName lappend node key value
-
Appends a value (as a list) to one of the keyed values
associated with an node. Returns the new value given to the
attribute key.
- 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 rename node newname
-
Renames the node node to newname. An error is thrown if
either the node does not exist, or a node with name newname does
exist. The result of the command is the new name of the node.
- treeName rootname
-
Returns the name of the root node of the tree.
- treeName serialize ?node?
-
This method serializes the sub-tree starting at node. In other
words it returns a tcl value completely describing the tree
starting at node.
This allows, for example, the transfer of tree objects (or parts
thereof) over arbitrary channels, persistence, etc.
This method is also the basis for both the copy constructor and
the assignment operator.
The result of this method has to be semantically identical over all
implementations of the tree interface. This is what will enable us to
copy tree data between different implementations of the same
interface.
The result is a list containing containing a multiple of three
elements. It is like a serialized array except that there are two
values following each key. They are the names of the nodes in the
serialized tree. The two values are a reference to the parent node and
the attribute data, in this order.
The reference to the parent node is the empty string for the root node
of the tree. For all other nodes it is the index of the parent node in
the list. This means that they are integers, greater than or equal to
zero, less than the length of the list, and multiples of three.
The order of the nodes in the list is important insofar as it is used
to reconstruct the lists of children for each node. The children of a
node have to be listed in the serialization in the same order as they
are listed in their parent in the tree.
The attribute data of a node is a dictionary, i.e. a list of even
length containing a serialized array. For a node without attribute
data the dictionary is the empty list.
Note: While the current implementation returns the root node as
the first element of the list, followed by its children and their
children in a depth-first traversal this is not necessarily true for
other implementations.
The only information a reader of the serialized data can rely on for
the structure of the tree is that the root node is signaled by the
empty string for the parent reference, that all other nodes refer to
their parent through the index in the list, and that children occur in
the same order as in their parent.
| |
# A possible serialization for the tree structure
#
# +- d
# +- a -+
# root -+- b +- e
# +- c
# is
#
# {root {} {} a 0 {} d 3 {} e 3 {} b 0 {} c 0 {}}
#
# The above assumes that none of the nodes have
# attributes.
|
- treeName set node key ?value?
-
Set or get one of the keyed values associated with a node. A node may
have any number of keyed values associated 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, and returns it.
- 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
-
Remove a keyed value from the node node. The method will do
nothing if the key does not exist.
- 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 indicates 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-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 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 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.
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
substitutions 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 occur 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
second.
The following noteworthy changes have occurred:
-
The API for accessing attributes and their values has been
simplified.
All functionality regarding the default attribute "data" has been
removed. This default attribute does not exist anymore. All accesses
to attributes have to specify the name of the attribute in
question. This backward incompatible change allowed us to
simplify the signature of all methods handling attributes.
Especially the flag -key is not required anymore, even more,
its use is now forbidden. Please read the documentation for the
methods set, get, getall, unset,
append, lappend, keyexists
and keys for a description of the new API's.
-
The methods keys and getall now take an optional
pattern argument and will return only attribute data for keys matching
this pattern.
-
Nodes can now be renamed. See the documentation for the method
rename.
-
The structure has been extended with API's for the serialization and
deserialization of tree objects, and a number of operations based on
them (tree assignment, copy construction).
Please read the documentation for the methods serialize,
deserialize, =, and -->, and the
documentation on the construction of tree objects.
Beyond the copying of whole tree objects these new API's also enable
the transfer of tree objects over arbitrary channels and for easy
persistence.
serialization, tree
Copyright © 2002 Andreas Kupries <andreas_kupries@users.sourceforge.net>