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
124
125
126


// TODO: bitvec
use std::collections::HashSet;

/// A very simple subset of slice's items that is able to iterate forward and backward over selected items.
/// 
/// # Examples
///
/// Basic usage:
///
/// ```
/// use subset::*;
/// 
/// let set = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
/// let idxs = vec![2, 2];
/// assert_eq!(Subset::new(&set, &idxs).err(), Some(IndexError::NotUnique));
/// let idxs = vec![10];
/// assert_eq!(Subset::new(&set, &idxs).err(), Some(IndexError::OutOfBounds));
/// let idxs = vec![2, 4, 7];   // Indexes of selected items
/// let subset = Subset::new(&set, &idxs).unwrap();
/// let mut iter = subset.iter();
/// 
/// assert_eq!(Some(&7), iter.next());
/// assert_eq!(Some(&2), iter.next_back());
/// assert_eq!(Some(&5), iter.next_back());
/// assert_eq!(None, iter.next());
/// assert_eq!(None, iter.next_back());
/// ```
pub struct Subset<'a, T> {
    set: &'a [T],
    idxs: &'a [usize]
}


/// Double-ended iterator over selected items of a vector.
pub struct SubsetIterator<'a, T> {
    subset: &'a Subset<'a, T>,
    iter: std::slice::Iter<'a, usize>
}


#[derive(Debug,PartialEq,Eq)]
pub enum IndexError {
    NotUnique,
    OutOfBounds
}


impl<'a, T> Subset<'a, T> {
    /// Creates a subset from the whole set and indexes of the selected items.
    /// Both the uniqueness of the selected items and the array bounds is checked.
    pub fn new(set: &'a [T], idxs: &'a [usize]) -> Result<Self, IndexError> {
        let set_size = set.len();
        let uniques: HashSet<usize> = idxs.iter().map(|v| *v).collect();
        if uniques.len() < idxs.len() {
            Err(IndexError::NotUnique)
        } else if idxs.iter().any(|v| *v >= set_size) {
            Err(IndexError::OutOfBounds)
        } else { Ok(unsafe{Self::new_unchecked(set, idxs)}) }
    }
    /// Creates a subset from the whole set and indexes of the selected items.
    /// Neither the uniqueness of the selected items, nor the array bounds is checked.
    pub unsafe fn new_unchecked(set: &'a [T], idxs: &'a [usize]) -> Self {
        Self {
            set: set,
            idxs: idxs
        }
    }
    pub fn set(&self) -> &[T] {
        self.set
    }
    pub fn idxs(&self) -> &[usize] {
        self.idxs
    }
    /// Returns an iterator over subset.
    pub fn iter(&'a self) -> SubsetIterator<'a, T> {
        SubsetIterator {
            subset: self,
            iter: self.idxs.iter()
        }
    }
}


impl<'a, T> Iterator for SubsetIterator<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        self.iter.next().map(|v| &self.subset.set[*v])
    }
}


impl<'a, T> DoubleEndedIterator for SubsetIterator<'a, T> {
    fn next_back(&mut self) -> Option<&'a T> {
        self.iter.next_back().map(|v| &self.subset.set[*v])
    }
}


#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_set() {
        let set = vec![9, 8, 7, 6, 5, 4, 3, 2, 1, 0];
        let idxs = vec![2, 2];
        assert_eq!(Subset::new(&set, &idxs).err(), Some(IndexError::NotUnique));
        let idxs = vec![10];
        assert_eq!(Subset::new(&set, &idxs).err(), Some(IndexError::OutOfBounds));
        let idxs = vec![2, 4, 7];
        let subset = Subset::new(&set, &idxs).unwrap();
        let mut sum = 0;
        for e in subset.iter() {
            sum += e;
        }
        assert_eq!(sum, 14);
        let mut sum = 0;
        for e in subset.iter().map(|v| 2*v).rev() {
            sum += e;
        }
        assert_eq!(sum, 28);
    }

}