foobar2000 SDK  2015-08-03
bit_array.cpp
Go to the documentation of this file.
1 #include "pfc.h"
2 
3 namespace pfc {
4  bit_array_var_impl::bit_array_var_impl( const bit_array & source, size_t sourceCount) {
5  for(size_t w = source.find_first( true, 0, sourceCount); w < sourceCount; w = source.find_next( true, w, sourceCount ) ) {
6  set(w, true);
7  }
8  }
9 
11  return m_data.have_item(n);
12  }
13  t_size bit_array_var_impl::find(bool val,t_size start,t_ssize count) const {
14  if (!val) {
15  return bit_array::find(false, start, count); //optimizeme.
16  } else if (count > 0) {
17  const t_size * v = m_data.find_nearest_item<true, true>(start);
18  if (v == NULL || *v > start+count) return start + count;
19  return *v;
20  } else if (count < 0) {
21  const t_size * v = m_data.find_nearest_item<true, false>(start);
22  if (v == NULL || *v < start+count) return start + count;
23  return *v;
24  } else return start;
25  }
26 
27  void bit_array_var_impl::set(t_size n,bool val) {
28  if (val) m_data += n;
29  else m_data -= n;
30  }
31 
32 
34  m_content.prealloc( 1024 );
35  }
36 
37  void bit_array_flatIndexList::add( size_t n ) {
38  m_content.append_single_val( n );
39  }
40 
42  size_t dummy;
43  return _find( n, dummy );
44  }
45  t_size bit_array_flatIndexList::find(bool val,t_size start,t_ssize count) const {
46  if (val == false) {
47  // unoptimized but not really used
48  return bit_array::find(val, start, count);
49  }
50 
51  if (count==0) return start;
52  else if (count<0) {
53  size_t idx;
54  if (!_findNearestDown( start, idx ) || m_content[idx] < start+count) return start + count;
55  return m_content[idx];
56  } else { // count > 0
57  size_t idx;
58  if (!_findNearestUp( start, idx ) || m_content[idx] > start+count) return start + count;
59  return m_content[idx];
60  }
61  }
62 
63  bool bit_array_flatIndexList::_findNearestUp( size_t val, size_t & outIdx ) const {
64  size_t idx;
65  if (_find( val, idx )) { outIdx = idx; return true; }
66  // we have a valid outIdx at where the bsearch gave up
67  PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
68  PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
69  if (idx == m_content.get_size()) return false;
70  outIdx = idx;
71  return true;
72  }
73  bool bit_array_flatIndexList::_findNearestDown( size_t val, size_t & outIdx ) const {
74  size_t idx;
75  if (_find( val, idx )) { outIdx = idx; return true; }
76  // we have a valid outIdx at where the bsearch gave up
77  PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
78  PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
79  if (idx == 0) return false;
80  outIdx = idx - 1;
81  return true;
82  }
83 
85  pfc::sort_t( m_content, pfc::compare_t< size_t, size_t >, m_content.get_size( ) );
86  }
87 
88 }
void set(t_size n, bool val)
Definition: bit_array.cpp:27
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.cpp:13
bool _findNearestUp(size_t val, size_t &outIdx) const
Definition: bit_array.cpp:63
t_size find_next(bool val, t_size previous, t_size max) const
Definition: bit_array.h:32
const t_storage * find_nearest_item(const t_search &p_search) const
Definition: avltree.h:371
t_size find_first(bool val, t_size start, t_size max) const
Definition: bit_array.h:31
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
Bit array interface class, constant version (you can only retrieve values). Range of valid indexes d...
Definition: bit_array.h:6
bool have_item(const t_param &p_item) const
Same as contains().
Definition: avltree.h:433
bool _findNearestDown(size_t val, size_t &outIdx) const
Definition: bit_array.cpp:73
size_t t_size
Definition: int_types.h:48
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.cpp:45
avltree_t< t_size > m_data
bool get(t_size n) const
Definition: bit_array.cpp:10
static void sort_t(t_container &p_data, t_compare p_compare, t_size p_count)
Definition: sort.h:162
pfc::sized_int_t< sizeof(size_t) >::t_signed t_ssize
Definition: int_types.h:49
bool get(t_size n) const
Definition: bit_array.cpp:41