src/tools/binsearch.c

   1 /* -*- mode: c; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; c-file-style: "stroustrup"; -*-
   2  * $Id: densorder.c,v 0.9
   3  *
   4  *                This source code is part of
   5  *
   6  *                 G   R   O   M   A   C   S
   7  *
   8  *          GROningen MAchine for Chemical Simulations
   9  *
  10  *                        VERSION 3.0
  11  *
  12  * Copyright (c) 1991-2001
  13  * BIOSON Research Institute, Dept. of Biophysical Chemistry
  14  * University of Groningen, The Netherlands
  15  *
  16  * This program is free software; you can redistribute it and/or
  17  * modify it under the terms of the GNU General Public License
  18  * as published by the Free Software Foundation; either version 2
  19  * of the License, or (at your option) any later version.
  20  *
  21  * If you want to redistribute modifications, please consider that
  22  * scientific software is very special. Version control is crucial -
  23  * bugs must be traceable. We will be happy to consider code for
  24  * inclusion in the official distribution, but derived work must not
  25  * be called official GROMACS. Details are found in the README & COPYING
  26  * files - if they are missing, get the official version at www.gromacs.org.
  27  *
  28  * To help us fund GROMACS development, we humbly ask that you cite
  29  * the papers on the package - you can find them in the top README file.
  30  *
  31  * Do check out http://www.gromacs.org , or mail us at gromacs@gromacs.org .
  32  *
  33  * And Hey:
  34  * Gyas ROwers Mature At Cryogenic Speed
  35  */
  36
  37 #ifdef HAVE_CONFIG_H
  38 #include <config.h>
  39 #endif
  40 #include <stdio.h>
  41 #include "types/simple.h"
  42 #include "gmx_fatal.h"
  43
  44 /*Make range-array (Permutation identity) for sorting */
  45 void rangeArray(int *ar,int size)
  46 {
  47     int i;
  48         for (i=0;i<size;i++){
  49                 ar[i]=i;
  50         }
  51 }
  52
  53 void pswap(int *v1, int *v2)
  54 {
  55         int temp;
  56         temp=*v1;
  57         *v1=*v2;
  58         *v2=temp;
  59 }
  60
  61
  62 void Swap (real *v1, real *v2)
  63 {
  64     real temp;
  65     temp = *v1;
  66     *v1 = *v2;
  67     *v2 = temp;
  68 }
  69
  70
  71
  72 void insertionSort(real *arr, int *perm, int startndx, int endndx, int direction) {
  73     int i, j;
  74
  75         if(direction>=0){
  76         for (i = startndx; i <=endndx; i++) {
  77             j = i;
  78
  79             while (j > startndx && arr[j - 1] > arr[j]) {
  80                 Swap(&arr[j],&arr[j-1]);
  81                                 pswap(&perm[j],&perm[j-1]);
  82                 j--;
  83             }
  84
  85         }
  86
  87         }
  88
  89         if(direction<0){
  90         for (i = startndx; i <=endndx; i++) {
  91             j = i;
  92
  93             while (j > startndx && arr[j - 1] < arr[j]) {
  94                 Swap(&arr[j],&arr[j-1]);
  95                                 pswap(&perm[j],&perm[j-1]);
  96                 j--;
  97             }
  98
  99         }
 100         }
 101 }
 102
 103
 104 int BinarySearch (real *array, int low, int high, real key,int direction)
 105 {
 106     int mid, max, min;
 107     max=high+2;
 108     min=low+1;
 109
 110 /*Iterative implementation*/
 111
 112     if (direction>=0){
 113         while (max-min>1){
 114             mid=(min+max)>>1;
 115             if(key<array[mid-1]) max=mid;
 116             else min=mid;
 117         }
 118         return min;
 119     }
 120
 121     else if (direction<0){
 122         while(max-min>1){
 123             mid=(min+max)>>1;
 124             if(key>array[mid-1]) max=mid;
 125             else min=mid;
 126         }
 127         return min-1;
 128
 129     }/*end -ifelse direction*/
 130    return -1;
 131 }
 132
 133
 134 int start_binsearch(real *array, int *perm, int low, int high,
 135                     real key, int direction)
 136 {
 137         insertionSort(array,perm,low,high,direction);
 138         return BinarySearch(array,low,high,key,direction);
 139 }
 140
 141 int LinearSearch (double *array,int startindx, int stopindx,
 142                   double key,int *count, int direction)
 143 {
 144     /*Iterative implementation - assume elements sorted*/
 145     int i;
 146     int keyindex;
 147
 148     if(direction>=0){
 149         keyindex=startindx;
 150         for (i=startindx;i<=stopindx;i++){
 151             (*count)++;
 152             if(array[i]>key) {
 153                 keyindex=i-1;
 154                 return keyindex;
 155             }
 156         }
 157     }
 158     else if(direction<0 ){
 159         keyindex=stopindx;
 160         for(i=stopindx;i>=startindx;i--){
 161             (*count)++;
 162             if (array[i]>key){
 163                 keyindex=i+1;
 164                 return keyindex;
 165             }
 166         }
 167     }
 168
 169     else
 170         gmx_fatal(FARGS,"Startindex=stopindex=%d\n",startindx);
 171
 172     return -1;
 173 }
 174