Struct Coding 

pub struct Coding<ValueType, D = BitsPerFragment> {
    pub values: Box<[ValueType]>,
    pub internal_nodes_count: Box<[u32]>,
    pub degree: D,
}

Succinct representation of minimum-redundancy coding (huffman tree of some degree in the canonical form).

Fields

values: Box<[ValueType]>

Values, from the most frequent to the least.

internal_nodes_count: Box<[u32]>

Number of the internal nodes of each tree level. The root is not counted. Contains exactly one zero at the end.

degree: D

Size of the fragment given as bits per fragment or the degree of the Huffman tree.

Implementations

impl<ValueType, D: TreeDegree> Coding<ValueType, D>

pub fn from_frequencies<F: Frequencies<Value = ValueType>>( degree: D, frequencies: F, ) -> Self

Constructs coding for given frequencies of values and degree of the Huffman tree.

pub fn from_frequencies_cloned<F: Frequencies<Value = ValueType>>( degree: D, frequencies: &F, ) -> Self

where F::Value: Clone,

Constructs coding for given frequencies of values and degree of the Huffman tree. Values are cloned from frequencies.

pub fn from_iter<Iter>(degree: D, iter: Iter) -> Self

where Iter: IntoIterator, Iter::Item: Borrow<ValueType>, ValueType: Hash + Eq + Clone,

Counts occurrences of all values exposed by iter and constructs coding for obtained frequencies of values and degree of the Huffman tree.

pub fn total_fragments_count(&self) -> usize

Returns total (summarized) number of code fragments of all values.

The algorithm runs in O(L) time and O(1) memory, where L is the number of fragments in the longest codeword.

pub fn decoder(&self) -> Decoder<'_, ValueType, D>

Returns decoder that allows for decoding a value.

pub fn from_sorted<W>( degree: D, values: Box<[ValueType]>, freq: &mut [W], ) -> Self

where W: Weight,

Construct coding (of given degree) for the given values, where freq is an array of numbers of occurrences of corresponding values. freq has to be in non-descending order and of the same length as values.

The algorithm runs in O(values.len) time, in-place (it uses and changes freq and move values to the returned Coding object).

pub fn from_unsorted<W>( degree: D, values: Box<[ValueType]>, freq: &mut [W], ) -> Self

where W: Weight,

Construct coding (of the given degree) for the given values, where freq has to be of the same length as values and contain number of occurrences of corresponding values.

The algorithm runs in O(values.len * log(values.len)) time.

pub fn write_internal_nodes_count_bytes(&self) -> usize

Returns number of bytes which write_internal_nodes_count will write.

pub fn write_internal_nodes_count(&self, output: &mut dyn Write) -> Result<()>

Writes internal_nodes_count to output as the following internal_nodes_count.len(), VByte values: internal_nodes_count.len()-1 (=l), internal_nodes_count[0], internal_nodes_count[1], …, internal_nodes_count[l]

pub fn read_internal_nodes_count(input: &mut dyn Read) -> Result<Box<[u32]>>

Reads (written by write_internal_nodes_count) internal_nodes_count from input.

pub fn write_values_size_bytes( &self, value_size: ValueSize<'_, ValueType>, ) -> usize

Returns number of bytes which write_values will write, assuming that each call to write_value writes the number of bytes pointed by value_size.

pub fn write_values<F>( &self, output: &mut dyn Write, write_value: F, ) -> Result<()>

where F: FnMut(&mut dyn Write, &ValueType) -> Result<()>,

Writes values to the given output, using write_value to write each value.

pub fn read_values<F>( input: &mut dyn Read, read_value: F, ) -> Result<Box<[ValueType]>>

where F: FnMut(&mut dyn Read) -> Result<ValueType>,

Reads values from the given input, using read_value to read each value.

pub fn write_size_bytes(&self, value_size: ValueSize<'_, ValueType>) -> usize

Returns number of bytes which write will write, assuming that each call to write_value writes the number of bytes pointed by value_size.

pub fn write<F>(&self, output: &mut dyn Write, write_value: F) -> Result<()>

where F: FnMut(&mut dyn Write, &ValueType) -> Result<()>,

Writes self to the given output, using write_value to write each value.

pub fn read<F>(input: &mut dyn Read, read_value: F) -> Result<Self>

where F: FnMut(&mut dyn Read) -> Result<ValueType>,

Reads Coding from the given input, using read_value to read each value.

pub fn levels(&self) -> LevelIterator<'_, ValueType, D>

Returns iterator over the levels of the huffman tree.

pub fn reverse_code(&self, codeword: &mut Code)

Reverse the codeword.

pub fn reversed_code(&self, codeword: Code) -> Code

Returns reversed copy of the given codeword.

pub fn codes(&self) -> CodesIterator<'_, ValueType, D>

Returns iterator over value-codeword pairs.

pub fn reversed_codes(&self) -> ReversedCodesIterator<'_, ValueType, D>

Returns iterator over value-codeword pairs with reversed codewords.

impl<ValueType: Hash + Eq, D: TreeDegree> Coding<ValueType, D>

pub fn code_lengths_ref(&self) -> HashMap<&ValueType, u32>

Returns a map from (references to) values to the lengths of their codes.

pub fn codes_for_values_ref(&self) -> HashMap<&ValueType, Code>

Returns a map from (references to) values to their codes.

pub fn reversed_codes_for_values_ref(&self) -> HashMap<&ValueType, Code>

Returns a map from (references to) values to their reversed codes.

impl<ValueType: Hash + Eq + Clone, D: TreeDegree> Coding<ValueType, D>

pub fn code_lengths(&self) -> HashMap<ValueType, u32>

Returns a map from (clones of) values to the lengths of their codes.

pub fn codes_for_values(&self) -> HashMap<ValueType, Code>

Returns a map from (clones of) values to their codes.

pub fn reversed_codes_for_values(&self) -> HashMap<ValueType, Code>

Returns a map from (clones of) values to their reversed codes.

impl<D: TreeDegree> Coding<u8, D>

pub fn code_lengths_array(&self) -> [u32; 256]

Returns array indexed by values that contains the lengths of their codes.

pub fn codes_for_values_array(&self) -> [Code; 256]

Returns array indexed by values that contains their codes.

pub fn reversed_codes_for_values_array(&self) -> [Code; 256]

Returns array indexed by values that contains their reversed codes.

Trait Implementations

impl<ValueType: GetSize, D> GetSize for Coding<ValueType, D>

const USES_DYN_MEM: bool = true

true if and only if the variables of this type can use dynamic (heap) memory.

fn size_bytes_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self. Same as self.size_bytes() - std::mem::size_of_val(self).

fn size_bytes_content_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self content. It usually equals to size_bytes_dyn(). However, sometimes it is smaller by the amount of memory reserved but not yet used (e.g., size_bytes_content_dyn() only takes into account the length of the vector and not its capacity).

fn size_bytes(&self) -> usize

Returns approximate, total (including heap memory) number of bytes occupied by self.