use core::{ops::{Bound, Deref, DerefMut, RangeBounds}, slice::SliceIndex};
use alloc::{vec, vec::Vec};
#[cfg(feature = "deku")]
use deku::{ctx::{Endian, Limit}, no_std_io::{Read, Seek, Write}, prelude::*};
use crate::{Delta, Diff};
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Commit<D: Delta, M> {
delta: D,
meta: M,
}
impl<D: Delta, M> Commit<D, M> {
pub fn new(delta: D, meta: M) -> Self {
Self {
delta,
meta,
}
}
pub fn new_with_default(delta: D) -> Self
where
M: Default,
{
Self::new(
delta,
M::default(),
)
}
pub fn meta(&self) -> &M {
&self.meta
}
}
impl<D: Delta, M> Deref for Commit<D, M> {
type Target = D;
fn deref(&self) -> &Self::Target {
&self.delta
}
}
#[cfg(feature = "deku")]
impl<D, M, Ctx1, Ctx2> DekuWriter<(Ctx1, Ctx2)> for Commit<D, M>
where
D: Delta + DekuWriter<Ctx1>,
M: DekuWriter<Ctx2>,
{
fn to_writer<W: Write + Seek>(&self, writer: &mut Writer<W>, (ctx1, ctx2): (Ctx1, Ctx2)) -> Result<(), DekuError> {
self.delta.to_writer(writer, ctx1)?;
self.meta.to_writer(writer, ctx2)
}
}
#[cfg(feature = "deku")]
impl<'a, D, M, Ctx1, Ctx2> DekuReader<'a, (Ctx1, Ctx2)> for Commit<D, M>
where
D: Delta + DekuReader<'a, Ctx1>,
M: DekuReader<'a, Ctx2>,
{
fn from_reader_with_ctx<R: Read + Seek>(reader: &mut Reader<R>, (ctx1, ctx2): (Ctx1, Ctx2),) -> Result<Self, DekuError>
where
Self: Sized
{
let delta = D::from_reader_with_ctx(reader, ctx1)?;
let meta = M::from_reader_with_ctx(reader, ctx2)?;
Ok(Self {
delta,
meta
})
}
}
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Timeline<D: Delta, M = ()> {
commits: Vec<Commit<D, M>>,
}
impl<D: Delta, M> Timeline<D, M> {
pub fn new() -> Self {
Self {
commits: Vec::new(),
}
}
pub fn push(&mut self, commit: Commit<D, M>) {
self.commits.push(commit);
}
pub fn pop(&mut self) -> Option<Commit<D, M>> {
self.commits.pop()
}
pub fn truncate(&mut self, len: usize) {
self.commits.truncate(len);
}
pub fn clear(&mut self) {
self.commits.clear();
}
pub fn pop_aggregate(&mut self, n: usize) -> Option<D> {
if n > self.len() {
return None;
}
let start = self.len() - n;
self.commits.drain(start..).map(|c| c.delta).reduce(|mut a, b| {
a.aggregate_owned(b);
a
})
}
fn get_starting_index(&self, bound: Bound<&usize>) -> Option<usize> {
let i = match bound {
Bound::Excluded(i) => *i + 1,
Bound::Included(i) => *i,
Bound::Unbounded => 0,
};
if i < self.len() {
Some(i)
} else {
None
}
}
fn get_ending_index(&self, bound: Bound<&usize>) -> Option<usize> {
let i = match bound {
Bound::Excluded(i) => *i,
Bound::Included(i) => *i + 1,
Bound::Unbounded => self.len(),
};
if i <= self.len() {
Some(i)
} else {
None
}
}
fn get_bounds(&self, range: impl RangeBounds<usize>) -> Option<(usize, usize)> {
let start = self.get_starting_index(range.start_bound())?;
let end = self.get_ending_index(range.end_bound())?;
if start < end {
Some((start, end))
} else {
None
}
}
pub fn merge_commits(&mut self, range: impl RangeBounds<usize>, new_meta: M) -> Option<usize> {
let i = self.get_starting_index(range.start_bound())?;
let Some(mut merged) = self.commits.drain(range).reduce(|mut a, b| {
a.delta.aggregate_owned(b.delta);
a
}) else {
return None;
};
merged.meta = new_meta;
self.commits.insert(i, merged);
Some(i)
}
pub fn get_aggregate(&self, range: impl RangeBounds<usize>) -> Option<D>
where
D: Clone,
{
let (start, end) = self.get_bounds(range)?;
if start >= end {
return None;
}
let mut delta = self.commits[start].delta.clone();
for i in start + 1..end {
delta.aggregate(&self.commits[i].delta);
}
Some(delta)
}
pub fn build_state<T, R>(&self, state: &mut T, range: R)
where
T: Diff<D>,
R: SliceIndex<[Commit<D, M>], Output = [Commit<D, M>]>,
{
for commit in &self.commits[range] {
state.patch(&commit.delta);
}
}
pub fn build_state_from_default<T, R>(&self, range: R) -> T
where
T: Diff<D> + Default,
R: SliceIndex<[Commit<D, M>], Output = [Commit<D, M>]>,
{
let mut state = T::default();
self.build_state(&mut state, range);
state
}
}
impl<D: Delta, M> Default for Timeline<D, M> {
fn default() -> Self {
Self::new()
}
}
impl<D: Delta, M> Deref for Timeline<D, M> {
type Target = [Commit<D, M>];
fn deref(&self) -> &Self::Target {
&self.commits
}
}
impl<D: Delta, M> DerefMut for Timeline<D, M> {
fn deref_mut(&mut self) -> &mut Self::Target {
&mut self.commits
}
}
impl<D: Delta> FromIterator<D> for Timeline<D, ()> {
fn from_iter<T: IntoIterator<Item = D>>(iter: T) -> Self {
iter.into_iter().map(|d| Commit::new(d, ())).collect()
}
}
impl<D: Delta, M> FromIterator<Commit<D, M>> for Timeline<D, M> {
fn from_iter<T: IntoIterator<Item = Commit<D, M>>>(iter: T) -> Self {
Self {
commits: iter.into_iter().collect(),
}
}
}
impl<D: Delta, M> Extend<Commit<D, M>> for Timeline<D, M> {
fn extend<I: IntoIterator<Item = Commit<D, M>>>(&mut self, iter: I) {
self.commits.extend(iter);
}
}
impl<D: Delta, M> IntoIterator for Timeline<D, M> {
type Item = Commit<D, M>;
type IntoIter = alloc::vec::IntoIter<Commit<D, M>>;
fn into_iter(self) -> Self::IntoIter {
self.commits.into_iter()
}
}
impl<'a, D: Delta, M> IntoIterator for &'a Timeline<D, M> {
type Item = &'a Commit<D, M>;
type IntoIter = core::slice::Iter<'a, Commit<D, M>>;
fn into_iter(self) -> Self::IntoIter {
self.commits.iter()
}
}
impl<D: Delta + Clone, M: Clone> Delta for Timeline<D, M> {
fn aggregate(&mut self, next: &Self) {
self.aggregate_owned(next.clone());
}
fn aggregate_owned(&mut self, next: Self)
where
Self: Sized
{
self.commits.extend(next.commits);
}
}
#[cfg(feature = "deku")]
impl<D, M, Ctx> DekuWriter<Ctx> for Timeline<D, M>
where
Ctx: Copy,
D: Delta,
Commit<D, M>: DekuWriter<Ctx>,
{
fn to_writer<W: Write + Seek>(&self, writer: &mut Writer<W>, ctx: Ctx) -> Result<(), DekuError> {
write_commits(&self.commits, writer, ctx)
}
}
#[cfg(feature = "deku")]
impl<'a, D, M, Ctx> DekuReader<'a, Ctx> for Timeline<D, M>
where
Ctx: Copy,
D: Delta,
Commit<D, M>: DekuReader<'a, Ctx>,
{
fn from_reader_with_ctx<R: Read + Seek>(reader: &mut Reader<R>, ctx: Ctx) -> Result<Self, DekuError>
where
Self: Sized {
let commits = read_commits(reader, ctx)?;
Ok(Self {
commits
})
}
}
#[cfg(feature = "deku")]
fn write_commits<W, D, M, Ctx>(commits: &[Commit<D, M>], writer: &mut Writer<W>, ctx: Ctx) -> Result<(), DekuError>
where
W: Write + Seek,
Ctx: Copy,
D: Delta,
Commit<D, M>: DekuWriter<Ctx>,
{
(commits.len() as u64).to_writer(writer, Endian::Big)?;
commits.to_writer(writer, ctx)
}
#[cfg(feature = "deku")]
fn read_commits<'a, R, D, M, Ctx>(reader: &mut Reader<R>, ctx: Ctx) -> Result<Vec<Commit<D, M>>, DekuError>
where
R: Read + Seek,
Ctx: Copy,
D: Delta,
Commit<D, M>: DekuReader<'a, Ctx>,
{
let len = u64::from_reader_with_ctx(reader, Endian::Big)?;
Vec::<Commit<D, M>>::from_reader_with_ctx(reader, (Limit::new_count(len as usize), ctx))
}
fn build_state_cache<T, D, M>(initial_state: T, timeline: &Timeline<D, M>, interval: usize) -> Vec<T>
where
T: Diff<D> + Clone,
D: Delta,
{
let cached_count = timeline.len() / interval;
let replay_len = cached_count * interval;
let mut states = Vec::with_capacity(cached_count + 1);
states.push(initial_state.clone());
let mut current = initial_state;
for i in 0..replay_len {
current.patch(&timeline[i]);
if (i + 1) % interval == 0 {
states.push(current.clone());
}
}
states
}
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct StateCachedTimeline<T, D, M = ()>
where
T: Diff<D> + Clone,
D: Delta,
{
timeline: Timeline<D, M>,
states: Vec<T>,
state_cache_interval: usize,
}
impl<T, D, M> StateCachedTimeline<T, D, M>
where
T: Diff<D> + Clone,
D: Delta,
{
pub fn new(state_cache_interval: usize, initial_state: T) -> Self {
assert!(state_cache_interval >= 1, "state_cache_interval must be >= 1");
Self {
timeline: Timeline::new(),
states: vec![initial_state],
state_cache_interval,
}
}
pub fn from_timeline(state_cache_interval: usize, timeline: Timeline<D, M>, initial_state: T) -> Self {
assert!(state_cache_interval >= 1, "state_cache_interval must be >= 1");
let states = build_state_cache(initial_state, &timeline, state_cache_interval);
Self {
timeline,
states,
state_cache_interval,
}
}
pub fn from_commits(
state_cache_interval: usize,
initial_state: T,
iter: impl IntoIterator<Item = Commit<D, M>>,
) -> Self {
let mut t = Self::new(state_cache_interval, initial_state);
t.extend(iter);
t
}
pub fn from_commits_with_default(
state_cache_interval: usize,
iter: impl IntoIterator<Item = Commit<D, M>>,
) -> Self
where
T: Default,
{
Self::from_commits(state_cache_interval, T::default(), iter)
}
pub fn set_initial_state(&mut self, state: T) {
self.states = build_state_cache(state, &self.timeline, self.state_cache_interval);
}
pub fn get_state_before(&self, i: usize) -> Option<T> {
let (cache_idx, cache) = self.get_nearest_state(i)?;
let mut state = cache.clone();
for j in cache_idx..i {
state.patch(&self.timeline[j]);
}
Some(state)
}
pub fn get_state_after(&self, i: usize) -> Option<T> {
if i >= self.timeline.len() {
return None;
}
let (cache_idx, cache) = self.get_nearest_state(i)?;
let mut state = cache.clone();
for j in cache_idx..=i {
state.patch(&self.timeline[j]);
}
Some(state)
}
pub fn current_state(&self) -> T {
self.get_state_before(self.timeline.len())
.expect("timeline.len() is always in bounds for get_state_before")
}
pub fn get_nearest_state(&self, i: usize) -> Option<(usize, &T)> {
if i > self.timeline.len() {
return None;
}
let cache_i = self.get_cache_index(i);
let cache = &self.states[cache_i];
Some((self.cache_to_timeline_index(cache_i), cache))
}
fn get_cache_index(&self, i: usize) -> usize {
debug_assert!(i <= self.timeline.len());
(i / self.state_cache_interval).min(self.states.len() - 1)
}
fn cache_to_timeline_index(&self, i: usize) -> usize {
debug_assert!(i < self.states.len());
i * self.state_cache_interval
}
const fn should_cache(&self, i: usize) -> bool {
i % self.state_cache_interval == 0
}
pub fn push(&mut self, commit: Commit<D, M>) {
let i = self.timeline.len();
self.timeline.push(commit);
if i != 0 && self.should_cache(i) {
let state = unsafe { self.get_state_before(i).unwrap_unchecked() };
self.states.push(state);
}
}
pub fn pop(&mut self) -> Option<Commit<D, M>> {
let commit = self.timeline.pop()?;
self.drop_stale_cache_entries();
Some(commit)
}
pub fn truncate(&mut self, len: usize) {
self.timeline.truncate(len);
self.drop_stale_cache_entries();
}
pub fn clear(&mut self) {
self.truncate(0);
}
fn drop_stale_cache_entries(&mut self) {
let len = self.timeline.len();
while self.states.len() > 1 && self.cache_to_timeline_index(self.states.len() - 1) > len {
self.states.pop();
}
}
pub fn get_aggregate_diffed(&self, range: impl RangeBounds<usize>) -> Option<D> {
let (start, end) = self.timeline.get_bounds(range)?;
let state_start = self.get_state_before(start)?;
let state_end = self.get_state_before(end)?;
Some(state_end.diff(&state_start))
}
pub fn delta_between(&self, from: usize, to: usize) -> Option<D> {
if from > self.timeline.len() || to > self.timeline.len() {
return None;
}
let state_from = self.get_state_before(from)?;
let state_to = self.get_state_before(to)?;
Some(state_to.diff(&state_from))
}
fn has_hanging(&self) -> bool {
self.states.len() > self.timeline.len() / self.state_cache_interval
}
}
impl<T, D, M> Extend<Commit<D, M>> for StateCachedTimeline<T, D, M>
where
T: Diff<D> + Clone,
D: Delta,
{
fn extend<I: IntoIterator<Item = Commit<D, M>>>(&mut self, iter: I) {
let start_i = self.timeline.len();
let mut state = unsafe { self.get_state_before(start_i).unwrap_unchecked() };
let mut i = start_i;
for commit in iter {
if i != 0 && self.should_cache(i) {
self.states.push(state.clone());
}
state.patch(&commit.delta);
self.timeline.push(commit);
i += 1;
}
}
}
impl<T, D, M> Deref for StateCachedTimeline<T, D, M>
where
T: Diff<D> + Clone,
D: Delta,
{
type Target = Timeline<D, M>;
fn deref(&self) -> &Self::Target {
&self.timeline
}
}
#[cfg(feature = "deku")]
#[derive(Debug, Clone, Copy, Default)]
pub enum IncludeCache {
TimelineOnly,
#[default]
CacheAndTimeline
}
#[cfg(feature = "deku")]
impl<T, D, M, Ctx1, Ctx2> DekuWriter<(IncludeCache, Ctx1, Ctx2)> for StateCachedTimeline<T, D, M>
where
Ctx1: Copy,
Ctx2: Copy,
T: Diff<D> + Clone + DekuWriter<Ctx2>,
D: Delta,
Commit<D, M>: DekuWriter<Ctx1>,
{
fn to_writer<W: Write + Seek>(&self, writer: &mut Writer<W>, (include_cache, ctx1, ctx2): (IncludeCache, Ctx1, Ctx2)) -> Result<(), DekuError> {
self.timeline.to_writer(writer, ctx1)?;
(self.state_cache_interval as u64).to_writer(writer, Endian::Big)?;
match include_cache {
IncludeCache::TimelineOnly => {
self.states[0].to_writer(writer, ctx2)?;
},
IncludeCache::CacheAndTimeline => {
self.has_hanging().to_writer(writer, ())?;
self.states.to_writer(writer, ctx2)?;
}
}
Ok(())
}
}
#[cfg(feature = "deku")]
impl<'a, T, D, M, Ctx1, Ctx2> DekuReader<'a, (IncludeCache, Ctx1, Ctx2)> for StateCachedTimeline<T, D, M>
where
Ctx1: Copy,
Ctx2: Copy,
T: Diff<D> + Clone + DekuReader<'a, Ctx2>,
D: Delta,
Commit<D, M>: DekuReader<'a, Ctx1>,
{
fn from_reader_with_ctx<R: Read + Seek>(reader: &mut Reader<R>, (include_cache, ctx1, ctx2): (IncludeCache, Ctx1, Ctx2)) -> Result<Self, DekuError>
where
Self: Sized
{
let timeline = Timeline::from_reader_with_ctx(reader, ctx1)?;
let state_cache_interval = u64::from_reader_with_ctx(reader, Endian::Big)? as usize;
match include_cache {
IncludeCache::TimelineOnly => {
let initial_state = T::from_reader_with_ctx(reader, ctx2)?;
Ok(Self::from_timeline(state_cache_interval, timeline, initial_state))
},
IncludeCache::CacheAndTimeline => {
let has_hanging: bool = bool::from_reader_with_ctx(reader, ())?;
let states_len = timeline.len() / state_cache_interval + has_hanging as usize;
let states = Vec::<T>::from_reader_with_ctx(reader, (Limit::new_count(states_len), ctx2))?;
Ok(Self {
timeline,
state_cache_interval,
states
})
}
}
}
}
#[cfg(test)]
mod tests {
use alloc::string::String;
use crate::{Patch, delta::ArithmeticDelta};
use super::*;
#[test]
fn test_commit_creation_and_deref() {
let commit = Commit::new(ArithmeticDelta(5i32), "metadata");
assert_eq!(commit.meta(), &"metadata");
assert_eq!(commit.0, 5);
let commit_default_meta: Commit<ArithmeticDelta<i32>, String> =
Commit::new_with_default(ArithmeticDelta(10));
assert_eq!(commit_default_meta.meta(), "");
assert_eq!(commit_default_meta.0, 10);
}
#[test]
fn test_timeline_basic_operations() {
let mut timeline = Timeline::new();
assert!(timeline.is_empty());
assert_eq!(timeline.len(), 0);
timeline.push(Commit::new(ArithmeticDelta(10i32), ()));
timeline.push(Commit::new(ArithmeticDelta(20i32), ()));
assert_eq!(timeline.len(), 2);
assert_eq!(timeline[0].0, 10);
assert_eq!(timeline[1].0, 20);
let popped = timeline.pop().expect("Should pop a commit");
assert_eq!(popped.0, 20);
assert_eq!(timeline.len(), 1);
timeline.clear();
assert!(timeline.is_empty());
}
#[test]
fn test_timeline_truncate() {
let mut timeline: Timeline<ArithmeticDelta<i32>, ()> = vec![
Commit::new(ArithmeticDelta(1), ()),
Commit::new(ArithmeticDelta(2), ()),
Commit::new(ArithmeticDelta(3), ()),
]
.into_iter()
.collect();
timeline.truncate(2);
assert_eq!(timeline.len(), 2);
assert_eq!(timeline[1].0, 2);
timeline.truncate(10);
assert_eq!(timeline.len(), 2);
}
#[test]
fn test_timeline_pop_aggregate() {
let mut timeline: Timeline<ArithmeticDelta<i32>, ()> = vec![
Commit::new(ArithmeticDelta(1), ()),
Commit::new(ArithmeticDelta(2), ()),
Commit::new(ArithmeticDelta(3), ()),
Commit::new(ArithmeticDelta(4), ()),
]
.into_iter()
.collect();
let agg = timeline.pop_aggregate(2);
assert_eq!(agg, Some(ArithmeticDelta(7)));
assert_eq!(timeline.len(), 2);
assert_eq!(timeline.pop_aggregate(5), None);
assert_eq!(timeline.len(), 2);
assert_eq!(timeline.pop_aggregate(0), None);
assert_eq!(timeline.len(), 2);
let agg_all = timeline.pop_aggregate(2);
assert_eq!(agg_all, Some(ArithmeticDelta(3)));
assert!(timeline.is_empty());
}
#[test]
fn test_timeline_get_aggregate() {
let timeline: Timeline<ArithmeticDelta<i32>, ()> = vec![
Commit::new(ArithmeticDelta(10), ()),
Commit::new(ArithmeticDelta(20), ()),
Commit::new(ArithmeticDelta(30), ()),
Commit::new(ArithmeticDelta(40), ()),
]
.into_iter()
.collect();
assert_eq!(timeline.get_aggregate(..), Some(ArithmeticDelta(100)));
assert_eq!(timeline.get_aggregate(1..3), Some(ArithmeticDelta(50)));
assert_eq!(timeline.get_aggregate(2..=3), Some(ArithmeticDelta(70)));
assert_eq!(timeline.get_aggregate(2..2), None);
assert_eq!(timeline.get_aggregate(3..1), None);
assert_eq!(timeline.get_aggregate(0..10), None);
}
#[test]
fn test_timeline_merge_commits() {
let mut timeline: Timeline<ArithmeticDelta<i32>, &'static str> = vec![
Commit::new(ArithmeticDelta(1), "a"),
Commit::new(ArithmeticDelta(2), "b"),
Commit::new(ArithmeticDelta(3), "c"),
Commit::new(ArithmeticDelta(4), "d"),
]
.into_iter()
.collect();
let merged_idx = timeline.merge_commits(1..3, "b+c");
assert_eq!(merged_idx, Some(1));
assert_eq!(timeline.len(), 3);
assert_eq!(timeline[0].0, 1);
assert_eq!(*timeline[0].meta(), "a");
assert_eq!(timeline[1].0, 5);
assert_eq!(*timeline[1].meta(), "b+c");
assert_eq!(timeline[2].0, 4);
assert_eq!(*timeline[2].meta(), "d");
assert_eq!(timeline.merge_commits(2..2, "empty"), None);
assert_eq!(timeline.merge_commits(10..12, "oob"), None);
}
#[test]
fn test_timeline_build_state() {
let timeline: Timeline<ArithmeticDelta<i32>, ()> = vec![
Commit::new(ArithmeticDelta(5), ()),
Commit::new(ArithmeticDelta(10), ()),
Commit::new(ArithmeticDelta(15), ()),
]
.into_iter()
.collect();
let mut state: i32 = 100;
timeline.build_state(&mut state, 0..2);
assert_eq!(state, 115);
let state_default: i32 = timeline.build_state_from_default(..);
assert_eq!(state_default, 30);
}
#[test]
fn test_timeline_conversions_and_iterators() {
let t1: Timeline<ArithmeticDelta<i32>, ()> =
vec![ArithmeticDelta(1), ArithmeticDelta(2)]
.into_iter()
.collect();
assert_eq!(t1.len(), 2);
let commits = vec![Commit::new(ArithmeticDelta(3), "meta")];
let mut t2: Timeline<ArithmeticDelta<i32>, &'static str> =
commits.into_iter().collect();
assert_eq!(t2.len(), 1);
t2.extend(vec![Commit::new(ArithmeticDelta(4), "meta2")]);
assert_eq!(t2.len(), 2);
let sum: i32 = (&t2).into_iter().map(|c| c.0).sum();
assert_eq!(sum, 7);
let owned_sum: i32 = t2.into_iter().map(|c| c.0).sum();
assert_eq!(owned_sum, 7);
}
#[test]
fn test_timeline_delta_trait_impl() {
let mut t1: Timeline<ArithmeticDelta<i32>, ()> =
vec![ArithmeticDelta(1), ArithmeticDelta(2)]
.into_iter()
.collect();
let t2: Timeline<ArithmeticDelta<i32>, ()> =
vec![ArithmeticDelta(3), ArithmeticDelta(4)]
.into_iter()
.collect();
t1.aggregate(&t2);
assert_eq!(t1.len(), 4);
assert_eq!(t1[2].0, 3);
t1.aggregate_owned(vec![ArithmeticDelta(5)].into_iter().collect());
assert_eq!(t1.len(), 5);
assert_eq!(t1[4].0, 5);
}
#[test]
#[should_panic(expected = "state_cache_interval must be >= 1")]
fn test_cached_timeline_zero_interval_panics() {
StateCachedTimeline::<i32, ArithmeticDelta<i32>, ()>::new(0, 0);
}
#[test]
fn test_cached_timeline_queries() {
let mut ct = StateCachedTimeline::new(2, 0i32);
ct.push(Commit::new(ArithmeticDelta(10), ())); ct.push(Commit::new(ArithmeticDelta(20), ())); ct.push(Commit::new(ArithmeticDelta(30), ())); ct.push(Commit::new(ArithmeticDelta(40), ()));
assert_eq!(ct.get_state_before(0), Some(0));
assert_eq!(ct.get_state_before(1), Some(10));
assert_eq!(ct.get_state_before(2), Some(30));
assert_eq!(ct.get_state_before(3), Some(60));
assert_eq!(ct.get_state_before(4), Some(100));
assert_eq!(ct.get_state_before(5), None);
assert_eq!(ct.get_state_after(0), Some(10));
assert_eq!(ct.get_state_after(1), Some(30));
assert_eq!(ct.get_state_after(2), Some(60));
assert_eq!(ct.get_state_after(3), Some(100));
assert_eq!(ct.get_state_after(4), None);
assert_eq!(ct.current_state(), 100);
}
#[test]
fn test_cached_timeline_get_nearest_state() {
let mut ct = StateCachedTimeline::new(3, 10i32);
for i in 1..=6 {
ct.push(Commit::new(ArithmeticDelta(i), ()));
}
let (idx_0, state_0) = ct.get_nearest_state(2).unwrap();
assert_eq!(idx_0, 0);
assert_eq!(state_0, &10);
let (idx_3, state_3) = ct.get_nearest_state(4).unwrap();
assert_eq!(idx_3, 3);
assert_eq!(state_3, &16);
let (idx_6_before, state_6_before) = ct.get_nearest_state(6).unwrap();
assert_eq!(idx_6_before, 3);
assert_eq!(state_6_before, &16);
ct.push(Commit::new(ArithmeticDelta(7), ()));
let (idx_6, state_6) = ct.get_nearest_state(6).unwrap();
assert_eq!(idx_6, 6);
assert_eq!(state_6, &31);
assert_eq!(ct.get_nearest_state(8), None);
}
#[test]
fn test_cached_timeline_constructors() {
let timeline: Timeline<ArithmeticDelta<i32>, ()> = vec![
Commit::new(ArithmeticDelta(5), ()),
Commit::new(ArithmeticDelta(15), ()),
Commit::new(ArithmeticDelta(25), ()),
]
.into_iter()
.collect();
let ct1 = StateCachedTimeline::from_timeline(2, timeline, 100i32);
assert_eq!(ct1.current_state(), 145);
assert_eq!(ct1.get_state_before(2), Some(120));
let ct2 = StateCachedTimeline::from_commits(
1,
50i32,
vec![Commit::new(ArithmeticDelta(10), ()), Commit::new(ArithmeticDelta(20), ())],
);
assert_eq!(ct2.current_state(), 80);
let ct3 = StateCachedTimeline::<i32, ArithmeticDelta<i32>, ()>::from_commits_with_default(
2,
vec![Commit::new(ArithmeticDelta(7), ())],
);
assert_eq!(ct3.current_state(), 7);
}
#[test]
fn test_cached_timeline_set_initial_state() {
let mut ct = StateCachedTimeline::new(2, 0i32);
ct.push(Commit::new(ArithmeticDelta(10), ()));
ct.push(Commit::new(ArithmeticDelta(20), ()));
ct.push(Commit::new(ArithmeticDelta(30), ()));
assert_eq!(ct.current_state(), 60);
ct.set_initial_state(100);
assert_eq!(ct.get_state_before(0), Some(100));
assert_eq!(ct.get_state_before(1), Some(110));
assert_eq!(ct.get_state_before(2), Some(130));
assert_eq!(ct.current_state(), 160);
}
#[test]
fn test_cached_timeline_pop_truncate_clear() {
let mut ct = StateCachedTimeline::new(2, 0i32);
for _ in 0..5 {
ct.push(Commit::new(ArithmeticDelta(10), ()));
}
assert_eq!(ct.current_state(), 50);
let popped = ct.pop();
assert_eq!(popped.unwrap().0, 10);
assert_eq!(ct.len(), 4);
assert_eq!(ct.current_state(), 40);
ct.truncate(1);
assert_eq!(ct.len(), 1);
assert_eq!(ct.current_state(), 10);
ct.clear();
assert_eq!(ct.len(), 0);
assert_eq!(ct.current_state(), 0);
}
#[test]
fn test_cached_timeline_extend() {
let mut ct = StateCachedTimeline::new(2, 5i32);
ct.extend(vec![
Commit::new(ArithmeticDelta(10), ()),
Commit::new(ArithmeticDelta(20), ()),
Commit::new(ArithmeticDelta(30), ()),
]);
assert_eq!(ct.len(), 3);
assert_eq!(ct.get_state_before(0), Some(5));
assert_eq!(ct.get_state_before(2), Some(35));
assert_eq!(ct.current_state(), 65);
}
#[test]
fn test_wrapping_arithmetic_overflow_behavior() {
let mut ct = StateCachedTimeline::new(1, 250u8);
ct.push(Commit::new(ArithmeticDelta(10u8), ()));
assert_eq!(ct.current_state(), 4u8);
let delta = 4u8.diff(&250u8);
assert_eq!(delta.0, 10u8);
}
#[test]
fn test_state_cached_timeline_get_aggregate_diffed() {
let commits = vec![
Commit::new(ArithmeticDelta(10), ()),
Commit::new(ArithmeticDelta(20), ()),
Commit::new(ArithmeticDelta(30), ()),
Commit::new(ArithmeticDelta(40), ()),
];
let sct = StateCachedTimeline::from_commits(2, 0i32, commits);
assert_eq!(sct.get_aggregate_diffed(..), Some(ArithmeticDelta(100)));
assert_eq!(sct.get_aggregate_diffed(..), sct.get_aggregate(..));
assert_eq!(sct.get_aggregate_diffed(1..3), Some(ArithmeticDelta(50)));
assert_eq!(sct.get_aggregate_diffed(1..3), sct.get_aggregate(1..3));
assert_eq!(sct.get_aggregate_diffed(2..=3), Some(ArithmeticDelta(70)));
assert_eq!(sct.get_aggregate_diffed(2..=3), sct.get_aggregate(2..=3));
assert_eq!(sct.get_aggregate_diffed(2..2), None);
assert_eq!(sct.get_aggregate_diffed(3..1), None);
assert_eq!(sct.get_aggregate_diffed(0..10), None);
}
#[test]
fn test_state_cached_timeline_diff_between() {
let commits = vec![
Commit::new(ArithmeticDelta(5), ()),
Commit::new(ArithmeticDelta(15), ()),
Commit::new(ArithmeticDelta(25), ()),
Commit::new(ArithmeticDelta(-10), ()),
];
let sct = StateCachedTimeline::from_commits(3, 100i32, commits);
assert_eq!(sct.delta_between(0, 4), Some(ArithmeticDelta(35))); assert_eq!(sct.delta_between(1, 3), Some(ArithmeticDelta(40)));
assert_eq!(sct.delta_between(4, 0), Some(ArithmeticDelta(-35))); assert_eq!(sct.delta_between(3, 1), Some(ArithmeticDelta(-40)));
assert_eq!(sct.delta_between(2, 2), Some(ArithmeticDelta(0)));
let mut current_state = sct.get_state_before(4).unwrap(); let inverted_delta = sct.delta_between(4, 1).unwrap(); current_state.patch(&inverted_delta);
assert_eq!(current_state, sct.get_state_before(1).unwrap());
assert_eq!(sct.delta_between(0, 10), None);
assert_eq!(sct.delta_between(10, 0), None);
}
#[cfg(test)]
mod deku_tests {
use super::*; use std::io::Cursor;
#[derive(Debug, PartialEq, DekuRead, DekuWrite, Clone)]
struct TestMeta(u8);
#[test]
fn test_commit_deku_serialization() {
let commit = Commit::new(ArithmeticDelta(42u32), TestMeta(7));
let ctx = (deku::ctx::Endian::Big, ());
let mut buf = Vec::new();
let mut cursor_write = Cursor::new(&mut buf);
let mut writer = Writer::new(&mut cursor_write);
commit.to_writer(&mut writer, ctx).expect("Failed to serialize Commit");
let mut cursor_read = Cursor::new(&buf);
let mut reader = Reader::new(&mut cursor_read);
let deserialized = Commit::<ArithmeticDelta<u32>, TestMeta>::from_reader_with_ctx(&mut reader, ctx)
.expect("Failed to deserialize Commit");
assert_eq!(commit, deserialized);
}
#[test]
fn test_timeline_deku_serialization() {
let mut timeline = Timeline::new();
timeline.push(Commit::new(ArithmeticDelta(10u32), TestMeta(1)));
timeline.push(Commit::new(ArithmeticDelta(20u32), TestMeta(2)));
timeline.push(Commit::new(ArithmeticDelta(30u32), TestMeta(3)));
let ctx = (deku::ctx::Endian::Big, ());
let mut buf = Vec::new();
let mut cursor_write = Cursor::new(&mut buf);
let mut writer = Writer::new(&mut cursor_write);
timeline.to_writer(&mut writer, ctx).expect("Failed to serialize Timeline");
let mut cursor_read = Cursor::new(&buf);
let mut reader = Reader::new(&mut cursor_read);
let deserialized = Timeline::<ArithmeticDelta<u32>, TestMeta>::from_reader_with_ctx(&mut reader, ctx)
.expect("Failed to deserialize Timeline");
assert_eq!(timeline, deserialized);
}
#[test]
fn test_empty_timeline_deku_serialization() {
let timeline = Timeline::<ArithmeticDelta<u32>, TestMeta>::new();
let ctx = (deku::ctx::Endian::Big, ());
let mut buf = Vec::new();
let mut cursor_write = Cursor::new(&mut buf);
let mut writer = Writer::new(&mut cursor_write);
timeline.to_writer(&mut writer, ctx).expect("Failed to serialize empty Timeline");
let mut cursor_read = Cursor::new(&buf);
let mut reader = Reader::new(&mut cursor_read);
let deserialized = Timeline::<ArithmeticDelta<u32>, TestMeta>::from_reader_with_ctx(&mut reader, ctx)
.expect("Failed to deserialize empty Timeline");
assert_eq!(timeline, deserialized);
}
#[test]
fn test_state_cached_timeline_deku_serialization() {
let mut sct = StateCachedTimeline::<u32, ArithmeticDelta<u32>, TestMeta>::new(2, 100);
sct.push(Commit::new(ArithmeticDelta(10u32), TestMeta(1)));
sct.push(Commit::new(ArithmeticDelta(20u32), TestMeta(2)));
let ctx = (IncludeCache::CacheAndTimeline, (deku::ctx::Endian::Big, ()), deku::ctx::Endian::Big);
let mut buf = Vec::new();
let mut cursor_write = Cursor::new(&mut buf);
let mut writer = Writer::new(&mut cursor_write);
sct.to_writer(&mut writer, ctx).expect("Failed to serialize StateCachedTimeline");
let mut cursor_read = Cursor::new(&buf);
let mut reader = Reader::new(&mut cursor_read);
let deserialized = StateCachedTimeline::<u32, ArithmeticDelta<u32>, TestMeta>::from_reader_with_ctx(&mut reader, ctx)
.expect("Failed to deserialize StateCachedTimeline");
assert_eq!(sct.len(), deserialized.len());
assert_eq!(sct.current_state(), deserialized.current_state());
assert_eq!(sct.get_state_before(0), deserialized.get_state_before(0));
}
}
}