Mercurial > foo_out_sdl

comparison foosdk/sdk/pfc/list.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 #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 }