Mercurial > foo_out_sdl

comparison foosdk/sdk/pfc/bit_array.cpp @ 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 #include "pfc-lite.h"
2 #include "bit_array.h"
3 #include "bit_array_impl.h"
4 #include "bit_array_impl_part2.h"
5 #include "sort.h"
6
7 namespace pfc {
8 void bit_array::for_each(bool value, size_t base, size_t max, std::function<void(size_t)> f) const {
9 for( size_t idx = find_first(value, base, max); idx < max; idx = find_next(value, idx, max) ) {
10 f(idx);
11 }
12 }
13 t_size bit_array::find(bool val, t_size start, t_ssize count) const
14 {
15 t_ssize d, todo, ptr = start;
16 if (count == 0) return start;
17 else if (count<0) { d = -1; todo = -count; }
18 else { d = 1; todo = count; }
19 while (todo>0 && get(ptr) != val) { ptr += d;todo--; }
20 return ptr;
21 }
22
23 t_size bit_array::calc_count(bool val, t_size start, t_size count, t_size count_max) const
24 {
25 t_size found = 0;
26 t_size max = start + count;
27 t_size ptr;
28 for (ptr = find(val, start, count);found<count_max && ptr<max;ptr = find(val, ptr + 1, max - ptr - 1)) found++;
29 return found;
30 }
31 t_size bit_array::find_first(bool val, t_size start, t_size max) const {
32 return find(val, start, max - start);
33 }
34 t_size bit_array::find_next(bool val, t_size previous, t_size max) const {
35 return find(val, previous + 1, max - (previous + 1));
36 }
37 void bit_array::walk(size_t to, std::function< void ( size_t ) > f, bool val ) const {
38 for ( size_t w = find_first(val, 0, to ); w < to; w = find_next(val, w, to) ) {
39 f(w);
40 }
41 }
42 void bit_array::walkBack(size_t from, std::function<void (size_t) > f, bool val) const {
43 t_ssize walk = from;
44 if ( walk == 0 ) return;
45 for( ;; ) {
46 walk = find(val, walk-1, - walk );
47 if ( walk < 0 ) return;
48 f ( walk );
49 }
50 }
51
52 bit_array_var_impl::bit_array_var_impl( const bit_array & source, size_t sourceCount) {
53 for(size_t w = source.find_first( true, 0, sourceCount); w < sourceCount; w = source.find_next( true, w, sourceCount ) ) {
54 set(w, true);
55 }
56 }
57
58 bool bit_array_var_impl::get(t_size n) const {
59 return m_data.have_item(n);
60 }
61 t_size bit_array_var_impl::find(bool val,t_size start,t_ssize count) const {
62 if (!val) {
63 return bit_array::find(false, start, count); //optimizeme.
64 } else if (count > 0) {
65 const t_size * v = m_data.find_nearest_item<true, true>(start);
66 if (v == NULL || *v > start+count) return start + count;
67 return *v;
68 } else if (count < 0) {
69 const t_size * v = m_data.find_nearest_item<true, false>(start);
70 if (v == NULL || *v < start+count) return start + count;
71 return *v;
72 } else return start;
73 }
74
75 void bit_array_var_impl::set(t_size n,bool val) {
76 if (val) m_data += n;
77 else m_data -= n;
78 }
79
80
81 bit_array_flatIndexList::bit_array_flatIndexList() {
82 m_content.prealloc( 1024 );
83 }
84
85 void bit_array_flatIndexList::add( size_t n ) {
86 m_content.append_single_val( n );
87 }
88
89 bool bit_array_flatIndexList::get(t_size n) const {
90 size_t dummy;
91 return _find( n, dummy );
92 }
93 t_size bit_array_flatIndexList::find(bool val,t_size start,t_ssize count) const {
94 if (val == false) {
95 // unoptimized but not really used
96 return bit_array::find(val, start, count);
97 }
98
99 if (count==0) return start;
100 else if (count<0) {
101 size_t idx;
102 if (!_findNearestDown( start, idx ) || (t_ssize)m_content[idx] < (t_ssize)start+count) return start + count;
103 return m_content[idx];
104 } else { // count > 0
105 size_t idx;
106 if (!_findNearestUp( start, idx ) || m_content[idx] > start+count) return start + count;
107 return m_content[idx];
108 }
109 }
110
111 bool bit_array_flatIndexList::_findNearestUp( size_t val, size_t & outIdx ) const {
112 size_t idx;
113 if (_find( val, idx )) { outIdx = idx; return true; }
114 // we have a valid outIdx at where the bsearch gave up
115 PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
116 PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
117 if (idx == m_content.get_size()) return false;
118 outIdx = idx;
119 return true;
120 }
121 bool bit_array_flatIndexList::_findNearestDown( size_t val, size_t & outIdx ) const {
122 size_t idx;
123 if (_find( val, idx )) { outIdx = idx; return true; }
124 // we have a valid outIdx at where the bsearch gave up
125 PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
126 PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
127 if (idx == 0) return false;
128 outIdx = idx - 1;
129 return true;
130 }
131
132 void bit_array_flatIndexList::presort() {
133 pfc::sort_t( m_content, pfc::compare_t< size_t, size_t >, m_content.get_size( ) );
134 }
135
136
137 bit_array_bittable::bit_array_bittable(const pfc::bit_array & in, size_t inSize) : m_count() {
138 resize(inSize);
139 for (size_t w = in.find_first(true, 0, inSize); w < inSize; w = in.find_next(true, w, inSize)) {
140 set(w, true);
141 }
142 }
143
144 void bit_array_bittable::resize(t_size p_count)
145 {
146 t_size old_bytes = g_estimate_size(m_count);
147 m_count = p_count;
148 t_size bytes = g_estimate_size(m_count);
149 m_data.set_size(bytes);
150 if (bytes > old_bytes) pfc::memset_null_t(m_data.get_ptr() + old_bytes, bytes - old_bytes);
151 }
152
153 void bit_array_bittable::set(t_size n, bool val)
154 {
155 if (n<m_count)
156 {
157 g_set(m_data, n, val);
158 }
159 }
160
161 bool bit_array_bittable::get(t_size n) const
162 {
163 bool rv = false;
164 if (n<m_count) {
165 rv = g_get(m_data, n);
166 }
167 return rv;
168 }
169
170 t_size bit_array_one::find(bool p_val, t_size start, t_ssize count) const
171 {
172 if (count == 0) return start;
173 else if (p_val)
174 {
175 if (count>0)
176 return (val >= start && (t_ssize)val < (t_ssize)start + count) ? val : start + count;
177 else
178 return (val <= start && (t_ssize)val > (t_ssize)start + count) ? val : start + count;
179 }
180 else
181 {
182 if (start == val) return count>0 ? start + 1 : start - 1;
183 else return start;
184 }
185 }
186 } // namespace pfc