david_set/
vecset.rs

1use std;
2use std::hash::Hash;
3use std::borrow::Borrow;
4
5/// A set that is stored in a Vec
6#[derive(Debug, Clone)]
7pub struct VecSet<T> { v: Vec<T> }
8impl<T: Eq> VecSet<T> {
9    /// Creates an empty set..
10    pub fn new() -> VecSet<T> {
11        VecSet { v: Vec::new() }
12    }
13    /// Returns the number of elements in the set.
14    pub fn len(&self) -> usize {
15        self.v.len()
16    }
17    /// Adds a value to the set.
18    ///
19    /// If the set did not have this value present, `true` is returned.
20    ///
21    /// If the set did have this value present, `false` is returned.
22    pub fn insert(&mut self, elem: T) -> bool {
23        if self.v.contains(&elem) {
24            false
25        } else {
26            self.v.push(elem);
27            true
28        }
29    }
30    /// Returns true if the set contains a value.
31    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
32        where
33        T: Borrow<Q>, Q: Hash + Eq,
34    {
35        for v in self.v.iter() {
36            if v.borrow() == value {
37                return true;
38            }
39        }
40        false
41    }
42    /// Removes an element, and returns true if that element was present.
43    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
44        where
45        T: Borrow<Q>, Q: Hash + Eq,
46    {
47        for i in 0..self.v.len() {
48            if self.v[i].borrow() == value {
49                self.v.swap_remove(i);
50                return true
51            }
52        }
53        false
54    }
55    /// Returns an iterator over the set.
56    pub fn iter(&self) -> Iter<T> {
57        Iter( self.v.iter() )
58    }
59}
60
61pub struct Iter<'a,T: 'a>(std::slice::Iter<'a,T>);
62impl<'a, T: 'a+Eq> Iterator for Iter<'a, T> {
63    type Item = &'a T;
64    fn next(&mut self) -> Option<&'a T> {
65        self.0.next()
66    }
67    fn size_hint(&self) -> (usize, Option<usize>) {
68        self.0.size_hint()
69    }
70}
71
72
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use std::collections::HashSet;
78    #[test]
79    fn it_works() {
80        let mut ss: VecSet<usize> = VecSet::new();
81        ss.insert(5);
82        assert!(ss.contains(&5));
83        assert!(!ss.contains(&4));
84        ss.insert(3);
85        println!("now {:?}", &ss);
86        assert!(ss.contains(&3));
87        assert!(ss.contains(&5));
88        assert!(ss.len() == 2);
89        for num in ss.iter() {
90            assert!(ss.contains(num));
91        }
92    }
93    #[test]
94    fn size_unwasted() {
95        println!("small size: {}", std::mem::size_of::<VecSet<usize>>());
96        println!(" hash size: {}", std::mem::size_of::<HashSet<usize>>());
97        assert!(std::mem::size_of::<VecSet<usize>>() <=
98                2*std::mem::size_of::<HashSet<usize>>());
99    }
100}
david_set/vecset.rs

david_set/
vecset.rs
