|
1
|
1 #pragma once
|
|
|
2 #include "bsearch.h"
|
|
|
3 #include "sort.h"
|
|
|
4 #include "primitives.h"
|
|
|
5 #include "traits.h"
|
|
|
6 #include "bit_array.h"
|
|
|
7 #include "bit_array_impl.h"
|
|
|
8 #include "order_helper.h"
|
|
|
9 #include "array.h"
|
|
|
10
|
|
|
11 #include <iterator>
|
|
|
12
|
|
|
13 namespace pfc {
|
|
|
14 template<typename arr_t>
|
|
|
15 class list_const_iterator {
|
|
|
16 typedef list_const_iterator<arr_t> self_t;
|
|
|
17 public:
|
|
|
18 typedef ptrdiff_t difference_type;
|
|
|
19 typedef typename arr_t::t_item value_type;
|
|
|
20 typedef const value_type* pointer;
|
|
|
21 typedef const value_type& reference;
|
|
|
22 typedef std::random_access_iterator_tag iterator_category;
|
|
|
23
|
|
|
24 list_const_iterator(arr_t* arr, size_t index) : m_arr(arr), m_index(index) {}
|
|
|
25 void operator++() { ++m_index; }
|
|
|
26 void operator--() { --m_index; }
|
|
|
27 value_type operator*() const { return m_arr->get_item(m_index); }
|
|
|
28
|
|
|
29 bool operator==(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index == other.m_index; }
|
|
|
30 bool operator!=(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index != other.m_index; }
|
|
|
31 bool operator>(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index > other.m_index; }
|
|
|
32 bool operator<(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index < other.m_index; }
|
|
|
33 bool operator>=(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index >= other.m_index; }
|
|
|
34 bool operator<=(const self_t& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index <= other.m_index; }
|
|
|
35
|
|
|
36 void operator+=(size_t v) { m_index += v; }
|
|
|
37 self_t operator+(size_t v) { self_t ret = *this; ret += v; return ret; }
|
|
|
38 difference_type operator-(self_t const& other) const { PFC_ASSERT(m_arr == other.m_arr); return m_index - other.m_index; }
|
|
|
39 void operator-=(size_t v) { m_index -= v; }
|
|
|
40 private:
|
|
|
41 arr_t* m_arr;
|
|
|
42 size_t m_index;
|
|
|
43 };
|
|
|
44 }
|
|
|
45
|
|
|
46 namespace std {
|
|
|
47 template<typename arr_t> struct iterator_traits< pfc::list_const_iterator<arr_t> > {
|
|
|
48 typedef ptrdiff_t difference_type;
|
|
|
49 typedef typename arr_t::t_item value_type;
|
|
|
50 typedef value_type* pointer;
|
|
|
51 typedef value_type& reference;
|
|
|
52 typedef std::random_access_iterator_tag iterator_category;
|
|
|
53 };
|
|
|
54 }
|
|
|
55
|
|
|
56 namespace pfc {
|
|
|
57
|
|
|
58 template<typename T>
|
|
|
59 class NOVTABLE list_base_const_t {
|
|
|
60 private: typedef list_base_const_t<T> t_self;
|
|
|
61 public:
|
|
|
62 typedef T t_item;
|
|
|
63 virtual t_size get_count() const = 0;
|
|
|
64 virtual void get_item_ex(T& p_out, t_size n) const = 0;
|
|
|
65
|
|
|
66 inline t_size get_size() const {return get_count();}
|
|
|
67 inline size_t size() const { return get_count(); }
|
|
|
68
|
|
|
69 inline T get_item(t_size n) const {T temp; get_item_ex(temp,n); return temp;}
|
|
|
70 inline T operator[](t_size n) const {T temp; get_item_ex(temp,n); return temp;}
|
|
|
71
|
|
|
72 template<typename t_compare>
|
|
|
73 t_size find_duplicates_sorted_t(t_compare p_compare,bit_array_var & p_out) const
|
|
|
74 {
|
|
|
75 return ::pfc::find_duplicates_sorted_t<list_base_const_t<T> const &,t_compare>(*this,get_count(),p_compare,p_out);
|
|
|
76 }
|
|
|
77
|
|
|
78 template<typename t_compare,typename t_permutation>
|
|
|
79 t_size find_duplicates_sorted_permutation_t(t_compare p_compare,t_permutation const & p_permutation,bit_array_var & p_out)
|
|
|
80 {
|
|
|
81 return ::pfc::find_duplicates_sorted_permutation_t<list_base_const_t<T> const &,t_compare,t_permutation>(*this,get_count(),p_compare,p_permutation,p_out);
|
|
|
82 }
|
|
|
83
|
|
|
84 template<typename t_search>
|
|
|
85 t_size find_item(const t_search & p_item) const//returns index of first occurance, infinite if not found
|
|
|
86 {
|
|
|
87 t_size n,max = get_count();
|
|
|
88 for(n=0;n<max;n++)
|
|
|
89 if (get_item(n)==p_item) return n;
|
|
|
90 return SIZE_MAX;
|
|
|
91 }
|
|
|
92
|
|
|
93 template<typename t_search>
|
|
|
94 inline bool have_item(const t_search & p_item) const {return find_item<t_search>(p_item)!=SIZE_MAX;}
|
|
|
95
|
|
|
96
|
|
|
97 template<typename t_compare, typename t_param>
|
|
|
98 bool bsearch_t(t_compare p_compare,t_param const & p_param,t_size &p_index) const {
|
|
|
99 return ::pfc::bsearch_t(get_count(),*this,p_compare,p_param,p_index);
|
|
|
100 }
|
|
|
101
|
|
|
102 template<typename t_compare,typename t_param,typename t_permutation>
|
|
|
103 bool bsearch_permutation_t(t_compare p_compare,t_param const & p_param,const t_permutation & p_permutation,t_size & p_index) const {
|
|
|
104 return ::pfc::bsearch_permutation_t(get_count(),*this,p_compare,p_param,p_permutation,p_index);
|
|
|
105 }
|
|
|
106
|
|
|
107 template<typename t_compare,typename t_permutation>
|
|
|
108 void sort_get_permutation_t(t_compare p_compare,t_permutation const & p_permutation) const {
|
|
|
109 ::pfc::sort_get_permutation_t<list_base_const_t<T>,t_compare,t_permutation>(*this,p_compare,get_count(),p_permutation);
|
|
|
110 }
|
|
|
111
|
|
|
112 template<typename t_compare,typename t_permutation>
|
|
|
113 void sort_stable_get_permutation_t(t_compare p_compare,t_permutation const & p_permutation) const {
|
|
|
114 ::pfc::sort_stable_get_permutation_t<list_base_const_t<T>,t_compare,t_permutation>(*this,p_compare,get_count(),p_permutation);
|
|
|
115 }
|
|
|
116
|
|
|
117 template<typename t_callback>
|
|
|
118 void enumerate(t_callback & p_callback) const {
|
|
|
119 for(t_size n = 0, m = get_count(); n < m; ++n ) {
|
|
|
120 p_callback( (*this)[n] );
|
|
|
121 }
|
|
|
122 }
|
|
|
123
|
|
|
124 static bool g_equals(const t_self & item1, const t_self & item2) {
|
|
|
125 const t_size count = item1.get_count();
|
|
|
126 if (count != item2.get_count()) return false;
|
|
|
127 for(t_size walk = 0; walk < count; ++walk) if (item1[walk] != item2[walk]) return false;
|
|
|
128 return true;
|
|
|
129 }
|
|
|
130 bool operator==(const t_self & item2) const {return g_equals(*this,item2);}
|
|
|
131 bool operator!=(const t_self & item2) const {return !g_equals(*this,item2);}
|
|
|
132
|
|
|
133 typedef list_const_iterator< const t_self > iterator;
|
|
|
134 typedef iterator const_iterator;
|
|
|
135
|
|
|
136 iterator begin() const { return iterator(this, 0); }
|
|
|
137 iterator end() const { return iterator(this, get_count()); }
|
|
|
138 protected:
|
|
|
139 list_base_const_t() {}
|
|
|
140 ~list_base_const_t() {}
|
|
|
141
|
|
|
142 list_base_const_t(const t_self &) {}
|
|
|
143 void operator=(const t_self &) {}
|
|
|
144
|
|
|
145 };
|
|
|
146
|
|
|
147
|
|
|
148 template<typename T>
|
|
|
149 class list_single_ref_t : public list_base_const_t<T>
|
|
|
150 {
|
|
|
151 public:
|
|
|
152 list_single_ref_t(const T & p_item,t_size p_count = 1) : m_item(p_item), m_count(p_count) {}
|
|
|
153 t_size get_count() const {return m_count;}
|
|
|
154 void get_item_ex(T& p_out, t_size n) const { PFC_ASSERT(n < m_count); (void)n; p_out = m_item; }
|
|
|
155 private:
|
|
|
156 const T & m_item;
|
|
|
157 t_size m_count;
|
|
|
158 };
|
|
|
159
|
|
|
160 template<typename item_t>
|
|
|
161 inline list_single_ref_t<item_t> list_single(item_t const& i, size_t n = 1) { return list_single_ref_t<item_t>(i, n); }
|
|
|
162
|
|
|
163 template<typename T>
|
|
|
164 class list_partial_ref_t : public list_base_const_t<T>
|
|
|
165 {
|
|
|
166 public:
|
|
|
167 list_partial_ref_t(const list_base_const_t<T> & p_list,t_size p_base,t_size p_count)
|
|
|
168 : m_list(p_list), m_base(p_base), m_count(p_count)
|
|
|
169 {
|
|
|
170 PFC_ASSERT(m_base + m_count <= m_list.get_count());
|
|
|
171 }
|
|
|
172
|
|
|
173 private:
|
|
|
174 const list_base_const_t<T> & m_list;
|
|
|
175 t_size m_base,m_count;
|
|
|
176
|
|
|
177 t_size get_count() const {return m_count;}
|
|
|
178 void get_item_ex(T & p_out,t_size n) const {m_list.get_item_ex(p_out,n+m_base);}
|
|
|
179 };
|
|
|
180
|
|
|
181 template<typename T,typename A>
|
|
|
182 class list_const_array_t : public list_base_const_t<T>
|
|
|
183 {
|
|
|
184 public:
|
|
|
185 inline list_const_array_t(A p_data,t_size p_count) : m_data(p_data), m_count(p_count) {}
|
|
|
186 t_size get_count() const {return m_count;}
|
|
|
187 void get_item_ex(T & p_out,t_size n) const {p_out = m_data[n];}
|
|
|
188 private:
|
|
|
189 A m_data;
|
|
|
190 t_size m_count;
|
|
|
191 };
|
|
|
192 template<typename t_array>
|
|
|
193 class list_const_array_ref_t : public list_base_const_t<typename t_array::t_item> {
|
|
|
194 public:
|
|
|
195 list_const_array_ref_t(const t_array & data) : m_data(data) {}
|
|
|
196 t_size get_count() const {return m_data.get_size();}
|
|
|
197 void get_item_ex(typename t_array::t_item & out, t_size n) const {out = m_data[n];}
|
|
|
198 private:
|
|
|
199 const t_array & m_data;
|
|
|
200 };
|
|
|
201
|
|
|
202 template<typename to,typename from>
|
|
|
203 class list_const_cast_t : public list_base_const_t<to>
|
|
|
204 {
|
|
|
205 public:
|
|
|
206 list_const_cast_t(const list_base_const_t<from> & p_from) : m_from(p_from) {}
|
|
|
207 t_size get_count() const {return m_from.get_count();}
|
|
|
208 void get_item_ex(to & p_out,t_size n) const
|
|
|
209 {
|
|
|
210 from temp;
|
|
|
211 m_from.get_item_ex(temp,n);
|
|
|
212 p_out = temp;
|
|
|
213 }
|
|
|
214 private:
|
|
|
215 const list_base_const_t<from> & m_from;
|
|
|
216 };
|
|
|
217
|
|
|
218 template<typename T,typename A>
|
|
|
219 class ptr_list_const_array_t : public list_base_const_t<T*>
|
|
|
220 {
|
|
|
221 public:
|
|
|
222 inline ptr_list_const_array_t(A p_data,t_size p_count) : m_data(p_data), m_count(p_count) {}
|
|
|
223 t_size get_count() const {return m_count;}
|
|
|
224 void get_item_ex(T* & p_out,t_size n) const {p_out = &m_data[n];}
|
|
|
225 private:
|
|
|
226 A m_data;
|
|
|
227 t_size m_count;
|
|
|
228 };
|
|
|
229 template<typename T>
|
|
|
230 class list_const_ptr_t : public list_base_const_t<T>
|
|
|
231 {
|
|
|
232 public:
|
|
|
233 inline list_const_ptr_t(const T * p_data,t_size p_count) : m_data(p_data), m_count(p_count) {}
|
|
|
234 t_size get_count() const {return m_count;}
|
|
|
235 void get_item_ex(T & p_out,t_size n) const {p_out = m_data[n];}
|
|
|
236 private:
|
|
|
237 const T * m_data;
|
|
|
238 t_size m_count;
|
|
|
239 };
|
|
|
240
|
|
|
241 template<typename T>
|
|
|
242 class NOVTABLE list_base_t : public list_base_const_t<T> {
|
|
|
243 private:
|
|
|
244 typedef list_base_t<T> t_self;
|
|
|
245 typedef const list_base_const_t<T> t_self_const;
|
|
|
246 public:
|
|
|
247 class NOVTABLE sort_callback
|
|
|
248 {
|
|
|
249 public:
|
|
|
250 virtual int compare(const T& p_item1,const T& p_item2) = 0;
|
|
|
251 };
|
|
|
252
|
|
|
253 virtual void filter_mask(const bit_array & mask) = 0;
|
|
|
254 virtual t_size insert_items(const list_base_const_t<T> & items,t_size base) = 0;
|
|
|
255 virtual void reorder_partial(t_size p_base,const t_size * p_data,t_size p_count) = 0;
|
|
|
256 virtual void sort(sort_callback & p_callback) = 0;
|
|
|
257 virtual void sort_stable(sort_callback & p_callback) = 0;
|
|
|
258 virtual void replace_item(t_size p_index,const T& p_item) = 0;
|
|
|
259 virtual void swap_item_with(t_size p_index,T & p_item) = 0;
|
|
|
260 virtual void swap_items(t_size p_index1,t_size p_index2) = 0;
|
|
|
261
|
|
|
262 inline void reorder(const t_size * p_data) {reorder_partial(0,p_data,this->get_count());}
|
|
|
263
|
|
|
264 inline t_size insert_item(const T & item,t_size base) {return insert_items(list_single_ref_t<T>(item),base);}
|
|
|
265 t_size insert_items_repeat(const T & item,t_size num,t_size base) {return insert_items(list_single_ref_t<T>(item,num),base);}
|
|
|
266 inline t_size add_items_repeat(T item,t_size num) {return insert_items_repeat(item,num,SIZE_MAX);}
|
|
|
267 t_size insert_items_fromptr(const T* source,t_size num,t_size base) {return insert_items(list_const_ptr_t<T>(source,num),base);}
|
|
|
268 inline t_size add_items_fromptr(const T* source,t_size num) {return insert_items_fromptr(source,num,SIZE_MAX);}
|
|
|
269
|
|
|
270 inline t_size add_items(const list_base_const_t<T> & items) {return insert_items(items,SIZE_MAX);}
|
|
|
271 inline t_size add_item(const T& item) {return insert_item(item,SIZE_MAX);}
|
|
|
272
|
|
|
273 inline void remove_mask(const bit_array & mask) {filter_mask(bit_array_not(mask));}
|
|
|
274 inline void remove_all() {filter_mask(bit_array_false());}
|
|
|
275 inline void truncate(t_size val) {if (val < this->get_count()) remove_mask(bit_array_range(val,this->get_count()-val,true));}
|
|
|
276
|
|
|
277 inline T replace_item_ex(t_size p_index,const T & p_item) {T ret = p_item;swap_item_with(p_index,ret);return ret;}
|
|
|
278
|
|
|
279 inline T operator[](t_size n) const {return this->get_item(n);}
|
|
|
280
|
|
|
281 template<typename t_compare>
|
|
|
282 class sort_callback_impl_t : public sort_callback
|
|
|
283 {
|
|
|
284 public:
|
|
|
285 sort_callback_impl_t(t_compare p_compare) : m_compare(p_compare) {}
|
|
|
286 int compare(const T& p_item1,const T& p_item2) {return m_compare(p_item1,p_item2);}
|
|
|
287 private:
|
|
|
288 t_compare m_compare;
|
|
|
289 };
|
|
|
290
|
|
|
291 class sort_callback_auto : public sort_callback
|
|
|
292 {
|
|
|
293 public:
|
|
|
294 int compare(const T& p_item1,const T& p_item2) {return ::pfc::compare_t(p_item1,p_item2);}
|
|
|
295 };
|
|
|
296
|
|
|
297 void sort() {sort_callback_auto cb;sort(cb);}
|
|
|
298 template<typename t_compare> void sort_t(t_compare p_compare) {sort_callback_impl_t<t_compare> cb(p_compare);sort(cb);}
|
|
|
299 template<typename t_compare> void sort_stable_t(t_compare p_compare) {sort_callback_impl_t<t_compare> cb(p_compare); sort_stable(cb);}
|
|
|
300
|
|
|
301 template<typename t_compare> void sort_remove_duplicates_t(t_compare p_compare)
|
|
|
302 {
|
|
|
303 sort_t<t_compare>(p_compare);
|
|
|
304 bit_array_bittable array(this->get_count());
|
|
|
305 if (this->template find_duplicates_sorted_t<t_compare>(p_compare,array) > 0)
|
|
|
306 remove_mask(array);
|
|
|
307 }
|
|
|
308
|
|
|
309 template<typename t_compare> void sort_stable_remove_duplicates_t(t_compare p_compare)
|
|
|
310 {
|
|
|
311 sort_stable_t<t_compare>(p_compare);
|
|
|
312 bit_array_bittable array(this->get_count());
|
|
|
313 if (this->template find_duplicates_sorted_t<t_compare>(p_compare,array) > 0)
|
|
|
314 remove_mask(array);
|
|
|
315 }
|
|
|
316
|
|
|
317
|
|
|
318 template<typename t_compare> void remove_duplicates_t(t_compare p_compare)
|
|
|
319 {
|
|
|
320 order_helper order(this->get_count());
|
|
|
321 sort_get_permutation_t<t_compare,order_helper&>(p_compare,order);
|
|
|
322 bit_array_bittable array(this->get_count());
|
|
|
323 if (this->template find_duplicates_sorted_permutation_t<t_compare,order_helper const&>(p_compare,order,array) > 0)
|
|
|
324 remove_mask(array);
|
|
|
325 }
|
|
|
326
|
|
|
327 template<typename t_func>
|
|
|
328 void for_each(t_func p_func) {
|
|
|
329 t_size n,max=this->get_count();
|
|
|
330 for(n=0;n<max;n++) p_func(this->get_item(n));
|
|
|
331 }
|
|
|
332
|
|
|
333 template<typename t_func>
|
|
|
334 void for_each(t_func p_func,const bit_array & p_mask) {
|
|
|
335 t_size n,max=this->get_count();
|
|
|
336 for(n=p_mask.find(true,0,max);n<max;n=p_mask.find(true,n+1,max-n-1)) {
|
|
|
337 p_func(this->get_item(n));
|
|
|
338 }
|
|
|
339 }
|
|
|
340
|
|
|
341 template<typename t_releasefunc>
|
|
|
342 void remove_mask_ex(const bit_array & p_mask,t_releasefunc p_func) {
|
|
|
343 this->template for_each<t_releasefunc>(p_func,p_mask);
|
|
|
344 remove_mask(p_mask);
|
|
|
345 }
|
|
|
346
|
|
|
347 template<typename t_releasefunc>
|
|
|
348 void remove_all_ex(t_releasefunc p_func) {
|
|
|
349 this->template for_each<t_releasefunc>(p_func);
|
|
|
350 remove_all();
|
|
|
351 }
|
|
|
352
|
|
|
353 template<typename t_in> t_self & operator=(t_in const & source) {remove_all(); add_items(source); return *this;}
|
|
|
354 template<typename t_in> t_self & operator+=(t_in const & p_source) {add_item(p_source); return *this;}
|
|
|
355 template<typename t_in> t_self & operator|=(t_in const & p_source) {add_items(p_source); return *this;}
|
|
|
356
|
|
|
357 protected:
|
|
|
358 list_base_t() {}
|
|
|
359 ~list_base_t() {}
|
|
|
360 list_base_t(const t_self&) {}
|
|
|
361 void operator=(const t_self&) {}
|
|
|
362 };
|
|
|
363
|
|
|
364
|
|
|
365 template<typename T,typename t_storage>
|
|
|
366 class list_impl_t : public list_base_t<T>
|
|
|
367 {
|
|
|
368 public:
|
|
|
369 typedef list_base_t<T> t_base;
|
|
|
370 typedef list_impl_t<T, t_storage> t_self;
|
|
|
371 list_impl_t() {}
|
|
|
372 list_impl_t(const t_self & p_source) { add_items(p_source); }
|
|
|
373
|
|
|
374 void copy(const t_self& p_source) { m_buffer = p_source.m_buffer; }
|
|
|
375 void move(t_self& p_source) { m_buffer = std::move(p_source.m_buffer); }
|
|
|
376
|
|
|
377 void prealloc(t_size count) {m_buffer.prealloc(count);}
|
|
|
378
|
|
|
379 void set_count(t_size p_count) {m_buffer.set_size(p_count);}
|
|
|
380 void set_size(t_size p_count) {m_buffer.set_size(p_count);}
|
|
|
381
|
|
|
382 template<typename t_in>
|
|
|
383 t_size _insert_item_t(const t_in & item, t_size idx) {
|
|
|
384 return ::pfc::insert_t(m_buffer, item, idx);
|
|
|
385 }
|
|
|
386 template<typename t_in>
|
|
|
387 t_size insert_item(const t_in & item, t_size idx) {
|
|
|
388 return _insert_item_t(item, idx);
|
|
|
389 }
|
|
|
390
|
|
|
391 t_size insert_item(const T& item,t_size idx) {
|
|
|
392 return _insert_item_t(item, idx);
|
|
|
393 }
|
|
|
394
|
|
|
395 T remove_by_idx(t_size idx)
|
|
|
396 {
|
|
|
397 T ret = std::move(m_buffer[idx]);
|
|
|
398 t_size n;
|
|
|
399 t_size max = m_buffer.get_size();
|
|
|
400 for(n=idx+1;n<max;n++) {
|
|
|
401 m_buffer[n - 1] = std::move(m_buffer[n]);
|
|
|
402 }
|
|
|
403 m_buffer.set_size(max-1);
|
|
|
404 return ret;
|
|
|
405 }
|
|
|
406
|
|
|
407
|
|
|
408 inline void get_item_ex(T& p_out,t_size n) const
|
|
|
409 {
|
|
|
410 PFC_ASSERT(n>=0);
|
|
|
411 PFC_ASSERT(n<get_size());
|
|
|
412 p_out = m_buffer[n];
|
|
|
413 }
|
|
|
414
|
|
|
415 inline const T& get_item_ref(t_size n) const
|
|
|
416 {
|
|
|
417 PFC_ASSERT(n>=0);
|
|
|
418 PFC_ASSERT(n<get_size());
|
|
|
419 return m_buffer[n];
|
|
|
420 }
|
|
|
421
|
|
|
422 inline T get_item(t_size n) const
|
|
|
423 {
|
|
|
424 PFC_ASSERT(n >= 0);
|
|
|
425 PFC_ASSERT(n < get_size() );
|
|
|
426 return m_buffer[n];
|
|
|
427 };
|
|
|
428
|
|
|
429 inline t_size get_count() const {return m_buffer.get_size();}
|
|
|
430 inline t_size get_size() const {return m_buffer.get_size();}
|
|
|
431 inline size_t size() const { return m_buffer.get_size(); }
|
|
|
432
|
|
|
433 inline const T & operator[](t_size n) const
|
|
|
434 {
|
|
|
435 PFC_ASSERT(n>=0);
|
|
|
436 PFC_ASSERT(n<get_size());
|
|
|
437 return m_buffer[n];
|
|
|
438 }
|
|
|
439
|
|
|
440 inline const T* get_ptr() const {return m_buffer.get_ptr();}
|
|
|
441 inline T* get_ptr() {return m_buffer.get_ptr();}
|
|
|
442
|
|
|
443 inline T& operator[](t_size n) {return m_buffer[n];}
|
|
|
444
|
|
|
445 inline void remove_from_idx(t_size idx,t_size num)
|
|
|
446 {
|
|
|
447 remove_mask(bit_array_range(idx,num));
|
|
|
448 }
|
|
|
449
|
|
|
450 t_size _insert_items_v(const list_base_const_t<T> & source,t_size base) { //workaround for inefficient operator[] on virtual-interface-accessed lists
|
|
|
451 t_size count = get_size();
|
|
|
452 if (base>count) base = count;
|
|
|
453 t_size num = source.get_count();
|
|
|
454 m_buffer.set_size(count+num);
|
|
|
455 if (count > base) {
|
|
|
456 for(t_size n=count-1;(int)n>=(int)base;n--) {
|
|
|
457 ::pfc::move_t(m_buffer[n+num],m_buffer[n]);
|
|
|
458 }
|
|
|
459 }
|
|
|
460
|
|
|
461 for(t_size n=0;n<num;n++) {
|
|
|
462 source.get_item_ex(m_buffer[n+base],n);
|
|
|
463 }
|
|
|
464 return base;
|
|
|
465 }
|
|
|
466 // use _insert_items_v where it's more efficient
|
|
|
467 t_size insert_items(const list_base_const_t<T> & source,t_size base) {return _insert_items_v(source, base);}
|
|
|
468 t_size insert_items(const list_base_t<T> & source,t_size base) {return _insert_items_v(source, base);}
|
|
|
469
|
|
|
470 template<typename t_in>
|
|
|
471 t_size insert_items(const t_in & source,t_size base) {
|
|
|
472 t_size count = get_size();
|
|
|
473 if (base>count) base = count;
|
|
|
474 t_size num = array_size_t(source);
|
|
|
475 m_buffer.set_size(count+num);
|
|
|
476 if (count > base) {
|
|
|
477 for(t_size n=count-1;(int)n>=(int)base;n--) {
|
|
|
478 ::pfc::move_t(m_buffer[n+num],m_buffer[n]);
|
|
|
479 }
|
|
|
480 }
|
|
|
481
|
|
|
482 for(t_size n=0;n<num;n++) {
|
|
|
483 m_buffer[n+base] = source[n];
|
|
|
484 }
|
|
|
485 return base;
|
|
|
486 }
|
|
|
487
|
|
|
488 template<typename t_in>
|
|
|
489 void add_items(const t_in & in) {insert_items(in, SIZE_MAX);}
|
|
|
490
|
|
|
491 void get_items_mask(list_impl_t<T,t_storage> & out,const bit_array & mask)
|
|
|
492 {
|
|
|
493 mask.walk( get_size(), [&] (size_t n) {
|
|
|
494 out.add_item(m_buffer[n]);
|
|
|
495 } );
|
|
|
496 }
|
|
|
497
|
|
|
498 void filter_mask(const bit_array & mask)
|
|
|
499 {
|
|
|
500 t_size n,count = get_size(), total = 0;
|
|
|
501
|
|
|
502 n = total = mask.find(false,0,count);
|
|
|
503
|
|
|
504 if (n<count) {
|
|
|
505 for(n=mask.find(true,n+1,count-n-1);n<count;n=mask.find(true,n+1,count-n-1))
|
|
|
506 ::pfc::move_t(m_buffer[total++],m_buffer[n]);
|
|
|
507
|
|
|
508 m_buffer.set_size(total);
|
|
|
509 }
|
|
|
510 }
|
|
|
511
|
|
|
512 void replace_item(t_size idx,const T& item)
|
|
|
513 {
|
|
|
514 PFC_ASSERT(idx>=0);
|
|
|
515 PFC_ASSERT(idx<get_size());
|
|
|
516 m_buffer[idx] = item;
|
|
|
517 }
|
|
|
518
|
|
|
519 void sort()
|
|
|
520 {
|
|
|
521 ::pfc::sort_callback_impl_auto_wrap_t<t_storage> wrapper(m_buffer);
|
|
|
522 ::pfc::sort(wrapper,get_size());
|
|
|
523 }
|
|
|
524
|
|
|
525 template<typename t_compare>
|
|
|
526 void sort_t(t_compare p_compare)
|
|
|
527 {
|
|
|
528 ::pfc::sort_callback_impl_simple_wrap_t<t_storage,t_compare> wrapper(m_buffer,p_compare);
|
|
|
529 ::pfc::sort(wrapper,get_size());
|
|
|
530 }
|
|
|
531
|
|
|
532 template<typename t_compare>
|
|
|
533 void sort_stable_t(t_compare p_compare)
|
|
|
534 {
|
|
|
535 ::pfc::sort_callback_impl_simple_wrap_t<t_storage,t_compare> wrapper(m_buffer,p_compare);
|
|
|
536 ::pfc::sort_stable(wrapper,get_size());
|
|
|
537 }
|
|
|
538 inline void reorder_partial(t_size p_base,const t_size * p_order,t_size p_count)
|
|
|
539 {
|
|
|
540 PFC_ASSERT(p_base+p_count<=get_size());
|
|
|
541 ::pfc::reorder_partial_t(m_buffer,p_base,p_order,p_count);
|
|
|
542 }
|
|
|
543
|
|
|
544 template<typename t_compare>
|
|
|
545 t_size find_duplicates_sorted_t(t_compare p_compare,bit_array_var & p_out) const
|
|
|
546 {
|
|
|
547 return ::pfc::find_duplicates_sorted_t<list_impl_t<T,t_storage> const &,t_compare>(*this,get_size(),p_compare,p_out);
|
|
|
548 }
|
|
|
549
|
|
|
550 template<typename t_compare,typename t_permutation>
|
|
|
551 t_size find_duplicates_sorted_permutation_t(t_compare p_compare,t_permutation p_permutation,bit_array_var & p_out)
|
|
|
552 {
|
|
|
553 return ::pfc::find_duplicates_sorted_permutation_t<list_impl_t<T,t_storage> const &,t_compare,t_permutation>(*this,get_size(),p_compare,p_permutation,p_out);
|
|
|
554 }
|
|
|
555
|
|
|
556
|
|
|
557 void move_from(t_self & other) {
|
|
|
558 remove_all();
|
|
|
559 m_buffer = std::move(other.m_buffer);
|
|
|
560 }
|
|
|
561
|
|
|
562 T* begin() { return m_buffer.get_ptr(); }
|
|
|
563 T* end() { return m_buffer.get_ptr() + get_size(); }
|
|
|
564 const T* begin() const { return m_buffer.get_ptr(); }
|
|
|
565 const T* end() const { return m_buffer.get_ptr() + get_size(); }
|
|
|
566
|
|
|
567 private:
|
|
|
568 class sort_callback_wrapper
|
|
|
569 {
|
|
|
570 public:
|
|
|
571 explicit inline sort_callback_wrapper(typename t_base::sort_callback & p_callback) : m_callback(p_callback) {}
|
|
|
572 inline int operator()(const T& item1,const T& item2) const {return m_callback.compare(item1,item2);}
|
|
|
573 private:
|
|
|
574 typename t_base::sort_callback & m_callback;
|
|
|
575 };
|
|
|
576 public:
|
|
|
577 void sort(typename t_base::sort_callback & p_callback)
|
|
|
578 {
|
|
|
579 sort_t(sort_callback_wrapper(p_callback));
|
|
|
580 }
|
|
|
581
|
|
|
582 void sort_stable(typename t_base::sort_callback & p_callback)
|
|
|
583 {
|
|
|
584 sort_stable_t(sort_callback_wrapper(p_callback));
|
|
|
585 }
|
|
|
586
|
|
|
587 void remove_mask(const bit_array & mask) {filter_mask(bit_array_not(mask));}
|
|
|
588
|
|
|
589 void remove_mask(const bool * mask) {remove_mask(bit_array_table(mask,get_size()));}
|
|
|
590 void filter_mask(const bool * mask) {filter_mask(bit_array_table(mask,get_size()));}
|
|
|
591
|
|
|
592 size_t add_item(const T& item) {
|
|
|
593 return pfc::append_t(m_buffer, item);
|
|
|
594 }
|
|
|
595
|
|
|
596 size_t add_item(T&& item) {
|
|
|
597 return pfc::append_t(m_buffer, std::move(item));
|
|
|
598 }
|
|
|
599
|
|
|
600 template<typename t_in> t_size add_item(const t_in & item) {
|
|
|
601 return pfc::append_t(m_buffer, item);
|
|
|
602 }
|
|
|
603
|
|
|
604 void remove_all() {remove_mask(bit_array_true());}
|
|
|
605
|
|
|
606 void remove_item(const T& item)
|
|
|
607 {
|
|
|
608 t_size n,max = get_size();
|
|
|
609 bit_array_bittable mask(max);
|
|
|
610 for(n=0;n<max;n++)
|
|
|
611 mask.set(n,get_item(n)==item);
|
|
|
612 remove_mask(mask);
|
|
|
613 }
|
|
|
614
|
|
|
615 void swap_item_with(t_size p_index,T & p_item)
|
|
|
616 {
|
|
|
617 PFC_ASSERT(p_index < get_size());
|
|
|
618 swap_t(m_buffer[p_index],p_item);
|
|
|
619 }
|
|
|
620
|
|
|
621 void swap_items(t_size p_index1,t_size p_index2)
|
|
|
622 {
|
|
|
623 PFC_ASSERT(p_index1 < get_size());
|
|
|
624 PFC_ASSERT(p_index2 < get_size());
|
|
|
625 swap_t(m_buffer[p_index1],m_buffer[p_index2]);
|
|
|
626 }
|
|
|
627
|
|
|
628 inline static void g_swap(list_impl_t<T,t_storage> & p_item1,list_impl_t<T,t_storage> & p_item2)
|
|
|
629 {
|
|
|
630 swap_t(p_item1.m_buffer,p_item2.m_buffer);
|
|
|
631 }
|
|
|
632
|
|
|
633 template<typename t_search>
|
|
|
634 t_size find_item(const t_search & p_item) const//returns index of first occurance, infinite if not found
|
|
|
635 {
|
|
|
636 t_size n,max = get_size();
|
|
|
637 for(n=0;n<max;n++)
|
|
|
638 if (m_buffer[n]==p_item) return n;
|
|
|
639 return SIZE_MAX;
|
|
|
640 }
|
|
|
641
|
|
|
642 template<typename t_search>
|
|
|
643 inline bool have_item(const t_search & p_item) const {return this->template find_item<t_search>(p_item)!=SIZE_MAX;}
|
|
|
644
|
|
|
645 template<typename t_in> t_self & operator=(t_in const & source) {remove_all(); add_items(source); return *this;}
|
|
|
646 template<typename t_in> t_self & operator+=(t_in const & p_source) {add_item(p_source); return *this;}
|
|
|
647 template<typename t_in> t_self & operator|=(t_in const & p_source) {add_items(p_source); return *this;}
|
|
|
648 protected:
|
|
|
649 t_storage m_buffer;
|
|
|
650 };
|
|
|
651
|
|
|
652 template<typename t_item, template<typename> class t_alloc = alloc_fast >
|
|
|
653 class list_t : public list_impl_t<t_item,array_t<t_item,t_alloc> > {
|
|
|
654 public:
|
|
|
655 typedef list_t<t_item, t_alloc> t_self;
|
|
|
656 template<typename t_in> const t_self & operator=(t_in const & source) {this->remove_all(); this->add_items(source); return *this;}
|
|
|
657 template<typename t_in> const t_self & operator+=(t_in const & p_source) {this->add_item(p_source); return *this;}
|
|
|
658 template<typename t_in> const t_self & operator|=(t_in const & p_source) {this->add_items(p_source); return *this;}
|
|
|
659
|
|
|
660 const t_self& operator=(t_self const& other) { this->copy(other); return *this; }
|
|
|
661 const t_self& operator=(t_self&& other) { this->move(other); return *this; }
|
|
|
662
|
|
|
663 list_t() {}
|
|
|
664 list_t(t_self const& other) { this->copy(other); }
|
|
|
665 list_t(t_self&& other) { this->move(other); }
|
|
|
666 };
|
|
|
667
|
|
|
668 template<typename t_item, t_size p_fixed_count, template<typename> class t_alloc = alloc_fast >
|
|
|
669 class list_hybrid_t : public list_impl_t<t_item,array_hybrid_t<t_item,p_fixed_count,t_alloc> > {
|
|
|
670 public:
|
|
|
671 typedef list_hybrid_t<t_item, p_fixed_count, t_alloc> t_self;
|
|
|
672 template<typename t_in> t_self & operator=(t_in const & source) {this->remove_all(); this->add_items(source); return *this;}
|
|
|
673 template<typename t_in> t_self & operator+=(t_in const & p_source) {this->add_item(p_source); return *this;}
|
|
|
674 template<typename t_in> t_self & operator|=(t_in const & p_source) {this->add_items(p_source); return *this;}
|
|
|
675 };
|
|
|
676
|
|
|
677 template<typename T>
|
|
|
678 class ptr_list_const_cast_t : public list_base_const_t<const T *>
|
|
|
679 {
|
|
|
680 public:
|
|
|
681 inline ptr_list_const_cast_t(const list_base_const_t<T*> & p_param) : m_param(p_param) {}
|
|
|
682 t_size get_count() const {return m_param.get_count();}
|
|
|
683 void get_item_ex(const T * & p_out,t_size n) const {T* temp; m_param.get_item_ex(temp,n); p_out = temp;}
|
|
|
684 private:
|
|
|
685 const list_base_const_t<T*> & m_param;
|
|
|
686
|
|
|
687 };
|
|
|
688
|
|
|
689
|
|
|
690 template<typename T,typename P>
|
|
|
691 class list_const_permutation_t : public list_base_const_t<T>
|
|
|
692 {
|
|
|
693 public:
|
|
|
694 inline list_const_permutation_t(const list_base_const_t<T> & p_list,P p_permutation) : m_list(p_list), m_permutation(p_permutation) {}
|
|
|
695 t_size get_count() const {return m_list.get_count();}
|
|
|
696 void get_item_ex(T & p_out,t_size n) const {m_list.get_item_ex(p_out,m_permutation[n]);}
|
|
|
697 private:
|
|
|
698 P m_permutation;
|
|
|
699 const list_base_const_t<T> & m_list;
|
|
|
700 };
|
|
|
701
|
|
|
702
|
|
|
703 template<class T>
|
|
|
704 class list_permutation_t : public list_base_const_t<T>
|
|
|
705 {
|
|
|
706 public:
|
|
|
707 t_size get_count() const {return m_count;}
|
|
|
708 void get_item_ex(T & p_out,t_size n) const {m_base.get_item_ex(p_out,m_order[n]);}
|
|
|
709 list_permutation_t(const list_base_const_t<T> & p_base,const t_size * p_order,t_size p_count)
|
|
|
710 : m_base(p_base), m_order(p_order), m_count(p_count)
|
|
|
711 {
|
|
|
712 PFC_ASSERT(m_base.get_count() >= m_count);
|
|
|
713 }
|
|
|
714 private:
|
|
|
715 const list_base_const_t<T> & m_base;
|
|
|
716 const t_size * m_order;
|
|
|
717 t_size m_count;
|
|
|
718 };
|
|
|
719
|
|
|
720 template<typename item, template<typename> class alloc> class traits_t<list_t<item, alloc> > : public combine_traits<traits_t<alloc<item> >, traits_vtable> {};
|
|
|
721
|
|
|
722 }
|
