Mercurial > foo_out_sdl

comparison foosdk/sdk/pfc/binary_search.h @ 1:20d02a178406 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
*: check in everything else yay
author Paper <paper@tflc.us>
date Mon, 05 Jan 2026 02:15:46 -0500
parents
children
comparison
equal deleted inserted replaced
0:e9bb126753e7 1:20d02a178406
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 };