Struct datazoo::packed_int_array::PackedIntArray

pub struct PackedIntArray<K: Index, V: From<u32>, Eq = ()> { /* private fields */ }

An associative array of small integers.

A 1-to-(1|0) mapping of integers to integers, in packed storage. It might help to think of this as a very compact Vec<Option<V>>.

See IndexMultimap for 1-to-N mapping.

Design

A typical array of integers (consider Vec<u32>) takes 32 bits per entry, a PackedIntArray only takes as much bit per entry as the largest entry.

// vec![12_u32, 2, 5, 8, 10, 9];
// size in memory: 24 stack bytes + 24 heap bytes
[cap; len; ptr] -> [ // binary
0000_0000_0000_0000_0000_0000_0000_1100 // 12
0000_0000_0000_0000_0000_0000_0000_0010 // 2
0000_0000_0000_0000_0000_0000_0000_0101 // 5
0000_0000_0000_0000_0000_0000_0000_1000 // 8
0000_0000_0000_0000_0000_0000_0000_1010 // 10
0000_0000_0000_0000_0000_0000_0000_1001 // 9
]
// PackedIntArray<u32, u32> = [12, 2, 5, 8, 10, 9];
// size in memory: 24 stack bytes + 4 heap bytes
[value_width; len; ptr] -> [ // binary
1100 // 12
0010 // 2
0101 // 5
1000 // 8
1010 // 10
1001 // 9
1111 // We use [u32] for storage, byte count is always
1111 // multiple of 4, empty trailing slots are filled with 1s.
]

Now, take Vec<Option<u32>>. [12, 2, 5, 8, 10, 9].map(Some) takes twice as much heap space. 48 bytes! PackedIntArray has special handling of empty slots, so they take exactly as much space as filled slots.

We went from 48 bytes to 4 bytes. We basically can divide by ten memory usage.

Note that while this may take less memory, it requires much more processing.

PartialEq implementation

The default PackedIntArray equality just compares the values as they are stored in the indexmap.

However, if your V’s implementation of equality differs from basic integer equality, you can use the ValueEq type as described in the ValueEq docs.

Example

use datazoo::PackedIntArray;

let mut map = PackedIntArray::<usize, u32>::with_capacity(200, 100);

map.set(&10, &2);
map.set(&11, &5);
map.set(&19, &9);
map.set(&15, &1);

map.set(&31, &22);
map.set(&30, &20);
map.set(&32, &21);

assert_eq!(map.get(&10), Some(2));
assert_eq!(map.get(&32), Some(21));

// zero is distinct from no values
assert_eq!(map.get(&13), None);
map.set(&13, &0);
assert_eq!(map.get(&13), Some(0));

// values and indices set out of bound do nothing.
// `set` returns `None` if they are out of bound.
assert_eq!(map.set(&350, &3), None);
assert_eq!(map.get(&350), None);

assert_eq!(map.set(&31, &200), None);
assert_eq!(map.get(&31), Some(22));

// Note that not _all_ values over the provided max_key and max_value are
// forbidden. You can't rely on them being available, but neither can you
// rely on them being never set. (max_key = 199, max_value = 99)
assert_eq!(map.set(&200, &3), Some(()));
assert_eq!(map.get(&200), Some(3));

assert_eq!(map.set(&200, &111), Some(()));
assert_eq!(map.get(&200), Some(111));

// It is also possible to use `collect` to create an `IndexMap`
let other_map: PackedIntArray<usize, u32> = [
    (10, 2),
    (11, 5),
    (19, 9),
    (15, 1),
    (31, 22),
    (30, 20),
    (32, 21),
    (13, 0),
    (200, 3),
    (200, 111),
].into_iter().collect();

assert_eq!(map, other_map);

Implementations

impl<K: Index, V: From<u32>, Eq> PackedIntArray<K, V, Eq>

pub fn with_capacity(key_len: usize, value_len: u32) -> Self

Initialize a PackedIntArray with static size.

You can always insert:

• Keys: (0 ..= key_len-1)
• Values: (0 ..= value_len-1)

In the case where either key_len or value_len is zero, you won’t be able to insert anything. set will do nothing, get always returns None.

When value_len equals 1, this is equivalent to a Bitset with key_len bits. When value_len is between u32::MAX / 2 and u32::MAX, this is equivalent to a Vec<u32>.

Some larger values may be accepted. Specifically, the following will be accepted in the current implementation. This is not stable, do not assume this will always be true:

• Values: any value smaller or equal to 2^vwidth - 1.
• Keys: ⌊LMO₃₂(max_key · vwidth) / vwidth⌋

Where:

• ⌈x⌉ = ceil(x)
• ⌊x⌋ = floor(x)
• LMOn(x) = n · ⌈x / n⌉ (lowest multiple of n over x)
• vwidth = ⌈log₂(max_value + 1)⌉ (width in bits of a value)

pub fn capacity(&self) -> usize

How many keys at most this contains.

Unlike a HashMap, the capacity also represents the upper limit of key values (all keys are smaller than capacity).

This might not be the key_len provided as argument to Self::with_capacity, as the underlying array aligns the number of bits to the next multiple of 32.

pub fn get(&self, index: &K) -> Option<V>

Get the value associated with index, None if there isn’t.

pub fn remove(&mut self, key: &K)

Remove value associated with key. Afterward, calling map.get(key) will return None.

pub fn set(&mut self, key: &K, value: &V) -> Option<()>where V: Index,

Set value of key to value.

Returns None if either value or key is out of bound.

Example

let mut map = PackedIntArray::<usize, u32>::with_capacity(200, 100);
assert_eq!(map.get(&32), None);

map.set(&32, &28);
assert_eq!(map.get(&32), Some(28));

map.set(&32, &0);
map.set(&33, &12);
assert_eq!(map.get(&32), Some(0));
assert_eq!(map.get(&33), Some(12));

pub fn set_expanding_values(&mut self, key: &K, value: &V) -> Option<()>where V: Index,

Set value of key to value.

Increase the size of the buffer if value is out of bound. If key is out of bound, does nothing and returns None.

pub fn iter(&self) -> impl Iterator<Item = (K, V)> + '_

Iterate over all values.

pub fn rev_iter(&self) -> impl Iterator<Item = (K, V)> + '_

Iterate over all values (reversed).

Trait Implementations

impl<K: Clone + Index, V: Clone + From<u32>, Eq: Clone> Clone for PackedIntArray<K, V, Eq>

fn clone(&self) -> PackedIntArray<K, V, Eq>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, Eq> Debug for PackedIntArray<K, V, Eq>where K: Index + Debug, V: From<u32> + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: Index, V: From<u32>, Eq> Default for PackedIntArray<K, V, Eq>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Index, V: From<u32> + Index> FromIterator<(K, V)> for PackedIntArray<K, V>

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self

Create a PackedIntArray where value at k will be value in (key, value) the last item where key == k.

Note that all K and V will be dropped.

impl<K: Index, V: From<u32>> PartialEq for PackedIntArray<K, V>

fn eq(&self, other: &Self) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: Index, V: From<u32> + PartialEq> PartialEq for PackedIntArray<K, V, ValueEq>

fn eq(&self, other: &Self) -> bool

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.