|
1
|
1 #pragma once
|
|
|
2
|
|
|
3 namespace pfc {
|
|
|
4 class comparator_default;
|
|
|
5
|
|
|
6 template<typename t_comparator = comparator_default>
|
|
|
7 class binarySearch {
|
|
|
8 public:
|
|
|
9
|
|
|
10 template<typename t_container,typename t_param>
|
|
|
11 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) {
|
|
|
12 t_size max = p_base + p_count;
|
|
|
13 t_size min = p_base;
|
|
|
14 while(min<max) {
|
|
|
15 t_size ptr = min + ( (max-min) >> 1);
|
|
|
16 int state = t_comparator::compare(p_param,p_container[ptr]);
|
|
|
17 if (state > 0) min = ptr + 1;
|
|
|
18 else if (state < 0) max = ptr;
|
|
|
19 else {
|
|
|
20 p_result = ptr;
|
|
|
21 return true;
|
|
|
22 }
|
|
|
23 }
|
|
|
24 p_result = min;
|
|
|
25 return false;
|
|
|
26 }
|
|
|
27
|
|
|
28
|
|
|
29 template<typename t_container,typename t_param>
|
|
|
30 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) {
|
|
|
31 t_size max = p_base + p_count;
|
|
|
32 t_size min = p_base;
|
|
|
33 bool found = false;
|
|
|
34 while(min<max) {
|
|
|
35 t_size ptr = min + ( (max-min) >> 1);
|
|
|
36 int state = t_comparator::compare(p_param,p_container[ptr]);
|
|
|
37 if (state > 0) min = ptr + 1;
|
|
|
38 else if (state < 0) max = ptr;
|
|
|
39 else {
|
|
|
40 found = true; max = ptr;
|
|
|
41 }
|
|
|
42 }
|
|
|
43 p_result = min;
|
|
|
44 return found;
|
|
|
45 }
|
|
|
46
|
|
|
47 template<typename t_container,typename t_param>
|
|
|
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) {
|
|
|
49 t_size max = p_base + p_count;
|
|
|
50 t_size min = p_base;
|
|
|
51 bool found = false;
|
|
|
52 while(min<max) {
|
|
|
53 t_size ptr = min + ( (max-min) >> 1);
|
|
|
54 int state = t_comparator::compare(p_param,p_container[ptr]);
|
|
|
55 if (state > 0) min = ptr + 1;
|
|
|
56 else if (state < 0) max = ptr;
|
|
|
57 else {
|
|
|
58 found = true; min = ptr + 1;
|
|
|
59 }
|
|
|
60 }
|
|
|
61 p_result = min;
|
|
|
62 return found;
|
|
|
63 }
|
|
|
64
|
|
|
65 template<typename t_container,typename t_param>
|
|
|
66 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) {
|
|
|
67 if (!runGroupBegin(p_container,p_base,p_count,p_param,p_result)) {
|
|
|
68 p_resultCount = 0;
|
|
|
69 return false;
|
|
|
70 }
|
|
|
71 t_size groupEnd;
|
|
|
72 if (!runGroupEnd(p_container,p_result,p_count - p_result,p_param,groupEnd)) {
|
|
|
73 //should not happen..
|
|
|
74 PFC_ASSERT(0);
|
|
|
75 p_resultCount = 0;
|
|
|
76 return false;
|
|
|
77 }
|
|
|
78 PFC_ASSERT(groupEnd > p_result);
|
|
|
79 p_resultCount = groupEnd - p_result;
|
|
|
80 return true;
|
|
|
81 }
|
|
|
82 };
|
|
|
83 };
|
