The Blt extension provides Tcl with a complex tree data structure, eg.

  set t [tree create]
  foreach i {Able Baker Charlie} { $t insert 0 -label $i }
  $t set 0->Able X 1 Y 2
  $t incr 0->Able X

1.  Static Tree.

Preloaded data trees are quite simple to define with the wize *tree command. Each line represents one row of data with the first token being the key. Subtrees are defined if the last element contains newlines. Titles fields are specified with a leading equals =. Here is an example:

 *tree new t = {
    = Age Salary
    Managers {
        = Age Salary Title
        Tina 29 10000 President
        Tom  28 8000 VP
    }
    Staff {
        # Inherit the titles of parent ie. "Age Salary".
        Mary 10 6000
        Sam  10 6000
    }
    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 Products
        NA {
            Oracle 888001 active
            MS     888002 active
        }
        SA {
            Pemex 888008 disabled
            Snapon {
                = Class Items
                pipes {single double twin}
                tools {spanners sockets wrenches}
                wire  { 10 12 14 16 18 }
            }
        }
        Europe {
            Finetix 888009 active { pipes {single twin} wire  { 10 12 14 16 18 } }
        }
    }
 }

 pack [treeview .t -tree $t -width 600 -height 600] -fill both -expand y
 eval .t col insert end [lsort [$t keys nonroot]]
 .t open all

 puts [$t get 0->Vendors->NA->Oracle]
 puts [$t incr 0->Vendors->NA->Oracle Id 0.5]
 puts [$t find -top 0->Vendors -name 888* -glob -key Id]

2.  Flat Tree Example

The following loads a table of data into a tree, then updates it. (See also Tables)

variable Users {
     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}}
 }

 # Load it.
 set t [tree create]
 foreach {l d} $Users {
    $t insert end -label $l -data $d  -tags $l
 }

 # Update it.
 $t update   tom       Sex F   Name "Tomi Brown" Age 21
 $t append   sam       Name " Jr"
 $t lappend  sam       Class 5
 $t incr     mary      Age
 $t update   tom       Rate(A) 2
 $t set      tom       Sax F
 $t set      sam       Rate(C) 0
 $t incr     0->mary   Age;   # Address via label instead of tag.

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

Note: nodes can be addressed using the form 0->LABEL. Tags can also be used to simplify indexing.

3.  Nested Tree Example

The following example loads data into a nested tree. (See Trees)

variable Info {
    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}}
    }
    admin {
        sully    { Name "Sully Van Damme"  Level 3 }
        maverick { Name "Maverick Gump"    Level 1 }
    }
}

# Load it. 
set s [tree create]
foreach {n vals} $Info {
    set ind [$s insert end -label $n -tags .$n]
    foreach {l d} $vals {
        $s insert $ind -label $l -data $d -tags .$n.$l
    }
}

# Do queries.
$s update   .network.dmz   Address 192.168.11
$s update   .network.wan   Class(A) 2

set old [$s get  .system.bing]
$s update   .system.bing   OS Linux Version 3.4
eval $s set .system.bing   $old; # ROLLBACK!

$s insert   .admin -label linus -data { Name "Linus Torvalds" Level 9 }
$s delete   .admin.sully


pack [treeview .s -tree $s -width 600] -fill both -expand y
eval .s column insert end [$s keys all]
.s open all

4.  Label & Tags

Nodes can be referenced using the label relative to the root, eg:

  $s update   0->system->bing   OS Linux Version 3.4

However, label indexing has several limitations.

If a duplicate labels exists in the same parent the first match is quietly used. And care must be used to avoid labels with spaces, leading integers, or the names of builtins like nextnode, or firstchild (unless quoted).

Another way is to use the index command, which suppors label path lookups, eg:

  $s update [$s index {system bing}]  OS Linux

Using tags however is simpler, and when used with a tag trace avoids duplicates.

5.  Enums

A tree can be used as a simple enum by simply setting keys in node 0.

  set t [tree create]
  $t set 0   apple 1 orange 2 banana 3
  puts [$t get 0]       ;  # "apple 1 orange 2 banana 3"
  puts [$t names 0]     ;  # "apple orange banana"
  puts [$t values 0]    ;  # "1 2 3"
  puts [$t get 0 apple] ;  # "1"

Multiple enums are also easily defined:

  set t [tree create]
  $t set 0  fruit { apple 1 orange 2 banana 3 }
  $t set 0  veggy { pea 1 bean 2 cabbage 3 }

  puts [$t get 0 fruit(apple)] ;  # "1"
  puts [$t get 0 veggy(bean)]  ;  # "2"

Alternatively, create each enum in its own node:

  set t [tree create]
  $t insert end -tags fruit -data { apple 1 orange 2 banana 3 }
  $t insert end -tags veggy -data { pea 1 bean 2 cabbage 3 }

  puts [$t get fruit apple] ;  # "1"
  puts [$t get veggy bean]  ;  # "2"

If using > 21 keys per node, see 12.  Key Hashing.

6.  With

Tree supports the with statement for accessing key data via an array. On entry it copies key values into an array variable, and on completion copies them back out. eg:

$t with s .system.sol {
     $t with b .system.bing {
          set s(OS)      $b(OS)
          set s(Version) $b(Version)
     }
}

See TreeWith for more details.

7.  Traces

Tree supports setting traces on nodes or notifiers on the tree. See TreeTrace for details.

8.  Performance

Performance is generally quite good. See here for details.

9.  Tree Iterators

The following tree commands iterate over a tag:

Name	Description
appendi	Append strings to key value.
incri	Increment a key value.
keys	Return keys for one or more nodes.
lappendi	Append list element to key value.
modify	Change data value for existing key.
set	Set/create data value for key.
sum	Sum values for a key field
vecdump	Dump values to a vector
vecload	Load values from a vector
with	Assign keys value to an array and eval

10.  Code Validation

wize supports validation of tree commands thus enabling static checking of tree code. To use this requires writing code using the tree object as data rather than as command. Thus the first example would be rewritten as:

 tree op update  $t tom Sex F Name "Tomi Brown" Age 19
 tree op append  $t sam     Name " Jr"
 tree op lappend $t sam     Class 5
 tree op incr    $t mary    Age
 tree op update  $t tom     Rate(A) 2
 tree op set     $t tom     Sax F
 tree op set     $t sam     Rate(C) 0
 tree op incr    $t 0->mary Age

The most important use is probably for with, eg.

     tree op with $t .system.bing b {
          set s(OS) LX
          set a b c
     }

to detect scripting errors.

11.  Data Validation

See Struct for one approach to data validation.

12.  Key Hashing

For nodes with 21 or fewer keys, tree remembers the order of key creation. Nodes with more than 21 keys will automatically change over to hash-table based key storage. One side-affect of this is that it alters the order of key iteration, which can change the results from get/names/values. That's because list-based storage preserves the order in which keys are added, whereas a hash-based storage has an undetermined order.

This can be overcome by creating the tree with a large -keyhash size (eg. 1000000).

For example, the following sets keys from a list and avoids being hashed:

  set t [tree create -keyhash [llength $lst]]
  set n -1
  foreach i $lst {
    $t set 0   $i [incr n]
  }
  puts [$t names 0 ; # outputs the original $lst.

Note that adding just one more key will cause the above to switch to hashing and thus scramble the lst order.

© 2008 Peter MacDonald