use std::fmt::{Debug, Write};
use std::iter::FromIterator;
use std::ops::{Index, IndexMut, Range};
pub trait Sequence<'a, Item: 'a, Subsequence: Sequence<'a, Item, Subsequence> + ?Sized>:
Index<usize, Output = Item> + Index<Range<usize>, Output = Subsequence>
{
type Iterator: DoubleEndedIterator<Item = &'a Item>;
fn prefix(&'a self, len: usize) -> &Subsequence {
debug_assert!(len < self.len());
&self[0..len]
}
fn suffix(&'a self, len: usize) -> &Subsequence {
debug_assert!(len < self.len());
&self[self.len() - len..self.len()]
}
fn iter(&'a self) -> Self::Iterator;
fn len(&self) -> usize;
fn is_empty(&self) -> bool {
self.len() == 0
}
fn first(&'a self) -> Option<&Item> {
self.iter().next()
}
fn last(&'a self) -> Option<&Item> {
self.iter().last()
}
fn is_proper_subsequence_of(&'a self, other: &Self) -> bool
where
Item: Eq,
{
if self.len() >= other.len() {
return false;
}
for start_index in 0..=other.len() - self.len() {
let mut found_subsequence = true;
for index in 0..self.len() {
if self[index] != other[start_index + index] {
found_subsequence = false;
break;
}
}
if found_subsequence {
return true;
}
}
false
}
fn contains(&'a self, item: &Item) -> bool
where
Item: Eq,
{
self.iter().any(|i| item == i)
}
fn forward_merge_iter_assume_mergeable(
&'a self,
suffix: &'a Self,
) -> std::iter::Chain<Self::Iterator, std::iter::Skip<Self::Iterator>>
where
Item: Eq,
{
let first_item_index = self
.iter()
.enumerate()
.filter(|(_, i)| *i == suffix.first().expect("The given sequence is empty."))
.map(|(i, _)| i)
.next()
.expect("This sequence does not contain the first item of the given sequence.");
self.iter()
.chain(suffix.iter().skip(self.len() - first_item_index))
}
fn backward_merge_iter_assume_mergeable(
&'a self,
suffix: &'a Self,
) -> std::iter::Chain<Self::Iterator, std::iter::Skip<Self::Iterator>>
where
Item: Eq,
{
suffix.forward_merge_iter_assume_mergeable(self)
}
fn to_debug_string(&'a self) -> String
where
Item: Debug,
{
let mut result = String::new();
write!(result, "[").unwrap();
let mut once = true;
for item in self.iter() {
if once {
once = false;
} else {
write!(result, ", ").unwrap();
}
write!(result, "{:?}", item).unwrap();
}
write!(result, "]").unwrap();
result
}
}
pub trait SequenceMut<'a, Item: 'a, Subsequence: SequenceMut<'a, Item, Subsequence> + ?Sized>:
Sequence<'a, Item, Subsequence>
+ IndexMut<usize, Output = Item>
+ IndexMut<Range<usize>, Output = Subsequence>
{
type IteratorMut: Iterator<Item = &'a mut Item>;
fn iter_mut(&'a mut self) -> Self::IteratorMut;
}
pub trait OwnedSequence<'a, Item: 'a, Subsequence: Sequence<'a, Item, Subsequence> + ?Sized>:
Sequence<'a, Item, Subsequence> + Sized
{
}
pub trait CloneableSequence<
'a,
Item: 'a + Clone,
Subsequence: CloneableSequence<'a, Item, Subsequence> + ?Sized,
>: ToOwned
{
}
pub trait EditableSequence<'a, Item: 'a, Subsequence: Sequence<'a, Item, Subsequence> + ?Sized>:
Sequence<'a, Item, Subsequence> + Extend<Item> + IntoIterator<Item = Item> + FromIterator<Item>
{
fn extend_into<
ExtensionItem: Into<Item>,
ExtensionSource: IntoIterator<Item = ExtensionItem>,
>(
&mut self,
extension: ExtensionSource,
) {
self.extend(extension.into_iter().map(Into::into));
}
}
#[cfg(test)]
mod tests {
use crate::interface::Sequence;
#[test]
fn test_merge_sequences_simple() {
let s1 = vec![0, 1, 2, 3, 4, 5];
let s2 = vec![3, 4, 5, 6, 7, 8];
let merged: Vec<_> = s1
.forward_merge_iter_assume_mergeable(&s2)
.copied()
.collect();
debug_assert_eq!(merged, vec![0, 1, 2, 3, 4, 5, 6, 7, 8]);
}
}