Manual Pages for UNIX Darwin command on man struct

Manual Pages for UNIX Darwin command on man struct_tree

tree(n) Tcl Data Structures tree(n)

NAME

tree - Create and manipulate tree objects

SYNOPSIS

package require TTccll 88..22 package require ssttrruucctt ??22..00?? ::::ssttrruucctt::::ttrreeee ?treeName? ?==|::==|aass|ddeesseerriiaalliizzee source? ttrreeeeNNaammee ooppttiioonn ?arg arg ...? treeName == sourcetree

treeName -->> desttree

treeName aappppeenndd node key value treeName aattttrr key

treeName aattttrr key -nnooddeess list

treeName aattttrr key -gglloobb globpattern

treeName aattttrr key -rreeggeexxpp repattern

treeName cchhiillddrreenn ?-aallll? node ?ffiilltteerr cmdprefix?

treeName ccuutt node treeName ddeelleettee node ?node ...? treeName ddeepptthh node treeName ddeesseerriiaalliizzee serialization treeName ddeessttrrooyy treeName eexxiissttss node treeName ggeett node key treeName ggeettaallll node ?pattern? treeName kkeeyyss node ?pattern? treeName kkeeyyeexxiissttss node key treeName iinnddeexx node treeName iinnsseerrtt parent index ?child ?child ...?? treeName iisslleeaaff node treeName llaappppeenndd node key value treeName mmoovvee parent index node ?node ...? treeName nneexxtt node treeName nnuummcchhiillddrreenn node treeName ppaarreenntt node treeName pprreevviioouuss node treeName rreennaammee node newname treeName rroooottnnaammee treeName sseerriiaalliizzee ?node? treeName sseett node key ?value? treeName ssiizzee ?node? treeName sspplliiccee parent from ?to? ?child? treeName sswwaapp node1 node2 treeName uunnsseett node key

treeName wwaallkk node ?-oorrddeerr order? ?-ttyyppee type? loopvar script

DESCRIPTION

A tree is a collection of elements, called nodes, one of which is dis-

tinguished 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 main-

taining 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 ssttrruucctt has been changed to ver-

sion 2.0, due to backward incompatible changes in the API of this mod-

ule. Please read the section CChhaannggeess ffoorr 22..00 for a full list of all changes, incompatible and otherwise. The main command of the package is: ::::ssttrruucctt::::ttrreeee ?treeName? ?==|::==|aass|ddeesseerriiaalliizzee 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: ttrreeeeNNaammee ooppttiioonn ?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 initial-

ized to it. For the operators ==, ::==, and aass source is interpreted as the name of another tree object, and the assignment operator == will be executed. For ddeesseerriiaalliizzee the source is a serialized tree object and ddeesseerriiaalliizzee 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 rreennaammee (see below). Whatever the current name for the root node of the tree is, it can be retrieved by calling the method rroooottnnaammee. 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 ddeesseerriiaalliizzee [sourcetree sseerriiaalliizzee]

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 ddeesseerriiaalliizzee [treeName sseerriiaalliizzee] treeName aappppeenndd 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 aattttrr key

treeName aattttrr key -nnooddeess list

treeName aattttrr key -gglloobb globpattern

treeName aattttrr key -rreeggeexxpp repattern

This method retrieves the value of the attribute named key, for all nodes in the tree (matching the restriction specified via one of the possible options) and having the specified attribute. The result is a dictionary mapping from node names to the value of attribute key at that node. Nodes not having the attribute key, or not passing a specified restriction, are not listed in the result. The possible restrictions are:

-nnooddeess The value is a list of nodes. Only the nodes mentioned in

this list are searched for the attribute.

-gglloobb The value is a glob pattern. Only the nodes in the tree

whose names match this pattern are searched for the attribute.

-rreeggeexxpp

The value is a regular expression. Only the nodes in the tree whose names match this pattern are searched for the attribute.

treeName cchhiillddrreenn ?-aallll? node ?ffiilltteerr cmdprefix?

Return a list of the children of node. If the option -aallll is

specified, then not only the direct children, but their chil-

dren, and so on are returned in the result. If a filter command is specified only those nodes are listed in the final result which pass the test. The command in cmdprefix is called with two arguments, the name of the tree object, and the name of the node in question. It is executed in the context of the caller and has to return a boolean value. Nodes for which the command returns ffaallssee are removed from the result list before it is returned to the caller. Some examples: mytree insert root end 0 ; mytree set 0 volume 30 mytree insert root end 1 mytree insert root end 2 mytree insert 0 end 3 mytree insert 0 end 4 mytree insert 4 end 5 ; mytree set 5 volume 50 mytree insert 4 end 6 proc vol {t n} {

$t keyexists $n volume

} proc vgt40 {t n} {

if {![$t keyexists $n volume]} {return 0}

expr {[$t get $n volume] > 40}

}

tclsh> lsort [mytree children -all root filter vol]

0 5

tclsh> lsort [mytree children -all root filter vgt40]

5 tclsh> lsort [mytree children root filter vol] 0 tclsh> puts ([lsort [mytree children root filter vgt40]]) () treeName ccuutt 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 ddeelleettee node ?node ...? Remove the specified nodes from the tree. All of the nodes' children will be removed as well to prevent orphaned nodes. treeName ddeepptthh node Return the number of steps from node node to the root node. treeName ddeesseerriiaalliizzee serialization This is the complement to sseerriiaalliizzee. 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 ddeessttrrooyy Destroy the tree, including its storage space and associated command. treeName eexxiissttss node Remove true if the specified node exists in the tree. treeName ggeett node key Returns the value associated with the key key for the node node. treeName ggeettaallll node ?pattern?

Returns a dictionary (suitable for use with [aarrrraayy sseett]) con-

taining 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 kkeeyyss node ?pattern?

Returns a list of keys for the node. If the pattern is speci-

fied only the attributes whose names match the pattern will be part of the returned list. The pattern is a gglloobb pattern. treeName kkeeyyeexxiissttss node key Return true if the specified key exists for the node. treeName iinnddeexx 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 iinnsseerrtt 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 rroooott, 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 eenndd 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 nodexx, where xx 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 iisslleeaaff node

Returns true if node is a leaf of the tree (if node has no chil-

dren), false otherwise. treeName llaappppeenndd node key value

Appends a value (as a list) to one of the keyed values associ-

ated with an node. Returns the new value given to the attribute key. treeName mmoovvee 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 nneexxtt node Return the right sibling of node, or the empty string if node was the last child of its parent. treeName nnuummcchhiillddrreenn node Return the number of immediate children of node. treeName ppaarreenntt node Return the parent of node. treeName pprreevviioouuss node Return the left sibling of node, or the empty string if node was the first child of its parent. treeName rreennaammee 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 rroooottnnaammee Returns the name of the root node of the tree. treeName sseerriiaalliizzee ?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, persis-

tence, 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 necessar-

ily 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 sseett 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 ssiizzee ?node? Return a count of the number of descendants of the node node; if no node is specified, rroooott is assumed. treeName sspplliiccee parent from ?to? ?child? Insert a node named child into the tree as a child of the node parent. If parent is rroooott, 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 eenndd. If no name is given for child, a name will be generated for the new node. The generated name is of the form nodexx, where xx is a number. The return result from this command is the name of the new node. treeName sswwaapp node1 node2 Swap the position of node1 and node2 in the tree. treeName uunnsseett node key Remove a keyed value from the node node. The method will do nothing if the key does not exist.

treeName wwaallkk node ?-oorrddeerr order? ?-ttyyppee type? loopvar script

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; bbffss indicates

breadth-first, ddffss 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; pprree indicates pre-order,

ppoosstt indicates post-order, bbootthh indicates both-order and iinn

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 tree is

walked. The combination of a breadth-first walk with in-order is

illegal. As the walk progresses, the script will be evaluated at each node. The evaluation takes place in the context of the caller of

the method. Regarding loop variables, these are listed in loop-

var. If one only one variable is specified it will be set to the id of the node. When two variables are specified, i.e. loopvar is a true list, then the first variable will be set to the action performed at the node, and the other to the id of the node itself. All loop variables are created in the context of the caller. There are three possible actions: eenntteerr, lleeaavvee, or vviissiitt. eenntteerr

actions occur during pre-order walks; lleeaavvee actions occur during

post-order walks; vviissiitt actions occur during in-order walks. In

a both-order walk, the command will be evaluated twice for each

node; the action is eenntteerr for the first evaluation, and lleeaavvee for the second. Note: The eenntteerr action for a node is always performed before the walker will look at the children of that node. This means that changes made by the script to the children of the node will immediately influence the walker and the steps it will take. Any other manipulation, for example of nodes higher in the tree (i.e already visited), or upon leaving will have undefined results. They may succeed, error out, silently compute the wrong result, or anything in between.

At last a small table showing the relationship between the vari-

ous options and the possible actions. order type actions notes

--- -- --- ---

pre dfs enter parent before children post dfs leave parent after children in dfs visit parent between first and second child. both dfs enter, leave parent before and after children

--- -- --- ---

pre bfs enter parent before children post bfs leave parent after children

in bfs - illegal -

both bfs enter, leave parent before and after children

--- -- --- ---

CChhaannggeess ffoorr 22..00 The following noteworthy changes have occurred:

[1] The API for accessing attributes and their values has been sim-

plified. 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 -kkeeyy is not required anymore, even more, its

use is now forbidden. Please read the documentation for the methods sseett, ggeett, ggeettaallll, uunnsseett, aappppeenndd, llaappppeenndd, kkeeyyeexxiissttss and kkeeyyss for a description of the new API's.

[2] The methods kkeeyyss and ggeettaallll now take an optional pattern argu-

ment and will return only attribute data for keys matching this pattern. [3] Nodes can now be renamed. See the documentation for the method rreennaammee. [4] 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 sseerriiaalliizzee, ddeesseerrii-

aalliizzee, ==, 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. [5] The walker API has been streamlined and made more similar to the command ffoorreeaacchh. In detail:

+o The superfluous option -ccoommmmaanndd has been removed.

+o Ditto for the place holders. Instead of the placeholders two loop variables have to be specified to contain node and action infromation. +o The old command argument has been documented as a script now, which it was in the past too. +o The fact that eenntteerr actions are called before the walker looks at the children of a node has been documented now. In other words it is now officially allowed to manipulate

the list of children for a node under these circum-

stances. It has been made clear that changes under any other circumstances will have undefined results, from silently computing the wrong result to erroring out. [6] A new method, aattttrr, was added allowing the query and retrieval of attribute data without regard to the node relationship. [7] The method cchhiillddrreenn has been extended with the ability to select from the children of the node based on an arbitrary filtering criterium. Another extension is the ability to look not only at the immediate children of the node, but the whole tree below it. KKEEYYWWOORRDDSS

breadth-first, depth-first, in-order, node, post-order, pre-order,

serialization, tree COPYRIGHT

struct 2.0 tree(n)