Recent Changes - Search:

Tree

(:toc:)

Tree

The Blt extension provides Tcl with a complex tree data (Overview of data in Tcl) 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

Dict/Array Keys

Keys in a tree may store a dict that is accessed using an array-like notation, eg.

  $t insert 0 -label Harry -data {X 1 Y "a 1 b 2"}
  $t incr 0->Harry Y(a)

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 {
        Tina 29 10000
        Tom  28 8000
    }
    Staff {
        Mary 10 6000
        Sam  10 6000
    }
  }

Trees are useful because of their ease of update and access:

 *tree new t = {
    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]

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.

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

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.

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

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.

Traces

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

Performance

Performance is generally quite good. See here for details.

Tree Iterators

The following tree commands iterate over a tag:

NameDescription
appendiAppend strings to key value.
incriIncrement a key value.
keysReturn keys for one or more nodes.
lappendiAppend list element to key value.
modifyChange data value for existing key.
setSet/create data value for key.
sumSum values for a key field
vecdumpDump values to a vector
vecloadLoad values from a vector
withAssign keys value to an array and eval

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.

Data Validation

See Struct for one approach to data validation.

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.

Edit - History - Print - Recent Changes - Search
Page last modified on September 15, 2010, at 06:54 PM