Mercurial > foo_out_sdl

comparison foosdk/sdk/pfc/sort.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 #include "array.h"
4
5 namespace pfc {
6
7 void swap_void(void * item1,void * item2,t_size width);
8
9 void reorder_void(void * data,t_size width,const t_size * order,t_size num,void (*swapfunc)(void * item1,void * item2,t_size width) = swap_void);
10
11 class NOVTABLE reorder_callback
12 {
13 public:
14 virtual void swap(t_size p_index1,t_size p_index2) = 0;
15 };
16
17 void reorder(reorder_callback & p_callback,const t_size * p_order,t_size p_count);
18
19 template<typename t_container>
20 class reorder_callback_impl_t : public reorder_callback
21 {
22 public:
23 reorder_callback_impl_t(t_container & p_data) : m_data(p_data) {}
24 void swap(t_size p_index1,t_size p_index2)
25 {
26 pfc::swap_t(m_data[p_index1],m_data[p_index2]);
27 }
28 private:
29 t_container & m_data;
30 };
31
32 class reorder_callback_impl_delta : public reorder_callback
33 {
34 public:
35 reorder_callback_impl_delta(reorder_callback & p_data,t_size p_delta) : m_data(p_data), m_delta(p_delta) {}
36 void swap(t_size p_index1,t_size p_index2)
37 {
38 m_data.swap(p_index1+m_delta,p_index2+m_delta);
39 }
40 private:
41 reorder_callback & m_data;
42 t_size m_delta;
43 };
44
45 template<typename t_container>
46 void reorder_t(t_container & p_data,const t_size * p_order,t_size p_count)
47 {
48 reorder_callback_impl_t<t_container> cb(p_data);
49 reorder(cb,p_order,p_count);
50 }
51
52 template<typename t_container>
53 void reorder_partial_t(t_container & p_data,t_size p_base,const t_size * p_order,t_size p_count)
54 {
55 reorder_callback_impl_t<t_container> cb1(p_data);
56 reorder_callback_impl_delta cb2( cb1, p_base );
57 reorder(cb2,p_order,p_count);
58 // reorder(reorder_callback_impl_delta(reorder_callback_impl_t<t_container>(p_data),p_base),p_order,p_count);
59 }
60
61 template<typename T>
62 class reorder_callback_impl_ptr_t : public reorder_callback
63 {
64 public:
65 reorder_callback_impl_ptr_t(T * p_data) : m_data(p_data) {}
66 void swap(t_size p_index1,t_size p_index2)
67 {
68 pfc::swap_t(m_data[p_index1],m_data[p_index2]);
69 }
70 private:
71 T* m_data;
72 };
73
74
75 template<typename T>
76 void reorder_ptr_t(T* p_data,const t_size * p_order,t_size p_count)
77 {
78 reorder_callback_impl_ptr_t<T> cb(p_data);
79 reorder(cb,p_order,p_count);
80 }
81
82
83
84 class NOVTABLE sort_callback
85 {
86 public:
87 virtual int compare(t_size p_index1, t_size p_index2) const = 0;
88 virtual void swap(t_size p_index1, t_size p_index2) = 0;
89 void swap_check(t_size p_index1, t_size p_index2) {if (compare(p_index1,p_index2) > 0) swap(p_index1,p_index2);}
90 };
91
92 class sort_callback_stabilizer : public sort_callback
93 {
94 public:
95 sort_callback_stabilizer(sort_callback & p_chain,t_size p_count);
96 virtual int compare(t_size p_index1, t_size p_index2) const;
97 virtual void swap(t_size p_index1, t_size p_index2);
98 private:
99 sort_callback & m_chain;
100 array_t<t_size> m_order;
101 };
102
103 void sort(sort_callback & p_callback,t_size p_count);
104 void sort_stable(sort_callback & p_callback,t_size p_count);
105
106 void sort_void_ex(void *base,t_size num,t_size width, int (*comp)(const void *, const void *),void (*swap)(void *, void *, t_size) );
107 void sort_void(void * base,t_size num,t_size width,int (*comp)(const void *, const void *) );
108
109 template<typename t_container,typename t_compare>
110 class sort_callback_impl_simple_wrap_t : public sort_callback
111 {
112 public:
113 sort_callback_impl_simple_wrap_t(t_container & p_data, t_compare p_compare) : m_data(p_data), m_compare(p_compare) {}
114 int compare(t_size p_index1, t_size p_index2) const
115 {
116 return m_compare(m_data[p_index1],m_data[p_index2]);
117 }
118
119 void swap(t_size p_index1, t_size p_index2)
120 {
121 swap_t(m_data[p_index1],m_data[p_index2]);
122 }
123 private:
124 t_container & m_data;
125 t_compare m_compare;
126 };
127
128 template<typename t_container>
129 class sort_callback_impl_auto_wrap_t : public sort_callback
130 {
131 public:
132 sort_callback_impl_auto_wrap_t(t_container & p_data) : m_data(p_data) {}
133 int compare(t_size p_index1, t_size p_index2) const
134 {
135 return compare_t(m_data[p_index1],m_data[p_index2]);
136 }
137
138 void swap(t_size p_index1, t_size p_index2)
139 {
140 swap_t(m_data[p_index1],m_data[p_index2]);
141 }
142 private:
143 t_container & m_data;
144 };
145
146 template<typename t_container,typename t_compare,typename t_permutation>
147 class sort_callback_impl_permutation_wrap_t : public sort_callback
148 {
149 public:
150 sort_callback_impl_permutation_wrap_t(const t_container & p_data, t_compare p_compare,t_permutation const & p_permutation) : m_data(p_data), m_compare(p_compare), m_permutation(p_permutation) {}
151 int compare(t_size p_index1, t_size p_index2) const
152 {
153 return m_compare(m_data[m_permutation[p_index1]],m_data[m_permutation[p_index2]]);
154 }
155
156 void swap(t_size p_index1, t_size p_index2)
157 {
158 swap_t(m_permutation[p_index1],m_permutation[p_index2]);
159 }
160 private:
161 const t_container & m_data;
162 t_compare m_compare;
163 t_permutation const & m_permutation;
164 };
165
166 template<typename t_container,typename t_compare>
167 static void sort_t(t_container & p_data,t_compare p_compare,t_size p_count)
168 {
169 sort_callback_impl_simple_wrap_t<t_container,t_compare> cb(p_data,p_compare);
170 sort(cb,p_count);
171 }
172
173 template<typename t_container,typename t_compare>
174 static void sort_stable_t(t_container & p_data,t_compare p_compare,t_size p_count)
175 {
176 sort_callback_impl_simple_wrap_t<t_container,t_compare> cb(p_data,p_compare);
177 sort_stable(cb,p_count);
178 }
179
180 template<typename t_container,typename t_compare,typename t_permutation>
181 static void sort_get_permutation_t(const t_container & p_data,t_compare p_compare,t_size p_count,t_permutation const & p_permutation)
182 {
183 sort_callback_impl_permutation_wrap_t<t_container,t_compare,t_permutation> cb(p_data,p_compare,p_permutation);
184 sort(cb,p_count);
185 }
186
187 template<typename t_container,typename t_compare,typename t_permutation>
188 static void sort_stable_get_permutation_t(const t_container & p_data,t_compare p_compare,t_size p_count,t_permutation const & p_permutation)
189 {
190 sort_callback_impl_permutation_wrap_t<t_container,t_compare,t_permutation> cb(p_data,p_compare,p_permutation);
191 sort_stable(cb,p_count);
192 }
193
194 }