|
1
|
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 }
|
