src/tools/binsearch.c

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 1991-2001
   5  * BIOSON Research Institute, Dept. of Biophysical Chemistry
   6  * University of Groningen, The Netherlands
   7  * Copyright (c) 2012, by the GROMACS development team, led by
   8  * David van der Spoel, Berk Hess, Erik Lindahl, and including many
   9  * others, as listed in the AUTHORS file in the top-level source
  10  * directory and at http://www.gromacs.org.
  11  *
  12  * GROMACS is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public License
  14  * as published by the Free Software Foundation; either version 2.1
  15  * of the License, or (at your option) any later version.
  16  *
  17  * GROMACS is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with GROMACS; if not, see
  24  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  25  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  26  *
  27  * If you want to redistribute modifications to GROMACS, please
  28  * consider that scientific software is very special. Version
  29  * control is crucial - bugs must be traceable. We will be happy to
  30  * consider code for inclusion in the official distribution, but
  31  * derived work must not be called official GROMACS. Details are found
  32  * in the README & COPYING files - if they are missing, get the
  33  * official version at http://www.gromacs.org.
  34  *
  35  * To help us fund GROMACS development, we humbly ask that you cite
  36  * the research papers on the package. Check out http://www.gromacs.org.
  37  */
  38
  39 #ifdef HAVE_CONFIG_H
  40 #include <config.h>
  41 #endif
  42 #include <stdio.h>
  43 #include "types/simple.h"
  44 #include "gmx_fatal.h"
  45
  46 /*Make range-array (Permutation identity) for sorting */
  47 void rangeArray(int *ar,int size)
  48 {
  49     int i;
  50         for (i=0;i<size;i++){
  51                 ar[i]=i;
  52         }
  53 }
  54
  55 void pswap(int *v1, int *v2)
  56 {
  57         int temp;
  58         temp=*v1;
  59         *v1=*v2;
  60         *v2=temp;
  61 }
  62
  63
  64 void Swap (real *v1, real *v2)
  65 {
  66     real temp;
  67     temp = *v1;
  68     *v1 = *v2;
  69     *v2 = temp;
  70 }
  71
  72
  73
  74 void insertionSort(real *arr, int *perm, int startndx, int endndx, int direction) {
  75     int i, j;
  76
  77         if(direction>=0){
  78         for (i = startndx; i <=endndx; i++) {
  79             j = i;
  80
  81             while (j > startndx && arr[j - 1] > arr[j]) {
  82                 Swap(&arr[j],&arr[j-1]);
  83                                 pswap(&perm[j],&perm[j-1]);
  84                 j--;
  85             }
  86
  87         }
  88
  89         }
  90
  91         if(direction<0){
  92         for (i = startndx; i <=endndx; i++) {
  93             j = i;
  94
  95             while (j > startndx && arr[j - 1] < arr[j]) {
  96                 Swap(&arr[j],&arr[j-1]);
  97                                 pswap(&perm[j],&perm[j-1]);
  98                 j--;
  99             }
 100
 101         }
 102         }
 103 }
 104
 105
 106 int BinarySearch (real *array, int low, int high, real key,int direction)
 107 {
 108     int mid, max, min;
 109     max=high+2;
 110     min=low+1;
 111
 112 /*Iterative implementation*/
 113
 114     if (direction>=0){
 115         while (max-min>1){
 116             mid=(min+max)>>1;
 117             if(key<array[mid-1]) max=mid;
 118             else min=mid;
 119         }
 120         return min;
 121     }
 122
 123     else if (direction<0){
 124         while(max-min>1){
 125             mid=(min+max)>>1;
 126             if(key>array[mid-1]) max=mid;
 127             else min=mid;
 128         }
 129         return min-1;
 130
 131     }/*end -ifelse direction*/
 132    return -1;
 133 }
 134
 135
 136 int start_binsearch(real *array, int *perm, int low, int high,
 137                     real key, int direction)
 138 {
 139         insertionSort(array,perm,low,high,direction);
 140         return BinarySearch(array,low,high,key,direction);
 141 }
 142
 143 int LinearSearch (double *array,int startindx, int stopindx,
 144                   double key,int *count, int direction)
 145 {
 146     /*Iterative implementation - assume elements sorted*/
 147     int i;
 148     int keyindex;
 149
 150     if(direction>=0){
 151         keyindex=startindx;
 152         for (i=startindx;i<=stopindx;i++){
 153             (*count)++;
 154             if(array[i]>key) {
 155                 keyindex=i-1;
 156                 return keyindex;
 157             }
 158         }
 159     }
 160     else if(direction<0 ){
 161         keyindex=stopindx;
 162         for(i=stopindx;i>=startindx;i--){
 163             (*count)++;
 164             if (array[i]>key){
 165                 keyindex=i+1;
 166                 return keyindex;
 167             }
 168         }
 169     }
 170
 171     else
 172         gmx_fatal(FARGS,"Startindex=stopindex=%d\n",startindx);
 173
 174     return -1;
 175 }
 176