ulis, 2002-11-09, Mass-widget, a design issue

  (My english is very bad, so I'll be happy if you correct it. 
  But, please, double check the meaning and, if needed, ask me: mailto:maurice.ulis@wanadoo.fr)

----

  What is it?
  
  A mass-widget is a widget that can handle from 1,000 to 1,000,000 items, and more.
  The best exemple is the list box. 
  Others exemples are the list box' derivatives: 
  - combo box (an entry associated with a list box), 
  - grid box (list boxes organized in columns).
  
  Why worrying?

  Now that hard disks are very large, directories can contain many thousands of files.
  I remember to become very unhappy when my new Columns megawidget died not so gracefully 
  when I wanted to display a huge directory: 
  my widget was busy a long time and suddently disappeared!
  So I tried to deal with that and written a list box megawidget that can handle 
  1,000,000 items and more.
  You can find this Hugelist megawidget at http://perso.wanadoo.fr/maurice.ulis/tcl/Hugelist.
  
  Problems and solution with mass-widgets
  
  There are two main problems:
  - displaying, selecting, scrolling, moving, resizing a mass-widget can hog all the CPU,
  - a 1,000,000 items mass-widget can hog all the memory.
  The two problems are addressed with sharing. 
  Sharing some display subwidgets for the first, 
  sharing common configurations for the second.
  I call this kind of solution a virtual subwidgets solution. 
  This is correlated with the "flyweight" design pattern (see: http://mini.net/tcl/2339).
  
  Sharing display subwidgets
  
  To display 1,000,000 items we only need to have the twenty display rows 
  that are visible inside our widget.
  Displaying twenty other items is matter of mapping them on the visible rows.
  Doing so has some implications when we want to select an item:
  - when selecting, we have to do the mapping between the selected visible row 
  and the currently displayed item,
  - when displaying, we need to know if a visible row is displaying a selected item.
  There is no difficulty here, just to deal with the mapping of the virtual items 
  and the registered set of selected items.
  And doing so has some implications when we want to scroll thru the items:
  The classical mechanism ([scrollbar set] and [widget x/yview]) can't be used directly.
  This is because we can't offset the visible area inside the widget surface: 
  we limited the widget surface to the visible area.
  So we have to redefine the mass-widget [x/yview] procs 
  and call the scrollbars' [set] proc ourself.
  And deal with the refreshment of the visible area.
  
  Sharing configurations
  
  In the Tk list box the configuration of each item contains four colors: 
  the foreground and background colors in the selected or the normal state.
  If each color needs 10 bytes and each item needs a 10 bytes control structure, 
  we need near 50 Mb to register the configurations of 1,000,000 items.
  We can do it with current computers but then the mass-widget 
  becomes very heavy to displace or to resize.
  You can experiment this with the demo script included in my Hugelist package: 
  editing the source permits you to toggle between hugelist and listbox.
  Happily mass-widgets tend to have standardized items which share common configurations. 
  So a lightweighted solution is to have shared configurations 
  and each item referencing these configurations.
  A more lightweighted solution is to define a set of items intervals, 
  each interval associated with a configuration.
  Using shared configurations implies to be able to mass-configure the items.
  That is a whole set of items is configured at once or each item of a set 
  is repeatedly configured with the same configuration.
  
  Indeed, the text of each item can't be integrated in shared configurations and is saved apart.

----

# Displaying virtual items

  # ------------------------
  # parameters
  # ------------------------
  
  set visible_width   20        ; # visible area width, in chars
  set visible_height  20        ; # visible area height, in rows
  set char_width      8         ; # char width, in pixels
  set char_height     16        ; # char height, in pixels
  set items_count     1000000   ; # items count
  
  # ------------------------
  # items init
  # ------------------------
  
  wm title . "items init..."
  update
  for {set i 0} {$i < $items_count} {incr i} { lappend items item-$i }
  wm title . "mass-widget"
  update
  
  # ------------------------
  # widget init
  # ------------------------
    
  set canvas_width    [expr {$visible_width * $char_width}]
  set canvas_height   [expr {$visible_height * $char_height}]
  frame .f
  canvas .f.c -width $canvas_width -height $canvas_height \
              -bg white -bd 2 -relief sunken
  set y 4
  set width [expr {$canvas_width + 4}]
  for {set i 0} {$i < $visible_height} {incr i} \
  { 
    .f.c create text 6 $y -tags text$i -anchor nw
    .f.c create rectangle 4 $y $width [incr y $char_height] \
                          -tags rect$i -outline ""
    .f.c raise text$i
  }
  
  # ------------------------
  # display proc
  # ------------------------
    
  proc display {} \
  {
    set item [.e get]
    for {set i 0} {$i < $::visible_height} {incr i} \
    { 
      .f.c itemconf text$i -text [lindex $::items $item]
      .f.c itemconf rect$i -fill ""
      incr item
    }
  }
  
  # ------------------------
  # interface
  # ------------------------
  
  label .l -text "enter an item number"
  entry .e 
  .e insert end 0
  button .b -text display -command display
  
  # ------------------------
  # start
  # ------------------------
    
  pack .f 
  pack .f.c -side left
  pack .l .e .b -pady 5
  display
  focus -force .e

----

# scrolling virtual items

  # ------------------------
  # scroll bar init
  # ------------------------
    
  scrollbar .f.s -command yview
  pack .f.s -side left -fill y
  
  # ------------------------
  # scroll procs
  # ------------------------
    
    # setting the scroll bar
  proc yset {} \
  {
    set first [.e get]
    set last [expr {$first + $::visible_height}]
    .f.s set [expr {double($first) / $::items_count}] \
             [expr {double($last) / $::items_count}]
  }
    # setting the visible area
  # parm1: scroll command (moveto or scroll)
  # parm2: scroll command args
  proc yview {cmd args} \
  {
    switch $cmd \
    {
      moveto    \
      {
        # absolute movement
        set first [expr {int($args * $::items_count)}]
      }
      scroll    \
      {
        # relative movement
        set count [lindex $args 0]
        set units [lindex $args 1]
        if {[string match p* $units]} \
        {
          # paging
          set count [expr {$count * $::visible_height}]
        }
        set first [.e get]
        incr first $count
      }
    }
    # setting the scroll bar & displaying the visible area
    if {$first < 0} { set first 0 }
    if {$first > $::items_count - $::visible_height} \
    { set first [expr {$::items_count - $::visible_height}] }
    .e delete 0 end
    .e insert end $first
    yset
    display
  }
  
  # ------------------------
  # button command
  # ------------------------
    
  .b config -command { yset; display }
  yset

----

# configuring virtual items

  # ------------------------
  # new config
  # ------------------------
  
  set defconf {"" black navy white}   ; # default config
  set configs [list $defconf]         ; # registered configs

  # parm1: config to register
  # return: config ID
  proc newconfig {config} \
  {
    set ID [llength $::configs]
    lappend ::configs $config
    return $ID
  }

  # ------------------------
  # new range
  # ------------------------
  
  set ranges {{0 0}}                         ; # config ID associated with each item
  
  # parm1: first item
  # parm2: last item
  # parm3: config ID
  proc newrange {first last CID} \
  {
    if {$first == [lindex [lindex $::ranges end] 0]} \
    {
      # add a new range
      set ::ranges [lreplace $::ranges end end [list $first $CID] [incr last]] 
    } \
    else \
    {
      # replace a range
      set step 1
      foreach range $::ranges \
      {
        foreach {start newID} $range break
        switch $step \
        {
          1 \
          {
            # before first
            if {$start < $first} \
            { 
              lappend newranges $range 
              if {$newID != ""} { set curID $newID }
            } \
            else \
            {
              lappend newranges [list $first $CID]
              if {$newID != ""} { set curID $newID }
              set step 2
            }
          }
          2 \
          {
            # between first & last
            if {$start > $last} \
            {
              lappend newranges [list [incr last] $curID]
              if {$newID != ""} { set curID $newID }
              set step 3
            } \
            elseif {$newID != ""} { set curID $newID }
          }
          3 \
          {
            # after last
            lappend newranges $range
          }
        }
      }
      if {$step == 2} { lappend newranges [list [incr last] $curID] }
      lappend newranges $::items_count
      set ::ranges $newranges
    }
  }

  # ------------------------
  # retrieve a config
  # ------------------------
  
  # parm1: item ID
  # return: registered config
  proc retrieve {item} \
  {
    set CID 0
    foreach range $::ranges \
    {
      foreach {start newID} $range break
      if {$start > $item} { break }
      set CID $newID
    }
    return [lindex $::configs $CID]
  }

  # ------------------------
  # mass-configure items
  # ------------------------

  # parm1: first item to configure
  # parm2: last item to configure (optional)
  # parm3: modified options from last config
  proc config {first last args} \
  {
    # get args
    if {[string index $last 0] == "-"} \
    { set args [linsert $args 0 $last]; set last "" }
    if {$last == ""} { set last $first }
    # modify & register config
    set CID [llength $::configs]; incr CID -1
    if {$args != ""} \
    {
      set config [lindex $::configs $CID]
      set changed 0
      foreach {background foreground selbackground selforeground} $config break
      foreach {key value} $args \
      {
        switch -glob -- $key \
        {
          -bg       -
          -bac*     { set background $value; set changed 1 }
          -fg       -
          -for*     { set foreground $value; set changed 1 }
          -selb*    -
          -selectb* { set selbackground $value; set changed 1 }
          -self*    -
          -selectf* { set selforeground $value; set changed 1 }
          -tex*     { set ::items [lreplace $::items $first $last $value }
        }
      }
      if {$changed} \
      {
        # create a new config
        set config [list $background $foreground $selbackground $selforeground]
        set CID [newconfig $config]
      }
    }
    # associate items range and config ID
    newrange $first $last $CID
  }

  # ------------------------
  # new display proc
  # ------------------------
  
  proc display {} \
  {
    set item [.e get]
    for {set i 0} {$i < $::visible_height} {incr i} \
    { 
      # retrieve config
      set config [retrieve $item]
      foreach {background foreground selbackground selforeground} $config break
      # map item 
      .f.c itemconf text$i -text [lindex $::items $item] -fill $foreground
      .f.c itemconf rect$i -fill $background
      incr item
    }
  }

  # ------------------------
  # configure & display
  # ------------------------
  
  # set global background
  set last [expr {$items_count - 1}] 
  config 0 $last -bg beige
  # change some items
  set incr [expr {$items_count / 100}]
  if {$incr == 0} { set incr 10 }
  for {set i 0} {$i < $items_count} {incr i $incr} { config $i -fg red }
  # display
  display