use crate::sequence::sequence_apply_patch::apply_patch;
use crate::sequence::sequence_delta_patch_towards::delta_towards;
use crate::{CreatedDelta, Diffable, Patchable};
use serde::Serialize;
mod longest_common_subsequence;
mod sequence_apply_patch;
mod sequence_delta_patch_towards;
impl<'s, 'e, T: 'e + Diffable<'s, 'e, T>> Diffable<'s, 'e, Vec<T>> for Vec<T>
where
T: PartialEq,
&'e T: serde::Serialize,
{
type Delta = Vec<SequenceModificationDelta<'e, T>>;
type DeltaOwned = Vec<SequenceModificationDeltaOwned<T>>;
fn create_delta_towards(&self, end_state: &'e Self) -> CreatedDelta<Self::Delta> {
delta_towards(self, end_state)
}
}
impl<T> Patchable<Vec<SequenceModificationDeltaOwned<T>>> for Vec<T> {
fn apply_patch(&mut self, patch: Vec<SequenceModificationDeltaOwned<T>>) {
apply_patch(self, patch)
}
}
impl<'s, 'e, T: 'e + Diffable<'s, 'e, T>> Diffable<'s, 'e, [T]> for &[T]
where
T: PartialEq,
&'e T: serde::Serialize,
{
type Delta = Vec<SequenceModificationDelta<'e, T>>;
type DeltaOwned = Vec<SequenceModificationDeltaOwned<T>>;
fn create_delta_towards(&self, end_state: &'e [T]) -> CreatedDelta<Self::Delta> {
delta_towards(self, end_state)
}
}
#[derive(Debug, Clone, Serialize)]
#[cfg_attr(test, derive(PartialEq))]
pub enum SequenceModificationDelta<'a, T>
where
&'a T: serde::Serialize,
{
InsertOne { index: usize, value: &'a T },
PrependOne { item: &'a T },
AppendOne { item: &'a T },
DeleteOne { index: usize },
ReplaceOne { index: usize, new: &'a T },
DeleteFirst,
DeleteLast,
ReplaceFirst { item: &'a T },
ReplaceLast { item: &'a T },
PrependMany { items: &'a [T] },
InsertMany { start_idx: usize, items: &'a [T] },
DeleteMany {
start_index: usize,
items_to_delete: usize,
},
AppendMany { items: &'a [T] },
ReplaceMany {
start_idx: usize,
items_to_replace: usize,
new: &'a [T],
},
ReplaceManySameAmountAddedAndRemoved { index: usize, new: &'a [T] },
ReplaceAll { new: &'a [T] },
DeleteAll,
DeleteAllBeforeIncluding { end_index: usize },
DeleteAllAfterIncluding { start_index: usize },
ReplaceAllBeforeIncluding { before: usize, new: &'a [T] },
ReplaceAllAfterIncluding { after: usize, new: &'a [T] },
}
#[derive(Debug, Clone, Serialize, Deserialize)]
#[cfg_attr(test, derive(PartialEq))]
pub enum SequenceModificationDeltaOwned<T> {
InsertOne { index: usize, value: T },
PrependOne { item: T },
AppendOne { item: T },
DeleteOne { index: usize },
ReplaceOne { index: usize, new: T },
DeleteFirst,
DeleteLast,
ReplaceFirst { item: T },
ReplaceLast { item: T },
PrependMany { items: Vec<T> },
InsertMany { start_idx: usize, items: Vec<T> },
DeleteMany {
start_index: usize,
items_to_delete: usize,
},
AppendMany { items: Vec<T> },
ReplaceMany {
start_idx: usize,
items_to_replace: usize,
new: Vec<T>,
},
ReplaceManySameAmountAddedAndRemoved { index: usize, new: Vec<T> },
ReplaceAll { new: Vec<T> },
DeleteAll,
DeleteAllBeforeIncluding { end_index: usize },
DeleteAllAfterIncluding { start_index: usize },
ReplaceAllBeforeIncluding { before: usize, new: Vec<T> },
ReplaceAllAfterIncluding { after: usize, new: Vec<T> },
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dipa_impl_tester::DipaImplTester;
use bincode::Options;
const BASE_PATCH_BYTES: usize = 1;
#[test]
fn vec_unchanged() {
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3],
end: &vec![1u8, 2, 3],
expected_delta: vec![],
expected_serialized_patch_size: 1,
expected_did_change: false,
}
.test();
}
#[test]
fn deletion_one_at_end() {
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1;
DipaImplTester {
label: None,
start: &mut vec![0u8, 1, 2, 3],
end: &vec![0u8, 1, 2],
expected_delta: vec![SequenceModificationDelta::DeleteLast],
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn deletion_many_at_end() {
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![0u8, 1, 2, 3, 4],
end: &vec![0u8, 1, 2],
expected_delta: vec![SequenceModificationDelta::DeleteAllAfterIncluding {
start_index: 3,
}],
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_one_at_beginning() {
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1;
DipaImplTester {
label: None,
start: &mut vec![0u8, 1, 2],
end: &vec![1u8, 2],
expected_delta: vec![SequenceModificationDelta::DeleteFirst],
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_many_at_beginning() {
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![0u8, 1, 2, 3],
end: &vec![2u8, 3],
expected_delta: vec![SequenceModificationDelta::DeleteAllBeforeIncluding {
end_index: 1,
}],
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_many_beginning_and_many_end() {
let expected_serialized_patch_size = BASE_PATCH_BYTES + 2 + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![0u8, 1, 2, 3, 4, 5],
end: &vec![2],
expected_delta: vec![
SequenceModificationDelta::DeleteAllAfterIncluding { start_index: 3 },
SequenceModificationDelta::DeleteAllBeforeIncluding { end_index: 1 },
],
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_one_in_middle() {
let expected_patch = vec![SequenceModificationDelta::DeleteOne { index: 1 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3],
end: &vec![1u8, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_many_in_middle() {
let expected_patch = vec![SequenceModificationDelta::DeleteMany {
start_index: 1,
items_to_delete: 2,
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4],
end: &vec![1u8, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_one_into_empty_vec() {
let expected_patch = vec![SequenceModificationDelta::ReplaceAll { new: &[1] }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![],
end: &vec![1u8],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_many_into_empty_vec() {
let expected_patch = vec![SequenceModificationDelta::ReplaceAll { new: &[1, 2] }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![],
end: &vec![1u8, 2],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_one_at_beginning() {
let expected_patch = vec![SequenceModificationDelta::PrependOne { item: &1 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![2u8, 3],
end: &vec![1u8, 2, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_many_at_beginning() {
let expected_patch = vec![SequenceModificationDelta::PrependMany { items: &[1, 2] }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![3u8, 4],
end: &vec![1u8, 2u8, 3, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_one_in_middle() {
let expected_patch = vec![SequenceModificationDelta::InsertOne {
index: 1,
value: &2,
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 3],
end: &vec![1u8, 2, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn insert_many_in_middle() {
let expected_patch = vec![SequenceModificationDelta::InsertMany {
start_idx: 1,
items: &[2, 3],
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 4],
end: &vec![1u8, 2, 3, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn append_one_at_end() {
let expected_patch = vec![SequenceModificationDelta::AppendOne { item: &3 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2],
end: &vec![1u8, 2, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn append_many_at_end() {
let expected_patch = vec![SequenceModificationDelta::AppendMany { items: &[3, 4] }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2],
end: &vec![1u8, 2, 3, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_one_at_beginning() {
let expected_patch = vec![SequenceModificationDelta::ReplaceFirst { item: &2 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 3],
end: &vec![2u8, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_many_at_beginning() {
let expected_patch = vec![SequenceModificationDelta::ReplaceAllBeforeIncluding {
before: 1,
new: &[5, 6],
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4],
end: &vec![5u8, 6, 3, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_one_at_end() {
let expected_patch = vec![SequenceModificationDelta::ReplaceLast { item: &3 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2],
end: &vec![1u8, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_many_at_end() {
let expected_patch = vec![SequenceModificationDelta::ReplaceAllAfterIncluding {
after: 2,
new: &[5, 6],
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4],
end: &vec![1u8, 2, 5, 6],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_one_in_middle() {
let expected_patch = vec![SequenceModificationDelta::ReplaceOne { index: 1, new: &4 }];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3],
end: &vec![1u8, 4, 3],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_many_in_middle() {
let expected_patch = vec![SequenceModificationDelta::ReplaceMany {
start_idx: 1,
items_to_replace: 3,
new: &[6, 7],
}];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4, 5],
end: &vec![1u8, 6, 7, 5],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn replace_many_in_middle_same_amount_added_and_removed() {
let expected_patch = vec![
SequenceModificationDelta::ReplaceManySameAmountAddedAndRemoved {
index: 1,
new: &[5, 6],
},
];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1 + 1 + 1 + 2;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4],
end: &vec![1u8, 5, 6, 4],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn delete_entire_vector() {
let expected_patch = vec![SequenceModificationDelta::DeleteAll];
let expected_serialized_patch_size = BASE_PATCH_BYTES + 1;
DipaImplTester {
label: None,
start: &mut vec![1u8, 2, 3, 4],
end: &vec![],
expected_delta: expected_patch,
expected_serialized_patch_size,
expected_did_change: true,
}
.test();
}
#[test]
fn sequence_variant_one_byte() {
let diff: SequenceModificationDelta<()> = SequenceModificationDelta::DeleteFirst;
assert_eq!(
bincode::options()
.with_varint_encoding()
.serialize(&diff)
.unwrap()
.len(),
1
);
}
}