Author: Thomas Bierhance
02.11.2004 Bug fixes (a bug list is available now), new insides on the mac os x problem and a new section on performance.
27.09.2004 Some bug fixes and a new addition...
Next update will discuss performance issues when using combo boxes with lot of items.
13.09.2004 We received more feedback - fixed some bugs and added new features...
31.08.2004 Thanks to the quick feedback from the people at Javalobby, some issues were identified. This update addresses the following...
Please contact me via email for further feedback.
Searching for an item in a combo box can be cumbersome if the box contains a lot of items.
If the user knows what he is looking for, it should be sufficient to enter the desired item. The user should be supported with automatic completion. This article shows how to implement this feature using the standard JComboBox without modifying it or inheriting from it. Although the following covers JComboBox, you should be able to auto-complete enable any combo box that follows Sun's design paradigm including data-aware combo boxes from 3rd parties.
You have a good knowledge of Swing or you really don't care about how the automatic completion works? You might want to skip the explanations and just look at the usage information.
The user can type into the combo box and his input will be automatically completed to the next matching item in the combo box. Except for this added auto-completion the combo box will behave as usual. Let us assume that the currently selected item is "Ester" but the user is looking for "Jorge" - he or she starts typing away...
The user interface therefore provides three information:
To realize the automatic completion the following features are needed:
While 3. and 4. can be realized straightforward, 1. and 2. need some understanding of the implementation details of JComboBox.
JComboBox is implemented as a compound component. It basically consists of a JButton with an arrow that pops up a JPopupMenu that contains all items. One can select an item that then can be edited in a JTextField.
Note that these are assumptions about the implementation that may not hold when using custom "look-and-feels".
Following the MVC Pattern the items are contained in a data model separated from the combo box itself.
Using the methods getSize and getElementAt one can easily iterate over the items. The selected item is controlled by the methods getSelectedItem and setSelectedItem. ComboBoxModel is an interface, details can be found in the default implementation DefaultComboBoxModel.
JComboBox offers convenience methods that call their counterparts in the model (getItemCount, getItemAt, setSelectedItem, getSelectedItem)
When a combo box is editable the user can enter text. See how this has been realized...
The editor is represented by the interface ComboBoxEditor. It can be assumed that the editor component is a JTextComponent. Once again following MVC the text is contained in a separated model (interface Document).
When the user enters or deletes text using his keyboard, the corresponding methods (insertString, remove) are called on the text component's document model.
Although there are possibly many ways to catch the input to a text component, only one is shown here. It is the same that once has been suggested by Sun's Java Tutorial to add validation to text components (replaced by JFormattedTextField ). It suggests to get control over the user input by implementing a specialized Document overriding the methods insertString and remove. Input to the text component can then be rejected, accepted or transformed in these two methods.
Let us start with an editable combo box that is not accepting anything to demonstrate how to change the editor component's document.
public class S01BadDocument extends PlainDocument {
public void insertString(int offs, String str, AttributeSet a) {
// reject the insert but print
a message on the console
System.out.println("insert " + str
+ " at " + offs);
}
public static void main(String[] args) {
// the combo box (add/modify items
if you like to)
JComboBox comboBox = new JComboBox(new Object[] {"Ester",
"Jordi", "Sergi"});
// has to be editable
comboBox.setEditable(true);
// get the combo box' editor component
JTextComponent editor = (JTextComponent) comboBox.getEditor().getEditorComponent();
// change the editor's document
to our BadDocument
editor.setDocument(new S01BadDocument());
// create and show a window
containing the combo box
JFrame frame = new JFrame();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().add(comboBox);
frame.pack(); frame.show();
}
}
Watch the console for output while you are selecting items and trying to enter text. Note that you indeed can select items, their names however, are not shown in the editor.
To actually select an item in the combo box access to the combo box' model is needed inside our document. It can be passed as a parameter to the constructor (omitted here, see sourcecode). Adding some kind of automatic selection inside insertString...
public void insertString(int offs, String str, AttributeSet a) throws
BadLocationException {
// insert the string into the document
super.insertString(offs, str, a);
// get the resulting string
String content = getText(0, getLength());
// lookup a matching item
Object item = lookupItem(content);
// select the item (or deselect if null)
model.setSelectedItem(item);
}
private Object lookupItem(String pattern) {
// iterate over all items
for (int i=0, n=model.getSize(); i < n; i++) {
Object currentItem = model.getElementAt(i);
// current item starts with the
pattern?
if (currentItem.toString().startsWith(pattern)) {
return currentItem;
}
}
// no item starts with the pattern => return
null
return null;
}
This automatic selection works, but it is rather confusing. This is due to the fact, that some magic already seems to do the automatic completion. Watch the console: if the users types 'J' the output looks like...
insert J at 0
insert Jordi at 0
However the user only inserted 'J' and the program does not contain any explicit call to insert the string 'Jordi'.
It comes out, that the call to setSelectedItem provokes another call to insertString with the newly selected item. This should normally lead to an infinite loop. On Sun's JDKs this won't happen when using DefaultComboBoxModel, as it only calls insertString if the selected item has not been selected before. However, when using a custom model or a JDK from Apple or IBM the call to setSelectedItem will not return. A flag can be set to indicate that setSelectedItem has been called from insertString. Any subsequent call will then return immediately without further processing when the flag is set.
// return immediately when selecting
an item
if (selecting) return;
[...]
selecting=true;
model.setSelectedItem(item);
selecting=false;
Now, to do automatic completion instead of just automatic selection access to the combo box' editor is needed. Otherwise it would not be possible to highlight the completed part using selection (see above). I added the whole JComboBox to the constructor. The selection should start right after the last character that was inserted (at position offs+str.length()).
See how the highlighting works inside insertString...
// remove all text and insert the
completed text
remove(0, getLength());
super.insertString(0, item.toString(), a);
// select the completed part
JTextComponent editor = (JTextComponent) comboBox.getEditor().getEditorComponent();
editor.setSelectionStart(offs+str.length());
editor.setSelectionEnd(getLength());
Although this works, it is not a robust implementation. However, it is a good starting point. You can strengthen the implementation on your own or follow the article...
The following additions are considered to be minor additions as they are small in size, easy to implement and often subject to personal preference and needs. However, the impact on the user experience can not be overestimated!
The typical usecases for an autocompleting combo box will hardly need case sensitive matches. It is easy to modify the lookup mechanism to ignore case, so that the user does not have to care about typing 'E' or 'e'. This short method does the trick...
private boolean startsWithIgnoreCase(String str1, String str2) {
return str1.toUpperCase().startsWith(str2.toUpperCase());
}
It's not convincing from a user's point of view, that the selected item might change although the entered letter fits the currently selected item (try it on your own: Select the item 'Jordina' and hit 'o' afterwards - 'Jordi' gets selected). Another modification to the lookup mechanism...
private Object lookupItem(String pattern) {
Object selectedItem = model.getSelectedItem();
// only search for a different item if the
currently selected does not match
if (selectedItem != null && startsWithIgnoreCase(selectedItem.toString(),
pattern)) {
return selectedItem;
} else [...]
}
If the user entered a key that does not match any item you get a NullPointerException. Of course this is not acceptable. A small enhancement in the insertString method will ignore 'invalid' input.
// lookup and select a matching item
Object item = lookupItem(getText(0, getLength()));
if (item != null) {
comboBox.setSelectedItem(item);
} else {
// keep old item selected if there is no match
item = comboBox.getSelectedItem();
// imitate no insert
// (later on offs will be incremented by str.length(): selection
won't move forward)
offs = offs-str.length();
// provide feedback to the user that his input
has been received but can not be accepted
// normally a "beep" that is
UIManager.getLookAndFeel().provideErrorFeedback(comboBox);
}
The solution is straight forward, although you might wonder why it is needed to decrement the offset. Try it yourself without the decrement (the cursor will move on as if you had typed the right letter).
In the first place there was no error feedback (normally a "beep") - I added it after a usability test. Users would sometimes wonder why the combo box was not accepting their input. The beep indicates to the user that his input has been received and processed but can not be accepted. Again, these little things make a big difference to the user experience!
I found that experienced users (aka power users) don't like their computer to beep and are tempted to turn this off. Don't do it - future users of your application (likely less experienced) will appreciate it.
When the user selects an item via mouse or using the cursor keys, the text is not highlighted. When the user select an item directly, the insertString method is called once with the complete string. Inside this method only completed text is highlighted which in this case is none, as the call already contained the complete string.
A solution is to highlight the complete text whenever an item gets selected and this selection was not initiated by the autocompletion mechanism. This can be achieved using an ActionListener...
comboBox.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
if (!selecting) highlightCompletedText(0);
}
});
One information that the user would like to have is the "neighbourhood" of the selected item (as has been described at the beginning). It would be nice to have the item list to popup when the user starts typing. The easiest solution is easy to add a KeyListener and call JComboBox.setPopupVisible whenever a keystroke is detected...
editor.addKeyListener(new KeyAdapter() {
public void keyPressed(KeyEvent e) {
if (comboBox.isDisplayable()) comboBox.setPopupVisible(true);
}
});
Note that calls to setPopupVisible() might fail (IllegalComponentStateException) when the combo box is not visible. A check is done to prevent this from happening although a keystroke on the editor is unlikely to occur when the combo box is not visible ;-)
This is really a minor addition and more a question of personal preference. You might have noticed that the cursor normally is located at the end of the completed text. If you prefer it to be at the beginning of the selected text try this...
private void highlightCompletedText(int start) {
editor.setCaretPosition(getLength());
editor.moveCaretPosition(start);
}
It is a quiet annoying that the initially selected item is not shown in the combo box. This can be easily changed in the constructor of the auto completing document.
public S11InitialSelection(JComboBox comboBox) {
[...]
editor.setDocument(this);
[...]
// Handle initially selected object Object
selected = comboBox.getSelectedItem();
if (selected!=null) setText(selected.toString());
highlightCompletedText(0);
}
Another situation that needs highlighting of the complete text is when the user switches to another gui control (e.g. pressing the tabulator key). Otherwise the partial selection would still be there when the user returns to the combo box. Highlighting the complete text when the combo box loses focus could be a solution. However, switching the focus via mouse will not lead to the desired behaviour then: The cursor gets positioned by the mouse click and therefore the prior selection is removed. A better solution is to highlight the text when the focus is gained.
// Highlight whole text when gaining focus
editor.addFocusListener(new FocusAdapter() {
public void focusGained(FocusEvent e) {
highlightCompletedText(0);
}
});
The popup list is hidden automatically when the user hits enter on most JDKs. The latest Java 1.5 release from Sun contains a bug and keeps the popup list visible. The popup list can't be hidden for all JDK versions as this might lead to malfunctioning. A workaround could look like this...
// Bug 5100422 on Java 1.5: Editable JComboBox
won't hide popup when tabbing out hidePopupOnFocusLoss=System.getProperty("java.version").startsWith("1.5");
// Highlight whole text when gaining focus
editor.addFocusListener(new FocusAdapter() {
[...]
public void focusLost(FocusEvent e) {
// Workaround for Bug 5100422
- Hide Popup on focus loss
if (hidePopupOnFocusLoss) comboBox.setPopupVisible(false);
}
});
One inconvenience is that after hitting backspace the selection is not moved backwards as one would expect. I first thought that this be would easy to implement. However, it came out that there are some tramps one should be aware of.
First, have a look when and how (parameters) the remove method is called...
You will have noticed that the method has been called on every key stroke whether you hit backspace or not. This happens because the selected text will always be removed before inserting a new letter!
Now, when should the selection move backwards and when should some text really be removed? Inside the remove method the information is needed if it was called because the user hit backspace or if it has been called for other reasons. There already is a KeyListener on the combo box' editor, so a boolean member variable named hitBackspace can be introduced that indicates whether the last key that has been pressed was backspace or not...
public void keyPressed(KeyEvent e) {
if (comboBox.isDisplayable()) comboBox.setPopupVisible(true);
hitBackspace=false;
if (e.getKeyCode()==KeyEvent.VK_BACK_SPACE) hitBackspace=true;
}
The remove method can now be modified.
public void remove(int offs, int len) throws BadLocationException {
// return immediately when selecting an item
if (selecting) return;
if (hitBackspace) {
// user hit backspace => move
the selection backwards
// old item keeps being selected
highlightCompletedText(offs-1);
} else {
super.remove(offs, len);
}
}
You might have noticed two remaining bugs: Pressing backspace at the beginning (e.g. when the complete text is highlighted) results in an IllegalArgumentException. Another inconvenience is that when the cursor is positioned on the end pressing backspace extends the selection to the last two characters not only to the last one. To solve this we also need to know if something was selected when the user hit backspace. Another variable to indicate this is introduced and the KeyListener and the remove method are modified accordingly. I also chose to ignore the deletion key...
editor.addKeyListener(new KeyAdapter() {
public void keyPressed(KeyEvent e) {
if (comboBox.isDisplayable()) comboBox.setPopupVisible(true);
hitBackspace=false;
switch (e.getKeyCode()) {
// determine if the
pressed key is backspace (needed by the remove method)
case KeyEvent.VK_BACK_SPACE :
hitBackspace=true;
hitBackspaceOnSelection=editor.getSelectionStart()!=editor.getSelectionEnd();
break;
// ignore delete key
case KeyEvent.VK_DELETE :
e.consume();
UIManager.getLookAndFeel().provideErrorFeedback(comboBox);
break;
}
}
});
public void remove(int offs, int len) throws BadLocationException {
// return immediately when selecting an item
if (selecting) return;
if (hitBackspace) {
// user hit backspace => move
the selection backwards
// old item keeps being selected
if (offs>0) {
if (hitBackspaceOnSelection) offs--;
} else {
// User hit backspace
with the cursor positioned on the start => beep
UIManager.getLookAndFeel().provideErrorFeedback(comboBox);
}
highlightCompletedText(offs);
} else {
super.remove(offs, len);
}
}
This feature is about reducing the amount of key strokes a user has to do to select an item. In our five name example it is obvious that when the user types 'J' he either means "Jordi", "Jordina" or "Jorge". All three of them start with "Jor". This can be taken into account when making the selection of the completed text. A picture makes it clear how this mechanism is supposed to work...
The user needs only two keystrokes instead of four to select "Jorge". This feature is not a really big advantage in the five name case from this article, but imagine a combo box with a list of chemical substances to choose from - like...
In cases like this one you might consider the maximum match feature (e.g. it takes 4 keystrokes instead of 18 to select the second entry).
However, take care in other circumstances: users don't like things happening out of their control. This feature can produce more confusion than clarity.
Enough warnings - how is it implemented?
As before, an item has been looked up in regard to the user's input. Now an iteration is done over all items again and other items that would have matched the user's input are collected. All these candidates are compared to find out if they have a common starting text. The common starting text won't be highlighted after the completion as if it was entered by the user. The main method to consider does the comparison...
// calculates how many characters are predetermined
by the given pattern.
private int getMaximumMatchingOffset(String pattern, Object selectedItem) {
String selectedAsString=selectedItem.toString();
int match=selectedAsString.length();
// look for items that match the given pattern
for (int i=0, n=model.getSize(); i < n; i++) {
String itemAsString = model.getElementAt(i).toString();
if (startsWithIgnoreCase(itemAsString, pattern)) {
// current item matches
the pattern
// how many leading characters have the
selected and the current item in common?
int tmpMatch=equalStartLength(itemAsString,
selectedAsString);
if (tmpMatch < match) match=tmpMatch;
}
}
return match;
}
Other modifications have been made to the insert method.
Further examples will not made use of this feature.
I was asked if it is possible to do non-strict matching - allowing the user to enter an item that is not (yet) contained in the combo box. This one is fairly easy to implement. Instead of rejecting non-matching input, accept it is accepted. The rejecting section inside the insert method...
if (item != null) {
setSelectedItem(item);
} else {
// keep old item selected if there
is no match
item = comboBox.getSelectedItem();
// imitate no insert
// (later on offs will be incremented
by str.length(): selection won't move forward)
offs = offs-str.length();
// provide feedback to the user that his input
has been received but can not be accepted
UIManager.getLookAndFeel().provideErrorFeedback(comboBox);
}
setText(item.toString());
// select the completed part
highlightCompletedText(offs+str.length());
...to accept all input it can be replaced by...
boolean listContainsSelectedItem = true;
if (item == null) {
// no item matches => use the current input
as selected item
item=getText(0, getLength());
listContainsSelectedItem=false;
}
setText(item.toString());
// select the completed part
if (listContainsSelectedItem) highlightCompletedText(offs+str.length());;
This works, but has some inconveniences:
The first issue can't be resolved very easily. Each insert would be written to a protocoll and later the original string could be reconstructed (here's the difficult part). I did a hack that is not really worth to be published but you can contact me, if you can't live without this feature.
The second needed some coding. It won't be explained here in more detail.
Further examples will not made use of this feature.
When the list contains a lot of items the autocompletion becomes less responsive. A lot of items is of course a relative term - I found that a few thousands work out ok, while searching tens of thousands is too slow. In the following section it is explained how to make the autocompletion more responsive.
When doing performance optimization one could follow these basic steps:
Applying the second step to our algorithm I identified two hotspots. As you might have expected, the brute force searching in lookupItem is resulting in linear cost. The method is accounting for approximately 30% of the total time spent in auto completion. Another even "hotter" spot to our surprise is JComboBox.setSelectedItem. About 70% of the total time is spent in this method!
I also found that most time was spent calculating sizes of strings (FontDesignMetrics.stringWidth).
The linear increase in execution time indicates that calls to setSelectedItem will cause iterations over all items inside the combo box. The setSelectedItem method is quiet short, but inspite of that it is hard to tell where these iterations happen exactly: swing is doing a lot of processing via indirect event notifications.
Setting a breakpoint on setSelectedItem and stepping through the call graph inside a debugger will end up in frustration soon. I set a second break point on DefaultComboBoxModel.getElementAt to find out where these iterations are done. From the call graph I found the following invocations:
Having a closer look at the BasicListUI.updateLayoutState method you will notice that the problematic code section is only executed on a condition:
if ((fixedCellWidth == -1) || (fixedCellHeight == -1)) {
[hotspot code]
}
If you set a prototype cell value on the list (JList.setPrototypeCellValue) the code won't be executed at all. Unfortunately the combo box' JList can't be accessed easily and the equivalent combo box method (JComboBox.setPrototypeDisplayValue) won't do the trick either. This is a bug - for the time being a workaround is to use reflection to set the prototype value.
The JList can be obtained using reflection from the combo box' UI delegate...
JList getListBox() {
JList listBox;
try {
Field field = JComponent.class.getDeclaredField("ui");
field.setAccessible(true);
BasicComboBoxUI ui = (BasicComboBoxUI) field.get(comboBox);
field = BasicComboBoxUI.class.getDeclaredField("listBox");
field.setAccessible(true);
listBox = (JList) field.get(ui);
} catch (NoSuchFieldException nsfe) {
throw new RuntimeException(nsfe);
} catch (IllegalAccessException iae) {
throw new RuntimeException(iae);
}
return listBox;
}
Now, it is possible to set a prototype value for both the combo box and the list. Only an appropriate prototype value is missing. It is likely the best choice to apply the same strategy that is used by the UI delegates to determine the biggest item (iterating over all items and choose the widest item). The only difference is, that you are now in control of when this code gets executed...
Object getPrototypeValue(JList list) {
Object prototypeValue=null; double prototypeWidth=0;
ListCellRenderer renderer = comboBox.getRenderer();
for (int i=0, n=model.getSize(); i<n; i++) {
Object value = model.getElementAt(i);
Component c = renderer.getListCellRendererComponent(list,
value, i, false, false);
double width = c.getPreferredSize().getWidth();
if (width>prototypeWidth) {
prototypeWidth=width;
prototypeValue=value;
}
}
return prototypeValue;
}
The prototype value should be updated whenever the combo box' datamodel has been changed.
Optimization is done. I profiled the auto completion again and found that the selection time was improved by more than 60%. That's an overall improvement of more than 40%.
complete source demo
applet
(~750KB; applet uses reflection, hence java asks for permission)
Now a start over: check if the total performance is acceptable. Many users perceive a response within 50 ms to be instantaneous. There's still work left.
Another idea is to tweak the lookup algorithm. Normally, the items will be ordered. This makes it possible to apply a modified binary search algorithm. The one that comes with Collections.binarySearch() can not be used, because it does an exact match instead of a partial match ("Jor" should match "Jorge" in our case). The following comparison is only taking the first letters into account...
private static int compareStartIgnoreCase(String str1, String str2) {
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
for (int i=0, n=ch2.length<ch1.length?ch2.length:ch1.length;
i<n; i++) {
int diff = Character.toUpperCase(ch2[i])-Character.toUpperCase(ch1[i]);
if (diff != 0) {
return diff;
}
}
if (ch1.length<ch2.length) return 1;
return 0;
}
I applied the well known binary search algorithm using this comparison. When a matching item has been found, this item is not being used straight away, because it is preferable to select not any but the first matching item. Therefore, the first matching item ist searched starting from the last lower bound. This degrades the lookup algorithm from O(log n) back to O(n), but it now makes up less than 5% of the total time spent when auto completing.
Anything below 25000 items feels quiet responsive with this solution. When using 50000 items it is still usable, but feels sluggish sometimes.
complete source demo
applet
(~750KB; applet uses reflection, hence java asks for permission)
An option worth considering is not to display all items inside the combo box, but only the matching items.
Another problem has been mentioned on the demo page: the lookup sometimes does not work. How come? Well, the items need to be ordered, but what does that exactly mean? Ordering strings is not as crystal clear as ordering numbers is. An option to workaround this problem would be a ternary search tree.
Both options will be explored in a future update.
Maybe another improvement could be made to the JComboBox.getSelectedIndex() method. It's not quiet convincing that selecting an item from a combo box is an O(n) and not a constant time operation.
Further examples will not made use of this feature.
If you want to use automatic completion in your own project just download this source code. Then use the following snippet in your GUI code...
AutoCompletion.enable(yourComboBox);
Combo boxes from third parties might not inherit from JComboBox. In this case the enable method won't work, but you still have a good chance to get it working. Look at the explanations from above and try to find hooks where you can apply the needed modifications to your combo box.
Drop me a note when you were sucessfull in applying the code to non standard combo boxes (3rd party, custom extensions, ...), as well as when you can't get it to work, find bugs, make interesting enhancements, etc!
Note that the maximum match, the non-strict match and the binary lookup feature are not part of this final source code.
On Mac OS X the popup is reported to be covering the textfield and therefore making autocompletion unusable. Curtis Stanford added that this is only true for combo boxes with less than 12 items. Alex Sherer remarks, that this limit (12 items) can be modified by using JComboBox.setMaximumRows. He also suggests, that if you can live without the aqua look&feel for the combo box you could easily switch: comboBox.setUI(new BasicComboBoxUI()) - though this will produce some ClassCastExceptions.
A typical approach to use a JComboBox inside a JTable is to use the DefaultCellEditor:
yourColumn.setCellEditor(new DefaultCellEditor(yourComboBox));
After having enabled the combo box to do automatic completion this code will stop working. This is due to the fact that the DefaultCellEditor will apply all procedures to stop editing when an item is selected. These procedures include hiding the combo box! But remember what we are doing in our sourcecode from above:
[...]
Object item = lookupItem(futureText);
model.setSelectedItem(item); // DefaultCellEditor
will hide the combo box!!!
remove(0, getLength());
super.insertString(0, futureText, a);
[...]
comboBox.setPopupVisible(true);
Now, because editing has been stopped after calling setSelectedItem, the modifications to the underlying document via insertString and remove will be ignored (at least the user won't see them ;-). Furthermore, the call to comboBox.setPopupVisible will lead to an java.awt.IllegalComponentStateException because the comboBox is visible no more. What now?
A solution would be to fix the actions that have been applied by the DefaultCellEditor.
Mainly that is, putting the cell into editing mode again (jTable.editCellAt(row,
column)). But it's never a good idea trying to reverse changes that have been
applied by portions of code you don't control: What if the code changes?
This would also lead to tighter coupling: We would need another reference to
the JTable. But what if the combo box is used without a JTable or inside a JTree?
A better approach is to fix the problem at its roots and get control over the problematic code. In this case that means writing a different CellEditor. This leads to better code with less coupling.
We give an example implementation named ComboBoxCellEditor, but won't explain it here. It depends on the class AbstractCellEditor introduced by JDK Version 1.3. If you would like to know more about JTable and CellEditor take a look at the source of DefaultCellEditor, this article by Brett Spell from IBM's developerworks or the section about JTable from Sun's java tutorial.