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
  43 /*Make range-array (Permutation identity) for sorting */
  44 void rangeArray(int *ar,int size)
  45 {
  46     int i;
  47         for (i=0;i<size;i++){
  48                 ar[i]=i;
  49         }
  50 }
  51
  52 void pswap(int *v1, int *v2)
  53 {
  54         int temp;
  55         temp=*v1;
  56         *v1=*v2;
  57         *v2=temp;
  58 }
  59
  60
  61 void Swap (real *v1, real *v2)
  62 {
  63     real temp;
  64     temp = *v1;
  65     *v1 = *v2;
  66     *v2 = temp;
  67 }
  68
  69
  70
  71 void insertionSort(real *arr, int *perm, int startndx, int endndx, int direction) {
  72     int i, j;
  73
  74         if(direction>=0){
  75         for (i = startndx; i <=endndx; i++) {
  76             j = i;
  77
  78             while (j > startndx && arr[j - 1] > arr[j]) {
  79                 Swap(&arr[j],&arr[j-1]);
  80                                 pswap(&perm[j],&perm[j-1]);
  81                 j--;
  82             }
  83
  84         }
  85
  86         }
  87
  88         if(direction<0){
  89         for (i = startndx; i <=endndx; i++) {
  90             j = i;
  91
  92             while (j > startndx && arr[j - 1] < arr[j]) {
  93                 Swap(&arr[j],&arr[j-1]);
  94                                 pswap(&perm[j],&perm[j-1]);
  95                 j--;
  96             }
  97
  98         }
  99         }
 100 }
 101
 102
 103 int BinarySearch (real *array, int low, int high, real key,int direction)
 104 {
 105     int mid, max, min;
 106     max=high+2;
 107     min=low+1;
 108
 109 /*Iterative implementation*/
 110
 111     if (direction>=0){
 112         while (max-min>1){
 113             mid=(min+max)>>1;
 114             if(key<array[mid-1]) max=mid;
 115             else min=mid;
 116         }
 117         return min;
 118     }
 119
 120     else if (direction<0){
 121         while(max-min>1){
 122             mid=(min+max)>>1;
 123             if(key>array[mid-1]) max=mid;
 124             else min=mid;
 125         }
 126         return min-1;
 127
 128     }/*end -ifelse direction*/
 129 }
 130
 131
 132 int start_binsearch(real *array, int *perm, int low, int high,
 133                     real key, int direction)
 134 {
 135         insertionSort(array,perm,low,high,direction);
 136         return BinarySearch(array,low,high,key,direction);
 137 }
 138
 139 int LinearSearch (double *array,int startindx, int stopindx,
 140                   double key,int *count, int direction)
 141 {
 142     /*Iterative implementation - assume elements sorted*/
 143     int i;
 144     int keyindex;
 145
 146     if(direction>=0){
 147         keyindex=startindx;
 148         for (i=startindx;i<=stopindx;i++){
 149             (*count)++;
 150             if(array[i]>key) {
 151                 keyindex=i-1;
 152                 return keyindex;
 153             }
 154         }
 155     }
 156     else if(direction<0 ){
 157         keyindex=stopindx;
 158         for(i=stopindx;i>=startindx;i--){
 159             (*count)++;
 160             if (array[i]>key){
 161                 keyindex=i+1;
 162                 return keyindex;
 163             }
 164         }
 165     }
 166
 167     else
 168         fprintf(stderr,"Error: startindex=stopindex=%d\n",startindx);
 169
 170 }
 171