1.  Trees using *tree

The *tree utility simplifies the creation and management of hierarchical data using a Tcl tree. The tree is setup to a variable and is automatically destroyed when the variable is deleted (eg. when exiting a function).

The *tree new command takes 1-3 arguments: the variable name, the type of the tree, and data used to populate the tree.

The type is one of:

• "=" - Labeled-Node Tree
• "*" - Unlabeled-Node Tree
• "-" - Flat Tree
• "+" - Varying Tree
• N - an integer giving nesting depth of the tree.

2.  Labeled-Node Tree: =

The = tree is the simplest form to use. It specifies one node per line with subtrees having embedded newlines in the last element. The key/titles are specified in the first row using a line starting with =. Comments start with a #.

 *tree new Ids = {
     = Age Gender Email
     Admin {
         Bob   9 M bob@frik.com
         Tina 19 F tina@hotmail.com
         John 18 M john@gmail.com
     }
     # This is a comment.
     User {
         Mary 10 F mary@gmail.com
         Jim  13 M jim@csc.com
     }
  }

This creates a new tree and sets it into the variable Ids. Data can be accessed thus:

  puts [$Ids get 0->Admin->Bob Age]
  $Ids set 0->Admin->Bob Gender ?
  array set q [$Ids get 0->Admin->Bob]

  $Ids incr 0->Admin->Tina Age
  $Ids incr 0->User->Jim Age 2
  $Ids incri all Age

  # Display it. 
  pack [treeview .z -tree $Ids -width 400] -fill both
  eval .z col insert end [$Ids keys nonroot]

2.1  Multiple Keys

Trees can define disjoint key sets within sublevels. Keys not defined in a level are derived from the parent, eg.

   *tree new emp = {
       = Age Salary
       Managers {
           # Age Salary Title
           Tina 29 10000 President
           Tom  28 8000 VP
       }
       Staff {
           Mary 10 6000 09
           Sam  10 6000 09
       }
       Contractors {
           = Age Salary Hired
           Mary 10 6000 09
           Sam  10 6000 09
       }
       Suppliers {
           = Id Description
           Costco 999012 "General goods"
           GM     999013 "Vehicles and service"
       }
       Vendors {
           = Id Status
           NA {
               Oracle 888001 active
               MS     888002 active
           }
           SA {
               Pemex 888008 disabled
           }
           Europe {
               Fintix 888009
           }
    }

    $emp incr 0->Staff->Mary Age

3.  Unlabeled-Node Tree: *

Alternatively, unlabeled data can be inserted with:

  *tree new x * {
       # Name Age
       Bob 9
           Tina 19
           John 18
       Mary 10
  }
  $x incr 1 Age

This however, is not as useful as labeled nodes as indexing is less intuitive.

4.  A Raw Tree: -

A raw or "-" tree simply dumps data directly into nodes, eg.

  *tree new data - { 
      { Name "Tom Brown"  Sex M Age 19 }
      { Name "Mary Brown" Sex F Age 16 }
      { Name "Sam Spade"  Sex M Age 19 }
  }

This is equivalent to:

  set data [tree create]
  foreach i $lst { $t insert 0 -data $i }

No checking is done and no indexing is provided.

5.  A Varying Depth Tree: +

A plus "+" describes a Varying Depth Tree.

6.  Integer Depth Trees

Integer depth trees provide integrity check to ensure a tree contains no duplicate keys.

Elements are indexed in one of two ways:

• depth=0 uses the label of each element as the index.
• depth>0 uses dot-delimiters to reflect record nesting.

Inserts and updates to *trees are managed to ensure that tags addresses are correctly maintained. Element labels in any case may not contain a dot.

Here is a *tree example of depth 3.

namespace eval ::myapp {

    *tree new mt 3 {
        operations {
            system {
                sol  { OS Linux Version 3.4 }
                bing { OS Win Version 7 }
                gui  { OS Mac Version 8 }
            }
            network {
                intra { Address 192.168.1  Netmask 255.255.255.0 }
                dmz   { Address 192.168.10 Netmask 255.255.255.0 }
                wan   { Address 0.0.0.0 Netmask 0.0.0.0 Class {A 1 B 4}}
            }
            admins {
                sully    { Name "Sully Van Damme" Level 3 }
                maverick { Name "Maverick Gump"     Level 1 }
            }
        }
        users {
            staff {
                morris { Name "Morris Trance" email morris@serve.com }
                sully  { Name "Sully Van Damme" email svd@a.b }
            }
            students {
                billyg { Name "Billy Gene" email billyg@serve.com }
            }
        }
    }

Access is like so:

  
    proc Main {args} {
        variable mt

        # Update it.
        $mt update  .operations.system.sol    Version 3.5   OS LX
        $mt incr    .operations.admins.sully  Level
        $mt insert  .users.staff -label manny -data { Name "Manny Gee" }
        $mt set     .users.staff.manny        email   manny@gee.com
        $mt incr    .operations.network.wan   Class(A) 2
        $mt append  .users.students.billyg    Name ", Jr"

        # Display it!
        pack [treeview .t -tree $mt] -fill both -expand y
        eval .t col insert end [$mt keys all]
        .t open all

        # Add some cool styles.
        .t style create textbox alt -bg lightblue
        .t conf -width 600 -bg white -underline 1 -altstyle alt
        eval .t col conf [.t col names] -relief raised -bd 1
    }

    eval Main $argv
}

7.  Flat Tree Example

Here is a flat (depth 0) *tree example. It is similar to *table, except values require the key name:

namespace eval ::myapp {

    *tree new mt 0 {
        tom  { Name "Tom Brown"  Sex M Age 19  Class {4 5} Rate {A 1 B 2}}
        mary { Name "Mary Brown" Sex F Age 16  Class {5}   Rate {A 2}}
        sam  { Name "Sam Spade"  Sex M Age 19  Class {3 4} Rate {B 3}}
    }


    proc Main {args} {
        variable mt

        # Update it.
        $mt update   tom       Sex F   Name "Tomi Brown" Age 21
        $mt append   sam       Name " Jr"
        $mt lappend  sam       Class 5
        $mt incr     mary      Age
        $mt update   tom       Rate(A) 2
        # The above only do updates. Now add some fields.
        $mt set      tom       Sax F
        $mt set      sam       Rate(C) 0

        # Display it.
        pack [treeview .t -tree $mt] -fill both -expand y
        eval .t column insert end [$mt keys all]
    }

    eval Main $argv

}

If we had used depth 1, indexes would use dot prefixes, eg:

       $mt set     .tom       Sex F
       $mt update  .sam       Rate(C) 2

Trees of depth >= 1 allow user defined tags, so long as tags don't start with a dot.

8.  Features

Following discusses some of the features of *tree.

8.1  Tag Addressing

Elements in the tree are automatically tagged to simplify addressing, both on load and when using insert. This provides 3 ways to address nodes: id, labels and tags, ie.

  $mt update  3                           Version 3.5
  $mt update  0->operations->system->sol  Version 3.5
  $mt update  .operations.system.sol      Version 3.5

Using tags for addressing avoids limitations with labels, namely: duplicates, integers and reserved words. (See the manpage for details.)

8.2  Integrity Constraints

Elements in the tree are automatically managed to prevent duplicates and maintain consistency. This includes when:

• The tree is initially loaded.
• Adding nodes with insert.
• Moving nodes with move.
• Changing labels with label.

Here are some examples that, in the context of the above, would generate duplicate errors:

  $mt insert  .operations.admins -label sully
  $mt label   .operations.admins.sully maverick
  $mt move    .operations.admins.sully .users.staff

8.3  Trace and Notify

Users can set traces to get control everytime a field is updated. Similarly, notifys can be set to get control everytime records are inserted, deleted or renamed, etc.

This is in fact how *tree provides integrity checking.

8.4  Performance

Performance in tree is surprisingly good, eg.

% time { $t incr .operations.admins.sully Level } 1000
3.979 microseconds per iteration
% time { $t incr 0->operations->admins->sully Level } 1000
5.537 microseconds per iteration
% time { $t incr .operations.network.wan Class(A) } 1000
4.413 microseconds per iteration

Compare this with Tcl:

% time { incr ::xx::pc(i) } 1000
1.757 microseconds per iteration
% time { dict incr xx::pc(a) i } 1000
6.98 microseconds per iteration

Note that although an array variable update is 2-3 times faster than tree, array+dict is actually slower. Performance gets worse still when another dict get is added to extract the field i:

% time { dict get [dict incr xx::pc(a) i] i } 1000
10.603 microseconds per iteration

Furthermore, tree is actually faster than a Tcl array when operating on ranges of node with tags:

% $t set all Level 1
19
% time { $t incri all Level } 1000
17.461 microseconds per iteration

The above updates 19 nodes in 18 microseconds, or 1 microsecond per node.

Now look what happens when we use array names to emulate tag-ranges:

% set i 0; while {[incr i]<=19} { set H($i) 1 }
% time { foreach i [array names H] { incr H($i) } } 1000
88.461 microseconds per iteration

To summarize, updating ranges with Tcl array can be 5 times slower (88/17.5) then tree using tags.

(Note: the tests for trees were performed unattached from treeview widgets as gui notification adds some overhead.)

9.  Struct Validation

Sometimes if you're writing lots of code it can be difficult to ensure sufficient code coverage tests. So being able to validate code without having to execute it can be helpful.

To achieve this with tree we can use generated access functions via *struct, which enables statically checkable code.

For example, we could add the following code:

    *struct new admin {
        { Name  {}  "Name of user" -notnull 1 }
        { Level 0   "Level of user" -type {Int -min 0} }
    } -typecheck 1 -strict 1

    proc Doit {} {
        variable mt
        S_admin $mt .operations.admins.sully    Level -99
        S_admin $mt .operations.admins.sully    Leve 0
    }

    proc Main {args} { ...

which when run warns of potential errors:

% wize -Wall /tmp/tre3.tcl

/tmp/tre3.tcl:39: warning: for argument #4 "args", the value
 "-99" does not match type <Int -min 0>  for "S_admin $mt
 .operations.admins.sully    Level -99" in proc [::myapp::Doit] <types,4>.
/tmp/tre3.tcl:40: warning: for argument #3 "args", the value
 "Leve" does not match type <Topts Name . Level {Int -min 0}> 
 for "S_admin $mt .operations.admins.sully    Leve 0" 
in proc [::myapp::Doit] <types,4>.

If Doit was actually executed, runtime errors would occur for either statement.

10.  GUI

Trees and tables are supported in gui, eg.

#!/usr/bin/env wize

# "File foo.gui"
{Toplevel +} {
  style {
     TreeView { -height 100 }
  }
  {TreeView - -tabledata foo2 -nice 1 -pos *} {
     # {Name Age}
     bob {Bob   9}
     bill {Bill  10}
  }
  {TreeView - -tabledata foo -nice 1 -pos *} {
     {Name Age}
     {Bob   9}
     {Bill  10}
  }
  {TreeView - -treedata {bar 0} -nice 1 -pos *} {
        tom  { Name "Tom Brown"  Sex M Age 19  Class {4 5} Rate {A 1 B 2}}
        mary { Name "Mary Brown" Sex F Age 16  Class {5}   Rate {A 2}}
        sam  { Name "Sam Spade"  Sex M Age 19  Class {3 4} Rate {B 3}}
  }
}

© 2008 Peter MacDonald