Deep copy and persistence of a BWidget's Tree

ABU 21 Jun 2005

This article introduces some new general operations that can be applied to a BWidget::Tree.

BWidget's Tree (from now on, "bw-tree") lacks in operations for persistent-storage (see persistence) and for deep (recursive) copy

This article provides a tcl-code implementation and examples aimed to overcome these lacks.


Well, I think we can start with a botanical metaphor ...

If we think at a bw-tree as a live tree, we could start thinking at a dried-tree as a synthetized clone of a bw-tree, i.e. a new kind of a copy of (a part of) a bw-tree.

This dried-tree is not a bw-tree; it is a derived from a bw-tree, but it cannot be handled with the usual bw-tree methods.

But there are many things we can do with a dried-tree :

We can graft a dried-tree in a live tree. Once grafted, the dried-tree becomes a 'live' part of the tree.

Moreover, we can also store the dried-tree in a box (a file) so that the bw-tree can be revitalized when the application re-starts ( or in a new application )

_
I believe we could review the whole terminology, converting the botanical terms in an proper graph-theory terminology ... this is not important here; purpose of this article is to discuss an extensions, determine its completeness and coherence, and discover its limitations.
Lars H
You wouldn't want the trees to be graph-theoretical trees, trust me. There are huge differences between what a computer scientist considers to be a tree and what a graph theorist considers to be a tree -- the computer scientists wants all sorts of bells and whistles in their constructs. and the bw-trees are clearly on the CS side. The botanical terminology seems entirely appropriate. On a completely different issue, you may want to think about whether it could be useful for a no-Tk interpreter to manipulate dried-trees.

That's the leading metaphor, now let's develope the idea ...

  • We need a way to create copies of a (part of a ) bw-tree.
  • These copies should be persistent, that is, they should survive after the application quits.

Let's call them dried-trees.

  • A dried-tree is a compact linear notation for storing the structure and contents of a BWidget's tree (bw-tree).
  • dried-tree can be used for restoring the original bw-tree,

but they can also be used for grafting, that is, they can be inserted under a node of an existing bw-tree.

Summarizing, we need new methods to:

  • create a dried-tree from a (sub-)bw-tree
  • graft the dried-tree under a node of a bw-tree (the original bw-tree or a different bw-tree)
  • store the dried-tree in a file
  • get a dried-tree from a file ( and then graft in a bw-tree)

Before looking at the core tcl-code for these new operations, I think it is important to look at some use cases:

  • Let's start creating a (classic) bw-tree ...
  #
  # this is our basic sample tree
  #
 package require BWidget
 pack [Tree .tree]
 .tree insert end root a  -text Aaa
 .tree insert end root b  -text Bbb
 .tree insert end root c  -text Ccc
 .tree insert end a    a1 -text Aa1
 .tree insert end a    a2 -text Aa2
 .tree insert end c    c1 -text Cc1
 .tree insert end c    c2 -text Cc2

  # some decorations ... 
 set font1 {Courier 10 bold}
 set font2 {Times 10 italic}
 set font3 {Helvetica 10 bold}

 .tree itemconfigure a  -font $font1 -fill blue
 .tree itemconfigure a1 -font $font1 -fill blue
 .tree itemconfigure a2 -font $font1 -fill blue
 .tree itemconfigure b  -font $font2 -fill gray
 .tree itemconfigure c  -font $font3 -fill red
 .tree itemconfigure c1 -font $font3 -fill red
 .tree itemconfigure c2 -font $font3 -fill red

. http://web.tiscali.it/irrational/tcl/bwtree0.0/ScreenShot001.gif

  • Get a clone
 # clone the 'c' subtree
 set myDriedTree [BWidget::Tree::clone .tree c]
  • Graft it under the "a" node (at position 1)
 BWidget::Tree::graft $myDriedTree .tree "a" 1

. http://web.tiscali.it/irrational/tcl/bwtree0.0/ScreenShot002.gif

  • Graft it in a new tree (under the root node)
 toplevel .new ; pack [Tree .new.tree]
 BWidget::Tree::graft $myDriedTree .new.tree root end

. http://web.tiscali.it/irrational/tcl/bwtree0.0/ScreenShot003.gif

  • Save it in a persistent store (a file)
 BWidget::Tree::store $myDriedTree driedA.dat
  • Retrieve a dried-tree from a file
 set myDriedTree [BWidget::Tree::load driedA.dat]
  # .. then you can start grafting in a bw-tree ....

  • The core tcl-code
 ##  bwtree.tcl
 ##
 ##  Copyright (c) 2005 <Irrational Numbers> : <[email protected]>
 ##
 ##  This program is free software; you can redistibute it and/or modify
 ##  it under the terms of the GNU General Public License as published by
 ##  the Free Software Foundation.
 ##

 package require BWidget

 namespace eval BWidget::Tree {
   ### unnecessary code
   ### namespace export every cancel

     # constant.  
     #  This is a special nodeID representing the 'root' of the dried-tree.
     #  Since "root" is a reserved ID for a bw-tree, and it is never copied,
     #   we can use it in a dried-tree without fear of overlapping.
   variable pseudoRoot  root


   proc _GetNodeOptions { tree node } {
      set res {}
      foreach c [$tree itemconfigure $node] {
         set option [lindex $c 0]
         set value  [lindex $c 4]
         lappend res $option $value
      }
      return $res
   }


    # return value: a 'dried-tree'
    #  i.e. a string containing a tcl-command 
    #       for rebuilding $node and all its descendants 
   proc clone {tree nodeID} {
      variable pseudoRoot

      if { $nodeID == "root" } {
          set L ""
          foreach n [$tree nodes root] {
              append L [_clone $tree $n \$tgtIdx $pseudoRoot]
              append L {if { $tgtIdx != "end" } {incr tgtIdx}} \n
          }
      } else {
          set L [_clone $tree $nodeID \$tgtIdx $pseudoRoot]
      }
      return $L
   }

   proc  _clone { tree nodeID idxString parent } {
      set options [_GetNodeOptions $tree $nodeID]
      set cmd [ format {set map(%s) [$tgtTree insert %s $map(%s) #auto %s ]} \
              $nodeID $idxString $parent $options]  

      append cmd \n   
      foreach child [$tree nodes $nodeID] {
          append cmd [_clone $tree $child end $nodeID]
      }
      return $cmd
   }


   proc graft { driedTree tgtTree parent tgtIdx } {
      variable pseudoRoot

      set map($pseudoRoot) $parent
       # NOTE: $tgtTree, $tgtIdx are used by driedTree
      eval $driedTree
   }


   proc store { driedTree fileName } {
      set f [open $fileName w]
      puts $f "$driedTree"
      close $f
   }


   proc load { fileName } {
      set f [open $fileName r]
      set driedTree [read $f] 
      close $f
      return $driedTree
   }
 }

 package provide BWidget::Tree 0.0

LIMITATIONS

This package (BWidget::Tree rev. 0.0) does not work if the cloned nodes contain some kind of reference to external objects.

In particular, nodes having the "-image" and "-window" options set will introduce some usage limitations...

-window
since two nodes with the -window option cannot share the same object, it is not possible to 'duplicate' such nodes. You should take care of duplicating the referred widgets ... difficult ...
-image
the limitation is minor since an image can be shared by many nodes, but, before 'recreating' a tree in a new application, you should ensure that the referenced images have been already loaded.

.. other ?


ABU 21 Jun 2005 - Removed (commented) unnecessary code from the attached package.


Schnexel Wrrr, the BWidget tree is so stupid! Already the graphics says it all: Look at the Screenshots above: The children nodes´ lines branch before the parent node, so parent node and child node graphically have the same parent node (the +/- box). Is there any Tcl/Tk tree that one can take serious?


ABU I like BWidget Tree.

  • The first reason is because it's pure-tcl code; it runs on ANY platform.
  • The second reason is that it is quite complete, and it has a well founded drag&drop support.
  • Third, altough its basic graphical look is notexciting, it is deeply customizable via 'configure'

Which other tree-widgets have these features ?


chin - 2009-09-10 05:59:32

The Id of the node is not maintained, if the tree is saved and loaded.

ABU The Id of the new nodes is automatic; think it as a serial number. This is necessary to avoid duplicated IDs.