IsoSpec 2.2.1
misc.cpp
1/*
2 * Copyright (C) 2015-2020 Mateusz Łącki and Michał Startek.
3 *
4 * This file is part of IsoSpec.
5 *
6 * IsoSpec is free software: you can redistribute it and/or modify
7 * it under the terms of the Simplified ("2-clause") BSD licence.
8 *
9 * IsoSpec is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12 *
13 * You should have received a copy of the Simplified BSD Licence
14 * along with IsoSpec. If not, see <https://opensource.org/licenses/BSD-2-Clause>.
15 */
16
17
18#include "misc.h"
19#include <utility>
20#include "platform.h"
21#include "isoMath.h"
22
23
24
25namespace IsoSpec
26{
27
28void* quickselect(void ** array, int n, int start, int end)
29{
30 if(start == end)
31 return array[start];
32
33 while(true)
34 {
35 // Partition part
36 int len = end - start;
37#if ISOSPEC_BUILDING_R
38 int pivot = len/2 + start;
39#else
40 size_t pivot = random_gen() % len + start; // Using Mersenne twister directly - we don't
41 // need a very uniform distribution just for pivot
42 // selection
43#endif
44 void* pval = array[pivot];
45 double pprob = getLProb(pval);
46 std::swap(array[pivot], array[end-1]);
47 int loweridx = start;
48 for(int i = start; i < end-1; i++)
49 {
50 if(getLProb(array[i]) < pprob)
51 {
52 std::swap(array[i], array[loweridx]);
53 loweridx++;
54 }
55 }
56 std::swap(array[end-1], array[loweridx]);
57
58 // Selection part
59 if(n == loweridx)
60 return array[n];
61 if(n < loweridx)
62 end = loweridx;
63 else
64 start = loweridx+1;
65 };
66}
67
68} // namespace IsoSpec