Mercurial > foo_out_sdl

comparison foosdk/sdk/pfc/bsearch.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
5 //deprecated
6
7 class NOVTABLE bsearch_callback
8 {
9 public:
10 virtual int test(t_size n) const = 0;
11 };
12
13 bool bsearch(t_size p_count, bsearch_callback const & p_callback,t_size & p_result);
14
15 template<typename t_container,typename t_compare, typename t_param>
16 class bsearch_callback_impl_simple_t : public bsearch_callback {
17 public:
18 int test(t_size p_index) const {
19 return m_compare(m_container[p_index],m_param);
20 }
21 bsearch_callback_impl_simple_t(const t_container & p_container,t_compare p_compare,const t_param & p_param)
22 : m_container(p_container), m_compare(p_compare), m_param(p_param)
23 {
24 }
25 private:
26 const t_container & m_container;
27 t_compare m_compare;
28 const t_param & m_param;
29 };
30
31 template<typename t_container,typename t_compare, typename t_param,typename t_permutation>
32 class bsearch_callback_impl_permutation_t : public bsearch_callback {
33 public:
34 int test(t_size p_index) const {
35 return m_compare(m_container[m_permutation[p_index]],m_param);
36 }
37 bsearch_callback_impl_permutation_t(const t_container & p_container,t_compare p_compare,const t_param & p_param,const t_permutation & p_permutation)
38 : m_container(p_container), m_compare(p_compare), m_param(p_param), m_permutation(p_permutation)
39 {
40 }
41 private:
42 const t_container & m_container;
43 t_compare m_compare;
44 const t_param & m_param;
45 const t_permutation & m_permutation;
46 };
47
48
49 template<typename t_container,typename t_compare, typename t_param>
50 bool bsearch_t(t_size p_count,const t_container & p_container,t_compare p_compare,const t_param & p_param,t_size & p_index) {
51 return bsearch(
52 p_count,
53 bsearch_callback_impl_simple_t<t_container,t_compare,t_param>(p_container,p_compare,p_param),
54 p_index);
55 }
56
57 template<typename t_container,typename t_compare,typename t_param,typename t_permutation>
58 bool bsearch_permutation_t(t_size p_count,const t_container & p_container,t_compare p_compare,const t_param & p_param,const t_permutation & p_permutation,t_size & p_index) {
59 t_size index;
60 if (bsearch(
61 p_count,
62 bsearch_callback_impl_permutation_t<t_container,t_compare,t_param,t_permutation>(p_container,p_compare,p_param,p_permutation),
63 index))
64 {
65 p_index = p_permutation[index];
66 return true;
67 } else {
68 return false;
69 }
70 }
71
72 template<typename t_container,typename t_compare, typename t_param>
73 bool bsearch_range_t(const t_size p_count,const t_container & p_container,t_compare p_compare,const t_param & p_param,t_size & p_range_base,t_size & p_range_count)
74 {
75 t_size probe;
76 if (!bsearch(
77 p_count,
78 bsearch_callback_impl_simple_t<t_container,t_compare,t_param>(p_container,p_compare,p_param),
79 probe)) return false;
80
81 t_size base = probe, count = 1;
82 while(base > 0 && p_compare(p_container[base-1],p_param) == 0) {base--; count++;}
83 while(base + count < p_count && p_compare(p_container[base+count],p_param) == 0) {count++;}
84 p_range_base = base;
85 p_range_count = count;
86 return true;
87 }
88
89 }