IsoSpec  2.1.2
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 
25 namespace IsoSpec
26 {
27 
28 void* 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
IsoSpec
Definition: allocator.cpp:20