IsoSpec  1.95
misc.cpp
1 /*
2  * Copyright (C) 2015-2018 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 "platform.h"
20 #include <stdlib.h>
21 
22 #define mswap(x, y) swapspace = x; x = y; y=swapspace;
23 
24 
25 namespace IsoSpec
26 {
27 
28 void* quickselect(void** array, int n, int start, int end)
29 {
30  void* swapspace;
31 
32  if(start == end)
33  return array[start];
34 
35  while(true)
36  {
37  // Partition part
38  int len = end - start;
39 #if ISOSPEC_BUILDING_R
40  int pivot = len/2 + start;
41 #else
42  int pivot = rand() % len + start;
43 #endif
44  void* pval = array[pivot];
45  double pprob = getLProb(pval);
46  mswap(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  mswap(array[i], array[loweridx]);
53  loweridx++;
54  }
55  }
56  mswap(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
69 
IsoSpec
Definition: allocator.cpp:21
IsoSpec::quickselect
void * quickselect(void **array, int n, int start, int end)
Quickly select the n'th positional statistic, including the weights.
Definition: misc.cpp:28