/***
    * AbstractSortableTableModel.java
    *
    * This file is part of the creme library.
    * The creme library intends to ease the development effort of large
    * applications by providing easy to use support classes.
    *
    * Copyright (C) 2002 Denis Bregeon
    *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   * Lesser General Public License for more details.
   *
   * You should have received a copy of the GNU Lesser General Public
   * License along with this library; if not, write to the Free Software
   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   *
   * contact information: dbregeon@sourceforge.net
   */
  package org.jcreme.swing.table;
  
  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.Vector;
  
  import javax.swing.table.AbstractTableModel;
  import javax.swing.table.TableModel;
  
  import org.jcreme.enumerations.SortOrder;
  
  /***
   * This class is an abstract implementation of the SortableTableModel interface.
   * Some of the features are inspired from the Java Tutorial TableSorter.java
   * sample. The concrete sub classes of this class can implement either of two
   * schemes: the data manipulator scheme described in the tutorial, the usual
   * scheme to create a direct subclass of this one. This class does not specify
   * how the resort is handled. It could be through the TableChangeEvents or
   * through any other scheme.
   * 
   * @author $Author: dbregeon $
   * @version $Revision: 1.1 $
   */
  public abstract class AbstractSortableTableModel extends AbstractTableModel
          implements SortableTableModel {
      /***
       * The index in the original model.
       */
      private int[] sortedIndexToOriginalIndex = new int[0];
  
      /***
       * The columns that provide the sort feature.
       */
      private transient SortableTableColumn[] sortingColumns = null;
  
      /***
       * The comparator used to sort the columns into their order in sort.
       */
      private final Comparator sortableColumnComparator = new Comparator() {
          public boolean equals(Object o) {
              return (o == this);
          }
  
          public int compare(Object o1, Object o2) {
              int result = 0;
              if ((o1 instanceof SortableTableColumn)
                      && (o2 instanceof SortableTableColumn)) {
                  SortableTableColumn column1 = (SortableTableColumn) o1;
                  SortableTableColumn column2 = (SortableTableColumn) o2;
                  if (column1.getOrderInSort() == null) {
                      result = (column2.getOrderInSort() == null) ? 0 : -1;
                  } else if (column2.getOrderInSort() == null) {
                      result = 1;
                  } else {
                      result = ((SortableTableColumn) o1)
                              .getOrderInSort()
                              .compareTo(
                                      ((SortableTableColumn) o2).getOrderInSort());
                  }
              }
              return result;
          }
      };
  
      /***
       * @see TableModel#getValueAt(int, int)
       */
      public Object getValueAt(int row, int column) {
          return getOriginalValueAt(getOriginalRow(row), column);
      }
  
      /***
       * @see TableModel#setValueAt(java.lang.Object, int, int)
       */
     public void setValueAt(Object value, int row, int column) {
         setOriginalValueAt(value, getOriginalRow(row), column);
     }
 
     /***
      * Enables to find a row number in the original model.
      * 
      * @param row
      *            the row as presented after sorting.
      * @return the row in the original (unsorted) model that corresponds to the
      *         parameter row.
      */
     public synchronized int getOriginalRow(int row) {
         // If the model has not been sorted since the last update.
         // Do as if it was not sorted to avoid errors.
         int result = row;
         if (this.sortedIndexToOriginalIndex.length == getRowCount()) {
             result = this.sortedIndexToOriginalIndex[row];
         }
         return result;
     }
 
     /***
      * This method returns the value at the original (non sorted) row.
      * 
      * @param row
      *            the row number in the original model.
      * @param column
      *            the column in the model.
      * @return the value at these coordinates in the original model.
      */
     protected abstract Object getOriginalValueAt(int row, int column);
 
     /***
      * This method enables to change the value at the original (non sorted) row.
      * 
      * @param value
      *            the value to set these coordinates in the original model.
      * @param row
      *            the row number in the original model.
      * @param column
      *            the column in the model.
      */
     protected abstract void setOriginalValueAt(Object value, int row, int column);
 
     /***
      * Sorts the TableModel using the columns given in the columns parameter in
      * the order given in columns. It also fires an event to signal the change
      * to eventual listeners.
      * 
      * @param columns
      *            the columns used to sort the table in the order they will be
      *            used.
      */
     public void sort(SortableTableColumn[] columns) {
         synchronized (this) {
             initConverterArray();
             if (columns != null) {
                 this.sortingColumns = columns;
                 Arrays.sort(this.sortingColumns, this.sortableColumnComparator);
                 shuttleSort((int[]) this.sortedIndexToOriginalIndex.clone(),
                         this.sortedIndexToOriginalIndex, 0, getRowCount());
             }
         }
         fireTableDataChanged();
     }
 
     // Taken From the Java Tutorial.
     // 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.
     protected void shuttleSort(int from[], int to[], int low, int high) {
         if (high - low < 2) {
             return;
         }
         int middle = (low + high) / 2;
         shuttleSort(to, from, low, middle);
         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 && compare(from[middle - 1], from[middle]) <= 0) {
             for (int i = low; i < high; i++) {
                 to[i] = from[i];
             }
             return;
         }
 
         // A normal merge.
 
         for (int i = low; i < high; i++) {
             if (q >= high || (p < middle && compare(from[p], from[q]) <= 0)) {
                 to[i] = from[p++];
             } else {
                 to[i] = from[q++];
             }
         }
     }
 
     /***
      * Compares two rows using the sortingColumns to determine which columns
      * (and in which order) are to be used in the sort. Inspired From the Java
      * Tutorial.
      * 
      * @param row1
      *            the index of the first row.
      * @param row2
      *            the index of the second row.
      * @return the comparison result.
      */
     protected int compare(int row1, int row2) {
         int result = 0;
         for (int level = 0; level < this.sortingColumns.length; level++) {
             result = compareRowsByColumn(row1, row2, level);
             if (result != 0) {
                 break;
             }
         }
         return result;
     }
 
     /***
      * This method enables to compare the values of a column for two different
      * rows.
      * 
      * @param row1
      *            the reference row.
      * @param row2
      *            the compared row.
      * @param column
      *            the column of comparison.
      * @return 0 if the values of the column for each row are equal. A negative
      *         number if the value in row2 is greater than the one in row1. A
      *         positive number if the value in row1 is greater than the value in
      *         row2.
      */
     public int compareRowsByColumn(int row1, int row2, int column) {
         int result = 0;
         if ((this.sortingColumns[column] != null)
                 && (this.sortingColumns[column].getOrder() != SortOrder.NONE)) {
             int modelIndex = this.sortingColumns[column].getModelIndex();
             Object o1 = getOriginalValueAt(row1, modelIndex);
             Object o2 = getOriginalValueAt(row2, modelIndex);
             Class type = getColumnClass(modelIndex);
 
             if (this.sortingColumns[column].getComparator() != null) {
                 result = this.sortingColumns[column].getComparator()
                         .getComparator().compare(o1, o2);
             } else if (o1 == null && o2 == null) {
                 // both are equal to null.
                 result = 0;
             } else if (o1 == null) {
                 // Define null less than everything.
                 result = -1;
             } else if (o2 == null) {
                 result = 1;
             } else if (Comparable.class.isAssignableFrom(type)) {
                 // column is comparable, use that property.
                 Comparable c1 = (Comparable) o1;
                 result = c1.compareTo(o2);
             } else if (Number.class.isAssignableFrom(type)) {
                 double d1, d2;
                 d1 = ((Number) o1).doubleValue();
                 d2 = ((Number) o2).doubleValue();
 
                 if (d1 < d2) {
                     result = -1;
                 } else if (d1 > d2) {
                     result = 1;
                 } else {
                     result = 0;
                 }
             } else if (Boolean.class.isAssignableFrom(type)) {
                 boolean b1 = ((Boolean) o1).booleanValue();
                 boolean b2 = ((Boolean) o2).booleanValue();
 
                 if (b1 == b2) {
                     result = 0;
                 } else if (b1) {
                     // Define false < true
                     result = 1;
                 } else {
                     result = -1;
                 }
             } else {
                 String s1 = o1.toString();
                 String s2 = o2.toString();
                 result = s1.compareTo(s2);
             }
             result = this.sortingColumns[column].getOrder().getOrder() * result;
         }
         return result;
     }
 
     /***
      * This method enables to ensure that the conversion array is big enough.
      */
     protected synchronized void initConverterArray() {
         if (this.sortedIndexToOriginalIndex.length != getRowCount()) {
             this.sortedIndexToOriginalIndex = new int[getRowCount()];
             for (int i = 0; i < this.sortedIndexToOriginalIndex.length; i++) {
                 this.sortedIndexToOriginalIndex[i] = i;
             }
         }
     }
 
     /***
      * This method enables to transform an interval of rows in the original data
      * into a set of intervals in the sorted data.
      * 
      * @param originalStart
      *            the row number of the start of the interval.
      * @param originalEnd
      *            the row number of the end of the interval.
      * @return an array of intervals (size nx2).
      */
     protected int[][] originalIntervalToSortedIntervals(int originalStart,
             int originalEnd) {
         Vector result = new Vector();
         // First convert original interval to discrete sorted indices.
         // Build array to convert original indices to sorted indices
         int[] originalIndexToSortedIndex = null;
         synchronized (this) {
             originalIndexToSortedIndex = new int[this.sortedIndexToOriginalIndex.length];
             for (int i = 0; i < this.sortedIndexToOriginalIndex.length; i++) {
                 originalIndexToSortedIndex[this.sortedIndexToOriginalIndex[i]] = i;
             }
         }
         //Then build array of discrete values corresponding to the parameter
         // interval
         int[] values = new int[originalEnd - originalStart + 1];
         for (int i = 0; i < values.length; i++) {
             values[i] = originalIndexToSortedIndex[originalStart + i];
         }
         java.util.Arrays.sort(values);
         // Then convert discrete sorted indices to intervals.
         int start = 0, end = 1;
         int elem = values[0] + 1;
         int maxIndex = values.length;
         while (start < maxIndex) {
             while ((end < maxIndex) && (values[end] == elem)) {
                 end++;
                 elem++;
             }
             if (end < maxIndex)
                 elem = values[end];
             result.add(new int[] { values[start], values[end - 1] });
             start = end;
         }
         return (int[][]) result.toArray(new int[result.size()][2]);
     }
 
     /***
      * @see javax.swing.table.TableModel#isCellEditable(int, int)
      */
     public boolean isCellEditable(int rowIndex, int columnIndex) {
         return isOriginalCellEditable(getOriginalRow(rowIndex), columnIndex);
     }
 
     /***
      * This method enables to determine if the value at the original (non
      * sorted) row can be modified.
      * 
      * @param row
      *            the row number in the original model.
      * @param column
      *            the column in the model.
      * @return true if the cell at the original coordinates is editable.
      */
     protected abstract boolean isOriginalCellEditable(int row, int column);
 
     /***
      * Provides access to the columns used for sorting.
      * 
      * @return the sortingColumns.
      */
     protected SortableTableColumn[] getSortingColumns() {
         return this.sortingColumns;
     }
 
 }