foobar2000 SDK  2015-08-03
Public Member Functions | Private Member Functions | Private Attributes
pfc::bit_array_flatIndexList

#include <bit_array_impl_part2.h>

+ Inheritance diagram for pfc::bit_array_flatIndexList:

Public Member Functions

 bit_array_flatIndexList ()
 
void add (size_t n)
 
t_size find (bool val, t_size start, t_ssize count) const
 
bool get (t_size n) const
 
void presort ()
 
- Public Member Functions inherited from pfc::bit_array
t_size calc_count (bool val, t_size start, t_size count, t_size count_max=~0) const
 
t_size find_first (bool val, t_size start, t_size max) const
 
t_size find_next (bool val, t_size previous, t_size max) const
 
bool operator[] (t_size n) const
 

Private Member Functions

bool _find (size_t val, size_t &outIdx) const
 
bool _findNearestDown (size_t val, size_t &outIdx) const
 
bool _findNearestUp (size_t val, size_t &outIdx) const
 

Private Attributes

pfc::array_t< size_t, pfc::alloc_fastm_content
 

Additional Inherited Members

- Protected Member Functions inherited from pfc::bit_array
 bit_array ()
 
 ~bit_array ()
 

Detailed Description

Specialized implementation of bit_array.
Indended for scenarios where fast searching for true values in a large list is needed, combined with low footprint regardless of the amount of items. Call add() repeatedly with the true val indexes. If the indexes were not added in increasing order, call presort() when done with adding.

Definition at line 23 of file bit_array_impl_part2.h.

Constructor & Destructor Documentation

pfc::bit_array_flatIndexList::bit_array_flatIndexList ( )

Definition at line 33 of file bit_array.cpp.

33  {
34  m_content.prealloc( 1024 );
35  }
pfc::array_t< size_t, pfc::alloc_fast > m_content

Member Function Documentation

bool pfc::bit_array_flatIndexList::_find ( size_t  val,
size_t &  outIdx 
) const
inlineprivate

Definition at line 37 of file bit_array_impl_part2.h.

37  {
38  return pfc::bsearch_simple_inline_t( m_content, m_content.get_size(), val, outIdx);
39  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
bool bsearch_simple_inline_t(const t_buffer &p_buffer, t_size p_count, t_value const &p_value, t_size &p_result)
bool pfc::bit_array_flatIndexList::_findNearestDown ( size_t  val,
size_t &  outIdx 
) const
private

Definition at line 73 of file bit_array.cpp.

73  {
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  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
bool _find(size_t val, size_t &outIdx) const
bool pfc::bit_array_flatIndexList::_findNearestUp ( size_t  val,
size_t &  outIdx 
) const
private

Definition at line 63 of file bit_array.cpp.

63  {
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  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
bool _find(size_t val, size_t &outIdx) const
void pfc::bit_array_flatIndexList::add ( size_t  n)

Definition at line 37 of file bit_array.cpp.

37  {
38  m_content.append_single_val( n );
39  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
t_size pfc::bit_array_flatIndexList::find ( bool  val,
t_size  start,
t_ssize  count 
) const
virtual

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.

Reimplemented from pfc::bit_array.

Definition at line 45 of file bit_array.cpp.

45  {
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  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
bool _findNearestUp(size_t val, size_t &outIdx) const
Definition: bit_array.cpp:63
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
bool _findNearestDown(size_t val, size_t &outIdx) const
Definition: bit_array.cpp:73
bool pfc::bit_array_flatIndexList::get ( t_size  n) const
virtual

Implements pfc::bit_array.

Definition at line 41 of file bit_array.cpp.

41  {
42  size_t dummy;
43  return _find( n, dummy );
44  }
bool _find(size_t val, size_t &outIdx) const
void pfc::bit_array_flatIndexList::presort ( )

Definition at line 84 of file bit_array.cpp.

84  {
85  pfc::sort_t( m_content, pfc::compare_t< size_t, size_t >, m_content.get_size( ) );
86  }
pfc::array_t< size_t, pfc::alloc_fast > m_content
static void sort_t(t_container &p_data, t_compare p_compare, t_size p_count)
Definition: sort.h:162

Field Documentation

pfc::array_t< size_t, pfc::alloc_fast > pfc::bit_array_flatIndexList::m_content
private

Definition at line 41 of file bit_array_impl_part2.h.


The documentation for this class was generated from the following files: