Struct SampleIndex 

pub struct SampleIndex { /* private fields */ }

An index for narrowing down a range before binary search.

SampleIndex takes a strictly increasing sequence of n values in 0..universe. The first value must be 0. The index chooses a divisor that partitions the universe into approximately n / 8 ranges. Each range i contains the values in range (i * divisor)..((i + 1) * divisor). Given a value x, we can restrict the binary search to the range self.range(x) of values.

Examples

use simple_sds_sbwt::int_vector::IntVector;
use simple_sds_sbwt::ops::{Vector, Access};
use simple_sds_sbwt::rl_vector::index::SampleIndex;

let values: Vec<usize> = vec![0, 33, 124, 131, 224, 291, 322, 341, 394, 466, 501];
let index = SampleIndex::new(values.iter().copied(), 540);

let range = index.range(300);
assert!(values[range.start] <= 300);
let upper_bound = *values.get(range.end).unwrap_or(&540);
assert!(upper_bound > 300);

Notes

• This is a simple support structure not intended to be serialized.

Implementations

impl SampleIndex

pub const RATIO: usize = 8usize

Ratio of number of values to number of samples.

pub fn new<T: Iterator<Item = usize> + ExactSizeIterator>( iter: T, universe: usize, ) -> Self

Returns a SampleIndex for the given values.

Arguments

• values: A strictly increasing sequence of values starting from 0.
• universe: Universe size. The values must be in range 0..universe.

Panics

Panics if the first value is not 0, the sequence of values is not strictly increasing, or if universe size is too small for the values.

pub fn range(&self, value: usize) -> Range<usize>

Returns a range that will contain the given value if it is present in the values.

If value < universe, the range guarantees the following invariants:

• values[range.start] <= value
• values.get(range.end).unwrap_or(universe) > value

Trait Implementations

impl Clone for SampleIndex

fn clone(&self) -> SampleIndex

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SampleIndex

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

Formats the value using the given formatter.

impl PartialEq for SampleIndex

fn eq(&self, other: &SampleIndex) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for SampleIndex

impl StructuralPartialEq for SampleIndex