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