/*
    * @(#)TableSorter.java	1.8 99/04/23
    *
    * Copyright (c) 1997-1999 by Sun Microsystems, Inc. All Rights Reserved.
    *
    * Sun grants you ("Licensee") a non-exclusive, royalty free, license to use,
    * modify and redistribute this software in source and binary code form,
    * provided that i) this copyright notice and license appear on all copies of
    * the software; and ii) Licensee does not utilize the software in a manner
   * which is disparaging to Sun.
   *
   * This software is provided "AS IS," without a warranty of any kind. ALL
   * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING ANY
   * IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR
   * NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT BE
   * LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING
   * OR DISTRIBUTING THE SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN OR ITS
   * LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT,
   * INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER
   * CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF
   * OR INABILITY TO USE SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
   * POSSIBILITY OF SUCH DAMAGES.
   *
   * This software is not designed or intended for use in on-line control of
   * aircraft, air traffic, aircraft navigation or aircraft communications; or in
   * the design, construction, operation or maintenance of any nuclear
   * facility. Licensee represents and warrants that it will not use or
   * redistribute the Software for such purposes.
   */
  
  /***
   * A sorter for TableModels. The sorter has a model (conforming to TableModel)
   * and itself implements TableModel. TableSorter does not store or copy
   * the data in the TableModel, instead it maintains an array of
   * integers which it keeps the same size as the number of rows in its
   * model. When the model changes it notifies the sorter that something
   * has changed eg. "rowsAdded" so that its internal array of integers
   * can be reallocated. As requests are made of the sorter (like
   * getValueAt(row, col) it redirects them to its model via the mapping
   * array. That way the TableSorter appears to hold another copy of the table
   * with the rows in a different order. The sorting algorthm used is stable
   * which means that it does not move around rows when its comparison
   * function returns 0 to denote that they are equivalent.
   *
   * @version 1.8 04/23/99
   * @author Philip Milne
   */
  package org.xnap.commons.gui.table;
  
  import java.util.ArrayList;
  import javax.swing.event.TableModelEvent;
  import javax.swing.event.TableModelListener;
  import javax.swing.table.AbstractTableModel;
  import javax.swing.table.TableModel;
  
  public class TableSorter extends AbstractTableModel implements SortableModel
  {
  
      protected int indexes[] = new int[0];
      protected int revIndexes[] = new int[0];
      protected ArrayList<Integer> sortingColumns = new ArrayList<Integer>();
      protected Order sortOrder = Order.UNSORTED;
      /***
       * Counts number of compares.
       */
      protected int compares;
      protected int lastSortedColumn = -1;
      protected boolean maintainSortOrder;
  	private TableModel tableModel;
  	private TableModelListener tableModelListener;
  	
      public TableSorter()
      {
  		this.tableModelListener = new TableModelHandler();
      }
  
      public TableSorter(TableModel tableModel)
      {
  		this();
  		
  		setTableModel(tableModel);
      }
  
      public TableModel getTableModel() {
          return tableModel;
      }
  
      // TableModel interface methods 
  
      public int getRowCount() {
          return (tableModel == null) ? 0 : tableModel.getRowCount();
      }
  
      public int getColumnCount() {
          return (tableModel == null) ? 0 : tableModel.getColumnCount();
      }
  
      public String getColumnName(int column) {
          return tableModel.getColumnName(column);
     }
 
     public Class<?> getColumnClass(int column) {
         return tableModel.getColumnClass(column);
     }
 
     public boolean isCellEditable(int row, int column) {
         return tableModel.isCellEditable(mapToIndex(row), column);
     }
 
     public Object getValueAt(int row, int column) {
 		synchronized (indexes) {
 			return tableModel.getValueAt(mapToIndex(row), column);
 		}
     }
 
     public void setValueAt(Object aValue, int row, int column) {
 		synchronized (indexes) {
 			tableModel.setValueAt(aValue, mapToIndex(row), column);
 		}
     }
 
     public int getSortedColumn()
     {
 		return lastSortedColumn;
     }
 
     public Order getSortOrder()
     {
 		return sortOrder;
     }
 
     /***
      * Returns the mapped row index.
      */
     public int mapToIndex(int i) 
     {
         return indexes[i];
     }
 
     public void setMaintainSortOrder(boolean newValue)
     {
 		maintainSortOrder = newValue;
     }
 
     public void setSortOrder(Order newValue)
     {
     	if (newValue == null) {
     		throw new IllegalArgumentException();
     	}
     	
 		sortOrder = newValue;
     }
 
     public void setTableModel(TableModel tableModel) {
         if (this.tableModel != null) {
             this.tableModel.removeTableModelListener(tableModelListener);
         }
 
         this.tableModel = tableModel;
         if (this.tableModel != null) {
             this.tableModel.addTableModelListener(tableModelListener);
         }
 
 		reallocateIndexes();
         fireTableStructureChanged();
     }
 
     /***
      * Sorts the table.
 	 *
 	 * @return true, if table is sorted ascending; false, if descending
      */
     public Order sortByColumn(int column, Order sortOrder, boolean revert) 
     {
 		// add column
 		if (column < 0 || column >= getColumnCount()) {
 			throw new IllegalArgumentException("Column is invalid");
 		}
 
 		sortingColumns.clear();
 		sortingColumns.add(new Integer(column));
 
 		setSortOrder(sortOrder);
 
 		if (!sort() && revert) {
 			setSortOrder(sortOrder.next());
 			sort();
 		}
 		lastSortedColumn = column;
 
 		return getSortOrder();
     }
 
     public void resort()
     {
 		if (lastSortedColumn != -1) {
 			sortByColumn(lastSortedColumn, getSortOrder(), false);
 		}
     }
 
     /***
      * Compares two rows.
      */
     protected int compare(int row1, int row2) 
     {
         compares++;
         for(int level = 0; level < sortingColumns.size(); level++) {
             int column = sortingColumns.get(level);
             int result = compareRowsByColumn(row1, row2, column);
             if (result != 0) {
                 return (sortOrder == Order.ASCENDING) ? result : -result; 
             }
         }
         return 0;
     }
 
     /***
      * Compares two rows by a column.
      */
     @SuppressWarnings("unchecked")
 	protected int compareRowsByColumn(int row1, int row2, int column) 
     {
         Class type = getColumnClass(column);
 
         // check for nulls
         Object o1 = tableModel.getValueAt(row1, column);
         Object o2 = tableModel.getValueAt(row2, column);
 
         // If both values are null return 0
 		// define: null is less than anything
         if (o1 == null && o2 == null) {
             return 0;
         } else if (o1 == null) { 
             return -1;
         } else if (o2 == null) {
             return 1;
         }
 
         /* We copy all returned values from the getValue call in case
 		   an optimised model is reusing one object to return many values.  The
 		   Number subclasses in the JDK are immutable and so will not be used in
 		   this way but other subclasses of Number might want to do this to save
 		   space and avoid unnecessary heap allocation.
 		*/
 		if (type == String.class) {
             String s1  = (String)o1;
             String s2  = (String)o2;
 			int result = s1.compareToIgnoreCase(s2);
 
 			// empty strings come last
 			if (s1.length() == 0 ^ s2.length() == 0) {
 				result = -result;
 			}
 
 			return result;
 		}
 		else if (o1 instanceof Comparable) {
 			return ((Comparable)o1).compareTo(o2);
 		}
 		/* Boolean implements Comparable, so there is no need for extra
 		 * handling code
 		else if (type == Boolean.class) {
             boolean b1 = ((Boolean)o1).booleanValue();
             boolean b2 = ((Boolean)o2).booleanValue();
 	    
 			// define: false < true
             if (b1 == b2) {
                 return 0;
             } else if (b1) {
                 return 1;
             } else {
                 return -1;
             }
         } 
         */
 		else {
 			// now what?
 			return o1.toString().compareTo(o2.toString());
         }
     }
 
     protected void reallocateIndexes(TableModelEvent e) 
     {
         int rowCount = getRowCount();
 
         if (rowCount == indexes.length)
             return;
 
         // Set up a new array of indexes with the right number of elements
         // for the new data model.
         int newIndexes[] = new int[rowCount];
         int newRevIndexes[] = new int[rowCount];
 
         synchronized (indexes) {
             int row = 0;
 
 			if (e != null && e.getType() == TableModelEvent.DELETE) {
 				// we need to remove the deleted lines from the index
 				// and decrease all row numbers by the appropriate
 				// amount
 				int skipped = 0;
 				for(; row < indexes.length; row++) {
 					int dec = 0;
 					boolean skip = false;
 					for (int i = e.getFirstRow(); i <= e.getLastRow(); i++) {
 						if (i < indexes[row])
 							dec++;
 						else if (i == indexes[row])
 							skip = true;
 					}
 					if (skip) {
 						skipped++;
 						continue;
 					}
 		    
 					newIndexes[row - skipped] = indexes[row] - dec;
 					newRevIndexes[indexes[row] - dec] = row - skipped;
 				}
 			} 
 			else if (e != null && (e.getType() == TableModelEvent.UPDATE
 								   && e.getLastRow() >= indexes.length)) {
 				// start from scratch
 				for (int i = 0; i < rowCount; i++) {
 					newIndexes[i] = i;
 					newRevIndexes[i] = i;
 				}
 			}
 			else {
 				// Add the new rows to the end of the map, but leave the
 				// beginning intact.
 				for(; row < indexes.length && row < rowCount; row++) {
 					newIndexes[row] = indexes[row];
 					newRevIndexes[row] = revIndexes[row];
 				}
 				for(; row < rowCount; row++) {
 					newIndexes[row] = row;
 					newRevIndexes[row] = row;
 				}
 		
 			}
 	    
 			indexes = newIndexes;
 			revIndexes = newRevIndexes;
 		}
     }
 
     protected void reallocateIndexes() 
     {
 		reallocateIndexes(null);
     }
     
     /***
      * Returns false if nothing has changed.
      */
     protected boolean sort() 
     {
         synchronized (indexes) {
         	if (sortOrder == Order.UNSORTED) {
         		for(int i = 0; i < indexes.length; i++) {
         			indexes[i] = i;
         			revIndexes[i] = i;
         		}
         		return false;
         	}
         	
 			compares = 0;
 			//long startTime = System.currentTimeMillis();
 
 			// copy indexes for sorting
 			int[] oldIndexes = new int[indexes.length];
 			System.arraycopy(indexes, 0, oldIndexes, 0, indexes.length);
 	    
 			if (shuttlesort(oldIndexes, indexes, 0, indexes.length)) {
 	    
 				//long elapsedTime = System.currentTimeMillis() - startTime;
 				//System.out.println("sorted with " + compares 
 				//+ " compares in " + elapsedTime + " ms.");
 		
 				// update reverse indexes
 				for(int i = 0; i < indexes.length; i++) {
 					revIndexes[indexes[i]] = i;
 				}
 		
 				fireTableChanged(new TableModelEvent(this));
 
 				return true;
 			}
 			else {
 				return false;
 			}
 		}
     }
 
     /***
      * Returns false if nothing has changed.
      */
     // This is a home-grown implementation which we have not had time
     // to research - it may perform poorly in some circumstances. It
     // requires twice the space of an in-place algorithm and makes
     // NlogN assigments shuttling the values between the two
     // arrays. The number of compares appears to vary between N-1 and
     // NlogN depending on the initial order but the main reason for
     // using it here is that, unlike qsort, it is stable.
     public boolean shuttlesort(int from[], int to[], int low, int high) 
     {
         if (high - low < 2) {
             return false;
         }
 
 		boolean changed = false;
         int middle = (low + high) / 2;
         changed |= shuttlesort(to, from, low, middle);
         changed |= shuttlesort(to, from, middle, high);
 
         int p = low;
         int q = middle;
 
         /* This is an optional short-cut; at each recursive call,
 		   check to see if the elements in this subset are already
 		   ordered.  If so, no further comparisons are needed; the
 		   sub-array can just be copied.  The array must be copied rather
 		   than assigned otherwise sister calls in the recursion might
 		   get out of sinc.  When the number of elements is three they
 		   are partitioned so that the first set, [low, mid), has one
 		   element and and the second, [mid, high), has two. We skip the
 		   optimisation when the number of elements is three or less as
 		   the first compare in the normal merge will produce the same
 		   sequence of steps. This optimisation seems to be worthwhile
 		   for partially ordered lists but some analysis is needed to
 		   find out how the performance drops to Nlog(N) as the initial
 		   order diminishes - it may drop very quickly.  */
 
         if (high - low >= 4) {
             if (compare(from[middle-1], from[middle]) <= 0) {
                 for (int i = low; i < high; i++) {
                     to[i] = from[i];
                 }
                 return changed;
             } else {
                 // an optimisation for lists with reverse order -- j.a.
                 if (compare(from[high-1], from[low]) < 0) {
                     int i = low;
                     for( ; q < high; q++) {
                         to[i++] = from[q];
                     }
                     for( ; i < high; i++) {
                         to[i] = from[p++];
                     }
                     return changed;
                 }
             }
         }
 
         // standard merge
         for (int i = low; i < high; i++) {
             if (q >= high || (p < middle && compare(from[p], from[q]) <= 0)) {
                 to[i] = from[p++];
             } 
 			else {
 				changed |= (p < middle);
                 to[i] = from[q++];
             }
         }
 
 		return changed;
     }
 
 	private class TableModelHandler implements TableModelListener 
 	{
 	    /***
 	     * We need to mangle these events to fire the right indicies.
 	     */
 	    public void tableChanged(TableModelEvent e) 
 	    {
 			reallocateIndexes(e);
 	
 			if (maintainSortOrder) {
 				// this will reset the user selection
 				if (sort()) {
 					// sort has already notified the super class
 					return;
 				}
 			}
 	
 			if (e.getType() == TableModelEvent.DELETE
 				|| (e.getType() == TableModelEvent.UPDATE && 
 					e.getLastRow() >= revIndexes.length)) {
 				// we don't know anymore which rows have been deleted
 				fireTableChanged(new TableModelEvent(TableSorter.this));
 			}
 			else {
 				for (int i = e.getFirstRow(); i <= e.getLastRow(); i++) {
 					TableModelEvent t = new TableModelEvent
 						(TableSorter.this, revIndexes[i], revIndexes[i], e.getColumn(),
 						 e.getType());
 					fireTableChanged(t);
 				}
 			}
 	    }
 	}
 
 	public boolean getMaintainSortOrder()
 	{
 		return maintainSortOrder;
 	}
 
 }