1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

//! A vector of slices.

use std::iter::{FusedIterator, IntoIterator};

/// A vector of slices.
///
/// Each slice is stored inline so as to be efficiently iterated through linearly.
#[derive(Debug)]
pub struct SliceVec<T> {
    data: Vec<T>,
    counts: Vec<usize>,
    indices: Vec<usize>,
}

impl<T> Default for SliceVec<T> {
    fn default() -> Self {
        Self {
            data: Vec::new(),
            counts: Vec::new(),
            indices: Vec::new(),
        }
    }
}

impl<T> SliceVec<T> {
    /// Pushes a new slice onto the end of the vector.
    pub fn push<I: IntoIterator<Item = T>>(&mut self, items: I) {
        self.indices.push(self.data.len());
        let mut count = 0;
        for item in items.into_iter() {
            self.data.push(item);
            count += 1;
        }
        self.counts.push(count);
    }

    /// Gets an iterator over slices starting from the given index.
    pub fn iter_from(&self, start: usize) -> SliceVecIter<T> {
        let index = *self.indices.get(start).unwrap_or(&self.data.len());
        SliceVecIter {
            data: &self.data[index..],
            counts: &self.counts[start..],
        }
    }
}

/// An iterator over slices in a `SliceVec`.
#[derive(Clone)]
pub struct SliceVecIter<'a, T> {
    pub(crate) data: &'a [T],
    pub(crate) counts: &'a [usize],
}

impl<'a, T> Iterator for SliceVecIter<'a, T> {
    type Item = &'a [T];

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if let Some((count, remaining_counts)) = self.counts.split_first() {
            let (data, remaining_data) = self.data.split_at(*count);
            self.counts = remaining_counts;
            self.data = remaining_data;
            Some(data)
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.counts.len(), Some(self.counts.len()))
    }

    #[inline]
    fn count(self) -> usize {
        self.len()
    }
}

impl<'a, T> ExactSizeIterator for SliceVecIter<'a, T> {}
impl<'a, T> FusedIterator for SliceVecIter<'a, T> {}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn create() {
        let _ = SliceVec::<usize>::default();
    }

    #[test]
    fn push() {
        let mut vec = SliceVec::default();
        let slices = [[1, 2, 3], [4, 5, 6]];

        for slice in &slices {
            vec.push(slice.iter().copied());
        }

        assert_eq!(vec.counts.len(), 2);
    }

    #[test]
    fn iter() {
        let mut vec = SliceVec::default();
        let slices = [[1, 2, 3], [4, 5, 6]];

        for slice in &slices {
            vec.push(slice.iter().copied());
        }

        assert_eq!(vec.counts.len(), 2);

        for (i, slice) in vec.iter_from(0).enumerate() {
            let expected = &slices[i];
            assert_eq!(slice.len(), expected.len());
            for (j, x) in slice.iter().enumerate() {
                assert_eq!(x, &expected[j]);
            }
        }
    }
}