use std::iter::{repeat, FromIterator};
use std::ops::{Index, Range};
pub type Item<T> = <T as Index<Range<usize>>>::Output;
pub type ZString = Nested<String>;
pub type ZVec<T> = Nested<Vec<T>>;
pub trait Collection: Index<Range<usize>> {
fn new() -> Self;
fn with_capacity(cap: usize) -> Self;
fn len(&self) -> usize;
fn truncate(&mut self, len: usize);
fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output);
fn split_off(&mut self, at: usize) -> Self;
}
impl<T: Clone> Collection for Vec<T> {
fn len(&self) -> usize {
self.len()
}
fn new() -> Self {
Vec::new()
}
fn with_capacity(cap: usize) -> Self {
Vec::with_capacity(cap)
}
fn truncate(&mut self, len: usize) {
self.truncate(len);
}
fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output) {
Vec::extend_from_slice(self, s)
}
fn split_off(&mut self, at: usize) -> Self {
self.split_off(at)
}
}
impl Collection for String {
fn len(&self) -> usize {
self.len()
}
fn new() -> Self {
String::new()
}
fn with_capacity(cap: usize) -> Self {
String::with_capacity(cap)
}
fn truncate(&mut self, len: usize) {
self.truncate(len);
}
fn extend_from_slice(&mut self, s: &<Self as Index<Range<usize>>>::Output) {
self.push_str(s)
}
fn split_off(&mut self, at: usize) -> Self {
self.split_off(at)
}
}
#[derive(Debug, Clone, PartialEq, Hash, Eq)]
pub struct Nested<T> {
indices: Vec<usize>,
data: T,
}
impl<T: Collection> Nested<T> {
pub fn new() -> Self {
Nested {
indices: vec![0],
data: T::new(),
}
}
pub fn with_capacity(len: usize, size: usize) -> Self {
let mut indices = Vec::with_capacity(len + 1);
indices.push(0);
Nested {
indices: indices,
data: T::with_capacity(size),
}
}
pub fn push<I: AsRef<Item<T>>>(&mut self, el: I) {
self.data.extend_from_slice(el.as_ref());
let len = self.data.len();
self.indices.push(len);
}
pub fn pop(&mut self) -> Option<T> {
if self.indices.len() > 1 {
let l = self.indices[self.indices.len() - 2];
let data = self.data.split_off(l);
self.indices.pop();
Some(data)
} else {
None
}
}
pub fn extend_empty(&mut self, count: usize) {
let len = self.data.len();
self.indices.extend(repeat(len).take(count));
}
#[inline]
pub fn len(&self) -> usize {
self.indices.len() - 1
}
#[inline]
pub fn data_len(&self) -> usize {
self.data.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn truncate(&mut self, len: usize) {
if len + 1 >= self.indices.len() {
return;
}
let size = self.indices[len];
self.indices.truncate(len + 1);
self.data.truncate(size);
}
#[inline]
pub fn clear(&mut self) {
self.indices.truncate(1);
self.data.truncate(0);
}
pub fn get(&self, index: usize) -> Option<&Item<T>> {
if index >= self.len() {
None
} else {
Some(&self[index])
}
}
pub fn into_parts(self) -> (Vec<usize>, T) {
(self.indices, self.data)
}
pub fn indices(&self) -> &[usize] {
&self.indices
}
pub fn data(&self) -> &T {
&self.data
}
pub fn iter(&self) -> Iter<T> {
Iter {
windows: self.indices.windows(2),
data: &self.data,
}
}
pub fn split_off(&mut self, at: usize) -> Nested<T> {
if at == self.len() {
return Nested::new();
}
assert!(at < self.len());
let mut new_indices = self.indices.split_off(at + 1);
let offset = self.indices[at];
let new_data = self.data.split_off(offset);
for i in &mut new_indices {
*i -= offset;
}
new_indices.insert(0, 0);
Nested {
indices: new_indices,
data: new_data,
}
}
}
impl<T: Collection> Index<usize> for Nested<T> {
type Output = Item<T>;
fn index(&self, index: usize) -> &Self::Output {
assert!(index + 1 <= self.indices.len());
let lo = self.indices[index];
let hi = self.indices[index + 1];
&self.data.index(lo..hi)
}
}
impl<T: Collection, A: AsRef<Item<T>>> Extend<A> for Nested<T> {
fn extend<I>(&mut self, iter: I)
where
I: IntoIterator,
I::Item: AsRef<Item<T>>,
{
for i in iter.into_iter() {
self.push(i);
}
}
}
#[derive(Debug, Clone)]
pub struct Iter<'a, T: 'a> {
windows: ::std::slice::Windows<'a, usize>,
data: &'a T,
}
impl<'a, T: Collection> Iterator for Iter<'a, T> {
type Item = &'a Item<T>;
fn next(&mut self) -> Option<Self::Item> {
self.windows.next().map(|w| self.data.index(w[0]..w[1]))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.windows.size_hint()
}
}
impl<'a, T: Collection> ExactSizeIterator for Iter<'a, T> {
fn len(&self) -> usize {
self.windows.len()
}
}
impl<'a, T: Collection> DoubleEndedIterator for Iter<'a, T> {
fn next_back(&mut self) -> Option<<Self as Iterator>::Item> {
self.windows
.next_back()
.map(|w| self.data.index(w[0]..w[1]))
}
}
impl<T: Collection, A: AsRef<Item<T>>> FromIterator<A> for Nested<T> {
fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
let iter = iter.into_iter();
let mut v = match iter.size_hint() {
(0, None) => Nested::new(),
(_, Some(l)) | (l, None) => Nested::with_capacity(l, l * 4),
};
v.extend(iter);
v
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_string() {
let mut v = Nested::<String>::new();
v.push("aaa");
v.push("bbb".to_string());
assert_eq!(v.len(), 2);
assert_eq!(&v[0], "aaa");
assert_eq!(&v[1], "bbb");
v.truncate(1);
assert_eq!(v.len(), 1);
assert_eq!(&v[0], "aaa");
assert_eq!(v.get(1), None);
v.extend_empty(3);
assert_eq!(v.len(), 4);
assert_eq!(&v[2], "");
}
#[test]
fn test_vec() {
let mut v = Nested::<Vec<_>>::new();
v.push(&[1, 2, 3]);
v.push(vec![1, 2, 4]);
assert_eq!(v.len(), 2);
assert_eq!(&v[0], &[1, 2, 3]);
assert_eq!(&v[1], &[1, 2, 4]);
v.truncate(1);
assert_eq!(v.len(), 1);
assert_eq!(&v[0], &[1, 2, 3]);
assert_eq!(v.get(1), None);
v.extend_empty(3);
assert_eq!(v.len(), 4);
assert_eq!(&v[2], &[]);
}
#[test]
fn test_collect() {
let sce = vec![
"a".to_string(),
"b".to_string(),
"c".to_string(),
"d".to_string(),
];
let v = sce.iter().collect::<Nested<String>>();
assert_eq!(v.len(), 4);
assert_eq!(&v[0], "a");
assert_eq!(&v[1], "b");
assert_eq!(&v[2], "c");
assert_eq!(&v[3], "d");
let sce = vec!["a", "b", "c", "d"];
let v2 = sce.iter().collect::<Nested<String>>();
assert_eq!(v, v2);
}
#[test]
fn test_iter() {
let sce = vec![
"a".to_string(),
"b".to_string(),
"c".to_string(),
"d".to_string(),
];
let v = sce.iter().collect::<Nested<String>>();
let new_sce = v.iter().map(|s| s.to_string()).collect::<Vec<_>>();
assert_eq!(sce, new_sce);
}
#[test]
fn test_split_off() {
let mut v = ["a", "b", "c", "d"].iter().collect::<Nested<String>>();
assert_eq!(v.len(), 4);
let u = v.split_off(2);
assert_eq!(v.len(), 2);
assert_eq!(u.len(), 2);
assert!(v.iter().zip(["a", "b"].iter()).all(|(r, l)| l.eq(&r)));
assert!(u.iter().zip(["c", "d"].iter()).all(|(r, l)| l.eq(&r)));
}
#[test]
fn test_pop() {
let mut v = ["a", "b", "c", "d"].iter().collect::<Nested<String>>();
assert_eq!(v.len(), 4);
assert_eq!(v.pop(), Some("d".to_string()));
assert_eq!(v.len(), 3);
assert_eq!(v.pop(), Some("c".to_string()));
assert_eq!(v.len(), 2);
assert_eq!(v.pop(), Some("b".to_string()));
assert_eq!(v.len(), 1);
assert_eq!(v.pop(), Some("a".to_string()));
assert_eq!(v.len(), 0);
assert_eq!(v.pop(), None);
assert_eq!(v.len(), 0);
}
}