pub struct RampTable<T> {
pub index: Vec<u32>,
pub values: Vec<T>,
}
Expand description
Contains a mapping from index (key) to a set of values. Each set of values is stored in order of increasing index (key).
RampTable
is optimized for certain usage patterns. For those patterns, it is an efficient
representation. For other usage patterns, RampTable
may be inefficient or unsuitable.
Common usages are for adjacency lists in graphs, sparse matrices, and in building YACC grammars.
A RampTable
stores its data in two vectors: index
and values
. The index
table contains
offsets into values
. These offsets are stored in non-decreasing order. The numeric difference
between two consecutive entries in values
gives the length of the slice within `values that
corresponds to the items for the lower index.
The usage pattern that RampTable
is designed for is appending a sequence of (key, value)
pairs, where each key is in non-decreasing order. The result is a representation that is
compact (has high data density), has constant-time lookup, and efficiently represents datasets
that have a wide variety of counts of items.
This representation also allows acquiring references to slices that span more than one key.
Terminology:
- key - An integer which identifies an ordered list of values in the table.
- value - One item that is present in the table. Each value is associated with exactly one key.
Note that it is possible to add unowned values to the end of the RampTable
. A well-formed
table will not have any unowned values.
Fields§
§index: Vec<u32>
contains the index into values[] where each entry starts
values: Vec<T>
Implementations§
Source§impl<T> RampTable<T>
impl<T> RampTable<T>
Sourcepub fn with_capacity(keys_capacity: usize, values_capacity: usize) -> Self
pub fn with_capacity(keys_capacity: usize, values_capacity: usize) -> Self
Creates a new, empty RampTable
, with space preallocated for keys and values.
Sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true
if there are no keys in this RampTable
. Equivalent to self.len() == 0
.
Note that a RampTable
may still contain unassociated values even if is_empty
returns
`true.
Sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
The number of keys in this RampTable
. All keys are numbered sequentially.
Sourcepub fn push_value(&mut self, value: T)
pub fn push_value(&mut self, value: T)
Pushes a value onto the end of the RampTable
. The item is not yet associated with any
key. In order to associate all unowned values with the next key, call finish_key
.
Sourcepub fn finish_key(&mut self) -> usize
pub fn finish_key(&mut self) -> usize
Adds a new key to the end of the key list, and implicitly associates all unassociated values with that key.
Example:
let mut rt = RampTable::new();
rt.push_value("foo");
rt.push_value("bar");
rt.finish_key();
assert_eq!(rt.entry_values(0), &["foo", "bar"]);
Sourcepub fn iter(
&self,
) -> impl Iterator<Item = &[T]> + '_ + DoubleEndedIterator + ExactSizeIterator
pub fn iter( &self, ) -> impl Iterator<Item = &[T]> + '_ + DoubleEndedIterator + ExactSizeIterator
Iterates slices of values, one slice for each key.
Example:
let mut rt = RampTable::new();
rt.push_value("foo");
rt.push_value("bar");
rt.finish_key(); // 0
rt.finish_key(); // 1
rt.push_value("alpha");
rt.push_value("bravo");
rt.finish_key(); // 2
let mut ii = rt.iter();
assert_eq!(ii.next(), Some(&["foo", "bar"][..]));
assert_eq!(ii.next(), Some(&[][..]));
assert_eq!(ii.next(), Some(&["alpha", "bravo"][..]));
assert_eq!(ii.next(), None);
Sourcepub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
pub fn iter_mut(&mut self) -> IterMut<'_, T> ⓘ
Iterates mutable slices of values, one slice for each key.
Example:
let mut rt = RampTable::new();
rt.push_value("foo");
rt.push_value("bar");
rt.finish_key(); // 0
rt.iter_mut().next().unwrap()[1] = "BAR";
assert_eq!(rt.entry_values(0), &["foo", "BAR"][..]);
pub fn entry_values_range(&self, index: usize) -> Range<usize>
pub fn entry_values(&self, index: usize) -> &[T]
pub fn entry_values_mut(&mut self, index: usize) -> &mut [T]
Sourcepub fn all_values(&self) -> &[T]
pub fn all_values(&self) -> &[T]
Returns a slice over all values in the table. The returned slice covers values in all keys as well as any unassociated values at the end of the table.
Sourcepub fn all_values_mut(&mut self) -> &mut [T]
pub fn all_values_mut(&mut self) -> &mut [T]
Returns a mutable slice over all values in the table. The returned slice covers values in all keys as well as any unassociated values at the end of the table.
Sourcepub fn iter_pairs(&self) -> impl Iterator<Item = (usize, &T)>
pub fn iter_pairs(&self) -> impl Iterator<Item = (usize, &T)>
Iterates pairs of (key, value)
items. The key
values are guaranteed to be iterated in
non-decreasing order.
pub fn iter_pairs_manual(&self) -> impl Iterator<Item = (usize, &T)>
Sourcepub fn num_values(&self) -> usize
pub fn num_values(&self) -> usize
Returns the total number of values (in all entries) in the table.
Sourcepub fn push_entry_copy(&mut self, values: &[T])where
T: Copy,
pub fn push_entry_copy(&mut self, values: &[T])where
T: Copy,
Pushes a new key-value entry in the table, copying values from a slice.
If the table contained any previously unassociated values, then these
become part of this new entry (and they precede the values passed in
values
).
Sourcepub fn push_entry_clone(&mut self, values: &[T])where
T: Clone,
pub fn push_entry_clone(&mut self, values: &[T])where
T: Clone,
Pushes a new key-value entry in the table, cloning values from a slice.
If the table contained any previously unassociated values, then these
become part of this new entry (and they precede the values passed in
values
).
Sourcepub fn push_entry_extend<I: Iterator<Item = T>>(&mut self, values: I)
pub fn push_entry_extend<I: Iterator<Item = T>>(&mut self, values: I)
Pushes a new key-value entry in the table, by iterating values.
If the table contained any previously unassociated values, then these
become part of this new entry (and they precede the values passed in
values
).