virtual listbox in Swing

I'm trying to figure out how to make a virtual listbox (or tree or outline) in Swing -- this would be one where the listbox can show a "view" within a large result set from a database without getting the entire result set's contents; all it needs to give me is a heads up that Items N1 - N2 are going to need to be displayed soon, so I can fetch them, and ask for the contents of item N.

I know how to do it in Win32 (ListView + LVS_OWNERDATA) and in XUL (custom treeview), and I found something for SWT, but not Swing.

Any suggestions?

update: aha, I didn't understand what to look for in search engines, & the tutorials don't seem to call it a "virtual listbox" or use the idea. I found a good tutorial that I can start from, and one of the Sun tutorials seems ok also.

Here's my example program, which works the way I expect... except it seems like the listbox queries my AbstractListModel for all rows, not just the rows that are visible. For a million-row virtual table this isn't practical. How can I fix this? (edit: it seems like setPrototypeCellValue fixes this. But I don't understand why...)

package com.example.test;

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.AbstractListModel;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JList;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JSpinner;
import javax.swing.SpinnerModel;
import javax.swing.SpinnerNumberModel;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

// based on:
// http://www.java2s.com/Tutorial/Java/0240__Swing/extendsAbstractListModel.htm
// http://www.java2s.com/Tutorial/Java/0240__Swing/SpinnerNumberModel.htm
// http://java.sun.com/j2se/1.4.2/docs/api/javax/swing/SpinnerNumberModel.html
// http://www.java2s.com/Tutorial/Java/0240__Swing/ListeningforJSpinnerEventswithaChangeListener.htm

public class HanoiMoves extends JFrame {
    public static void main(String[] args) {
        HanoiMoves hm = new HanoiMoves();
    }

    static final int initialLevel = 6;
    final private JList list1 = new JList();
    final private HanoiData hdata = new HanoiData(initialLevel);

    public HanoiMoves() {
        this.setTitle("Solution to Towers of Hanoi");
        this.getContentPane().setLayout(new BorderLayout());
        this.setSize(new Dimension(400, 300));
        list1.setModel(hdata);

        SpinnerModel model1 = new SpinnerNumberModel(initialLevel,1,31,1);
        final JSpinner spinner1 = new JSpinner(model1);

        this.getContentPane().add(new JScrollPane(list1), BorderLayout.CENTER);
        JLabel label1 = new JLabel("Number of disks:");
        JPanel panel1 = new JPanel(new BorderLayout());
        panel1.add(label1, BorderLayout.WEST);
        panel1.add(spinner1, BorderLayout.CENTER);
        this.getContentPane().add(panel1, BorderLayout.SOUTH);      

        ChangeListener listener = new ChangeListener() {
            public void stateChanged(ChangeEvent e) {
                Integer newLevel = (Integer)spinner1.getValue();
                hdata.setLevel(newLevel);
            }
        };

        spinner1.addChangeListener(listener);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(true);
    }
}

class HanoiData extends AbstractListModel {
    public HanoiData(int level) { this.level = level; }

    private int level;
    public int getLevel() { return level; }
    public void setLevel(int level) {
        int oldSize = getSize();
        this.level = level;
        int newSize = getSize();

        if (newSize > oldSize)
            fireIntervalAdded(this, oldSize+1, newSize);
        else if (newSize < oldSize)
            fireIntervalRemoved(this, newSize+1, oldSize);
    }   

    public int getSize() { return (1 << level); }

    // the ruler function (http://mathworld.wolfram.com/RulerFunction.html)
    // = position of rightmost 1
    // see bit-twiddling hacks page:
    // http://www-graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
    public int rulerFunction(int i)
    {
        long r1 = (i & (-i)) & 0xffffffff;
        r1 *= 0x077CB531;
        return MultiplyDeBruijnBitPosition[(int)((r1 >> 27) & 0x1f)];       
    }
    final private static int[] MultiplyDeBruijnBitPosition = 
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };  

    public Object getElementAt(int index) {
        int move = index+1;
        if (move >= getSize())
            return "Done!";

        int disk = rulerFunction(move)+1;
        int x = move >> (disk-1); // guaranteed to be an odd #
        x = (x - 1) / 2;
        int K = 1 << (disk&1); // alternate directions for even/odd # disks
        x = x * K;
        int post_before = (x % 3) + 1;
        int post_after  = ((x+K) % 3) + 1;
        return String.format("%d. move disk %d from post %d to post %d", 
                move, disk, post_before, post_after);
    }
}

update:

per jfpoilpret's suggestion, I put a breakpoint in the getElementData() function.

if ((index & 0x3ff) == 0)
{
  System.out.println("getElementAt("+index+")");
}

I looked at the stacktrace for the thread in question. It's not really that helpful (posted below). From some other tweaking, however, it looks like the culprits are the fireIntervalAdded()/fireIntervalRemoved() and the change in the result of getSize(). The fireIntervalxxxx seems to clue Swing into checking the getSize() function, and if the size changes, it goes and refetches ALL of the row contents immediately (or at least it puts requests into the event queue to do so).

There must be some way to tell it Don't Do That!!!! but I don't know what.

com.example.test.HanoiMoves at localhost:3333   
    Thread [main] (Suspended (breakpoint at line 137 in HanoiData)) 
        HanoiData.getElementAt(int) line: 137   
        BasicListUI.updateLayoutState() line: not available 
        BasicListUI.maybeUpdateLayoutState() line: not available    
        BasicListUI.getPreferredSize(JComponent) line: not available    
        JList(JComponent).getPreferredSize() line: not available    
        ScrollPaneLayout$UIResource(ScrollPaneLayout).layoutContainer(Container) line: not available    
        JScrollPane(Container).layout() line: not available 
        JScrollPane(Container).doLayout() line: not available   
        JScrollPane(Container).validateTree() line: not available   
        JPanel(Container).validateTree() line: not available    
        JLayeredPane(Container).validateTree() line: not available  
        JRootPane(Container).validateTree() line: not available 
        HanoiMoves(Container).validateTree() line: not available    
        HanoiMoves(Container).validate() line: not available    
        HanoiMoves(Window).show() line: not available   
        HanoiMoves(Component).show(boolean) line: not available 
        HanoiMoves(Component).setVisible(boolean) line: not available   
        HanoiMoves(Window).setVisible(boolean) line: not available  
        HanoiMoves.<init>() line: 69    
        HanoiMoves.main(String[]) line: 37  
    Thread [AWT-Shutdown] (Running) 
    Daemon Thread [AWT-Windows] (Running)   
    Thread [AWT-EventQueue-0] (Running) 

Update: I tried using some of the FastRenderer.java code from the Advanced JList Programming article and that fixed it. But it turns out it's not the renderer at all! One line of code fixed my problem, and I don't understand why:

list1.setPrototypeCellValue(list1.getModel().getElementAt(0));

The problem is that even using intelligent pre-fetch you cannot guarantee that all visible rows were prefetched when they are needed.

I'll sketch a solution which I used once in a project and which worked extremely well.

My solution was to make a ListModel will return a stub for missing rows that tell the user, that the item is loading. (You can enhance the visual experience with a custom ListCellRenderer which renders the stub specially). Additionally make the ListModel enqueue a request to fetch the missing row. The ListModel will have to spawn a thread which reads the queue and fetches the missing rows. After a row was fetched invoke fireContentsChanges to the fetched row. You can also use a Executor in you listmodel:

private Map<Integer,Object> cache = new HashMap<Integer,Object>();
private Executor executor = new ThreadPoolExecutor(...);
...
public Object getElementAt(final int index) {
  if(cache.containsKey(index)) return cache.get(index);
  executor.execute(new Runnable() {
        Object row = fetchRowByIndex(index);
        cache.put(index, row);
        fireContentsChanged(this, index, index);
  }
}

You can improve this sketched solution in the following ways:

• No only fetch the requested item but also some items "around" it. The user likely will scroll up and down.
• In case of really big lists make the ListModel forget those rows which are far away from the ones fetched last.
• Use a LRU-cache
• If desired prefetch all items in the background thread.
• Make the ListModel a Decorator for a eager implementation of ListModel (this is what I did)
• If you have multiple "big" ListModels for Lists visible at the same time use a central request queue to fetch the missing items.