Struct mayda::monotone::Monotone
[−]
[src]
pub struct Monotone<B> { // some 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 (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, 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]
fn new() -> Self
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);
fn from_slice(slice: &[B]) -> Result<Self, Error>
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);
fn is_empty(&self) -> bool
Returns true when there are no encoded entries.
Examples
use mayda::Monotone; let mut bits = Monotone::<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, 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);
fn storage(&self) -> &[u32]
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);
unsafe fn mut_storage(&mut self) -> &mut Box<[u32]>
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.
fn required_width(&self) -> u32
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: PartialOrd> PartialOrd for Monotone<B>
[src]
fn partial_cmp(&self, __arg_0: &Monotone<B>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, __arg_0: &Monotone<B>) -> bool
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
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
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
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 Monotone<B>
[src]
fn eq(&self, __arg_0: &Monotone<B>) -> bool
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
This method tests for !=
.
impl<B: Hash> Hash for Monotone<B>
[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 Monotone<B>
[src]
impl<B: Debug> Debug for Monotone<B>
[src]
impl<B: Clone> Clone for Monotone<B>
[src]
fn clone(&self) -> Monotone<B>
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<B> for Monotone<B>
[src]
fn encode(&mut self, input: &[B]) -> Result<(), Error>
Encodes the slice into the Encode
object. Read more
fn decode(&self) -> Vec<B>
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
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
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>
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>
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>
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>
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>
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>
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
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
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
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
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
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
The method for the access foo.access_into(bar, slice)
operation.