here is the song and dance I had to go through to keep a table ordered
with new elements arriving with random sort keys to insert them in the
right spot or overwrite an existing element.

package com.mindprod.table;

import java.awt.event.InputEvent;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.Comparator;
import java.util.HashMap;

import javax.swing.JTable;
import javax.swing.table.JTableHeader;
import javax.swing.table.TableColumnModel;

/**
* TableOrderer, Keeps a table in order sorted on several columns.
* Also ensures no dups inserted.
* Also ensures table does not get too big.
* Does not implement OrderedTableModel but requires a TableModel that
does.
* It is not aware of how long the various rows are.
* It just keeps track of rows.
*
* @author Roedy Green
* @version 1.1
* @since 2002  Sep 10
*/
public class TableOrderer
  {

  /**
   * Column sorted in ascending order.
   */
  public static final int ASCENDING = 1;

  /**
   * Column sorted in descending order
   */
  public static final int DESCENDING = -1;

  /**
   * Column not sorted.
   */
  public static final int UNSORTED = 0;

  /**
  * constant to specify pruning tables at row 0,
  * Usually used with ascending sorts. Scrolling text moves up.
  * Chops off biggest values.
  */
  public final static int CHOP_AT_TOP = 0;

  /**
   * constant to specify pruning tables at the last row.
   * Usually used with descending sorts, or unsorted
   * tables. Scrolling text moves down. chops off smallest values.
   */
  public final static int CHOP_AT_BOTTOM = 1;

  /**
   * whether ith key to sort on is ascending or
   * descending.  True for ascending.
   */
  private boolean[] ascDesc;

  /**
   *comparator to order this table, null forunsorted.
   */
  private Comparator comparator;

  /**
   * Column we want to keep free of duplicates, 0-based.
   */
  private int deDupCol;

  /**
   * List of keys we don't want to duplicate
   * and where they currently are in the list.
   */
  private HashMap deDupMap = null;

  /**
   * true if the deduping code is turned on.
   */
  private boolean deDupEngaged;

  /**
   * Maximum number of rows we will allow the table to grow too.
   * We let the table temporarily get one bigger than this.
   */
  private int maxRows = 1000;

  /**
   * OrderedTableModel that we are keeping in
   * order and deduped.
   */
  private OrderedTableModel model;

  /**
   * most recently changed row.  If rows are added, this does not
slide.
   * It is the absolute position of the data when it was recently
changed,
   * not where it slid to now.
   */
  private int mostRecentlyChangedRow = -1;

  /**
   * CHOP_AT_TOP CHOP_AT_BOTTOM
   */
  private int whereToChop = CHOP_AT_TOP;

  /**
  * zero based columns to sort on, major first.
  * null if no sort keys. Usually array of one element holding the
0-based column to sort on.
  */
  private int[] sortCols0Based;

  /**
   * true if the sorting code is turned on.
   */
  private boolean sortEngaged;

  /**
   * Track how long (in looks) the dup list has remained stable.
   * If it sits stable it is faster to use the HashMap,
   * if not, linear search for detecting dups.
   */
  private int stableFor = 0;

  /**
   * Public constructor.
   * Should do a setComparator, setMaxRows, setWhereToChop,
setDeDupCol as well.
   *
   * @param model  OrderedTableModel to be kept deduped/sorted.
   */
  public TableOrderer ( OrderedTableModel model )
     {
     this.model = model;
     }

  /**
   * replace a row cyclically within an single table.
   * Does no sort or dedup.
   * @param aux     auxiliary data about the row,
   *                usually dangerlevel and age.
   *                possibly null.
   *
   * @param rowData row of Object data to add.
   */
  public void acceptCyclicRow( Object[] rowData, Object aux )
     {
     int row = mostRecentlyChangedRow+1;
     if ( row >= maxRows )
        {
        row  = 0;
        }
     if ( row < model.getRowCount() )
        {
        // write over top of an existing row.
        model.replaceRow( rowData, aux, row );
        setMostRecentlyChangedRow( row );
        model.fireTableRowsUpdated( row, row );
        }
     else
        {
        // it is a brand new row, add it to the end, will not
overflow.
        model.addRow( rowData, aux, row );
        setMostRecentlyChangedRow( row );
        model.fireTableRowsInserted( row, row );
        }
     }

  /**
   * Accept a new row, add/delete/replace existing row if duplicate.
   *
   * @param rowData row of Object data to add.
   * @param aux     auxiliary data about the row,
   *                usually dangerlevel and age.
   *                possibly null.
   * @param specialInstructions
   *                ServerDataItemResponse.ADD, ADD_NO_DEDUP or
DELETE.
   */
  public void acceptRow( Object[] rowData, Object aux, int
specialInstructions )
     {
     switch ( specialInstructions )
        {
        case ServerDataItemResponse.ADD:
           this.addRow( rowData, aux);
           break;

        case ServerDataItemResponse.ADD_NO_DEDUP:
           this.addRowInOrder ( rowData, aux );
           break;

        case ServerDataItemResponse.DELETE:
           this.deleteMatchingRow ( rowData );
           break;

        default:
           Log.println( Log.BUG,"invalid specialInstructions.");
        }
     }

  /**
   * Add a new row, replace existing row if duplicate.
   *
   * @param rowData row of Object data to add.
   * @param aux     auxiliary data about the row,
   *                usually dangerlevel and age.
   *                possibly null.
   */
  public void addRow( Object[] rowData, Object aux )
     {
     if ( deDupEngaged )
        {
        int row = findDup( rowData[ deDupCol ] );
        if ( row >= 0 )
           {
           // was a duplicate, replace existing
           // This should be the normal case.
           this.replaceRow ( rowData, aux, row );
           }
        else
           {
           /* not a duplicate */
           this.addRowInOrder ( rowData, aux );
           /* deDupMap is no longer valid, we don't know where that
row will go or how it will shift other rows. */
           invalidateDeDupMap();
           }
        }
     else
        {
        /* no deduping */
        this.addRowInOrder ( rowData, aux );
        }
     }

  /**
   * add a new row wherever it belongs in sort order.
   *
   * @param rowData row of Object data to add.
   * @param aux     auxiliary data about the row,
   *                usually dangerlevel and age.
   *                possibly null.
   */
  private void addRowInOrder( Object[] rowData, Object aux)
     {
     if ( sortEngaged )
        {
        /* row where found dup */
        int where = model.binarySearch( rowData, comparator );
        /* row where to insert new row */
        int insertAt = where;
        if ( where < 0 )
           {
           /* we did not find it there already,
           where contains (-(insertion point) - 1) */
           insertAt = -where - 1;
           }
        else
           {
           /* found key, we have the index of one of the dups. */
           switch ( whereToChop )
              {
              case CHOP_AT_BOTTOM:

                 // We chop at bottom, (desc order) so we want to add
before all dups.
                 // Remember that descending Comparator has reverse
sign result.
                 for ( int row=where-1; row>=0; row-- )
                    {
                    if ( comparator.compare( rowData,
model.getQuickRowData(row)) > 0 )
                       {
                       insertAt = row+1;
                       break;
                       }
                    }
                 if ( insertAt == where )
                    {
                    // did not find anything smaller
                    insertAt = 0;
                    }
                 break;

              case CHOP_AT_TOP:

                 // We chop at top, (asc order) so we want to add
after all dups.
                 // CHOP_AT_TOP
                 int numRows = model.getRowCount();
                 for ( int row=where+1; row<numRows; row++ )
                    {
                    if ( comparator.compare(
model.getQuickRowData(row), rowData) > 0 )
                       {
                       insertAt = row;
                       break;
                       }
                    }
                 if ( insertAt == where )
                    {
                    // did not find anything bigger
                    insertAt = numRows;
                    }
                 break;

              default: break;
              } // end switch
           } // end else
        // We now have the insertion point.
        /* add either at insertion point or or after dup */
        if ( insertAt >= maxRows && whereToChop == CHOP_AT_BOTTOM )
           {
           // off the bottom end.  No point in inserting at all, will
just get chopped.
           insertAt = -1;
           }

        if ( insertAt == 0 && model.getRowCount() >= maxRows &&
whereToChop == CHOP_AT_TOP )
           {
           // off the top end. table is full.  Adding a row at the
top will just get chopped.
           // don't bother.
           insertAt = -1;
           }

        if ( insertAt >= 0 )
           {

           model.addRow( rowData, aux, insertAt );
           setMostRecentlyChangedRow( insertAt );
           model.fireTableRowsInserted( insertAt, insertAt );
           /* inserted record may push existing one off either end */
           chopTable( 0 );
           }
        // otherwise we discarded the row as off either end.
        // leave existing mostRecentlyChangedRow
        }
     else
        {
        // not sorting    
        // make room for new row
        chopTable( 1 );
        switch ( whereToChop )
           {
           case CHOP_AT_BOTTOM:
              // not sorting, just add at the top,
              model.addRow( rowData, aux, 0 );
              setMostRecentlyChangedRow ( 0 );
              model.fireTableRowsInserted( 0, 0 );
              break;

           case CHOP_AT_TOP:
              // not sorting, just add at the bottom
              int size = model.getRowCount();
              model.addRow( rowData, aux, size );
              setMostRecentlyChangedRow( size );
              model.fireTableRowsInserted( size, size );
              break;
           }
        }
     invalidateDeDupMap(); /* added row, disturbs map */
     }

  /**
   * Allow user to select a new sort column.
   * Works by adding a MouseListener to the column headers.
   * Mouse listener fields requests for sorting columns.
   * Allows click, shift-click on column to select column and
ascending/descending.
   *
   * @param table  the visible JTable part of the table.
   */
  public void allowUserToSelectSortColumn( JTable table )
     {
     // make available to anonymous inner class
     final JTable tableView = table;
     tableView.setColumnSelectionAllowed( false );
     JTableHeader th = tableView.getTableHeader();
     th.addMouseListener(
                        new MouseAdapter()
                           {
                           /**
                            * Handler for mouse selection of sort
column
                            * and order. Shift-click means
descending.
                            *
                            * @param event  Details of event
                            */
                           public void mouseClicked( MouseEvent event
)
                              {
                              TableColumnModel columnModel =
tableView.getColumnModel();
                              int viewColumn =
columnModel.getColumnIndexAtX( event.getX() );
                              int column =
tableView.convertColumnIndexToModel( viewColumn );
                              if ( event.getClickCount() == 1 &&
column != -1 )
                                 {
                                 int shiftPressed =
event.getModifiers() & InputEvent.SHIFT_MASK;
                                 boolean ascending = ( shiftPressed
== 0 );
                                 // if we are ascending, we chop at
the top, if descending at the bottom.
                                 TableOrderer.this.setWhereToChop(
ascending ?
TableOrderer.CHOP_AT_TOP :
TableOrderer.CHOP_AT_BOTTOM);
                                 // uses 1-based column numbers, -ve
to request descending
                                 TableOrderer.this.sortByColumns( new
int[] { ascending ? column +1 : -(column+1)} );
                                 }
                              }
                           }
                        );
     } // end allowUserToSelectSortColumn

  /**
   * Are two rows exactly equal? (except aux).
   *
   * @param rowa   First row to compare. Defines number of columns.
   * @param rowb   Second row To Compare
   *
   * @return true if all fields exactly match.
   */
  private static boolean areRowsExactlyEqual ( Object[] rowa,
Object[] rowb )
     {
     int cols = rowa.length;
     // rowb may have an aux appended, one extra ignored column.
     for ( int i=0; i<cols; i++ )
        {
        if ( ( (Comparable)rowa[i] ).compareTo( rowb[i] ) != 0 )
           {
           return false;
           }
        }
     return true;
     }

  /**
   * chop table back down to size if it has grown
   * too big. We do this whether or not deDuping or sorting.
   * Chop from bottom or top as controlled by whereToChop.
   * ChopTable maintains mostRecentlyChangedRow.
   *
   * @param room   How many free slots are needed to be free, in
rows.
   */
  private void chopTable( int room )
     {
     // remove excess rows, working backwards.  More efficient.
     // In practice should never have to chop more than one row,
     // so it does not may to save up the fireTableRows events.
     int highestRowToDelete = model.getRowCount()-1;
     int highestRowToKeep = maxRows-1-room;
     for ( int i=highestRowToDelete; i>highestRowToKeep; i-- )
        {
        switch ( whereToChop )
           {
           
           case CHOP_AT_BOTTOM:
              model.removeRow ( i );
              model.fireTableRowsDeleted(i, i);
              // don't setMostRecentlyChangedRow yet
              break;

           case CHOP_AT_TOP:
              model.removeRow ( 0 );
              model.fireTableRowsDeleted(0, 0);
              // don't setMostRecentlyChangedRow yet
              break;

           default:
              throw new IllegalArgumentException
("TableOrderer.chopTable expects only CHOP_AT_BOTTOM or CHOP_AT_TOP");
           }
        /* deDupMap is no longer valid, since chopped key is no
longer in list. */
        /* only called if we chop a row */
        invalidateDeDupMap();
        } // end for
     }

  /**
   * find a duplicate via a dedup mechanism. Needs match on only one
column.
   * presumes deDupEngaged.
   *
   * @param item   Item to check for duplicate. The value of the
   *               cell to match in the deDup column.
   * @return row where dup found, or -1 if not a dup.
   */
  private int findDup ( Object item )
     {
     int row;
     /* check to see if we have seen this key before */
     /* pick faster algorithm, depending on recent stability. */
     if ( stableFor > 50 )
        {
        row = findDupViaMap( item );
        }
     else
        {
        /* Everthing is changing so fast, no point in using deDupMap,
since
           it goes out of date and has to be rebuilt. */
        row = findDupViaModel( item );
        }
     stableFor++; /* note one more cycle of stability. */
     return row;
     }

  /**
   * Find duplicate of this row using HashMap lookup.
   * This technique means we don't need to sort on dedup column.
   *
   * @param item   Item to check for duplicate. The value of the
   *               cell to match in the deDup column.
   * @return row where dup found, or -1 if not a dup.
   */
  private int findDupViaMap( Object item )
     {
     if ( deDupMap == null )
        {
        rebuildDeDupMap();
        }
     Integer row = (Integer)deDupMap.get( item );
     return row == null ? -1 : row.intValue();
     }

  /**
   * Find duplicate of this row using linear search of Model
   *
   * @param item   Item to check for duplicate. The value of the
   *               cell to match in the deDup column.
   * @return row where dup found, or -1 if not a dup.
   */
  private int findDupViaModel( Object item )
     {
     int numRows = model.getRowCount();
     for ( int row=0; row<numRows; row++ )
        {
        if ( item.equals( model.getValueAt( row, deDupCol ) ) )
           {
           return row;
           }
        }
     return -1;
     }

  /**
   * Delete a matching row, all fields must match exactly except aux.
   * If more than one row matches, only first match is deleted.
   * If no match in found, that is OK.
   *
   * @param rowData matching row of Object data to delete.
   */
  public void deleteMatchingRow( Object[] rowData )
     {
     // try for a fast lookup via the dedup mechanism.
     int row = -1;
     if ( deDupEngaged )
        {
        row = findExactMatchViaMap( rowData );
        }
     if ( row < 0 )
        {
        // dedup mechanism failed, try linear search from the top
        row = findExactMatchViaModel( rowData, 0 );
        }

     if ( row >= 0 )
        {
        model.removeRow( row );
        /* most recently changed row won't be there, use row where it
was. */
        setMostRecentlyChangedRow( row );
        // if there is a second match, we leave it.
        model.fireTableRowsDeleted( row, row );
        }
     // otherwise could not find a match. Don't complain.
     }  // end deleteMatchingRow

  /**
   * Find exact duplicate of this row using dedup mechanism.
   * all fields must match. Presumes deDupEngaged,
   *
   * @param rowData row of Object data to match
   * @return row where match found, or -1 if not found
   */
  private int findExactMatchViaMap( Object[] rowData )
     {
     int row = findDup( rowData[ deDupCol ] );
     if ( row >= 0 )
        {
        if ( areRowsExactlyEqual( rowData, model.getQuickRowData( row
) ) )
           {
           return row;
           }
        // try linear search of succeeding entries
        return findExactMatchViaModel ( rowData, row+1 );
        }
     return -1;
     }

  /**
   * Find exact duplicate of this row using linear search of Model.
   * All fields must match.
   *
   * @param rowData  row of Object data to match
   * @param startRow row where to start looking.  Does not search
   *                 above this row.
   * @return row where match found, or -1 if not found
   */
  private int findExactMatchViaModel( Object[] rowData, int startRow
)
     {
     // do a linear search starting at the given row. No wrap around.
     int numRows = model.getRowCount();
     for ( int row=startRow; row<numRows; row++ )
        {
        if ( areRowsExactlyEqual ( rowData,  model.getQuickRowData(
row ) ) )
           {
           return row;
           }
        }
     return -1;
     }

  /**
   * Mark deDupMap as no longer accurate.
   * The mapping of dups to row numbers has
   * been disturbed.  The table needs to be
   * rebuilt.
   */
  private void invalidateDeDupMap()
     {
     deDupMap = null;
     stableFor = 0;
     }

  /**
   * Was this row recently changed?
   * If so it will likely get inverse highlighting.
   *
   * @param row    0-based row in question.
   * @return true if this was the most recently painted row.
   */
  public boolean isRecentlyChanged ( int row )
     {
     return row == mostRecentlyChangedRow;
     }

  /**
   * Which row was most recently changed?
   *
   * @return 0-based row most recently changed.
   *         -1 if none.
   */
  public int getMostRecentlyChangedRow ()
     {
     return  mostRecentlyChangedRow;
     }

  /**
   * How is a given column sorted.  Used by header painting routines.
   *
   * @param column zero-based column number
   * @return  1, 0, -1 ASCENDING UNSORTED DESCENDING
   */
  public int howColumnSorted ( int column )
     {
     if ( sortCols0Based == null || sortCols0Based.length == 0 )
return UNSORTED;
     for ( int i=0; i<sortCols0Based.length; i++ )
        {
        if ( column == sortCols0Based[i] ) return  ascDesc[i] ?
ASCENDING : DESCENDING;
        }
     return UNSORTED;
     }

  /**
   * rebuild the list of dups and which row
   * they are associated with.
   * This is likely to be a bottleneck.
   * Becomes invalid as soon as any row moves or changes dedup key.
   * Only useful when display has a fixed set of dedup keys with
changing data.
   */
  private void rebuildDeDupMap ()
     {
     if ( deDupEngaged )
        {
        int numRows = model.getRowCount();
        deDupMap = new HashMap( numRows * 2 );
        for ( int i=0; i<numRows; i++ )
           {
           deDupMap.put( model.getValueAt(i, deDupCol), new
Integer(i));
           }
        }
     }

  /**
   * replace a row, doing sort adjust.
   *
   * @param rowData row of Object data to replace the existing row
with.
   * @param aux     auxiliary data about the row,
   *                usually dangerlevel and age.
   *                possibly null.
   * @param row     row number to replace
   */
  public void replaceRow( Object[] rowData, Object aux, int row )
     {
     if ( sortEngaged )
        {
        model.replaceRow( rowData, aux, row );

        // need to determine if this disturbed the existing ordering.
        if ( ( row > 0 && model.compareRows( row, row-1, comparator )
< 0 )
             ||( row < model.getRowCount()-1 &&
                 model.compareRows( row+1, row, comparator ) < 0 ) )
           {
           // row is now out of place.
           // mostRecentlyChangedRow will soon be set in
addRowInOrder
           model.removeRow( row );
           model.fireTableRowsDeleted( row, row );
           this.addRowInOrder( rowData, aux );
           /* deDupMap is no longer valid, we don't know where that
row will go or how it will shift other rows. */
           invalidateDeDupMap();
           }
        else
           {
           // did not disturb order
           setMostRecentlyChangedRow( row );
           model.fireTableRowsUpdated( row, row );
           }
        }
     else
        {
        // no sort
        model.replaceRow( rowData, aux, row );
        setMostRecentlyChangedRow( row );
        model.fireTableRowsUpdated( row, row );
        }
     } // end replaceRow

  /** which column should be keep free of duplicates?
   *
   * @param deDupCol1based to keep free of duplicates. 1-based.
   *  0 means no deduping
   */
  public void setDeDupColumn( int deDupCol1based )
     {
     int deDupCol = deDupCol1based - 1;
     if ( this.deDupCol != deDupCol )
        {
        this.invalidateDeDupMap();
        }
     this.deDupCol = deDupCol;
     this.deDupEngaged = ( deDupCol >= 0 );
     }

  /**
   * How many rows of data should be allow to accumulate before
pruning it back.
   * Does not clear the model of data.
   * @param maxRows max size we are to allow the table to get.  If it
gets
   * bigger we chop off the last row.
   * 0 means leave the value as it was.
   */
  public void setMaxRows( int maxRows )
     {
     if ( maxRows != 0 )
        {
        this.maxRows = maxRows;
        chopTable( 0 );
        }
     }

  /**
   * Track the MostRecentlyChangedRow and
   * previouslyChangedRow. Used to refresh display
   * of previously changed row.
   *
   * @param mostRecentlyChangedRow
   *               New row that was most recently changed.
   *               -1 if none.
   */
  private void setMostRecentlyChangedRow ( int mostRecentlyChangedRow
)
     {
     int prev = this.mostRecentlyChangedRow;
     this.mostRecentlyChangedRow = mostRecentlyChangedRow;
     if ( 0 <= prev && prev != mostRecentlyChangedRow && prev <
model.getRowCount() )
        {
        /* Repaint the previous, since likely won't need highlight
any more.
           It does not matter if data moved. We want the slot where
it was. */
        model.fireTableRowsUpdated( prev, prev );
        }
     /* don't need to fire new mostRecentlyChangedRow, since handled
separately.
        There are too many variants of the fireTableChange  */
     }

  /**
   * Where should data be pruned when the table gets too big?
   * @param whereToChop CHOP_AT_TOP  if should chop bottom element
when table gets too big,
   *  CHOP_AT_BOTTOM  chop the top element.
   */
  public void setWhereToChop( int whereToChop )
     {
     this.whereToChop = whereToChop;
     chopTable( 0 );
     }

  /**
   * reSort the entire table, using the current Comparator.
   */
  private void sort()
     {
     if ( sortEngaged )
        {
        if ( model.getRowCount() > 0 )
           {
           // will not be able to track where most recently changed
went.
           setMostRecentlyChangedRow( -1 );
           model.sort( comparator );
           model.fireTableDataChanged();

           }
        /* deDupMap is no longer valid, who knows how sort shuffled.
*/
        invalidateDeDupMap();
        }
     } // end sort

  /**
   * Sort on a set of columns
   *
   * @param sortCols1Based
   *               array of column-1 based columns so sort on,
   *               major key first.
   *               Negative column number means desceding sort.
   */
  public void sortByColumns( int[] sortCols1Based )
     {
     final int size = sortCols1Based.length;
     if ( size == 0 )
        {
        this.sortCols0Based = null;
        this.ascDesc = null;
        this.sortEngaged = false;
        this.comparator = null;
        }
     else
        {
        // convert to more convenient
        // zero-based format, with separate ascending/descending
boolean.
        this.sortCols0Based = new int[ size ];
        this.ascDesc = new boolean[ size ];
        for ( int i=0; i<size; i++ )
           {
           if ( sortCols1Based[i] == 0 )
              {
              throw new IllegalArgumentException("columns to sort
cannot be 0 in TableOrderer.sortByColumns");
              }
           sortCols0Based[ i ] = Math.abs( sortCols1Based[ i ] ) -1;
           ascDesc[ i ] = sortCols1Based[ i ] > 0 /* true=ascending
*/;
           }
        this.comparator = new MultiColumnComparator( sortCols0Based,
ascDesc );
        this.sortEngaged = true;
        sort();
        }
     // make sure headers get repainted
     model.fireTableStructureChanged();
     }

  } // end TableOrderer