Struct mayda::monotone::Monotone
[−]
[src]
pub struct Monotone<B> { /* fields omitted */ }
The type of a monotone 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^37 - 2^7) 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, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let mut bits = Monotone::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, 20); let range = bits.access(1..4); assert_eq!(range, vec![5, 7, 15]);
Performance
Decoding does not allocate except for the return value, and decodes around
7.5 GiB/s of decoded integers on difficult inputs. Encoding allocates O(n)
memory (n
in the length of the array), and encodes around 4.5 GiB/s of
decoded integers. Run cargo bench --bench monotone
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 Monotone
objects
from untrusted sources.
A Monotone
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> Monotone<B>
[src]
pub fn new() -> Self
[src]
Creates an empty Monotone
object.
Examples
use mayda::{Encode, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let mut bits = Monotone::new(); bits.encode(&input).unwrap(); let bytes = std::mem::size_of_val(bits.storage()); assert_eq!(bytes, 16);
pub fn from_slice(slice: &[B]) -> Result<Self, Error>
[src]
Creates a Monotone
object that encodes the slice.
Examples
use mayda::{Encode, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let bits = Monotone::from_slice(&input).unwrap(); let output = bits.decode(); assert_eq!(input, output);
pub fn is_empty(&self) -> bool
[src]
Returns true when there are no encoded entries.
Examples
use mayda::Monotone; let mut bits = Monotone::<u32>::new(); assert_eq!(bits.is_empty(), true);
pub fn len(&self) -> usize
[src]
Returns the number of encoded entries. Note that since the length has to
be calculated, Monotone::len()
is more expensive than Slice::len()
.
Examples
use mayda::{Encode, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let mut bits = Monotone::new(); bits.encode(&input).unwrap(); assert_eq!(bits.len(), 6);
pub fn storage(&self) -> &[u32]
[src]
Exposes the word storage of the Monotone
object.
Examples
use mayda::{Encode, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let mut bits = Monotone::new(); bits.encode(&input).unwrap(); let storage = bits.storage(); assert_eq!(storage.len(), 4);
pub unsafe fn mut_storage(&mut self) -> &mut Box<[u32]>
[src]
Exposes the mutable word storage of the Monotone
object.
Safety
A Monotone
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.
pub fn required_width(&self) -> u32
[src]
Returns the width of the encoded integer type.
Examples
use mayda::{Encode, Monotone}; let input: Vec<u32> = vec![1, 5, 7, 15, 20, 27]; let mut bits = Monotone::new(); bits.encode(&input).unwrap(); assert_eq!(bits.required_width(), 32);
Trait Implementations
impl<B: Clone> Clone for Monotone<B>
[src]
fn clone(&self) -> Monotone<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 Monotone<B>
[src]
fn fmt(&self, __arg_0: &mut Formatter) -> Result
[src]
Formats the value using the given formatter. Read more
impl<B: Default> Default for Monotone<B>
[src]
impl<B: Hash> Hash for Monotone<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 Monotone<B>
[src]
fn eq(&self, __arg_0: &Monotone<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: &Monotone<B>) -> bool
[src]
This method tests for !=
.
impl<B: PartialOrd> PartialOrd for Monotone<B>
[src]
fn partial_cmp(&self, __arg_0: &Monotone<B>) -> Option<Ordering>
[src]
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, __arg_0: &Monotone<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: &Monotone<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: &Monotone<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: &Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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 Monotone<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.