Struct DArray

pub struct DArray<const SELECT0_SUPPORT: bool = false> { /* private fields */ }

Const generic SELECT0_SUPPORT may optionally add extra data structures to support fast select0 queries, which otherwise are not supported.

Implementations

impl<const SELECT0_SUPPORT: bool> DArray<SELECT0_SUPPORT>

Const genetic SELECT0_SUPPORT

pub fn new(bv: BitVector) -> Self

Creates a DArray from a BitVector.

Examples

use qwt::{DArray, SelectBin};

let v = vec![0,2,3,4,5];
let da: DArray::<true> = v.into_iter().collect(); // <true> to support the select0 query

assert_eq!(da.select1(2), Some(3));
assert_eq!(da.select0(0), Some(1));

pub fn ones(&self) -> BitVectorBitPositionsIter<'_, true>

Returns a non-consuming iterator over positions of bits set to 1 in the bit vector.

Examples

use qwt::DArray;

let vv: Vec<usize> = vec![0, 63, 128, 129, 254, 1026];
let da: DArray = vv.iter().copied().collect();

let v: Vec<usize> = da.ones().collect();
assert_eq!(v, vv);

pub fn ones_with_pos(&self, pos: usize) -> BitVectorBitPositionsIter<'_, true>

Returns a non-consuming iterator over positions of bits set to 1 in the bit vector, starting at a specified bit position.

Examples

use qwt::DArray;

let vv: Vec<usize> = vec![0, 63, 128, 129, 254, 1026];
let da: DArray = vv.iter().copied().collect();

let v: Vec<usize> = da.ones_with_pos(2).collect();
assert_eq!(v, vec![63, 128, 129, 254, 1026]);

pub fn zeros(&self) -> BitVectorBitPositionsIter<'_, false>

Returns a non-consuming iterator over positions of bits set to 0 in the bit vector.

Examples

use qwt::DArray;
use qwt::perf_and_test_utils::negate_vector;

let vv: Vec<usize> = vec![0, 63, 128, 129, 254, 1026];
let da: DArray = vv.iter().copied().collect();

let v: Vec<usize> = da.zeros().collect();
assert_eq!(v, negate_vector(&vv));

pub fn zeros_with_pos(&self, pos: usize) -> BitVectorBitPositionsIter<'_, false>

Returns a non-consuming iterator over positions of bits set to 0 in the bit vector, starting at a specified bit position.

pub fn iter(&self) -> BitVectorIter<'_>

Returns a non-consuming iterator over bits of the bit vector.

Examples

use qwt::DArray;

let v = vec![0,2,3,5];
let da: DArray = v.into_iter().collect();

let mut iter = da.iter();
assert_eq!(iter.next(), Some(true)); // First bit is true
assert_eq!(iter.next(), Some(false)); // Second bit is false
assert_eq!(iter.next(), Some(true)); // Third bit is true
assert_eq!(iter.next(), Some(true)); // Fourth bit is true
assert_eq!(iter.next(), Some(false)); // Fifth bit is false
assert_eq!(iter.next(), Some(true)); // Sixth bit is true
assert_eq!(iter.next(), None); // End of the iterator

pub fn count_ones(&self) -> usize

Returns the number of ones in the DArray.

Examples

use qwt::{DArray, SelectBin};

let v = vec![0, 2, 3, 4, 5];
let da: DArray<true> = v.into_iter().collect(); // <true> to support the select0 query

assert_eq!(da.count_ones(), 5);

pub fn count_zeros(&self) -> usize

Returns the number of zeros in the DArray.

Examples

use qwt::{DArray, SelectBin};

let v = vec![0, 2, 3, 4, 5];
let da: DArray<true> = v.into_iter().collect(); // <true> to support the select0 query

assert_eq!(da.count_zeros(), 1);

pub fn len(&self) -> usize

Returns the number of elements in the DArray.

Examples

use qwt::{DArray, SelectBin};

let v = vec![0, 2, 3, 4, 5];
let da: DArray<true> = v.into_iter().collect(); // <true> to support the select0 query

assert_eq!(da.len(), 6);

pub fn is_empty(&self) -> bool

Checks if the DArray is empty.

Examples

use qwt::{DArray, SelectBin};

let v: Vec<usize> = vec![];
let da: DArray<true> = v.into_iter().collect(); // <true> to support the select0 query

assert!(da.is_empty());

Trait Implementations

impl<const SELECT0_SUPPORT: bool> AccessBin for DArray<SELECT0_SUPPORT>

fn get(&self, i: usize) -> Option<bool>

Returns the bit at the given position i, or None if i is out of bounds.

Examples

use qwt::{DArray, AccessBin};

let v = vec![0,2,3,4,5];
let da: DArray = v.into_iter().collect();;

assert_eq!(da.get(5), Some(true));
assert_eq!(da.get(1), Some(false));
assert_eq!(da.get(10), None);

unsafe fn get_unchecked(&self, i: usize) -> bool

Returns the bit at position i.

Safety

Calling this method with an out-of-bounds index is undefined behavior.

Examples

use qwt::{DArray, AccessBin};

let v = vec![0,2,3,4,5];
let da: DArray = v.into_iter().collect();;
assert_eq!(unsafe{da.get_unchecked(8)}, false);

impl<const SELECT0_SUPPORT: bool> Clone for DArray<SELECT0_SUPPORT>

fn clone(&self) -> DArray<SELECT0_SUPPORT>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const SELECT0_SUPPORT: bool> Debug for DArray<SELECT0_SUPPORT>

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

Formats the value using the given formatter.

impl<const SELECT0_SUPPORT: bool> Default for DArray<SELECT0_SUPPORT>

fn default() -> DArray<SELECT0_SUPPORT>

Returns the “default value” for a type.

impl<'de, const SELECT0_SUPPORT: bool> Deserialize<'de> for DArray<SELECT0_SUPPORT>

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<V, const SELECT0_SUPPORT: bool> FromIterator<V> for DArray<SELECT0_SUPPORT>

where V: MyPrimInt + PartialOrd, <V as TryInto<usize>>::Error: Debug,

Create a DArray from an iterator over strictly increasing sequence of integer values.

Panics

Panics if the sequence is not stricly increasing or if any value of the sequence cannot be converted to usize.

Examples

use qwt::{DArray, AccessBin};

// Create a [`DArray`] from an iterator over strictly increasing sequence of non-negative integer values.
let da: DArray = vec![0, 1, 3, 5].into_iter().collect();

assert_eq!(da.len(), 6);
assert_eq!(da.get(3), Some(true));

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = V>, <V as TryInto<usize>>::Error: Debug,

Creates a value from an iterator.

impl<const SELECT0_SUPPORT: bool> FromIterator<bool> for DArray<SELECT0_SUPPORT>

Creates a DArray from an iterator over bool values.

Examples

use qwt::{AccessBin, DArray};

// Create a bit vector from an iterator over bool values
let da: DArray = vec![true, false, true].into_iter().collect();

assert_eq!(da.len(), 3);
assert_eq!(da.get(1), Some(false));

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = bool>,

Creates a value from an iterator.

impl<const SELECT0_SUPPORT: bool> PartialEq for DArray<SELECT0_SUPPORT>

fn eq(&self, other: &DArray<SELECT0_SUPPORT>) -> 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<const SELECT0_SUPPORT: bool> SelectBin for DArray<SELECT0_SUPPORT>

fn select1(&self, i: usize) -> Option<usize>

Answers a select1 query.

The query select1(i) returns the position of the (i+1)-th occurrence of 1 in the binary vector.

Examples

use qwt::{DArray, SelectBin};

let v: Vec<usize> = vec![0, 12, 33, 42, 55, 61, 1000];
let da: DArray = v.into_iter().collect();

assert_eq!(da.select1(1), Some(12));

Panics

It panics if DArray is built without support for select0query.

unsafe fn select1_unchecked(&self, i: usize) -> usize

Answers a select1 query without checking for bounds.

The query select1(i) returns the position of the (i+1)-th occurrence of 1 in the binary vector.

Examples

use qwt::{DArray, SelectBin};

let v: Vec<usize> = vec![0, 12, 33, 42, 55, 61, 1000];
let da: DArray = v.into_iter().collect();

assert_eq!(unsafe{da.select1_unchecked(1)}, 12);

fn select0(&self, i: usize) -> Option<usize>

Answers a select0 query.

The query select0(i) returns the position of the (i+1)-th occurrence of 0 in the binary vector.

Examples

use qwt::{DArray, SelectBin};

let v: Vec<usize> = vec![0, 12, 33, 42, 55, 61, 1000];
let da: DArray<true> = v.into_iter().collect();

assert_eq!(da.select0(1), Some(2));
assert_eq!(da.select0(11), Some(13));

Panics

It panics if DArray is built without support for select0query.

unsafe fn select0_unchecked(&self, i: usize) -> usize

Answers a select0 query without checkin bounds.

The query select0(i) returns the position of the (i+1)-th occurrence of 0 in the binary vector.

Examples

use qwt::{DArray, SelectBin};

let v: Vec<usize> = vec![0, 12, 33, 42, 55, 61, 1000];
let da: DArray<true> = v.into_iter().collect();

assert_eq!(unsafe{da.select0_unchecked(1)}, 2);
assert_eq!(unsafe{da.select0_unchecked(11)}, 13);

impl<const SELECT0_SUPPORT: bool> Serialize for DArray<SELECT0_SUPPORT>

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<const SELECT0_SUPPORT: bool> SpaceUsage for DArray<SELECT0_SUPPORT>

fn space_usage_byte(&self) -> usize

Returns the space usage of the data structure in bytes.

fn space_usage_KiB(&self) -> f64

Gives the space usage of the data structure in KiB.

fn space_usage_MiB(&self) -> f64

Gives the space usage of the data structure in MiB.

fn space_usage_GiB(&self) -> f64

Gives the space usage of the data structure in GiB.

impl<const SELECT0_SUPPORT: bool> StructuralPartialEq for DArray<SELECT0_SUPPORT>