src/gromacs/gmxana/binsearch.c

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