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, 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 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 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
 137     else if (direction < 0)
 138     {
 139         while (iMax-iMin > 1)
 140         {
 141             iMid = (iMin+iMax)>>1;
 142             if (key > array[iMid-1])
 143             {
 144                 iMax = iMid;
 145             }
 146             else
 147             {
 148                 iMin = iMid;
 149             }
 150         }
 151         return iMin-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         for (i = startindx; i <= stopindx; i++)
 175         {
 176             (*count)++;
 177             if (array[i] > key)
 178             {
 179                 keyindex = i-1;
 180                 return keyindex;
 181             }
 182         }
 183     }
 184     else if (direction < 0)
 185     {
 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 }