/*
 * QuerySort
 * Rick Osborne, 1999, <rick@rixsoft.com>
 * $Log: $
 * Incoming attributes:
 *   QUERY   : The query to be sorted *in-place*.
 *   COLUMN1 : The column to be sorted on.
 *   COLUMN2 : (Optional) the second column to be sorted on
 * Outgoing attributes
 *   ERROR   : (Defaults to "QuerySort.Error") Any error messages returned.
 * Notes:
 * - This module sorts a query *in-place*, so if you want an unsorted
 *   copy of your query then make a backup *before* you call it.
 * - Sorting is *always* alphabetic, *never* numeric.  The whole point
 *   of this module is to sort large text fields, so it will *never*
 *   sort for numeric order.  Also, it is case-insensitive.
 * - Right now, only 2 columns are supported.  If you need more columns,
 *   add the code yourself.  This code should be fairly straightforward,
 *   and it is trivial to add columns if necessary.  Check out the
 *   row_compare() function if you have questions.
 * - If you don't have a second column to sort on, *don't* pass one in!
 *   It tries to do a bit of optimizing if you only have one column, so
 *   if you second-guess it you will break it!
 * - It *should* work with CF versions < 4, but I haven't tested it.
 * - It uses a basic quicksort algorithm.  A 200MHz with 128MB RAM and
 *   moderate load sorted 20000 entries in just under 15 secs.  Anything
 *   less than 10000 is pretty much instantaneous.
 * Usage:
 *   <CFQUERY DATASOURCE="MyDataSourceName" NAME="qFoo">
 *   SELECT some_id, some_memo_field FROM some_table
 *   </CFQUERY>
 *   <CFTRY>
 *     <CFX_QUERYSORT QUERY="qFoo" COLUMN1="some_memo_field" ERROR="qsErr">
 *   <CFCATCH TYPE="ANY">
 *     <CFIF IsDefined("qsError")>
 *       <CFOUTPUT>Ack! #qsError#</CFOUTPUT>
 *     <CFELSE>
 *       <CFOUTPUT>Eek!  Something very bad happened!</CFOUTPUT>
 *     </CFIF>
 *   </CFCATCH>
 *   </CFTRY>
 *   <CFOUTPUT QUERY="qFoo">
 *   #some_memo_field#
 *   </CFOUTPUT>
 */

#include <windows.h>
#include "cfx.h"
#define TAG_ERROR_HEADER	"Error occurred in CFX_QUERYSORT tag"

void query_sort(CCFXQuery*, int, int, int, int, int);
void row_swap(CCFXQuery*, int, int, int);
int  row_compare(CCFXQuery*, int, int, LPCSTR, int, int, int, int);
void query_quicksort1(CCFXQuery*, int, int, int, int, int);
void query_quicksort2(CCFXQuery*, int, int, int, int, int, int, int);

void ProcessTagRequest(CCFXRequest* pRequest) {
  HMODULE hInst = NULL;
  LPCSTR sColumn1 = pRequest->GetAttribute("COLUMN1");
  LPCSTR sColumn2 = pRequest->GetAttribute("COLUMN2");
  LPCSTR sOrder1 = pRequest->GetAttribute("ORDER1");
  LPCSTR sOrder2 = pRequest->GetAttribute("ORDER2");
  LPCSTR sError   = pRequest->GetAttribute("ERROR");
  int iOrder1, iOrder2;
  if(!sError || !*sError) sError = "QuerySort.Error";
  try {
    CCFXQuery* qThis = pRequest->GetQuery();
    if (!qThis) throw "Required QUERY not found.";
    CCFXStringSet* ssCols = qThis->GetColumns();
    if (!sColumn1 || !*sColumn1) throw "Required COLUMN1 attribute not found";
    int iCol1 = ssCols->GetIndexForString(sColumn1);
    if (iCol1 == CFX_STRING_NOT_FOUND) throw "Column COLUMN1 not found in QUERY.";
    int iCol2 = ssCols->GetIndexForString(sColumn2);
    if (sColumn2 && *sColumn2 && (iCol2 == CFX_STRING_NOT_FOUND)) throw "Column COLUMN2 not found in query.";
    if(!sColumn2 || !*sColumn2) iCol2 = CFX_STRING_NOT_FOUND;
    if(!sOrder1 || !*sOrder1) iOrder1 = 1;
    else if(!stricmp(sOrder1,"ASC")) iOrder1 = 1;
    else if(!stricmp(sOrder1,"DESC")) iOrder1 = -1;
    else throw "Possible values of ORDER1 are 'ASC' or 'DESC'.";
    if(!sOrder2 || !*sOrder2) iOrder2 = 1;
    else if(!stricmp(sOrder2,"ASC")) iOrder2 = 1;
    else if(!stricmp(sOrder2,"DESC")) iOrder2 = -1;
    else throw "Possible values of ORDER2 are 'ASC' or 'DESC'.";
    query_sort(qThis,iCol1,iCol2,ssCols->GetCount(),iOrder1,iOrder2);
  } //try
  catch(CCFXException* e) {
    pRequest->ReThrowException(e);
  } //catch
  catch(char *cp) {
    pRequest->SetVariable(sError,cp);
    pRequest->ThrowException(TAG_ERROR_HEADER,cp);
  } //catch
  catch( ... ) {
    pRequest->ThrowException(TAG_ERROR_HEADER,"Unexpected error occurred while processing tag.");
  } //catch
} //ProcessTagRequest

void query_sort(CCFXQuery* qIn, int iCol1, int iCol2, int iCols, int iOrder1, int iOrder2) {
  if(iCol2 == CFX_STRING_NOT_FOUND) query_quicksort1(qIn,1,qIn->GetRowCount(),iCol1,iCols,iOrder1);
  else query_quicksort2(qIn,1,qIn->GetRowCount(),iCol1,iCol2,iCols,iOrder1,iOrder2);
} /* query_sort */

void row_swap(CCFXQuery* qIn, int iRow1, int iRow2, int iCols) {
  LPCSTR sTemp1;
  if(iRow1 == iRow2) return;
  for (int k=1;k<=iCols;++k) {
    sTemp1 = strdup(qIn->GetData(iRow1,k));
    qIn->SetData(iRow1,k,qIn->GetData(iRow2,k));
    qIn->SetData(iRow2,k,sTemp1);
    if(sTemp1) free((void*)sTemp1);
  } //for
}

void query_quicksort1(CCFXQuery* qIn, int iMin, int iMax, int iCol1, int iCols, int iOrder1) {
  int i, j;
  if (iMin < iMax) {
    LPCSTR sMin1;
    sMin1 = qIn->GetData(iMin,iCol1);
    i = iMin;
    j = iMax;
    while (i <= j) {
      while ((j > iMin) && ((stricmp(qIn->GetData(j,iCol1),sMin1) * iOrder1) > 0)) --j;
      while ((i < iMax) && ((stricmp(qIn->GetData(i,iCol1),sMin1) * iOrder1) < 0)) ++i;
      if (i < j) row_swap(qIn,i++,j--,iCols);
      else if (i == j) { i++; j--; }
    } //while
    if(i < iMax) query_quicksort1(qIn,i,iMax,iCol1,iCols,iOrder1);
    if(j > iMin) query_quicksort1(qIn,iMin,j,iCol1,iCols,iOrder1);
  } //if
} /* query_partition */

void query_quicksort2(CCFXQuery* qIn, int iMin, int iMax, int iCol1, int iCol2, int iCols, int iOrder1, int iOrder2) {
  int i, j;
  if (iMin < iMax) {
    LPCSTR sMin1;
    sMin1 = qIn->GetData(iMin,iCol1);
    i = iMin;
    j = iMax;
    while (i <= j) {
      while ((j > iMin) && (row_compare(qIn,j,iMin,sMin1,iCol1,iCol2,iOrder1,iOrder2) > 0)) --j;
      while ((i < iMax) && (row_compare(qIn,i,iMin,sMin1,iCol1,iCol2,iOrder1,iOrder2) < 0)) ++i;
      if (i < j) row_swap(qIn,i++,j--,iCols);
      else if (i == j) { i++; j--; }
    } //while
    if(i < iMax) query_quicksort2(qIn,i,iMax,iCol1,iCol2,iCols,iOrder1,iOrder2);
    if(j > iMin) query_quicksort2(qIn,iMin,j,iCol1,iCol2,iCols,iOrder1,iOrder2);
  } //if
} /* query_partition */

inline int row_compare(CCFXQuery* qIn, int iRow1, int iRow2, LPCSTR sBase, int iCol1, int iCol2, int iOrder1, int iOrder2) {
  int ret;
  if ((ret = (stricmp(qIn->GetData(iRow1,iCol1),sBase) * iOrder1)) == 0) return (stricmp(qIn->GetData(iRow1,iCol2),qIn->GetData(iRow2,iCol2)) * iOrder2);
  else return ret;
}