Trait sux::traits::indexed_dict::IndexedDict

pub trait IndexedDict {
    type Input: PartialEq<Self::Output> + PartialEq + ?Sized;
    type Output: PartialEq<Self::Input> + PartialEq;

    // Required methods
    unsafe fn get_unchecked(&self, index: usize) -> Self::Output;
    fn len(&self) -> usize;

    // Provided methods
    fn get(&self, index: usize) -> Self::Output { ... }
    fn contains(&self, value: &Self::Input) -> bool { ... }
    fn is_empty(&self) -> bool { ... }
}

A dictionary of values indexed by a usize.

The input and output values may be different, to make it easier to implement compressed structures (see, e.g., rear-coded lists).

It is suggested that any implementation of this trait also implements IntoIterator with Item = Self::Output on a reference. This property can be tested on a type D with the clause where for<'a> &'a D: IntoIterator<Item = Self::Output>. Many implementations offer also a method into_iter_from that returns an iterator starting at a given position in the dictionary.

We provide a blanket implementation for types that dereference to a slice of T’s, where T implements ToOwned.

Required Associated Types

type Input: PartialEq<Self::Output> + PartialEq + ?Sized

type Output: PartialEq<Self::Input> + PartialEq

Required Methods

unsafe fn get_unchecked(&self, index: usize) -> Self::Output

Return the value at the specified index.

Safety

index must be in [0..len). No bounds checking is performed.

fn len(&self) -> usize

Return the length (number of items) of the dictionary.

Provided Methods

fn get(&self, index: usize) -> Self::Output

Return the value at the specified index.

Panics

May panic if the index is not in in [0..len).

Examples found in repository

examples/bench_rear_coded_list.rs (line 70)

pub fn main() -> Result<()> {
    env_logger::builder()
        .filter_level(log::LevelFilter::Info)
        .try_init()?;

    let args = Args::parse();

    let mut rcab = RearCodedListBuilder::new(args.k);
    let mut pl = ProgressLogger::default();
    pl.display_memory(true).item_name("line");

    let lines = std::io::BufReader::new(std::fs::File::open(&args.file_path)?);

    pl.start("Inserting...");

    for_!(result in  LineLender::new(lines) {
        match result {
            Ok(line) => {
                rcab.push(line);
                pl.light_update();
            }
            Err(e) => {
                panic!("Error reading input: {}", e);
            }
        }
    });

    pl.done();

    rcab.print_stats();
    let rca = rcab.build();

    let mut rand = SmallRng::seed_from_u64(0);

    let start = std::time::Instant::now();
    for _ in 0..args.accesses {
        let i = rand.gen::<usize>() % rca.len();
        let _ = black_box(rca.get(i));
    }
    let elapsed = start.elapsed();
    println!(
        "avg_rnd_access_speed: {} ns/access",
        elapsed.as_nanos() as f64 / args.accesses as f64
    );

    Ok(())
}

examples/bench_elias_fano.rs (line 107)

fn main() -> Result<()> {
    env_logger::builder()
        .filter_level(log::LevelFilter::Info)
        .try_init()?;

    let args = Args::parse();
    let mut values = Vec::with_capacity(args.n);
    let mut rng = SmallRng::seed_from_u64(0);
    for _ in 0..args.n {
        values.push(rng.gen_range(0..args.u));
    }
    values.sort();
    // Build Elias-Fano
    let mut elias_fano_builder = EliasFanoBuilder::new(args.n, args.u);
    for value in &values {
        elias_fano_builder.push(*value)?;
    }

    // Frequency of ones in the inventory for one-level index
    const FIXED1_LOG2_ONES_PER_INVENTORY: usize = 8;
    // Add an index on ones
    let elias_fano_q: EliasFano<SelectFixed1<_, _, FIXED1_LOG2_ONES_PER_INVENTORY>> =
        elias_fano_builder.build().convert_to()?;
    // Add an index on zeros
    let elias_fano_q: EliasFano<
        SelectZeroFixed1<
            SelectFixed1<_, _, FIXED1_LOG2_ONES_PER_INVENTORY>,
            _,
            FIXED1_LOG2_ONES_PER_INVENTORY,
        >,
    > = elias_fano_q.convert_to()?;

    elias_fano_q.mem_dbg(DbgFlags::default() | DbgFlags::PERCENTAGE)?;

    let mut elias_fano_builder = EliasFanoBuilder::new(args.n, args.u);
    for value in &values {
        elias_fano_builder.push(*value)?;
    }
    const FIXED2_LOG2_ONES_PER_INVENTORY: usize = 10;
    const FIXED2_LOG2_U64_PER_INVENTORY: usize = 2;
    // Add an index on ones
    let elias_fano_s: EliasFano<
        SelectFixed2<_, _, FIXED2_LOG2_ONES_PER_INVENTORY, FIXED2_LOG2_U64_PER_INVENTORY>,
    > = elias_fano_builder.build().convert_to()?;
    // Add an index on zeros
    let elias_fano_s: EliasFano<
        SelectZeroFixed2<
            SelectFixed2<_, _, FIXED2_LOG2_ONES_PER_INVENTORY, FIXED2_LOG2_U64_PER_INVENTORY>,
            _,
            FIXED2_LOG2_ONES_PER_INVENTORY,
            FIXED2_LOG2_U64_PER_INVENTORY,
        >,
    > = elias_fano_s.convert_to()?;

    println!();
    elias_fano_s.mem_dbg(DbgFlags::default() | DbgFlags::PERCENTAGE)?;

    let mut ranks = Vec::with_capacity(args.t);
    for _ in 0..args.t {
        ranks.push(rng.gen_range(0..args.n));
    }

    for _ in 0..args.repeats {
        let mut pl = ProgressLogger::default();

        pl.start("Benchmarking q.get()...");
        for &rank in &ranks {
            black_box(elias_fano_q.get(rank));
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking q.get_unchecked()...");
        for &rank in &ranks {
            unsafe {
                black_box(elias_fano_q.get_unchecked(rank));
            }
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking s.get()...");
        for &rank in &ranks {
            black_box(elias_fano_s.get(rank));
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking s.get_unchecked()...");
        for &rank in &ranks {
            unsafe {
                black_box(elias_fano_s.get_unchecked(rank));
            }
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking q.succ()...");
        for _ in 0..args.t {
            black_box(
                elias_fano_q
                    .succ(&rng.gen_range(0..args.u))
                    .unwrap_or((0, 0))
                    .0,
            );
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking q.succ_unchecked::<false>()...");
        let upper_bound = *values.last().unwrap();
        for _ in 0..args.t {
            black_box(unsafe {
                elias_fano_q
                    .succ_unchecked::<false>(&rng.gen_range(0..upper_bound))
                    .0
            });
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking s.succ()...");
        for _ in 0..args.t {
            black_box(
                elias_fano_s
                    .succ(&rng.gen_range(0..args.u))
                    .unwrap_or((0, 0))
                    .0,
            );
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking s.succ_unchecked::<false>()...");
        let upper_bound = *values.last().unwrap();
        for _ in 0..args.t {
            black_box(unsafe {
                elias_fano_s
                    .succ_unchecked::<false>(&rng.gen_range(0..upper_bound))
                    .0
            });
        }
        pl.done_with_count(args.t);

        let first = *values.first().unwrap();

        pl.start("Benchmarking q.pred()...");
        for _ in 0..args.t {
            black_box(
                elias_fano_q
                    .pred(&(rng.gen_range(first..args.u)))
                    .unwrap_or((0, 0))
                    .0,
            );
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking q.pred_unchecked::<false>()...");
        for _ in 0..args.t {
            black_box(unsafe {
                elias_fano_q
                    .pred_unchecked::<false>(&rng.gen_range(first..args.u))
                    .0
            });
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarkins s.pred()...");
        for _ in 0..args.t {
            black_box(
                elias_fano_s
                    .pred(&(rng.gen_range(first..args.u)))
                    .unwrap_or((0, 0))
                    .0,
            );
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking s.pred_unchecked::<false>()...");
        for _ in 0..args.t {
            black_box(unsafe {
                elias_fano_s
                    .pred_unchecked::<false>(&rng.gen_range(first..args.u))
                    .0
            });
        }
        pl.done_with_count(args.t);

        pl.start("Benchmarking q.iter()...");
        for i in &elias_fano_q {
            black_box(i);
        }
        pl.done_with_count(args.n);

        pl.start("Benchmarking s.iter()...");
        for i in &elias_fano_s {
            black_box(i);
        }
        pl.done_with_count(args.n);
    }

    Ok(())
}

fn contains(&self, value: &Self::Input) -> bool

Return true if the dictionary contains the given value.

The default implementations just checks iteratively if the value is equal to any of the values in the dictionary.

fn is_empty(&self) -> bool

Return true if len is zero.

Object Safety

This trait is not object safe.

Implementations on Foreign Types

impl<T: ToOwned> IndexedDict for [T]

where T::Owned: PartialEq<T> + PartialEq,

type Input = <T as ToOwned>::Owned

type Output = <T as ToOwned>::Owned

unsafe fn get_unchecked(&self, index: usize) -> Self::Output

fn len(&self) -> usize

impl<T: IndexedDict + ?Sized> IndexedDict for &T

type Input = <T as IndexedDict>::Input

type Output = <T as IndexedDict>::Output

fn get(&self, index: usize) -> Self::Output

unsafe fn get_unchecked(&self, index: usize) -> Self::Output

fn contains(&self, value: &Self::Input) -> bool

fn len(&self) -> usize

fn is_empty(&self) -> bool

impl<T: IndexedDict + ?Sized> IndexedDict for &mut T

type Input = <T as IndexedDict>::Input

type Output = <T as IndexedDict>::Output

fn get(&self, index: usize) -> Self::Output

unsafe fn get_unchecked(&self, index: usize) -> Self::Output

fn contains(&self, value: &Self::Input) -> bool

fn len(&self) -> usize

fn is_empty(&self) -> bool

impl<T: IndexedDict + ?Sized> IndexedDict for Box<T>

type Input = <T as IndexedDict>::Input

type Output = <T as IndexedDict>::Output

fn get(&self, index: usize) -> Self::Output

unsafe fn get_unchecked(&self, index: usize) -> Self::Output

fn contains(&self, value: &Self::Input) -> bool

fn len(&self) -> usize

fn is_empty(&self) -> bool

Implementors

impl<D: AsRef<[u8]>, P: AsRef<[usize]>> IndexedDict for RearCodedList<D, P>

type Output = String

type Input = str

impl<H: AsRef<[usize]> + Select, L: BitFieldSlice<usize>> IndexedDict for EliasFano<H, L>

type Output = usize

type Input = usize