Tcl Library Source Code

Documentation
Login


[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

NAME

struct::tree - Create and manipulate tree objects

Table Of Contents

SYNOPSIS

package require Tcl 8.5 9
package require struct::tree ?2.1.1?
package require struct::list ?1.5?

::struct::tree ?treeName? ?=|:=|as|deserialize source?
treeName option ?arg arg ...?
::struct::tree::prune
treeName = sourcetree
treeName --> desttree
treeName ancestors node
treeName append node key value
treeName attr key
treeName attr key -nodes list
treeName attr key -glob globpattern
treeName attr key -regexp repattern
treeName children ?-all? node ?filter cmdprefix?
treeName cut node
treeName delete node ?node ...?
treeName depth node
treeName descendants node ?filter cmdprefix?
treeName deserialize serialization
treeName destroy
treeName exists node
treeName get node key
treeName getall node ?pattern?
treeName keys node ?pattern?
treeName keyexists node key
treeName index node
treeName insert parent index ?child ?child ...??
treeName isleaf node
treeName lappend node key value
treeName leaves
treeName move parent index node ?node ...?
treeName next node
treeName numchildren node
treeName nodes
treeName parent node
treeName previous node
treeName rename node newname
treeName rootname
treeName serialize ?node?
treeName set node key ?value?
treeName size ?node?
treeName splice parent from ?to? ?child?
treeName swap node1 node2
treeName unset node key
treeName walk node ?-order order? ?-type type? loopvar script
treeName walkproc node ?-order order? ?-type type? cmdprefix

DESCRIPTION

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.

The element names can be arbitrary strings.

A tree is thus similar to an array, but with three important differences:

  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.

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.

API

Tree CLASS API

The main commands of the package are:

Tree OBJECT API

Two general observations beforehand:

  1. 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.

  2. The method insert is the only way to create new nodes, and they are automatically added to a parent. A tree object cannot have nodes without a parent, save the root node.

And now the methods supported by tree objects created by this package:

Changes for 2.0

The following noteworthy changes have occurred:

  1. 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.

  2. The methods keys and getall now take an optional pattern argument and will return only attribute data for keys matching this pattern.

  3. Nodes can now be renamed. See the documentation for the method rename.

  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 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.

  5. The walker API has been streamlined and made more similar to the command foreach. In detail:

    • The superfluous option -command has been removed.
    • Ditto for the place holders. Instead of the placeholders two loop variables have to be specified to contain node and action information.
    • The old command argument has been documented as a script now, which it was in the past too.
    • The fact that enter 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 circumstances. 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, attr, was added allowing the query and retrieval of attribute data without regard to the node relationship.

  7. The method children 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.

EXAMPLES

The following example demonstrates the creation of new nodes:

mytree insert root end 0   ; # Create node 0, as child of the root
mytree insert root end 1 2 ; # Ditto nodes 1 & 2
mytree insert 0    end 3   ; # Now create node 3 as child of node 0
mytree insert 0    end     ; # Create another child of 0, with a
#                              generated name. The name is returned
#                              as the result of the command.

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. 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 output 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

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

CATEGORY

Data structures

COPYRIGHT

Copyright © 2002-2004,2012 Andreas Kupries