src/gromacs/gmxana/binsearch.cpp

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2010,2011,2013,2014,2015,2016,2017,2018, 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 "binsearch.h"
  38
  39 #include <cstdio>
  40
  41 #include "gromacs/utility/fatalerror.h"
  42 #include "gromacs/utility/real.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 static void pswap(int *v1, int *v2)
  55 {
  56     int temp;
  57     temp = *v1;
  58     *v1  = *v2;
  59     *v2  = temp;
  60 }
  61
  62
  63 static 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 (const real *array, int low, int high, real key, int direction)
 113 {
 114     int iMid, iMax, iMin;
 115     iMax = high+2;
 116     iMin = low+1;
 117
 118 /*Iterative implementation*/
 119
 120     if (direction >= 0)
 121     {
 122         while (iMax-iMin > 1)
 123         {
 124             iMid = (iMin+iMax)>>1;
 125             if (key < array[iMid-1])
 126             {
 127                 iMax = iMid;
 128             }
 129             else
 130             {
 131                 iMin = iMid;
 132             }
 133         }
 134         return iMin;
 135     }
 136     else
 137     {
 138         while (iMax-iMin > 1)
 139         {
 140             iMid = (iMin+iMax)>>1;
 141             if (key > array[iMid-1])
 142             {
 143                 iMax = iMid;
 144             }
 145             else
 146             {
 147                 iMin = iMid;
 148             }
 149         }
 150         return iMin-1;
 151     }
 152 }
 153
 154
 155 int start_binsearch(real *array, int *perm, int low, int high,
 156                     real key, int direction)
 157 {
 158     insertionSort(array, perm, low, high, direction);
 159     return BinarySearch(array, low, high, key, direction);
 160 }
 161
 162 int LinearSearch (const double *array, int startindx, int stopindx,
 163                   double key, int *count, int direction)
 164 {
 165     /*Iterative implementation - assume elements sorted*/
 166     int i;
 167     int keyindex;
 168
 169     if (direction >= 0)
 170     {
 171         for (i = startindx; i <= stopindx; i++)
 172         {
 173             (*count)++;
 174             if (array[i] > key)
 175             {
 176                 keyindex = i-1;
 177                 return keyindex;
 178             }
 179         }
 180     }
 181     else
 182     {
 183         for (i = stopindx; i >= startindx; i--)
 184         {
 185             (*count)++;
 186             if (array[i] > key)
 187             {
 188                 keyindex = i+1;
 189                 return keyindex;
 190             }
 191         }
 192     }
 193
 194     return -1;
 195 }