src/gromacs/gmxana/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     {
  50         ar[i] = i;
  51     }
  52 }
  53
  54 void pswap(int *v1, int *v2)
  55 {
  56     int temp;
  57     temp = *v1;
  58     *v1  = *v2;
  59     *v2  = temp;
  60 }
  61
  62
  63 void Swap (real *v1, real *v2)
  64 {
  65     real temp;
  66     temp = *v1;
  67     *v1  = *v2;
  68     *v2  = temp;
  69 }
  70
  71
  72
  73 void insertionSort(real *arr, int *perm, int startndx, int endndx, int direction)
  74 {
  75     int i, j;
  76
  77     if (direction >= 0)
  78     {
  79         for (i = startndx; i <= endndx; i++)
  80         {
  81             j = i;
  82
  83             while (j > startndx && arr[j - 1] > arr[j])
  84             {
  85                 Swap(&arr[j], &arr[j-1]);
  86                 pswap(&perm[j], &perm[j-1]);
  87                 j--;
  88             }
  89
  90         }
  91
  92     }
  93
  94     if (direction < 0)
  95     {
  96         for (i = startndx; i <= endndx; i++)
  97         {
  98             j = i;
  99
 100             while (j > startndx && arr[j - 1] < arr[j])
 101             {
 102                 Swap(&arr[j], &arr[j-1]);
 103                 pswap(&perm[j], &perm[j-1]);
 104                 j--;
 105             }
 106
 107         }
 108     }
 109 }
 110
 111
 112 int BinarySearch (real *array, int low, int high, real key, int direction)
 113 {
 114     int mid, max, min;
 115     max = high+2;
 116     min = low+1;
 117
 118 /*Iterative implementation*/
 119
 120     if (direction >= 0)
 121     {
 122         while (max-min > 1)
 123         {
 124             mid = (min+max)>>1;
 125             if (key < array[mid-1])
 126             {
 127                 max = mid;
 128             }
 129             else
 130             {
 131                 min = mid;
 132             }
 133         }
 134         return min;
 135     }
 136
 137     else if (direction < 0)
 138     {
 139         while (max-min > 1)
 140         {
 141             mid = (min+max)>>1;
 142             if (key > array[mid-1])
 143             {
 144                 max = mid;
 145             }
 146             else
 147             {
 148                 min = mid;
 149             }
 150         }
 151         return min-1;
 152
 153     } /*end -ifelse direction*/
 154     return -1;
 155 }
 156
 157
 158 int start_binsearch(real *array, int *perm, int low, int high,
 159                     real key, int direction)
 160 {
 161     insertionSort(array, perm, low, high, direction);
 162     return BinarySearch(array, low, high, key, direction);
 163 }
 164
 165 int LinearSearch (double *array, int startindx, int stopindx,
 166                   double key, int *count, int direction)
 167 {
 168     /*Iterative implementation - assume elements sorted*/
 169     int i;
 170     int keyindex;
 171
 172     if (direction >= 0)
 173     {
 174         keyindex = startindx;
 175         for (i = startindx; i <= stopindx; i++)
 176         {
 177             (*count)++;
 178             if (array[i] > key)
 179             {
 180                 keyindex = i-1;
 181                 return keyindex;
 182             }
 183         }
 184     }
 185     else if (direction < 0)
 186     {
 187         keyindex = stopindx;
 188         for (i = stopindx; i >= startindx; i--)
 189         {
 190             (*count)++;
 191             if (array[i] > key)
 192             {
 193                 keyindex = i+1;
 194                 return keyindex;
 195             }
 196         }
 197     }
 198
 199     else
 200     {
 201         gmx_fatal(FARGS, "Startindex=stopindex=%d\n", startindx);
 202     }
 203
 204     return -1;
 205 }