/* EGAD: search_and_sort.cpp
   
Navin Pokala and Tracy Handel
Dept. of Molecular and Cell Biology
University of California, Berkeley
Copyright (C) 2003 Regents of the University of California
GNU Public License
Aug 12 2003

Absolutely no warranties are made or are implied with the use of this program or its parts.

This file contains functions for sorting and searching arrays in EGAD.
   
*/


#include "search_and_sort.h"

/* use these for bsearch/qsort */
/* return int that is <,=,> 0 depending on how the two arguments are related (<, =, >) */
/* nomenclature: xxx_yyy */
/* xxx = element being compared; yyy  = structure-type */


/* RESPARAM residuetype comparision function for bsearch/qsort */
int restypecompare_resparam(const void *node1, const void *node2)
{
   return(strcmp(((const RESPARAM *)node1)->residuetype,((const RESPARAM *)node2)->residuetype)); 
}


/* ROTAMERLIB residuetype comparision function for bsearch/qsort */
int restypecompare_rotamerlib(const void *node1, const void *node2)
{
  return(strcmp(((const ROTAMERLIB *)node1)->residuetype,((const ROTAMERLIB *)node2)->residuetype));
}

/* ATOMRESPARAM atomname comparision function for bsearch/qsort */
int atomnamecompare_atomresparam(const void *node1, const void *node2)
{
  return(strcmp(((const ATOMRESPARAM *)node1)->atomname,((const ATOMRESPARAM *)node2)->atomname));
}

/* Binary search for a specific atomname in an sorted array of ATOMRESPARAM 
   Returns the index of the array position */

int search_atomname_ATOMRESPARAM(char *atomname, ATOMRESPARAM atomresparam[])
{
  int i; /* the index of interest */
  int lower,upper; /* lower and upper bound indexes for the search */
  int found; /* flag for whether we have found the atomnname of interest; found=0 for not found */
  
  i=1;
  
  found = 0;  /* not found */

  lower = 1; upper = MAX_RES_SIZE-1;

  while(lower<=upper && found==0)
    {
      i = (lower+upper)/2;
      if(strcmp(atomresparam[i].atomname,atomname)==0)   /* found */
	found = 1;    
      else
	if(strcmp(atomresparam[i].atomname,atomname)<0)
	  lower = i+1;
	else
	  upper = i-1;
    }

 
  if(found==1)
  	return i;
  else
	return 0;	
 

}

/* Binary search for a specific residuetype in an array of RESPARAM; 
   Returns the index of the array position 	*/ 

int search_residuetype_RESPARAM(char *residuetype, RESPARAM resparam[])
{
  int i; /* the index of interest */
  int lower,upper; /* lower and upper bound indexes for the search */
  int found; /* flag for whether we have found the residuetype of interest; found=0 for not found */
  
  found = 0;  /* not found */

  lower = 1; upper = MAXRESTYPES-1;

  while(lower<=upper && found==0)
    {
      i = (lower+upper)/2;
      if(strcmp(resparam[i].residuetype,residuetype)==0)   /* found */
	found = 1;    
      else
	if(strcmp(resparam[i].residuetype,residuetype)<0)
	  lower = i+1;
	else
	  upper = i-1;
    }

   
  if(found==1)
  	return i;
  else
	return 0;	
 

}


/* sorts an array of CHROMOSOMEs by energy (lowest energy-->highest), using the quicksort algorithm  
   first=1; last = size of array 
*/ 
void sort_CHROMOSOME(int *first, int *last, CHROMOSOME chr[])
{
  int left, right;
  CHROMOSOME pivot;
  CHROMOSOME dummy;

  left = *first;
  right = *last;
  
 
  pivot = chr[(left+right)/2];

  
  while(left <= right)
    {
      while(chr[right].energy > pivot.energy)
	--right;
      while(chr[left].energy < pivot.energy)
	++left;
      if(left <= right)
	{
	  dummy = chr[left];
	  chr[left] = chr[right];
	  chr[right] = dummy;

	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_CHROMOSOME(first,&right,chr);
  if(*last > left)
    sort_CHROMOSOME(&left,last,chr);
}

/* sorts an array of ROTAMER by freq (highest->lowest), using the quicksort algorithm  
  first=1; last = size of array 
*/ 
void sort_ROTAMER(int *first, int *last, ROTAMER rotamer[])
{
  int left, right;
  ROTAMER pivot;
  ROTAMER dummy;

  left = *first;
  right = *last;
  
  pivot = rotamer[(left+right)/2];
 
  while(left <= right)
    {
      while((-rotamer[right].freq) > (-pivot.freq))
	--right;
      while((-rotamer[left].freq) < (-pivot.freq))
	++left;
      if(left <= right)
	{
	  dummy = rotamer[left];
	  rotamer[left] = rotamer[right];
	  rotamer[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_ROTAMER(first,&right,rotamer);
  if(*last > left)
    sort_ROTAMER(&left,last,rotamer);
}

/* sorts an array of CHOICE by resparam_ptr->one_letter_code, using the quicksort algorithm  
  first=1; last = size of array 
*/ 
void sort_CHOICE(int *first, int *last, CHOICE arrayint[])
{
  int left, right;
  CHOICE pivot;
  CHOICE dummy;
  
  left = *first;
  right = *last;
  
  pivot = arrayint[(left+right)/2];
  
  while(left <= right)
    {
      while( arrayint[right].resparam_ptr->one_letter_code[0] > pivot.resparam_ptr->one_letter_code[0] )
	--right;
      while( arrayint[left].resparam_ptr->one_letter_code[0] < pivot.resparam_ptr->one_letter_code[0] )
	++left;
      if(left <= right)
	{
	  dummy = arrayint[left];
	  arrayint[left] = arrayint[right];
	  arrayint[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_CHOICE(first,&right,arrayint);
  if(*last > left)
    sort_CHOICE(&left,last,arrayint);
}



/* sorts an array of int by value (lowest->highest), using the quicksort algorithm  
  first=1; last = size of array 
*/ 

void sort_int(int *first, int *last, int arrayint[])
{
  int left, right;
  int pivot;
  int dummy;
  
  left = *first;
  right = *last;
  
  pivot = arrayint[(left+right)/2];
  
  while(left <= right)
    {
      while(arrayint[right] > pivot)
	--right;
      while(arrayint[left] < pivot)
	++left;
      if(left <= right)
	{
	  dummy = arrayint[left];
	  arrayint[left] = arrayint[right];
	  arrayint[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_int(first,&right,arrayint);
  if(*last > left)
    sort_int(&left,last,arrayint);
}

/* sorts an array of double by value (lowest->highest), using the quicksort algorithm  
  first=1; last = size of array 
*/ 
void sort_double(int *first, int *last, double arraydouble[])
{
  int left, right;
  double pivot;
  double dummy;
  
  left = *first;
  right = *last;
  
  pivot = arraydouble[(left+right)/2];
  
  while(left <= right)
    {
      while(arraydouble[right] > pivot)
	--right;
      while(arraydouble[left] < pivot)
	++left;
      if(left <= right)
	{
	  dummy = arraydouble[left];
	  arraydouble[left] = arraydouble[right];
	  arraydouble[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_double(first,&right,arraydouble);
  if(*last > left)
    sort_double(&left,last,arraydouble);
}

/* sorts an array of double by value (highest->lowest); ie: by rank;
	opposite order of sort_double. 
  	first=1; last = size of array.
*/ 
void rank_sort_double(int *first, int *last, double arraydouble[])
{
  int left, right;
  double pivot;
  double dummy;
  
  left = *first;
  right = *last;
  
  pivot = -arraydouble[(left+right)/2];
  
  while(left <= right)
    {
      while(-arraydouble[right] > pivot)
	--right;
      while(-arraydouble[left] < pivot)
	++left;
      if(left <= right)
	{
	  dummy = arraydouble[left];
	  arraydouble[left] = arraydouble[right];
	  arraydouble[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    rank_sort_double(first,&right,arraydouble);
  if(*last > left)
    rank_sort_double(&left,last,arraydouble);
}

/* sorts an array of VARIABLE_POSITION by seq_position (lowest->highest), using the quicksort algorithm  
  first=1; last = size of array 
*/ 
void sort_VARIABLE_POSITION(int *first, int *last, VARIABLE_POSITION varpos[])
{
  int left, right;
  VARIABLE_POSITION pivot;
  VARIABLE_POSITION dummy;
  
  left = *first;
  right = *last;
  
  pivot = varpos[(left+right)/2];
  
  while(left <= right)
    {
      while(varpos[right].seq_position > pivot.seq_position)
	--right;
      while(varpos[left].seq_position < pivot.seq_position)
	++left;
      if(left <= right)
	{
	  dummy = varpos[left];
	  varpos[left] = varpos[right];
	  varpos[right] = dummy;
	  ++left;
	  --right;
	}
    }
  if(*first < right)
    sort_VARIABLE_POSITION(first,&right,varpos);
  if(*last > left)
    sort_VARIABLE_POSITION(&left,last,varpos);
}