foobar2000 SDK  2015-08-03
bit_array_impl.h
Go to the documentation of this file.
1 #ifndef _PFC_BIT_ARRAY_IMPL_H_
2 #define _PFC_BIT_ARRAY_IMPL_H_
3 
4 template<class T>
6 {
7  const T * data;
9  bool after;
10 public:
11  inline bit_array_table_t(const T * p_data,t_size p_count,bool p_after = false)
12  : data(p_data), count(p_count), after(p_after)
13  {
14  }
15 
16  bool get(t_size n) const
17  {
18  if (n<count) return !!data[n];
19  else return after;
20  }
21 };
22 
23 template<class T>
25 {
26  T * data;
28  bool after;
29 public:
30  inline bit_array_var_table_t(T * p_data,t_size p_count,bool p_after = false)
31  : data(p_data), count(p_count), after(p_after)
32  {
33  }
34 
35  bool get(t_size n) const {
36  if (n<count) return !!data[n];
37  else return after;
38  }
39 
40  void set(t_size n,bool val) {
41  if (n<count) data[n] = !!val;
42  }
43 };
44 
45 
48 
49 class bit_array_range : public bit_array
50 {
51  t_size begin,end;
52  bool state;
53 public:
54  bit_array_range(t_size first,t_size count,bool p_state = true) : begin(first), end(first+count), state(p_state) {}
55 
56  bool get(t_size n) const
57  {
58  bool rv = n>=begin && n<end;
59  if (!state) rv = !rv;
60  return rv;
61  }
62 };
63 
66 class bit_array_and : public bit_array
67 {
68  const bit_array & a1, & a2;
69 public:
70  bit_array_and(const bit_array & p_a1, const bit_array & p_a2) : a1(p_a1), a2(p_a2) {}
71  bool get(t_size n) const {return a1.get(n) && a2.get(n);}
72 };
73 
76 class bit_array_or : public bit_array
77 {
78  const bit_array & a1, & a2;
79 public:
80  bit_array_or(const bit_array & p_a1, const bit_array & p_a2) : a1(p_a1), a2(p_a2) {}
81  bool get(t_size n) const {return a1.get(n) || a2.get(n);}
82 };
83 
86 class bit_array_xor : public bit_array
87 {
88  const bit_array & a1, & a2;
89 public:
90  bit_array_xor(const bit_array & p_a1, const bit_array & p_a2) : a1(p_a1), a2(p_a2) {}
91  bool get(t_size n) const
92  {
93  bool v1 = a1.get(n), v2 = a2.get(n);
94  return (v1 && !v2) || (!v1 && v2);
95  }
96 };
97 
100 class bit_array_not : public bit_array
101 {
102  const bit_array & a1;
103 public:
104  bit_array_not(const bit_array & p_a1) : a1(p_a1) {}
105  bool get(t_size n) const {return !a1.get(n);}
106  t_size find(bool val,t_size start,t_ssize count) const
107  {return a1.find(!val,start,count);}
108 
109 };
110 
111 class bit_array_true : public bit_array
112 {
113 public:
114  bool get(t_size n) const {return true;}
115  t_size find(bool val,t_size start,t_ssize count) const
116  {return val ? start : start+count;}
117 };
118 
120 {
121 public:
122  bool get(t_size n) const {return false;}
123  t_size find(bool val,t_size start,t_ssize count) const
124  {return val ? start+count : start;}
125 };
126 
127 class bit_array_val : public bit_array
128 {
129  bool val;
130 public:
131  bit_array_val(bool v) : val(v) {}
132  bool get(t_size n) const {return val;}
133  t_size find(bool p_val,t_size start,t_ssize count) const
134  {return val==p_val ? start : start+count;}
135 };
136 
137 class bit_array_one : public bit_array
138 {
140 public:
141  bit_array_one(t_size p_val) : val(p_val) {}
142  virtual bool get(t_size n) const {return n==val;}
143 
144  virtual t_size find(bool p_val,t_size start,t_ssize count) const
145  {
146  if (count==0) return start;
147  else if (p_val)
148  {
149  if (count>0)
150  return (val>=start && val<start+count) ? val : start+count;
151  else
152  return (val<=start && val>start+count) ? val : start+count;
153  }
154  else
155  {
156  if (start == val) return count>0 ? start+1 : start-1;
157  else return start;
158  }
159  }
160 };
161 
165 {
168 public:
169  //helpers
170  template<typename t_array>
171  inline static bool g_get(const t_array & p_array,t_size idx)
172  {
173  return !! (p_array[idx>>3] & (1<<(idx&7)));
174  }
175 
176  template<typename t_array>
177  inline static void g_set(t_array & p_array,t_size idx,bool val)
178  {
179  unsigned char & dst = p_array[idx>>3];
180  unsigned char mask = 1<<(idx&7);
181  dst = val ? dst|mask : dst&~mask;
182  }
183 
184  inline static t_size g_estimate_size(t_size p_count) {return (p_count+7)>>3;}
185 
186  void resize(t_size p_count)
187  {
188  t_size old_bytes = g_estimate_size(m_count);
189  m_count = p_count;
190  t_size bytes = g_estimate_size(m_count);
191  m_data.set_size(bytes);
192  if (bytes > old_bytes) pfc::memset_null_t(m_data.get_ptr()+old_bytes,bytes-old_bytes);
193  }
194 
195  bit_array_bittable(t_size p_count) : m_count(0) {resize(p_count);}
196  bit_array_bittable(const pfc::bit_array & in, size_t inSize) : m_count() {
197  resize(inSize);
198  for(size_t w = in.find_first(true, 0, inSize); w < inSize; w = in.find_next(true, w, inSize) ) {
199  set( w, true );
200  }
201  }
202  bit_array_bittable() : m_count() {}
203 
204  void set(t_size n,bool val)
205  {
206  if (n<m_count)
207  {
208  g_set(m_data,n,val);
209  }
210  }
211 
212  bool get(t_size n) const
213  {
214  bool rv = false;
215  if (n<m_count) {
216  rv = g_get(m_data,n);
217  }
218  return rv;
219  }
220 };
221 
222 
226 public:
227  bit_array_order_changed(const t_size * p_order) : m_order(p_order) {}
228  bool get(t_size n) const
229  {
230  return m_order[n] != n;
231  }
232 
233 private:
234  const t_size * m_order;
235 };
236 
237 #define for_each_bit_array(var,mask,val,start,count) for(var = mask.find(val,start,count);var<start+count;var=mask.find(val,var+1,count-(var+1-start)))
238 
239 
240 #endif //_PFC_BIT_ARRAY_IMPL_H_
t_size find(bool p_val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
void resize(t_size p_count)
const bit_array & a2
const t_item * get_ptr() const
Definition: array.h:213
t_size find_next(bool val, t_size previous, t_size max) const
Definition: bit_array.h:32
bit_array_var_table_t(T *p_data, t_size p_count, bool p_after=false)
t_size find_first(bool val, t_size start, t_size max) const
Definition: bit_array.h:31
static bool g_get(const t_array &p_array, t_size idx)
virtual t_size find(bool val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
Definition: bit_array.h:11
Generic variable bit_array implementation. Needs to be initialized with requested array size before ...
Bit array interface class, constant version (you can only retrieve values). Range of valid indexes d...
Definition: bit_array.h:6
bit_array_not(const bit_array &p_a1)
bit_array_table_t< bool > bit_array_table
bit_array_var_table_t< bool > bit_array_var_table
bit_array_order_changed(const t_size *p_order)
bit_array_one(t_size p_val)
bit_array_or(const bit_array &p_a1, const bit_array &p_a2)
Negation of another array. Valid index range is the same as valid index range of the parameter array...
bit_array_and(const bit_array &p_a1, const bit_array &p_a2)
static void g_set(t_array &p_array, t_size idx, bool val)
virtual bool get(t_size n) const =0
Combines two arrays using the AND logical operator. Valid index range is an intersection of valid in...
t_size find(bool val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
t_size find(bool val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
Combines two arrays using the XOR logical operator. Valid index range is an intersection of valid in...
const bit_array & a2
size_t t_size
Definition: int_types.h:48
const bit_array & a1
void set_size(t_size p_size)
Definition: array.h:104
t_size find(bool val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
void memset_null_t(T *p_buffer, t_size p_count)
Definition: primitives.h:638
bit_array_bittable(t_size p_count)
Bit array interface class, variable version (you can both set and retrieve values). As with the constant version, valid index range depends on the context.
Definition: bit_array.h:40
virtual t_size find(bool p_val, t_size start, t_ssize count) const
Returns the first occurance of val between start and start+count (excluding start+count), or start+count if not found; count may be negative to search back rather than forward. Can be overridden by bit_array implementations for improved speed in specific cases.
bit_array_xor(const bit_array &p_a1, const bit_array &p_a2)
pfc::sized_int_t< sizeof(size_t) >::t_signed t_ssize
Definition: int_types.h:49
Bit array that takes a permutation and signals indexes reordered by the permutation. Valid index range same as length of the permutation.
bit_array_bittable(const pfc::bit_array &in, size_t inSize)
bit_array_range(t_size first, t_size count, bool p_state=true)
bit_array_table_t(const T *p_data, t_size p_count, bool p_after=false)
bit_array_val(bool v)
pfc::array_t< t_uint8 > m_data
const bit_array & a2
static t_size g_estimate_size(t_size p_count)
Combines two arrays using the OR logical operator. Valid index range is an intersection of valid ind...