Struct ramp_table::RampTable

pub struct RampTable<T> {
    pub index: Vec<u32>,
    pub values: Vec<T>,
}

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>

Methods

impl<T> RampTable<T>

pub fn new() -> Self

Creates a new, empty RampTable.

pub fn with_capacity(keys_capacity: usize, values_capacity: usize) -> Self

Creates a new, empty RampTable, with space preallocated for keys and values.

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.

pub fn len(&self) -> usize

The number of keys in this RampTable. All keys are numbered sequentially.

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.

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"]);

pub fn clear(&mut self)

Deletes all keys and values from the RampTable.

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);

Important traits for IterMut<'a, T>

impl<'a, T> Iterator for IterMut<'a, T> type Item = &'a mut [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]

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.

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.

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)>

pub fn num_values(&self) -> usize

Returns the total number of values (in all entries) in the table.

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).

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).

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).

Trait Implementations

impl<T: Clone> Clone for RampTable<T>

fn clone(&self) -> RampTable<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for RampTable<T>

fn fmt(&self, fmt: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T> Default for RampTable<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T: Eq> Eq for RampTable<T>

impl<T> Index<usize> for RampTable<T>

type Output = [T]

The returned type after indexing.

fn index(&self, i: usize) -> &[T]

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for RampTable<T>

fn index_mut(&mut self, i: usize) -> &mut [T]

Performs the mutable indexing (container[index]) operation.

impl<T: PartialEq> PartialEq<RampTable<T>> for RampTable<T>

fn eq(&self, other: &RampTable<T>) -> bool

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

fn ne(&self, other: &RampTable<T>) -> bool

This method tests for !=.

impl<T> StructuralEq for RampTable<T>

impl<T> StructuralPartialEq for RampTable<T>