Creating a Sorted Component

Articles Index

My personal digital assistant (PDA) provides contact information for friends, family, and coworkers. The PDA allows me to find a person's phone number easily by searching on that person's name. The information is sorted according to standard dictionary-sort order for the contact's name. That is, the name Michèle comes before Robert in the list. Without this sort order, I would have difficulty finding names quickly and easily.

Java technology programmers often use the javax.swing.JList component to provide list views of similar data, whether it be a phone contact list or a grocery list. Despite the convenience of this user interface (UI) component, a JList doesn't sort its elements. It displays them in the same order provided by its underlying javax.swing.ListModel interface. Neither the ListModel interface nor the javax.swing.DefaultListModel class provides sorted data. Instead, the default model provides its content in the same order as you enter it. If you enter unsorted data -- for example, the letters B, C, and A -- the model provides it to list components without sorting it to either ascending order -- A, B, C -- or to descending order -- C, B, A. Lists are appropriate UI components for many applications, but an unsorted list has limited usefulness.

This article describes how to produce sorted lists and uses a simple application to demonstrate concepts. You can download all the demo source code using the link at the end of this article. Although I developed the demo source as a NetBeans IDE 5.0 project, the demo's ANT script does not require that you use that IDE to compile or execute the application. The demo application uses the decorator design pattern to provide additional functionality to the ListModel object you already use. This allows you to use and benefit from a sorted model after making only minimal changes to your existing application code base. You really can have your list model and sort it too.

The demo application uses two main classes:

• SortedListModel
• SortedListModelDemo

The SortedListModel class is a decorator class that implements all the sorting functionality. The SortedListModelDemo class contains the application that demonstrates how to use the SortedListModel.

Requirements for a SortedListModel class are the following:

• Use the decorator design pattern to provide sorting to any ListModel object
  
• Provide mapping between the sorted-list representation and the unordered list
  
• Allow programmers to provide their own java.util.Comparator object to compare model elements
  
• Provide ascending, descending, and unordered sort
  
• Require minimal updates to existing application code
  

The final demo will look like Figure 1. The demo displays a JList component, a radio box with sort-order options, and Add and Delete buttons. Of course, you can use the SortedListModel class with more complex applications too.

Figure 1. You can create sorted lists with the decorator pattern.

The decorator or wrapper design pattern allows you to add responsibilities to existing objects at runtime. Although you can use subclassing to add functionality to a class, using the decorator pattern at runtime is more flexible. Decorators provide the same interface to their clients as the wrapped component -- or decoratee -- provides to its clients, but decorators usually perform additional tasks. They typically perform these tasks before or after passing method calls to the decorated object.

Version 6 of the Java Platform, Standard Edition (Java SE, formerly referred to as J2SE) will add sorting and filtering abilities to the javax.swing.JTable class. * The Java Foundation Classes/Swing (JFC/Swing) engineering team has added a TableRowSorter class to Java SE 6 to handle sorting and filtering. This class behaves like a decorator in that it represents the underlying table model and adds sorting to it at runtime. You create a TableRowSorter object by providing the original table model in the constructor. Then you call the table's setRowSorter method. Thereafter, the JTable object will use the TableRowSorter object to get a sorted representation of the base model. Unfortunately, this same feature is not yet available for the JList class, nor will it be available in the next release. But we can borrow the decorator idea to create a SortedListModel class that adds sorting abilities to any ListModel object. Note: The demo application and code in this article apply to all versions of the JDK through version 6.

Because a SortedListModel object must wrap a ListModel object, it should at least implement the same interface. However, because it will also need to maintain and fire events for data listeners, I extend the javax.swing.AbstractListModel class, which provides a convenient implementation that can manage and notify ListDataListener objects.

One common way to create a decorator is to pass the wrapped object into the decorator's constructor. The SortedListModel class has a constructor that requires a reference to a ListModel object. The SortedListModel object maintains this reference to the original unsorted ListModel object so that it can pass some method calls through to it.

Because the project requirements include the ability to produce ascending, descending, or unordered sorts, the class constructor needs additional parameters. The programmer must provide a sort-order preference and a way to sort the original model's elements. A SortOrder object represents your preference for ascending, descending, or unordered sorting. Finally, a Comparator object compares model elements that will assist in the sort. Although the demo contains several constructors, they all eventually call the following one.

Code Example 1. SortedListModel constructor creates a sorted model.

 1 public SortedListModel(ListModel model, SortOrder sortOrder, 
 2                        Comparator comp) {
 3   unsortedModel = model;
 4   unsortedModel.addListDataListener(new ListDataListener() {
 5    public void intervalAdded(ListDataEvent e) {
 6       unsortedIntervalAdded(e);
 7     }
 8
 9     public void intervalRemoved(ListDataEvent e) {
10       unsortedIntervalRemoved(e);
11     }
12
13     public void contentsChanged(ListDataEvent e) {
14       unsortedContentsChanged(e);
15     }
16          
17   });
18   this.sortOrder = sortOrder;
19   if (comp != null) {
20     comparator = comp;
21   } else {
22     comparator = Collator.getInstance();
23   }
24     
25   // Get base model info.
26   int size = model.getSize();
27   sortedModel = new ArrayList<SortedListEntry>(size);
28   for (int x = 0; x < size; ++x) {
29     SortedListEntry entry = new SortedListEntry(x);
30     int insertionPoint = findInsertionPoint(entry);
31     sortedModel.add(insertionPoint, entry);
32   }
33 }

In Code Example 1, the first step in constructing the decorator is to save a reference to the original model, as shown in line 3. Because this object needs to respond when the unsorted model adds, removes, or changes elements, it adds a listener object to the original model. Because we must sort according to user prefences, the constructor records that preference in line 18. Then the application copies the Comparator object, as shown in lines 19 through 23. Of course, if you don't provide a specific Comparator object for your model's elements, this constructor creates a default Comparator, as shown in line 22. Finally, the constructor produces a sorted array of element indices by iterating through the unsorted model, finding an insertion point in the sorted list of indices, and then adding a sorted-model entry at that position. The sorted-model entry is a SortedListEntry object, which contains an index into the unsorted model.

After construction, the SortedListModel object has at least four important qualities:

• It has a reference to the original model.
  
• It knows the user's preference for a sort order.
  
• It has a Comparator object capable of comparing model elements for sorting.
  
• It has a sorted representation of the original model.
  

SortedListModel provides an inner class that represents a user's sort-order preference. This class is an enumeration called SortOrder. Enumerations are a relatively new language feature supported since Java 2 Platform, Standard Edition 5.0 (J2SE 5.0).

Code Example 2. SortOrder is an enumeration of sort preferences.

public enum SortOrder {
  UNORDERED,  // Leaves the model in its original order
  ASCENDING,  // Produces a sort in ascending order
  DESCENDING; // Produces a sort in descending order
}  

A Comparator is an interface that defines compareTo and equals methods. Classes that implement this interface are able to provide comparison results for specific types of objects. SortedListModel objects use a comparator to determine sort-order positions of all elements in the original model. Rather than duplicating all element data, the sorted model maintains only a list of pointer indices into the unsorted model. SortedListModel uses a java.text.Collator instance created for the default locale of the Java Virtual Machine (JVM). ^† A Collator instance can compare only String objects, so if your model elements are anything else, you should provide your own Comparator implementation. If you don't provide your own implementation, SortedListModel calls the toString method of your unsorted-model elements so that its own Collator instance will be able to compare the string representation of the elements.

SortedListModel maintains a sorted list of SortedListEntry elements. These elements contain only one data item, which is just an index into the unsorted model. SortedListEntry objects implement the Comparable interface, which allows the Collections class to perform binary searches on arrays and lists of these objects.

How does a SortedListEntry implement the Comparable interface? It must provide a compareTo method, of course. However, in SortedListEntry elements, this method doesn't really compare SortedListEntry objects. Instead, the compareTo method retrieves the unsorted-model element that the SortedListEntry object's index field referenced. This method uses the provided Comparator object to compare two unsorted-model elements. Figure 2 shows the mapping of SortedListEntry entries to their corresponding elements in the original unsorted model. Code Example 3 shows the compareTo method that is part of the Comparable interface.

Figure 2. The sorted model maintains a list of sorted indices that point into the unsorted model.

Code Example 3. SortedListEntry implements the Comparable interface.

public int compareTo(Object o) {
  // Retrieve the element that this entry points to 
  // in the original model.
  Object thisElement = unsortedModel.getElementAt(index);
  SortedListEntry thatEntry = (SortedListEntry)o;
  // Retrieve the element that thatEntry points to 
  // in the original model.
  Object thatElement = 
    unsortedModel.getElementAt(thatEntry.getIndex());
  if (comparator instanceof Collator) {
    thisElement = thisElement.toString();
    thatElement = thatElement.toString();
  }
  // Compare the base model's elements using the provided comparator.
  int comparison = comparator.compare(thisElement, thatElement);
  // Convert to descending order as necessary.
  if (sortOrder == SortOrder.DESCENDING) {
    comparison = -comparison;
  }
  return comparison;
}        
private int index;

When does the application invoke the compareTo method? It is called when you add or change elements in the sorted model as a result of additions, changes, or deletions in the original unsorted model. Specifically, the findInsertionPoint method in SortedListModel invokes a binary search from the Collections class. You can see this in Code Example 4.

Code Example 4. Collections can search SortedListEntry lists because the SortedListEntry class implements the Comparable interface.

/**
 * Internal helper method to find the insertion point for a new 
 * entry in the sorted model
 */
private int findInsertionPoint(SortedListEntry entry) {
  int insertionPoint = sortedModel.size();
  if (sortOrder != SortOrder.UNORDERED)  {
    insertionPoint = 
      Collections.binarySearch((List)sortedModel, entry);
    if (insertionPoint < 0) {
      insertionpoint = -(insertionpoint +1);
    }
  }
  return insertionpoint;
}  

The code in Code Example 4 performs a binary search on the SortedListEntry list to find out where a new entry should go. Notice that if the user has selected an unordered sort, the code adds the entry to the end of the sorted model.

ListModel Interface

The SortedListModel class implements the ListModel interface, so you can use it with JList components just as you could your original model. Whenever you select a cell in a JList object, the list will call this model's getElementAt method to retrieve the object that should occupy a given list cell. The list's purpose is not to display index positions, so the getElementAt implementation must convert the sorted-model index position to an unsorted-model index. The method uses the converted index to retrieve the desired element from the decoratee. How does it retrieve the desired element from the unsorted model? After converting the index to the unsorted model's index, the SortedListModel object calls the the unsorted model's getElementAt method, as shown in Code Example 5.

Code Example 5. The SortedListModel object converts its index and retrieves an element from the unsorted model.

public Object getElementAt(int index) 
    throws IndexOutOfBoundsException {
  int modelIndex = toUnsortedModelIndex(index);
  Object element = unsortedModel.getElementAt(modelIndex);
  return element;
}

Additionally, the class implements the getSize method. Because the sorted and unsorted model should always have the same elements, the size should always be the same as well. In this method, the sorted model does not have to pass any work to the underlying unsorted model. Instead, it just gets the size from its own internal list, which contains pointer indices into the decorated model.

Code Example 6. Provide the model's size as part of the ListModel interface.

public int getSize() {
  int size = sortedModel.size();
  return size;
}

Event Handlers

The sorted model must know when the unsorted model updates its content. ListModel instances provide this information to ListDataListener objects that register their interest in update events. SortedListModel registers its interest in data updates by adding a ListDataListener object within its own constructor. This anonymous listener forwards the following events to private methods within the SortedListModel object:

• unsortedContentsChanged
  
• unsortedIntervalAdded
  
• unsortedIntervalRemoved

Code Example 7. Register with the unsorted model to receive list data events.

unsortedModel.addListDataListener(new ListDataListener() {
  public void contentsChanged(ListDataEvent e) {
    unsortedContentsChanged(e);
  }

  public void intervalAdded(ListDataEvent e) {
    unsortedIntervalAdded(e);
  }

  public void intervalRemoved(ListDataEvent e) {
    unsortedIntervalRemoved(e);
  }
}); 

The unsortedContentsChanged method needs to sort the model data again whenever an element changes. Once it has finished the sort, it alerts any listeners, typically the JList, that the change has occurred. In this simple case, the method tells the list that all the elements have changed, so there is opportunity here for optimization. For example, you might improve the method by notifying the list only about changed items that are in the immediate view window.

Code Example 8. A change in the original model content generates an event that sorts the sorted model again.

private void unsortedContentsChanged(ListDataEvent e) {
  Collections.sort(sortedModel);
  fireContentsChanged(ListDataEvent.CONTENTS_CHANGED, 0, 
    sortedModel.size()-1);
}

The unsortedIntervalAdded method is more complex. When the unsorted model receives new elements, it provides the beginning and ending indices of the inserted elements to its listeners. Although those indices are consecutive numbers in the unsorted model, those indices are not in the same position in the sorted-model representation. The sorted-index pointers will now be invalid for all indices higher than the interval's beginning index. Therefore, the sorted-model indices higher than the interval's beginning must be incremented to account for this change. Once you fix the old indices to account for the additions, you can add new index values in their sorted position. See Code Example 9.

Code Example 9. Add elements to the sorted model after updating indices.

private void unsortedIntervalAdded(ListDataEvent e) {
  int begin = e.getIndex0();
  int end = e.getIndex1();
  int nElementsAdded = end-begin+1;
    
  /* Items in the decorated model have shifted position.
   * Increment model pointers into the decorated model.
   * Increment indices that intersect with the insertion
   * point in the decorated model.
   */
  for (SortedListEntry entry: sortedModel) {
    int index = entry.getIndex();
    // If the model points to a model index >= to where
    // new model entries are added, increment their index.
    if (index >= begin) {
      entry.setIndex(index+nElementsAdded);
    }
  }
  
  // Now add the new items from the decorated model
  // and notify listeners.
  for (int x = begin; x <= end; ++x) {
    sortedlistentry newentry = new sortedlistentry(x);
    int insertionpoint = findinsertionpoint(newentry);
    sortedmodel.add(insertionpoint, newentry);
    fireintervaladded(listdataevent.interval_added, insertionpoint, 
      insertionpoint);
  }   
}

The unsortedIntervalRemoved method must work similarly. Instead of incrementing affected indices, the method must decrement the affected indices. Also, it must notify listeners about the change. See Code Example 10.

Code Example 10. Remove elements from the sorted model after updating the indices.

/**
 * Update this model when items are removed from the 
 * original/decorated model. Also, let listeners know that 
 * items have been removed.
 */
private void unsortedIntervalRemoved(ListDataEvent e) {
  int begin = e.getIndex0();
  int end = e.getIndex1();
  int nElementsRemoved = end-begin+1;
        
  /*
  * Move from end to beginning of our sorted model, updating
  * element indices into the decorated model or removing
  * elements as necessary.
  */
  int sortedSize = sortedModel.size();
  boolean[] bElementRemoved = new boolean[sortedSize];
  for (int x = sortedSize-1; x >=0; --x) {
    SortedListEntry entry = sortedModel.get(x);
    int index = entry.getIndex();
    if (index > end) {
      entry.setIndex(index - nElementsRemoved);
    } else if (index >= begin) {
      sortedModel.remove(x);
      bElementRemoved[x] = true;
    }
  }
  // Let listeners know about removed items.
  for(int x = bElementRemoved.length-1; x>=0; --x) {
    if (bElementRemoved[x]) {
      fireIntervalRemoved(ListDataEvent.INTERVAL_REMOVED, x, x);
    }
  }
}

Your application will probably register to receive event notification from the JList component. When it receives notifications such as a ListSelectionEvent event, the event object will contain information about which list cell was selected. However, your application must make a choice about which it will process: the sorted- or the unsorted-model values. Most likely, you will need to process elements in the original unsorted model because that model contains the data relevant to your application. However, the ListSelectionEvent events refer to indices in the sorted model, not in the unsorted model.

Consequently, your code must convert the sorted-model selection to an unsorted-model selection. Once you have the index values for the original unsorted model, you can interact directly with the model just as you would normally. Code Example 11 shows the conversion method that the SortedListModel class provides.

Code Example 11. The SortedListModel class provides a method to convert sorted-model indices to the original unsorted-model indices.

/**
 * Convert sorted-model index to an unsorted-model index.
 * @param index an index in the sorted model
 * @return modelIndex an index in the unsorted model
 */
public int toUnsortedModelIndex(int index) 
    throws IndexOutOfBoundsException {
  int modelIndex = -1;
  SortedListEntry entry = sortedModel.get(index);
  modelIndex = entry.getIndex();
  return modelIndex;
} 

To use this sorted model for your own application, here are the few changes you will have to make. To demonstrate, I have provided a SortedListModelDemo application that shows how you might use the SortedListModel class.

In the beginning, this application uses an unsorted model to store list contents. Figure 3 shows this application. Note that the radio buttons are disabled. For the moment, the application allows the user only to add and delete list items.

Figure 3. The original application has an unsorted list.

The model is a DefaultListModel as shown in the following code.

Code Example 12. The demo application begins without sorted models.

public SortedListModelDemo() {
  super("Sorted ListModel Demo");
  unsortedModel = new DefaultListModel();
  initComponents();
}
    
private void initComponents() {
  ...
  list.setModel(unsortedModel);
  ...
}

To use the new SortedListModel class, change the following in your existing applications:

1. Create a SortedListModel object.
   
2. Add the SortedListModel object to the JList object.
   
3. Convert the sorted-model indices to unsorted-model indices where necessary.

In the SortedListModelDemo constructor, create a SortedListModel object, as shown in Code Example 13. Notice that you must "wrap" the original model by passing it as a parameter to the constructor.

Code Example 13. Updating the demo requires the creation of a sorted model.

public SortedListModelDemo() {
  super("Sorted ListModel Demo");
  unsortedModel = new DefaultListModel();
  // Add a sorted model.
  sortedModel = new SortedListModel(unsortedModel);
  initComponents();
}

Next, within the same initComponents method, as shown in Code Example 13, you must replace the JList model with the new decorator model. See Code Example 14. The code example shows the old code commented out above the new code.

Code Example 14. The demo must provide the new model to the JList object.

private void initComponents() {
  ...
  //list.setModel(unsortedModel);
  list.setModel(sortedModel);
  ...
}

Finally, when your application receives an event notification from the JList object, you must be careful to convert the reported indices from those of the sorted model to those of the original unsorted model. After all, the real data is in the original model, not in our decorator model. Code Example 15 shows an example of a demo-application listener method that must convert the indices to act on a user's selection.

Code Example 15. You must convert indices that the JList object reports.

private void 
    listValueChanged(javax.swing.event.ListSelectionEvent evt) {
  int sortedFirstIndex = evt.getFirstIndex();
  int sortedLastIndex = evt.getLastIndex();
  for (int sortedIndex = sortedFirstIndex; 
      sortedIndex <= sortedLastIndex; sortedIndex++) {
    // Convert index before using it to retrieve model elements.
    int unsortedIndex = sortedModel.toUnsortedModelIndex(sortedIndex);
    // Do something with unsorted-model index.
    System.out.printf(
        "listValueChanged index: %d (sorted) %d(unsorted)\n", 
        sortedIndex, unsortedIndex);
  }
}

The demo application allows the user to delete list elements. Because I want to delete elements in the original model, I must remember to convert the indices again, as shown in Code Example 16.

Code Example 16. Convert indices to unsorted-model indices when you need to modify elements in the unsorted model.

private void btnDeleteSelectionActionPerformed(
    java.awt.event.ActionEvent evt) {
  int[] sortedSelection = list.getSelectedIndices();
  int[] unsortedSelection = 
    sortedModel.toUnsortedModelIndices(sortedSelection);
  for (int x = unsortedSelection.length - 1; x >= 0; --x) {
    unsortedModel.remove(unsortedSelection[x]);
  }
}

You can use the decorator pattern to create sorted representations of your JList models. Decorating the model at runtime with a decorator is more flexible than is subclassing your existing models or the JList itself. Converting your existing applications to use a sorted model should be relatively simple and require few changes. Just remember to convert the indices reported from the JList to your unsorted-model indices when you need to add, delete, or change your model's content.

Although Java SE 6 will provide core library support for sorting and filtering JTable components, JList components will not have this functionality yet. In the meantime, you can add sorted JList components to your applications by using ideas and designs similar to those in this article's demo. The demonstration code works well, but it is not optimized. You might have fun optimizing the code as well as using it as is.

• Download the SortedListModel Demo source code.
  
• Download the NetBeans IDE.
  
• Read the documentation for the javax.swing.JList, javax.swing.ListModel, and javax.swing.DefaultListModel classes.
  
• Refer to the Wikipedia entry for decorator design pattern.

* Any API additions or other enhancements to the Java SE platform specification are subject to review and approval by the JSR 270 Expert Group.

† The terms "Java Virtual Machine" and "JVM" mean a Virtual Machine for the Java platform.