Struct sux::rank_sel::SelectFixed1

pub struct SelectFixed1<B: SelectHinted = CountBitVec, O: BitFieldSlice<usize> = Vec<usize>, const LOG2_ONES_PER_INVENTORY: usize = 8> { /* private fields */ }

A selection structure based on a one-level index.

More precisely, given a constant LOG2_ONES_PER_INVENTORY, this index records the position of one every 2^{LOG2_ONES_PER_INVENTORY}. The positions are recorded in a BitFieldSlice whose bit width must be sufficient to record all the positions.

Note that SelectFixed2 has usually better performance than this structure, which is mainly useful for testing, benchmarking and debugging.

The current implementation uses a Vec<usize> as the underlying BitFieldSlice. Thus, the overhead of the structure is BitCount::count() * usize::BITS / 2^{LOG2_ONES_PER_INVENTORY} bits.

The index takes a backend parameter B that can be any type that implements SelectHinted. This will usually be something like CountBitVec, or possibly a CountBitVec wrapped in another index structure for which this structure has delegation (e.g., SelectZeroFixed1). See the documentation of EliasFano for an example of this approach.

See SelectZeroFixed1 for the same structure for zeros.

Implementations

impl<B: SelectHinted + AsRef<[usize]>, const LOG2_ONES_PER_INVENTORY: usize> SelectFixed1<B, Vec<usize>, LOG2_ONES_PER_INVENTORY>

pub fn new(bitvec: B, number_of_ones: usize) -> Self

Trait Implementations

impl<B: SelectHinted + AsRef<[usize]>, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> AsRef<[usize]> for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward AsRef<[usize]> to the underlying implementation.

fn as_ref(&self) -> &[usize]

Converts this type into a shared reference of the (usually inferred) input type.

impl<B: SelectHinted + BitCount, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> BitCount for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward BitCount to the underlying implementation.

fn count(&self) -> usize

Return the number of ones in the underlying bit vector.

impl<B: SelectHinted + BitLength, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> BitLength for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward BitLength to the underlying implementation.

fn len(&self) -> usize

Return the length in bits of the underlying bit vector.

impl<B: Clone + SelectHinted, O: Clone + BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> Clone for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

fn clone(&self) -> SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<B: SelectHinted, T, const LOG2_ONES_PER_INVENTORY: usize> ConvertTo<B> for SelectFixed1<B, T, LOG2_ONES_PER_INVENTORY>

where T: AsRef<[usize]>,

Forget the index.

fn convert_to(self) -> Result<B>

impl<B: SelectHinted, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> CopyType for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

type Copy = Deep

impl<B, O, const LOG2_ONES_PER_INVENTORY: usize> CopyType for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

where B: MemSize + SelectHinted, O: MemSize + BitFieldSlice<usize>, PhantomData<[(); LOG2_ONES_PER_INVENTORY]>: MemSize,

type Copy = False

impl<B: Debug + SelectHinted, O: Debug + BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> Debug for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<B, O, const LOG2_ONES_PER_INVENTORY: usize> DeserializeInner for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

where B: DeserializeInner + SelectHinted, O: DeserializeInner + BitFieldSlice<usize>, PhantomData<[(); LOG2_ONES_PER_INVENTORY]>: DeserializeInner, for<'epserde_desertype> <B as DeserializeInner>::DeserType<'epserde_desertype>: SelectHinted, for<'epserde_desertype> <O as DeserializeInner>::DeserType<'epserde_desertype>: BitFieldSlice<usize>,

fn _deserialize_full_inner( backend: &mut impl ReadWithPos ) -> Result<Self, Error>

type DeserType<'epserde_desertype> = SelectFixed1<<B as DeserializeInner>::DeserType<'epserde_desertype>, <O as DeserializeInner>::DeserType<'epserde_desertype>, LOG2_ONES_PER_INVENTORY>

The deserialization type associated with this type. It can be retrieved conveniently with the alias DeserType.

fn _deserialize_eps_inner<'a>( backend: &mut SliceWithPos<'a> ) -> Result<Self::DeserType<'a>, Error>

impl<B, O, const LOG2_ONES_PER_INVENTORY: usize> MemDbgImpl for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

where B: MemDbgImpl + SelectHinted, O: MemDbgImpl + BitFieldSlice<usize>, PhantomData<[(); LOG2_ONES_PER_INVENTORY]>: MemDbgImpl,

fn _mem_dbg_rec_on( &self, _memdbg_writer: &mut impl Write, _memdbg_total_size: usize, _memdbg_max_depth: usize, _memdbg_prefix: &mut String, _memdbg_is_last: bool, _memdbg_flags: DbgFlags ) -> Result

impl<B, O, const LOG2_ONES_PER_INVENTORY: usize> MemSize for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

where B: MemSize + SelectHinted, O: MemSize + BitFieldSlice<usize>, PhantomData<[(); LOG2_ONES_PER_INVENTORY]>: MemSize,

fn mem_size(&self, _memsize_flags: SizeFlags) -> usize

Return the (recursively computed) overall memory size of the structure in bytes.

impl<B: SelectHinted + Rank, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> Rank for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward Rank to the underlying implementation.

fn rank(&self, pos: usize) -> usize

Return the number of ones preceding the specified position.

unsafe fn rank_unchecked(&self, pos: usize) -> usize

Return the number of ones preceding the specified position.

impl<B: SelectHinted + RankZero, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> RankZero for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward RankZero to the underlying implementation.

fn rank_zero(&self, pos: usize) -> usize

Return the number of zeros preceding the specified position.

unsafe fn rank_zero_unchecked(&self, pos: usize) -> usize

Return the number of zeros preceding the specified position.

impl<B: SelectHinted + ReprHash, O: BitFieldSlice<usize> + ReprHash, const LOG2_ONES_PER_INVENTORY: usize> ReprHash for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

fn repr_hash(hasher: &mut impl Hasher, offset_of: &mut usize)

Accumulate representional information in hasher assuming to be positioned at offset_of.

fn repr_hash_val(&self, hasher: &mut impl Hasher, offset_of: &mut usize)

Call ReprHash::repr_hash on a value.

impl<B: SelectHinted + BitCount, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> Select for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Provide the hint to the underlying structure

unsafe fn select_unchecked(&self, rank: usize) -> usize

Return the position of the one of given rank.

fn select(&self, rank: usize) -> Option<usize>

Return the position of the one of given rank, or None if no such bit exist.

impl<B: SelectHinted + SelectZero, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> SelectZero for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward SelectZero to the underlying implementation.

fn select_zero(&self, rank: usize) -> Option<usize>

Return the position of the zero of given rank, or None if no such bit exist.

unsafe fn select_zero_unchecked(&self, rank: usize) -> usize

Return the position of the zero of given rank.

impl<B: SelectHinted + SelectZeroHinted, O: BitFieldSlice<usize>, const LOG2_ONES_PER_INVENTORY: usize> SelectZeroHinted for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

Forward SelectZeroHinted to the underlying implementation.

unsafe fn select_zero_hinted_unchecked( &self, rank: usize, pos: usize, rank_at_pos: usize ) -> usize

Select the zero of given rank, provided the position of a preceding zero and its rank.

fn select_zero_hinted( &self, rank: usize, pos: usize, rank_at_pos: usize ) -> Option<usize>

Select the zero of given rank, provided the position of a preceding zero and its rank.

impl<B, O, const LOG2_ONES_PER_INVENTORY: usize> SerializeInner for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

where B: SerializeInner + SelectHinted, O: SerializeInner + BitFieldSlice<usize>, PhantomData<[(); LOG2_ONES_PER_INVENTORY]>: SerializeInner,

const IS_ZERO_COPY: bool = _

Inner constant used by the derive macros to keep track recursively of whether the type satisfies the conditions for being zero-copy. It is checked at runtime against the trait implemented by the type, and if a ZeroCopy type has this constant set to false serialization will panic.

const ZERO_COPY_MISMATCH: bool = _

Inner constant used by the derive macros to keep track of whether all fields of a type are zero-copy but neither the attribute #[zero_copy] nor the attribute #[deep_copy] was specified. It is checked at runtime, and if it is true a warning will be issued, as the type could be zero-copy, which would be more efficient.

fn _serialize_inner(&self, backend: &mut impl WriteWithNames) -> Result<()>

Serialize this structure using the given backend.

impl<B: SelectHinted + TypeHash, O: BitFieldSlice<usize> + TypeHash, const LOG2_ONES_PER_INVENTORY: usize> TypeHash for SelectFixed1<B, O, LOG2_ONES_PER_INVENTORY>

fn type_hash(hasher: &mut impl Hasher)

Accumulate type information in hasher.

fn type_hash_val(&self, hasher: &mut impl Hasher)

Call TypeHash::type_hash on a value.