Struct succinct::int_vector::IntVec

pub struct IntVec<Block: BlockType = usize> {
    // some fields omitted
}

A vector of k-bit unsigned integers, where k is determined at run time.

Block gives the representation type. The element size k can never exceed the number of bits in Block.

Methods

impl<Block: BlockType> IntVec<Block>

fn new(element_bits: usize) -> Self

Creates a new integer vector.

Arguments

• element_bits — the size of each element in bits; hence elements range from 0 to 2.pow(element_bits) - 1.

Result

The new, empty integer vector.

fn with_capacity(element_bits: usize, capacity: u64) -> Self

Creates a new, empty integer vector, allocating sufficient storage for capacity elements.

fn with_block_capacity(element_bits: usize, block_capacity: usize) -> Self

Creates a new, empty integer vector, allocating block_capacity blocks of storage.

fn with_fill(element_bits: usize, len: u64, value: Block) -> Self

Creates a new integer vector containing len copies of value.

fn with_fill_block(element_bits: usize, block_len: usize, value: Block) -> Self

Creates a new integer vector containing block_len copies of the block value.

The length of the new vector will be the number of elements of size element_bits that fit in block_len blocks.

fn is_okay_size(element_bits: usize, n_elements: u64) -> bool

Determines whether we can support a vector with the given element size and number of elements.

We cannot support vectors where:

• block_bits() < element_bits;
• n_elements * element_bits doesn’t fit in a u64; or
• n_elements * element_bits / block_bits() (but with the division rounded up) doesn’t fit in a usize.

where block_bits() is the size of the Block type parameter.

fn get_random(&self, bit_offset: u64, element_bits: usize, element_index: u64) -> Block

Returns the element at a given index, also given an arbitrary element size and bit offset.

This computes the location of the element_indexth element supposing that elements are element_bits side, then adds bit_offset additional bits and returns the element_bits-bit value found at that location.

Panics

Panics if the referenced bits are out of bounds. Bounds are considered to the end of the support array, even if that goes past the last element of the IntArray.

fn set_random(&mut self, bit_offset: u64, element_bits: usize, element_index: u64, element_value: Block)

Sets the element at a given index to a given value, also given an arbitrary element size and bit offset.

This computes the location of the element_indexth element supposing that elements are element_bits side, then adds bit_offset additional bits and modifies the element_bits-bit value found at that location.

Panics

• Panics if the referenced bits are out of bounds. Bounds are considered to the end of the support array, even if that goes past the last element of the IntArray.

• Debug mode only: Panics if element_value is too large to fit in the element size. (TODO: What’s the right thing here?)

fn push(&mut self, element_value: Block)

Pushes an element onto the end of the vector, increasing the length by 1.

fn pop(&mut self) -> Option<Block>

Removes and returns the last element of the vector, if present.

fn capacity(&self) -> u64

The number of elements the vector can hold without reallocating.

fn block_capacity(&self) -> usize

The number of blocks of elements the vector can hold without reallocating.

fn resize(&mut self, n_elements: u64, fill: Fill<Block>)

Resizes to the given number of elements, filling if necessary.

fn resize_block(&mut self, n_blocks: usize, fill: Block)

Resizes to the given number of blocks, filling if necessary.

fn reserve(&mut self, additional: u64)

Reserves capacity for at least additional more elements to be inserted in the given IntVec<Block>.

The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the size conditions of IntVec::<Block>::is_okay_size() are not met. This will happen if the total number of bits overflows u64.

fn reserve_block(&mut self, additional: usize)

Reserves capacity for at least additional blocks of values to be inserted.

The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the number of blocks overflows a usize.

fn reserve_exact(&mut self, additional: u64)

Reserves capacity for at least additional more elements to be inserted in the given IntVec<Block>.

Unlike reserve, does nothing if the capacity is already sufficient.

Panics

Panics if the size conditions of IntVec::<Block>::is_okay_size() are not met. This will happen if the total number of bits overflows u64.

fn reserve_exact_block(&mut self, additional: usize)

Reserves capacity for at least additional blocks of values to be inserted.

Unlike reserve_block, does nothing if the capacity is already sufficient.

The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the number of blocks overflows a usize.

fn shrink_to_fit(&mut self)

Shrinks the capacity to just fit the number of elements.

fn truncate(&mut self, n_elements: u64)

Shrinks to the given size.

Does nothing if n_elements is greater than the current size.

fn truncate_block(&mut self, n_blocks: usize)

Shrinks to the given number of blocks.

Does nothing if n_blocks is greater than the current blocks.

fn clear(&mut self)

Sets the size to 0 while retaining the allocated storage.

fn iter(&self) -> Iter<Block>

Gets an iterator over the elements of the vector.

fn block_bits() -> usize

The number of bits per block of storage.

fn is_packed(&self) -> bool

True if elements are packed one per block.

fn is_aligned(&self) -> bool

True if elements are aligned within blocks.

Trait Implementations

impl<Block: Ord + BlockType> Ord for IntVec<Block>

fn cmp(&self, __arg_0: &IntVec<Block>) -> Ordering

This method returns an Ordering between self and other.

impl<Block: PartialOrd + BlockType> PartialOrd for IntVec<Block>

fn partial_cmp(&self, __arg_0: &IntVec<Block>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, __arg_0: &IntVec<Block>) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, __arg_0: &IntVec<Block>) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, __arg_0: &IntVec<Block>) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, __arg_0: &IntVec<Block>) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<Block: Eq + BlockType> Eq for IntVec<Block>

impl<Block: PartialEq + BlockType> PartialEq for IntVec<Block>

fn eq(&self, __arg_0: &IntVec<Block>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &IntVec<Block>) -> bool

This method tests for !=.

impl<Block: Hash + BlockType> Hash for IntVec<Block>

fn hash<__HBlock: Hasher>(&self, __arg_0: &mut __HBlock)

Feeds this value into the state given, updating the hasher as necessary.

fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher

Feeds a slice of this type into the state provided.

impl<Block: Clone + BlockType> Clone for IntVec<Block>

fn clone(&self) -> IntVec<Block>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Block: BlockType> IntVector for IntVec<Block>

type Block = Block

The type of primitive value to represent elements.

fn len(&self) -> u64

The number of elements.

fn get(&self, element_index: u64) -> Block

Fetches the value of the indexth element.

fn element_bits(&self) -> usize

The bit width of each element.

fn is_empty(&self) -> bool

Is the vector empty?

impl<Block: BlockType> IntVectorMut for IntVec<Block>

fn set(&mut self, element_index: u64, element_value: Block)

Updates the value of the indexth element.

impl<Block: BlockType> Bits for IntVec<Block>

type Block = Block

The underlying block type used to store the bits of the slice.

fn block_len(&self) -> usize

The length of the slice in blocks.

fn bit_len(&self) -> u64

The length of the slice in bits.

fn get_block(&self, position: usize) -> Block

Gets the block at position

fn get_bit(&self, position: u64) -> bool

Gets the bit at position

fn get_bits(&self, start: u64, count: usize) -> Self::Block

Gets count bits starting at bit index start, interpreted as a little-endian integer.

impl<Block: BlockType> BitsMut for IntVec<Block>

fn set_block(&mut self, position: usize, value: Block)

Sets the block at position to value.

fn set_bit(&mut self, position: u64, value: bool)

Sets the bit at position to value.

fn set_bits(&mut self, start: u64, count: usize, value: Self::Block)

Sets count bits starting at bit index start, interpreted as a little-endian integer.

impl<'a, Block: BlockType + 'a> IntoIterator for &'a IntVec<Block>

type Item = Block

The type of the elements being iterated over.

type IntoIter = Iter<'a, Block>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<Block> Debug for IntVec<Block> where Block: BlockType + Debug

fn fmt(&self, formatter: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<A: BlockType> SpaceUsage for IntVec<A>

fn is_stack_only() -> bool

Is the size of this type known statically?

fn heap_bytes(&self) -> usize

Calculates the heap portion of the size of an object.

fn total_bytes(&self) -> usize

Computes the size of the receiver in bytes.

fn stack_bytes() -> usize

Calculates the stack portion of the size of this type.