Source code
Revision control
Copy as Markdown
Other Tools
//Note: this could be the only place where we need `SmallVec`.
//TODO: consider getting rid of it.
use smallvec::SmallVec;
use std::{fmt::Debug, iter, ops::Range};
/// Structure that keeps track of a I -> T mapping,
/// optimized for a case where keys of the same values
/// are often grouped together linearly.
#[derive(Clone, Debug, PartialEq)]
pub(crate) struct RangedStates<I, T> {
/// List of ranges, each associated with a singe value.
/// Ranges of keys have to be non-intersecting and ordered.
ranges: SmallVec<[(Range<I>, T); 1]>,
}
impl<I: Copy + Ord, T: Copy + PartialEq> RangedStates<I, T> {
pub fn from_range(range: Range<I>, value: T) -> Self {
Self {
ranges: iter::once((range, value)).collect(),
}
}
/// Construct a new instance from a slice of ranges.
#[cfg(test)]
pub fn from_slice(values: &[(Range<I>, T)]) -> Self {
Self {
ranges: values.iter().cloned().collect(),
}
}
pub fn iter(&self) -> impl Iterator<Item = &(Range<I>, T)> + Clone {
self.ranges.iter()
}
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut (Range<I>, T)> {
self.ranges.iter_mut()
}
/// Check that all the ranges are non-intersecting and ordered.
/// Panics otherwise.
#[cfg(test)]
fn check_sanity(&self) {
for a in self.ranges.iter() {
assert!(a.0.start < a.0.end);
}
for (a, b) in self.ranges.iter().zip(self.ranges[1..].iter()) {
assert!(a.0.end <= b.0.start);
}
}
/// Merge the neighboring ranges together, where possible.
pub fn coalesce(&mut self) {
let mut num_removed = 0;
let mut iter = self.ranges.iter_mut();
let mut cur = match iter.next() {
Some(elem) => elem,
None => return,
};
for next in iter {
if cur.0.end == next.0.start && cur.1 == next.1 {
num_removed += 1;
cur.0.end = next.0.end;
next.0.end = next.0.start;
} else {
cur = next;
}
}
if num_removed != 0 {
self.ranges.retain(|pair| pair.0.start != pair.0.end);
}
}
pub fn iter_filter<'a>(
&'a self,
range: &'a Range<I>,
) -> impl Iterator<Item = (Range<I>, &T)> + 'a {
self.ranges
.iter()
.filter(move |&(inner, ..)| inner.end > range.start && inner.start < range.end)
.map(move |(inner, v)| {
let new_range = inner.start.max(range.start)..inner.end.min(range.end);
(new_range, v)
})
}
/// Split the storage ranges in such a way that there is a linear subset of
/// them occupying exactly `index` range, which is returned mutably.
///
/// Gaps in the ranges are filled with `default` value.
pub fn isolate(&mut self, index: &Range<I>, default: T) -> &mut [(Range<I>, T)] {
//TODO: implement this in 2 passes:
// 1. scan the ranges to figure out how many extra ones need to be inserted
// 2. go through the ranges by moving them them to the right and inserting the missing ones
let mut start_pos = match self.ranges.iter().position(|pair| pair.0.end > index.start) {
Some(pos) => pos,
None => {
let pos = self.ranges.len();
self.ranges.push((index.clone(), default));
return &mut self.ranges[pos..];
}
};
{
let (range, value) = self.ranges[start_pos].clone();
if range.start < index.start {
self.ranges[start_pos].0.start = index.start;
self.ranges
.insert(start_pos, (range.start..index.start, value));
start_pos += 1;
}
}
let mut pos = start_pos;
let mut range_pos = index.start;
loop {
let (range, value) = self.ranges[pos].clone();
if range.start >= index.end {
self.ranges.insert(pos, (range_pos..index.end, default));
pos += 1;
break;
}
if range.start > range_pos {
self.ranges.insert(pos, (range_pos..range.start, default));
pos += 1;
range_pos = range.start;
}
if range.end >= index.end {
if range.end != index.end {
self.ranges[pos].0.start = index.end;
self.ranges.insert(pos, (range_pos..index.end, value));
}
pos += 1;
break;
}
pos += 1;
range_pos = range.end;
if pos == self.ranges.len() {
self.ranges.push((range_pos..index.end, default));
pos += 1;
break;
}
}
&mut self.ranges[start_pos..pos]
}
/// Helper method for isolation that checks the sanity of the results.
#[cfg(test)]
pub fn sanely_isolated(&self, index: Range<I>, default: T) -> Vec<(Range<I>, T)> {
let mut clone = self.clone();
let result = clone.isolate(&index, default).to_vec();
clone.check_sanity();
result
}
}
#[cfg(test)]
mod test {
//TODO: randomized/fuzzy testing
use super::RangedStates;
#[test]
fn sane_good() {
let rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9)]);
rs.check_sanity();
}
#[test]
#[should_panic]
fn sane_empty() {
let rs = RangedStates::from_slice(&[(1..4, 9u8), (5..5, 9)]);
rs.check_sanity();
}
#[test]
#[should_panic]
fn sane_intersect() {
let rs = RangedStates::from_slice(&[(1..4, 9u8), (3..5, 9)]);
rs.check_sanity();
}
#[test]
fn coalesce() {
let mut rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9), (5..7, 1), (8..9, 1)]);
rs.coalesce();
rs.check_sanity();
assert_eq!(rs.ranges.as_slice(), &[(1..5, 9), (5..7, 1), (8..9, 1),]);
}
#[test]
fn isolate() {
let rs = RangedStates::from_slice(&[(1..4, 9u8), (4..5, 9), (5..7, 1), (8..9, 1)]);
assert_eq!(&rs.sanely_isolated(4..5, 0), &[(4..5, 9u8),]);
assert_eq!(
&rs.sanely_isolated(0..6, 0),
&[(0..1, 0), (1..4, 9u8), (4..5, 9), (5..6, 1),]
);
assert_eq!(&rs.sanely_isolated(8..10, 1), &[(8..9, 1), (9..10, 1),]);
assert_eq!(
&rs.sanely_isolated(6..9, 0),
&[(6..7, 1), (7..8, 0), (8..9, 1),]
);
}
}