Updated 2006-05-22 20:22:25 ▲

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

What is it?

A mass-widget is a widget that can handle from 1,000 to 1,000,000 items, and more. The best example is the listbox. Others examples are the listbox' derivatives:

  • combobox (an entry associated with a listbox),
  • grid box (listboxes organized in columns).

Why worry?

Now that hard disks are very large, directories can contain many thousands of files. I remember becoming 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 wrote a listbox 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, or resizing a mass-widget can hog all the CPU,
  • a 1,000,000 item mass-widget can hog all the memory.

The two problems can be addressed through 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: Design patterns in Tcl).

Sharing display subwidgets

To display 1,000,000 items we only need to show 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.

This is not difficult, we just need 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 refreshing the visible area.

Sharing configurations

In the Tk listbox 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 nearly 50 Mb to register the configurations of 1,000,000 items. We can do it with current computers but the mass-widget becomes very heavy to move or 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. Luckily mass-widgets tend to have standardized items which share common configurations. So a lightweight solution is to have shared configurations and each item referencing these configurations. A more lightweight solution is to define a set of item intervals, each interval associated with a configuration. Using shared configurations allows one to mass-configure the items. I.e. a whole set of items is configured at once or each item of a set is repeatedly configured with the same configuration.

In fact, the text of each item can't be integrated in shared configurations, so it is saved separately.

I can see where this might be an issue with the BWidgets tree widget. Conceptually I see both of these as an example where there is a view port used to display a current subset of a potentially very large set of data. Putting all of the data in a native widget or a megawidget might be possible, but it could also cause massive problems. Part of the problem is that the widget controls need to control the base set of data and not just the currently displayed subset. So there is a need for some indirection or virtualization between the controls and the display mechanisms. Only some of the data that might need to be displayed needs to be saved for data not currently being displayed. You could keep an array that tracked which nodes of a tree were not collapsed. As the user navigated around the tree and different pieces were swapped into the native widget, the state of the tree nodes would be recreated from the associated data instead of being all stored within the tree widget itself.

--escargo 11/11/2002

# 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

# selecting items
  # ------------------------
  # select binding
  # ------------------------

  bind .f.c <1> { select %y }

  # ------------------------
  # select proc
  # ------------------------

  set selection {}                ; # selected items list
  # parm1: y listbox coordinate
  proc select {y} \
  {
    # get item
    set item [expr {[.e get] + $y / $::char_height}]
    # toggle select state
    set n [lsearch $::selection $item]
    if {$n == -1} { lappend ::selection $item } \
    else { set ::selection [lreplace $::selection $n $n] }
    # display
    display
  }

  # ------------------------
  # new display proc
  # ------------------------

  proc display {} \
  {
    # get first item
    set item [.e get]
    # display all visible items
    for {set i 0} {$i < $::visible_height} {incr i} \
    {
      # retrieve config
      set config [retrieve $item]
      foreach {background foreground selbackground selforeground} $config break
      # set colors
      if {[lsearch $::selection $item] != -1} \
      {
        set background $selbackground
        set foreground $selforeground
      }
      # map item
      .f.c itemconf text$i -text [lindex $::items $item] -fill $foreground
      .f.c itemconf rect$i -fill $background
      incr item
    }
  }

# editing items
  # ------------------------
  # edit binding
  # ------------------------

  bind .f.c <Double-1> { edit %y }

  # ------------------------
  # edit proc
  # ------------------------

  set edited  ""                      ; # edited item
  # parm1: y listbox coordinate
  proc edit {y} \
  {
    # get row and mapped item
    set row [expr {$y / $::char_height}]
    set item [expr {[.e get] + $row}]
    # save item
    set ::edited $item
    # create edit box
    foreach {x y} [.f.c bbox text$row] break
    set text [lindex $::items $item]
    set width [expr {[string length $text] * 2}]
    entry .edit -width $width \
                -validate focusout -vcmd validate
    .edit insert end $text
    .edit selection range 0 end
    place .edit -in .f.c -x $x -y $y
    # focus management
    bind .edit <Return> validate
    focus -force .edit
    set ::binding [bind .f.c <1>]
    bind .f.c <1> {+ focus .f.c }
  }

  # ------------------------
  # validate proc
  # ------------------------

  proc validate {} \
  {
    # get item
    set item $::edited
    # get new text
    set text [.edit get]
    # update item
    set ::items [lreplace $::items $item $item $text]
    # display
    place forget .edit
    display
    # restore as before
    bind .f.c <1> $::binding
    focus -force .e
    after idle destroy .edit
    return 1
  }

Category GUI | Category Design | Category Performance | Category Widget