Struct mayda::unimodal::Unimodal
[−]
[src]
pub struct Unimodal<B> { /* 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 (237 - 27) entries, or
about 512 GiB of u32
s. 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<B>
[src]
fn new() -> Self
[src]
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>
[src]
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
[src]
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
[src]
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]
[src]
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]>
[src]
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
[src]
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: Clone> Clone for Unimodal<B>
[src]
fn clone(&self) -> Unimodal<B>
[src]
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl<B: Debug> Debug for Unimodal<B>
[src]
impl<B: Default> Default for Unimodal<B>
[src]
impl<B: Hash> Hash for Unimodal<B>
[src]
fn hash<__HB: Hasher>(&self, __arg_0: &mut __HB)
[src]
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0[src]
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<B: PartialEq> PartialEq for Unimodal<B>
[src]
fn eq(&self, __arg_0: &Unimodal<B>) -> bool
[src]
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, __arg_0: &Unimodal<B>) -> bool
[src]
This method tests for !=
.
impl<B: PartialOrd> PartialOrd for Unimodal<B>
[src]
fn partial_cmp(&self, __arg_0: &Unimodal<B>) -> Option<Ordering>
[src]
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, __arg_0: &Unimodal<B>) -> bool
[src]
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, __arg_0: &Unimodal<B>) -> bool
[src]
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<B>) -> bool
[src]
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, __arg_0: &Unimodal<B>) -> bool
[src]
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<B: Bits> Encode<B> for Unimodal<B>
[src]
fn encode(&mut self, input: &[B]) -> Result<(), Error>
[src]
Encodes the slice into the Encode
object. Read more
fn decode(&self) -> Vec<B>
[src]
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
[src]
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
impl<B: Bits> Access<usize> for Unimodal<B>
[src]
type Output = B
The type returned by the access operation.
fn access(&self, index: usize) -> B
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<Range<usize>> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, range: Range<usize>) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<RangeFrom<usize>> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, range: RangeFrom<usize>) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<RangeTo<usize>> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, range: RangeTo<usize>) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<RangeFull> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, _: RangeFull) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<RangeInclusive<usize>> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, range: RangeInclusive<usize>) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> Access<RangeToInclusive<usize>> for Unimodal<B>
[src]
type Output = Vec<B>
The type returned by the access operation.
fn access(&self, range: RangeToInclusive<usize>) -> Vec<B>
[src]
The method for the access foo.access(bar)
operation.
impl<B: Bits> AccessInto<Range<usize>, B> for Unimodal<B>
[src]
fn access_into(&self, range: Range<usize>, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.
impl<B: Bits> AccessInto<RangeFrom<usize>, B> for Unimodal<B>
[src]
fn access_into(&self, range: RangeFrom<usize>, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.
impl<B: Bits> AccessInto<RangeTo<usize>, B> for Unimodal<B>
[src]
fn access_into(&self, range: RangeTo<usize>, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.
impl<B: Bits> AccessInto<RangeFull, B> for Unimodal<B>
[src]
fn access_into(&self, _: RangeFull, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.
impl<B: Bits> AccessInto<RangeInclusive<usize>, B> for Unimodal<B>
[src]
fn access_into(&self, range: RangeInclusive<usize>, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.
impl<B: Bits> AccessInto<RangeToInclusive<usize>, B> for Unimodal<B>
[src]
fn access_into(&self, range: RangeToInclusive<usize>, output: &mut [B]) -> usize
[src]
The method for the access foo.access_into(bar, slice)
operation.