Struct mayda::unimodal::Unimodal [−] [src]

pub struct Unimodal<B> {
    // some fields omitted
}

The type of a unimodal encoded integer array. Designed for moderate compression and efficient decoding through the Encode trait, and efficient random access through the Access and AccessInto traits.

Support is provided for arrays with as many as (2³⁷ - 2⁷⁾ entries, or about 512 GiB of u32s. If your application requires more than that, you should probably be designing your own data structure anyway.

Examples

use mayda::{Access, Encode, Unimodal};

let input: Vec<u32> = vec![1, 4, 2, 8, 5, 7];
let mut bits = Unimodal::new();
bits.encode(&input).unwrap();

let length = bits.len();
assert_eq!(length, 6);

let output = bits.decode();
assert_eq!(input, output);

let value = bits.access(4);
assert_eq!(value, 5);

let range = bits.access(1..4);
assert_eq!(range, vec![4, 2, 8]);

Performance

Decoding does not allocate except for the return value, and decodes around 6 GiB/s of decoded integers on difficult inputs. Encoding allocates O(n) memory (n in the length of the array), and encodes around 250 MiB/s of decoded integers. Around three-fourths of the encoding runtime is due to the algorithm utility::select_m used to find the median of a block. Run cargo bench --bench unimodal for performance numbers on your setup.

The performance (speed and compression) degrades gradually as the number of entries falls below 128.

Safety

As a general rule, you should not decode or access Unimodal objects from untrusted sources.

A Unimodal object performs unsafe pointer operations during encoding and decoding. Changing the header information with mut_storage can cause data to be written to or read from arbitrary addresses in memory.

That said, the situation is the same for any of the data structures in the standard library (consider the set_len method of a Vec).

Methods

`impl<B: Bits> Unimodal`
[src]

`fn new() -> Self`

Creates an empty Unimodal object.

Examples

use mayda::{Encode, Unimodal};

let input: Vec<u32> = vec![1, 4, 2, 8, 5, 7];
let mut bits = Unimodal::new();
bits.encode(&input).unwrap();

let bytes = std::mem::size_of_val(bits.storage());
assert_eq!(bytes, 16);

`fn from_slice(slice: &[B]) -> Result<Self, Error>`

Creates a Unimodal object that encodes the slice.

Examples

use mayda::{Encode, Unimodal};

let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27];
let bits = Unimodal::from_slice(&input).unwrap();

let output = bits.decode();
assert_eq!(input, output);

`fn is_empty(&self) -> bool`

Returns true when there are no encoded entries.

Examples

use mayda::Unimodal;

let mut bits = Unimodal::<u32>::new();
assert_eq!(bits.is_empty(), true);

`fn len(&self) -> usize`

Returns the number of encoded entries. Note that since the length has to be calculated, Unimodal::len() is more expensive than Slice::len().

Examples

use mayda::{Encode, Unimodal};

let input: Vec<u32> = vec![1, 4, 2, 8, 5, 7];
let mut bits = Unimodal::new();
bits.encode(&input).unwrap();

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

`fn storage(&self) -> &[u32]`

Exposes the word storage of the Unimodal object.

Examples

use mayda::{Encode, Unimodal};

let input: Vec<u32> = vec![1, 4, 2, 8, 5, 7];
let mut bits = Unimodal::new();
bits.encode(&input).unwrap();

let storage = bits.storage();
assert_eq!(storage.len(), 4);

`unsafe fn mut_storage(&mut self) -> &mut Box<[u32]>`

Exposes the mutable word storage of the Unimodal object.

Safety

A Unimodal object performs unsafe pointer operations during encoding and decoding. Changing the header information can cause data to be written to or read from arbitrary addresses in memory.

`fn required_width(&self) -> u32`

Returns the width of the encoded integer type.

Examples

use mayda::{Encode, Unimodal};

let input: Vec<u32> = vec![1, 4, 2, 8, 5, 7];
let mut bits = Unimodal::new();
bits.encode(&input).unwrap();

assert_eq!(bits.required_width(), 32);

Trait Implementations

`impl<B: PartialOrd> PartialOrd for Unimodal`
[src]

`fn partial_cmp(&self, __arg_0: &Unimodal) -> Option<Ordering>`

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

`fn lt(&self, __arg_0: &Unimodal) -> bool`

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

`fn le(&self, __arg_0: &Unimodal) -> bool`

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

`fn gt(&self, __arg_0: &Unimodal) -> bool`

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

`fn ge(&self, __arg_0: &Unimodal) -> bool`

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

`impl<B: PartialEq> PartialEq for Unimodal`
[src]

`fn eq(&self, __arg_0: &Unimodal) -> bool`

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

`fn ne(&self, __arg_0: &Unimodal) -> bool`

This method tests for !=.

`impl<B: Hash> Hash for Unimodal`
[src]

`fn hash<HB: Hasher>(&self, arg_0: &mut __HB)`

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

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

Feeds a slice of this type into the state provided.

`impl<B: Default> Default for Unimodal`
[src]

`fn default() -> Unimodal`

Returns the "default value" for a type. Read more

`impl<B: Debug> Debug for Unimodal`
[src]

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

Formats the value using the given formatter.

`impl<B: Clone> Clone for Unimodal`
[src]

`fn clone(&self) -> Unimodal`

Returns a copy of the value. Read more

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

Performs copy-assignment from source. Read more

`impl<B: Bits> Encode for Unimodal`
[src]

`fn encode(&mut self, input: &[B]) -> Result<(), Error>`

Encodes the slice into the Encode object. Read more

`fn decode(&self) -> Vec`

Decodes the contents of the Encode object. Returns a vector because ownership of the returned value must be given to the caller. Read more

`fn decode_into(&self, output: &mut [B]) -> usize`

Decodes the contents of the Encode object and writes the result into the slice provided. More efficient than decode if the slice is already allocated. Returns the number of decoded entries. Read more