Struct RampTable

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

Source

pub fn new() -> Self

Creates a new, empty RampTable.

Source

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

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

Source

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.

Source

pub fn len(&self) -> usize

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

Source

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.

Source

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

pub fn clear(&mut self)

Deletes all keys and values from the RampTable.

Source

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

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

pub fn entry_values_range(&self, index: usize) -> Range<usize>

Source

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

Source

pub fn entry_values_mut(&mut self, index: usize) -> &mut [T]

Source

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.

Source

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.

Source

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.

Source

pub fn iter_pairs_manual(&self) -> impl Iterator<Item = (usize, &T)>

Source

pub fn num_values(&self) -> usize

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

Source

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

Source

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

Source

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§

Source§

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

Source§

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

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

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

Source§

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

Formats the value using the given formatter. Read more
Source§

impl<T> Default for RampTable<T>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

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

Source§

type Output = [T]

The returned type after indexing.
Source§

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

Performs the indexing (container[index]) operation. Read more
Source§

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

Source§

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

Performs the mutable indexing (container[index]) operation. Read more
Source§

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

Source§

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

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

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

Source§

impl<T> StructuralPartialEq for RampTable<T>

Auto Trait Implementations§

§

impl<T> Freeze for RampTable<T>

§

impl<T> RefUnwindSafe for RampTable<T>
where T: RefUnwindSafe,

§

impl<T> Send for RampTable<T>
where T: Send,

§

impl<T> Sync for RampTable<T>
where T: Sync,

§

impl<T> Unpin for RampTable<T>
where T: Unpin,

§

impl<T> UnwindSafe for RampTable<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dst: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dst. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.