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:
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:
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:
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
}