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
use std;
use std::hash::Hash;
use std::borrow::Borrow;
#[derive(Debug, Clone)]
pub struct VecSet<T> { v: Vec<T> }
impl<T: Eq> VecSet<T> {
pub fn new() -> VecSet<T> {
VecSet { v: Vec::new() }
}
pub fn default() -> VecSet<T> {
Self::new()
}
pub fn len(&self) -> usize {
self.v.len()
}
pub fn insert(&mut self, elem: T) -> bool {
if self.v.contains(&elem) {
false
} else {
self.v.push(elem);
true
}
}
pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>, Q: Hash + Eq,
{
for v in self.v.iter() {
if v.borrow() == value {
return true;
}
}
false
}
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>, Q: Hash + Eq,
{
for i in 0..self.v.len() {
if self.v[i].borrow() == value {
self.v.swap_remove(i);
return true
}
}
false
}
pub fn iter(&self) -> Iter<T> {
Iter( self.v.iter() )
}
}
pub struct Iter<'a,T: 'a>(std::slice::Iter<'a,T>);
impl<'a, T: 'a+Eq> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
self.0.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashSet;
#[test]
fn it_works() {
let mut ss: VecSet<usize> = VecSet::new();
ss.insert(5);
assert!(ss.contains(&5));
assert!(!ss.contains(&4));
ss.insert(3);
println!("now {:?}", &ss);
assert!(ss.contains(&3));
assert!(ss.contains(&5));
assert!(ss.len() == 2);
for num in ss.iter() {
assert!(ss.contains(num));
}
}
#[test]
fn size_unwasted() {
println!("small size: {}", std::mem::size_of::<VecSet<usize>>());
println!(" hash size: {}", std::mem::size_of::<HashSet<usize>>());
assert!(std::mem::size_of::<VecSet<usize>>() <=
2*std::mem::size_of::<HashSet<usize>>());
}
}