/***
 *  PROJECT     :  Generation of Anatomical Models for Surgical Simulators (GAMSS)
 *  AUTHOR      :  Raimundo Sierra
 *  CONTACT     :  http://www.rsierra.com/?main=contact
 *  CREATED     :  01.10.2001
 *  CHANGED     :  
 *  DESCRIPTION :  different sorting functions, minmax etc
 * 
 *  TODO        :    
 */


#ifndef SORTFUNCTIONS
#define SORTFUNCTIONS

#include <assert.h>
#include <iostream.h>

////////////////////////////////////////////////////////////////////////////////////////////
// SECTION QuickSort
////////////////////////////////////////////////////////////////////////////////////////////
 
////////////////////////////////////////////////////////////////////////////////////////////
// Quicksort with addition of Resultvector
// Resultvector is the position where the value in the sorted vector originaly was.
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> void QuickSort(T *Sortvector, int p, int r, int *Resultvector=NULL){
  if(r-p >= 1){
    int q = Partition( Sortvector, p, r, Resultvector);
    QuickSort( Sortvector, p, q, Resultvector);
    QuickSort( Sortvector, q+1, r, Resultvector);
  }
}

////////////////////////////////////////////////////////////////////////////////////////////
// Help functions for QuickSort  
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> int  Partition(T *Sortvector, int p, int r, int *Resultvector=NULL) {
  T x = Sortvector[p];
  int i = p;
  int j = r;
  while( i<j ){
    if( Sortvector[j] <= x ){
      j--;
    }
    else {
      if ( Sortvector[i] > x ){
	i++;
      }
      else {
	LabelSwap( Sortvector[i], Sortvector[j], i, j, Resultvector);
      }
    }
  }
#ifdef DEBUG
  assert(i==j);
  for( int k=p;   k<=j; k++) assert(Sortvector[k] >= x);
  for( int k=j+1; k<=p; k++) assert(Sortvector[k] <= x);
  assert (j!=r );
#endif
  return j;
}
       
////////////////////////////////////////////////////////////////////////////////////////////
// Help functions for QuickSort with Resultvector
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> void LabelSwap(T &i, T &j,   const int p1, const int p2, int *labelhistogram=NULL){
  Swap(i,j);
  if(labelhistogram != NULL){
    Swap(labelhistogram[p2], labelhistogram[p1]);
  }
}

////////////////////////////////////////////////////////////////////////////////////////////
// ordinary Swap function
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> void Swap(T &i, T &j){
  T tmp = i;
  i = j;
  j = tmp;
}

////////////////////////////////////////////////////////////////////////////////////////////
// sort 3 elements
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> void sort(T &small, T &medium, T &big){
  T array[3];
  array[0] = small;
  array[1] = medium;
  array[2] = big;
  QuickSort(array, 0, 2); // this sorts descending => "revert" results
  small    = array[2];
  medium   = array[1];
  big      = array[0];
}

////////////////////////////////////////////////////////////////////////////////////////////
// sort 4 elements
////////////////////////////////////////////////////////////////////////////////////////////
template<class T> void sort(T &small, T &medium, T &medium2, T &big){
  T array[4];
  array[0] = small;
  array[1] = medium;
  array[2] = medium2;
  array[3] = big;
  QuickSort(array, 0, 3); // this sorts descending => "revert" results
  small    = array[3];
  medium   = array[2];
  medium2  = array[1];
  big      = array[0];
}


////////////////////////////////////////////////////////////////////////////////////////////
// find minimum and maximum value of vector of length
// min must be larger then smallest value
// max must be smaller then largest value
////////////////////////////////////////////////////////////////////////////////////////////

template<class T> void minmax(const T* data, const int length, T &min, T &max){

#ifdef INFO
  T tmpmin = min;
  T tmpmax = max;
#endif
  min = data[0];
  max = data[0];
  
  for(int i=0; i<length; i++){
    if(data[i] <min) min=data[i];
    if(data[i] >max) max=data[i];
  }
#ifdef INFO
  if(tmpmin == min || tmpmax == max){
    cout << "\nINFO:Did not find new minimum and maximum values\n"
      "\tin function minmax()\n";
    cout << "\tValues are: Minimum="<<min<<" Maximum="<<max<<endl;
  }
  else {
    cout << "INFO:\tValues found in function minmax() are Minimum: "<<min<<" Maximum: "<<max<<endl<<flush;
  }
#endif
}


#endif // SORTFUNCTIONS