2 * This file is part of the GROMACS molecular simulation package.
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.
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.
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.
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.
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.
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.
38 #include "binsearch.h"
42 #include "gromacs/utility/fatalerror.h"
43 #include "gromacs/utility/real.h"
45 /*Make range-array (Permutation identity) for sorting */
46 void rangeArray(int* ar, int size)
49 for (i = 0; i < size; i++)
55 static void pswap(int* v1, int* v2)
64 static void Swap(real* v1, real* v2)
73 void insertionSort(real* arr, int* perm, int startndx, int endndx, int direction)
79 for (i = startndx; i <= endndx; i++)
83 while (j > startndx && arr[j - 1] > arr[j])
85 Swap(&arr[j], &arr[j - 1]);
86 pswap(&perm[j], &perm[j - 1]);
94 for (i = startndx; i <= endndx; i++)
98 while (j > startndx && arr[j - 1] < arr[j])
100 Swap(&arr[j], &arr[j - 1]);
101 pswap(&perm[j], &perm[j - 1]);
109 int BinarySearch(const real* array, int low, int high, real key, int direction)
111 int iMid, iMax, iMin;
115 /*Iterative implementation*/
119 while (iMax - iMin > 1)
121 iMid = (iMin + iMax) >> 1;
122 if (key < array[iMid - 1])
135 while (iMax - iMin > 1)
137 iMid = (iMin + iMax) >> 1;
138 if (key > array[iMid - 1])
152 int start_binsearch(real* array, int* perm, int low, int high, real key, int direction)
154 insertionSort(array, perm, low, high, direction);
155 return BinarySearch(array, low, high, key, direction);
158 int LinearSearch(const double* array, int startindx, int stopindx, double key, int* count, int direction)
160 /*Iterative implementation - assume elements sorted*/
166 for (i = startindx; i <= stopindx; i++)
178 for (i = stopindx; i >= startindx; i--)