ramp_table/lib.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
use core::ops::Range;
/// 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.
#[derive(Clone, Eq, PartialEq)]
pub struct RampTable<T> {
/// contains the index into values[] where each entry starts
pub index: Vec<u32>,
pub values: Vec<T>,
}
impl<T> Default for RampTable<T> {
fn default() -> Self {
Self {
index: vec![0],
values: Vec::new(),
}
}
}
impl<T> RampTable<T> {
/// Creates a new, empty `RampTable`.
pub fn new() -> Self {
Self {
index: vec![0],
values: Vec::new(),
}
}
/// Creates a new, empty `RampTable`, with space preallocated for keys and values.
pub fn with_capacity(keys_capacity: usize, values_capacity: usize) -> Self {
let mut table = Self {
index: Vec::with_capacity(keys_capacity + 1),
values: Vec::with_capacity(values_capacity),
};
table.index.push(0);
table
}
/// 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 is_empty(&self) -> bool {
self.index.len() == 1
}
/// The number of keys in this `RampTable`. All keys are numbered sequentially.
pub fn len(&self) -> usize {
self.index.len() - 1
}
/// 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 push_value(&mut self, value: T) {
self.values.push(value);
}
/// Adds a new key to the end of the key list, and implicitly associates all unassociated values
/// with that key.
///
/// Example:
///
/// ```
/// # use ramp_table::RampTable;
/// 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 finish_key(&mut self) -> usize {
let key = self.index.len() - 1;
self.index.push(self.values.len() as u32);
key
}
/// Deletes all keys and values from the `RampTable`.
pub fn clear(&mut self) {
self.values.clear();
self.index.clear();
self.index.push(0);
}
/// Iterates slices of values, one slice for each key.
///
/// Example:
///
/// ```
/// # use ramp_table::RampTable;
/// 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);
/// ```
pub fn iter(
&self,
) -> impl Iterator<Item = &[T]> + '_ + DoubleEndedIterator + ExactSizeIterator {
self.index
.windows(2)
.map(move |w| &self.values[w[0] as usize..w[1] as usize])
}
/// Iterates mutable slices of values, one slice for each key.
///
/// Example:
///
/// ```
/// # use ramp_table::RampTable;
/// 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 iter_mut(&mut self) -> IterMut<'_, T> {
let mut index_iter = self.index.iter();
let last_index = (*index_iter.next().unwrap()) as usize;
IterMut {
last_index,
index_iter,
values: &mut self.values,
}
}
pub fn entry_values_range(&self, index: usize) -> Range<usize> {
self.index[index] as usize..self.index[index + 1] as usize
}
pub fn entry_values(&self, index: usize) -> &[T] {
&self.values[self.entry_values_range(index)]
}
pub fn entry_values_mut(&mut self, index: usize) -> &mut [T] {
let range = self.entry_values_range(index);
&mut self.values[range]
}
/// 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(&self) -> &[T] {
&self.values
}
/// 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 all_values_mut(&mut self) -> &mut [T] {
&mut self.values
}
/// Iterates pairs of `(key, value)` items. The `key` values are guaranteed to be iterated in
/// non-decreasing order.
pub fn iter_pairs(&self) -> impl Iterator<Item = (usize, &'_ T)> {
self.iter()
.enumerate()
.map(move |(i, values)| values.iter().map(move |v| (i, v)))
.flatten()
}
pub fn iter_pairs_manual(&self) -> impl Iterator<Item = (usize, &'_ T)> {
struct Pairs<'a, T> {
value_iter: core::slice::Iter<'a, T>,
index_iter: core::slice::Iter<'a, u32>,
current_key: usize,
current_index: usize,
num_values: usize,
}
impl<'a, T> Iterator for Pairs<'a, T> {
type Item = (usize, &'a T);
fn next(&mut self) -> Option<Self::Item> {
if let Some(value) = self.value_iter.next() {
// What key is this value for?
while self.num_values == 0 {
let next_index = *self.index_iter.next().unwrap() as usize;
self.num_values = next_index - self.current_index;
self.current_index = next_index;
self.current_key += 1;
}
// TODO: current_key is not correct yet
self.num_values -= 1;
Some((self.current_key, value))
} else {
None
}
}
}
Pairs {
value_iter: self.values.iter(),
index_iter: self.index.iter(),
current_key: 0,
current_index: 0,
num_values: 0,
}
}
/// Returns the total number of values (in all entries) in the table.
pub fn num_values(&self) -> usize {
self.values.len()
}
/// 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_copy(&mut self, values: &[T])
where
T: Copy,
{
self.values.extend(values.iter());
self.finish_key();
}
/// 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_clone(&mut self, values: &[T])
where
T: Clone,
{
self.values.extend(values.iter().cloned());
self.finish_key();
}
/// 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`).
pub fn push_entry_extend<I: Iterator<Item = T>>(&mut self, values: I) {
self.values.extend(values);
self.finish_key();
}
}
impl<T> core::ops::Index<usize> for RampTable<T> {
type Output = [T];
fn index(&self, i: usize) -> &[T] {
self.entry_values(i)
}
}
impl<T> core::ops::IndexMut<usize> for RampTable<T> {
fn index_mut(&mut self, i: usize) -> &mut [T] {
self.entry_values_mut(i)
}
}
pub struct IterMut<'a, T> {
last_index: usize,
index_iter: core::slice::Iter<'a, u32>,
values: &'a mut [T],
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut [T];
fn next(&mut self) -> Option<Self::Item> {
if let Some(&index) = self.index_iter.next() {
let values = std::mem::replace(&mut self.values, &mut []);
let entry_len = index as usize - self.last_index;
let (head, tail) = values.split_at_mut(entry_len);
self.values = tail;
self.last_index = index as usize;
Some(head)
} else {
None
}
}
}
use core::fmt::{Debug, Formatter};
impl<T: Debug> Debug for RampTable<T> {
fn fmt(&self, fmt: &mut Formatter<'_>) -> core::fmt::Result {
fmt.debug_map()
.entries(
self.iter()
.enumerate()
.filter(|(_, values)| !values.is_empty()),
)
.finish()
}
}