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_fast >	m_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.

                                                     {
        m_content.prealloc( 1024 ); 
    }

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.

                                                        {
            return pfc::bsearch_simple_inline_t( m_content, m_content.get_size(), val, outIdx);
        }

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

private

Definition at line 73 of file bit_array.cpp.

                                                                                      {
        size_t idx;
        if (_find( val, idx )) { outIdx = idx; return true; }
        // we have a valid outIdx at where the bsearch gave up
        PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
        PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
        if (idx == 0) return false;
        outIdx = idx - 1;
        return true;
    }

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

private

Definition at line 63 of file bit_array.cpp.

                                                                                    {
        size_t idx;
        if (_find( val, idx )) { outIdx = idx; return true; }
        // we have a valid outIdx at where the bsearch gave up
        PFC_ASSERT ( idx == 0 || m_content [ idx - 1 ] < val );
        PFC_ASSERT ( idx == m_content.get_size() || m_content[ idx ] > val );
        if (idx == m_content.get_size()) return false;
        outIdx = idx;
        return true;
    }

void pfc::bit_array_flatIndexList::add

(

size_t

n

)

Definition at line 37 of file bit_array.cpp.

                                                {
        m_content.append_single_val( n );
    }

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.

                                                                                  {
        if (val == false) {
            // unoptimized but not really used
            return bit_array::find(val, start, count);
        }
            
        if (count==0) return start;
        else if (count<0) {
            size_t idx;
            if (!_findNearestDown( start, idx ) || m_content[idx] < start+count) return start + count;
            return m_content[idx];
        } else { // count > 0
            size_t idx;
            if (!_findNearestUp( start, idx ) || m_content[idx] > start+count) return start + count;
            return m_content[idx];
        }
    }

bool pfc::bit_array_flatIndexList::get ( t_size  n ) const

virtual

Implements pfc::bit_array.

Definition at line 41 of file bit_array.cpp.

                                                    {
        size_t dummy;
        return _find( n, dummy );
    }

void pfc::bit_array_flatIndexList::presort

(

)

Definition at line 84 of file bit_array.cpp.

                                          {
        pfc::sort_t( m_content, pfc::compare_t< size_t, size_t >, m_content.get_size( ) );
    }

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:

• pfc/bit_array_impl_part2.h
• pfc/bit_array.cpp