foobar2000 SDK  2015-08-03
binary_search.h
Go to the documentation of this file.
1 namespace pfc {
2  class comparator_default;
3 
4  template<typename t_comparator = comparator_default>
5  class binarySearch {
6  public:
7 
8  template<typename t_container,typename t_param>
9  static bool run(const t_container & p_container,t_size p_base,t_size p_count,const t_param & p_param,t_size & p_result) {
10  t_size max = p_base + p_count;
11  t_size min = p_base;
12  while(min<max) {
13  t_size ptr = min + ( (max-min) >> 1);
14  int state = t_comparator::compare(p_param,p_container[ptr]);
15  if (state > 0) min = ptr + 1;
16  else if (state < 0) max = ptr;
17  else {
18  p_result = ptr;
19  return true;
20  }
21  }
22  p_result = min;
23  return false;
24  }
25 
26 
27  template<typename t_container,typename t_param>
28  static bool runGroupBegin(const t_container & p_container,t_size p_base,t_size p_count,const t_param & p_param,t_size & p_result) {
29  t_size max = p_base + p_count;
30  t_size min = p_base;
31  bool found = false;
32  while(min<max) {
33  t_size ptr = min + ( (max-min) >> 1);
34  int state = t_comparator::compare(p_param,p_container[ptr]);
35  if (state > 0) min = ptr + 1;
36  else if (state < 0) max = ptr;
37  else {
38  found = true; max = ptr;
39  }
40  }
41  p_result = min;
42  return found;
43  }
44 
45  template<typename t_container,typename t_param>
46  static bool runGroupEnd(const t_container & p_container,t_size p_base,t_size p_count,const t_param & p_param,t_size & p_result) {
47  t_size max = p_base + p_count;
48  t_size min = p_base;
49  bool found = false;
50  while(min<max) {
51  t_size ptr = min + ( (max-min) >> 1);
52  int state = t_comparator::compare(p_param,p_container[ptr]);
53  if (state > 0) min = ptr + 1;
54  else if (state < 0) max = ptr;
55  else {
56  found = true; min = ptr + 1;
57  }
58  }
59  p_result = min;
60  return found;
61  }
62 
63  template<typename t_container,typename t_param>
64  static bool runGroup(const t_container & p_container,t_size p_base,t_size p_count,const t_param & p_param,t_size & p_result,t_size & p_resultCount) {
65  if (!runGroupBegin(p_container,p_base,p_count,p_param,p_result)) {
66  p_resultCount = 0;
67  return false;
68  }
69  t_size groupEnd;
70  if (!runGroupEnd(p_container,p_result,p_count - p_result,p_param,groupEnd)) {
71  //should not happen..
72  PFC_ASSERT(0);
73  p_resultCount = 0;
74  return false;
75  }
76  PFC_ASSERT(groupEnd > p_result);
77  p_resultCount = groupEnd - p_result;
78  return true;
79  }
80  };
81 };
int compare(t1 const &p1, t2 const &p2)
Definition: pathUtils.h:29
static bool runGroupBegin(const t_container &p_container, t_size p_base, t_size p_count, const t_param &p_param, t_size &p_result)
Definition: binary_search.h:28
static bool run(const t_container &p_container, t_size p_base, t_size p_count, const t_param &p_param, t_size &p_result)
Definition: binary_search.h:9
size_t t_size
Definition: int_types.h:48
static bool runGroupEnd(const t_container &p_container, t_size p_base, t_size p_count, const t_param &p_param, t_size &p_result)
Definition: binary_search.h:46
static bool runGroup(const t_container &p_container, t_size p_base, t_size p_count, const t_param &p_param, t_size &p_result, t_size &p_resultCount)
Definition: binary_search.h:64