src/gromacs/gmxana/binsearch.cpp

   1 /*
   2  * This file is part of the GROMACS molecular simulation package.
   3  *
   4  * Copyright (c) 2010-2018, The GROMACS development team.
   5  * Copyright (c) 2019, by the GROMACS development team, led by
   6  * Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   7  * and including many others, as listed in the AUTHORS file in the
   8  * top-level source directory and at http://www.gromacs.org.
   9  *
  10  * GROMACS is free software; you can redistribute it and/or
  11  * modify it under the terms of the GNU Lesser General Public License
  12  * as published by the Free Software Foundation; either version 2.1
  13  * of the License, or (at your option) any later version.
  14  *
  15  * GROMACS is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * Lesser General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public
  21  * License along with GROMACS; if not, see
  22  * http://www.gnu.org/licenses, or write to the Free Software Foundation,
  23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  24  *
  25  * If you want to redistribute modifications to GROMACS, please
  26  * consider that scientific software is very special. Version
  27  * control is crucial - bugs must be traceable. We will be happy to
  28  * consider code for inclusion in the official distribution, but
  29  * derived work must not be called official GROMACS. Details are found
  30  * in the README & COPYING files - if they are missing, get the
  31  * official version at http://www.gromacs.org.
  32  *
  33  * To help us fund GROMACS development, we humbly ask that you cite
  34  * the research papers on the package. Check out http://www.gromacs.org.
  35  */
  36 #include "gmxpre.h"
  37
  38 #include "binsearch.h"
  39
  40 #include <cstdio>
  41
  42 #include "gromacs/utility/fatalerror.h"
  43 #include "gromacs/utility/real.h"
  44
  45 /*Make range-array (Permutation identity) for sorting */
  46 void rangeArray(int* ar, int size)
  47 {
  48     int i;
  49     for (i = 0; i < size; i++)
  50     {
  51         ar[i] = i;
  52     }
  53 }
  54
  55 static void pswap(int* v1, int* v2)
  56 {
  57     int temp;
  58     temp = *v1;
  59     *v1  = *v2;
  60     *v2  = temp;
  61 }
  62
  63
  64 static void Swap(real* v1, real* v2)
  65 {
  66     real temp;
  67     temp = *v1;
  68     *v1  = *v2;
  69     *v2  = temp;
  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     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 int BinarySearch(const real* array, int low, int high, real key, int direction)
 110 {
 111     int iMid, iMax, iMin;
 112     iMax = high + 2;
 113     iMin = low + 1;
 114
 115     /*Iterative implementation*/
 116
 117     if (direction >= 0)
 118     {
 119         while (iMax - iMin > 1)
 120         {
 121             iMid = (iMin + iMax) >> 1;
 122             if (key < array[iMid - 1])
 123             {
 124                 iMax = iMid;
 125             }
 126             else
 127             {
 128                 iMin = iMid;
 129             }
 130         }
 131         return iMin;
 132     }
 133     else
 134     {
 135         while (iMax - iMin > 1)
 136         {
 137             iMid = (iMin + iMax) >> 1;
 138             if (key > array[iMid - 1])
 139             {
 140                 iMax = iMid;
 141             }
 142             else
 143             {
 144                 iMin = iMid;
 145             }
 146         }
 147         return iMin - 1;
 148     }
 149 }
 150
 151
 152 int start_binsearch(real* array, int* perm, int low, int high, real key, int direction)
 153 {
 154     insertionSort(array, perm, low, high, direction);
 155     return BinarySearch(array, low, high, key, direction);
 156 }
 157
 158 int LinearSearch(const double* array, int startindx, int stopindx, double key, int* count, int direction)
 159 {
 160     /*Iterative implementation - assume elements sorted*/
 161     int i;
 162     int keyindex;
 163
 164     if (direction >= 0)
 165     {
 166         for (i = startindx; i <= stopindx; i++)
 167         {
 168             (*count)++;
 169             if (array[i] > key)
 170             {
 171                 keyindex = i - 1;
 172                 return keyindex;
 173             }
 174         }
 175     }
 176     else
 177     {
 178         for (i = stopindx; i >= startindx; i--)
 179         {
 180             (*count)++;
 181             if (array[i] > key)
 182             {
 183                 keyindex = i + 1;
 184                 return keyindex;
 185             }
 186         }
 187     }
 188
 189     return -1;
 190 }