1 use std::fmt::{self, Debug}; 2 use std::slice; 3 4 pub use self::ordered::OrderedSet; 5 pub use self::unordered::UnorderedSet; 6 7 mod ordered { 8 use super::{Iter, UnorderedSet}; 9 use std::borrow::Borrow; 10 use std::hash::Hash; 11 12 pub struct OrderedSet<T> { 13 set: UnorderedSet<T>, 14 vec: Vec<T>, 15 } 16 17 impl<'a, T> OrderedSet<&'a T> 18 where 19 T: Hash + Eq, 20 { new() -> Self21 pub fn new() -> Self { 22 OrderedSet { 23 set: UnorderedSet::new(), 24 vec: Vec::new(), 25 } 26 } 27 insert(&mut self, value: &'a T) -> bool28 pub fn insert(&mut self, value: &'a T) -> bool { 29 let new = self.set.insert(value); 30 if new { 31 self.vec.push(value); 32 } 33 new 34 } 35 contains<Q>(&self, value: &Q) -> bool where &'a T: Borrow<Q>, Q: ?Sized + Hash + Eq,36 pub fn contains<Q>(&self, value: &Q) -> bool 37 where 38 &'a T: Borrow<Q>, 39 Q: ?Sized + Hash + Eq, 40 { 41 self.set.contains(value) 42 } 43 get<Q>(&self, value: &Q) -> Option<&'a T> where &'a T: Borrow<Q>, Q: ?Sized + Hash + Eq,44 pub fn get<Q>(&self, value: &Q) -> Option<&'a T> 45 where 46 &'a T: Borrow<Q>, 47 Q: ?Sized + Hash + Eq, 48 { 49 self.set.get(value).copied() 50 } 51 } 52 53 impl<'a, T> OrderedSet<&'a T> { is_empty(&self) -> bool54 pub fn is_empty(&self) -> bool { 55 self.vec.is_empty() 56 } 57 iter(&self) -> Iter<'_, 'a, T>58 pub fn iter(&self) -> Iter<'_, 'a, T> { 59 Iter(self.vec.iter()) 60 } 61 } 62 63 impl<'s, 'a, T> IntoIterator for &'s OrderedSet<&'a T> { 64 type Item = &'a T; 65 type IntoIter = Iter<'s, 'a, T>; into_iter(self) -> Self::IntoIter66 fn into_iter(self) -> Self::IntoIter { 67 self.iter() 68 } 69 } 70 } 71 72 mod unordered { 73 use std::borrow::Borrow; 74 use std::collections::HashSet; 75 use std::hash::Hash; 76 77 // Wrapper prohibits accidentally introducing iteration over the set, which 78 // could lead to nondeterministic generated code. 79 pub struct UnorderedSet<T>(HashSet<T>); 80 81 impl<T> UnorderedSet<T> 82 where 83 T: Hash + Eq, 84 { new() -> Self85 pub fn new() -> Self { 86 UnorderedSet(HashSet::new()) 87 } 88 insert(&mut self, value: T) -> bool89 pub fn insert(&mut self, value: T) -> bool { 90 self.0.insert(value) 91 } 92 contains<Q>(&self, value: &Q) -> bool where T: Borrow<Q>, Q: ?Sized + Hash + Eq,93 pub fn contains<Q>(&self, value: &Q) -> bool 94 where 95 T: Borrow<Q>, 96 Q: ?Sized + Hash + Eq, 97 { 98 self.0.contains(value) 99 } 100 get<Q>(&self, value: &Q) -> Option<&T> where T: Borrow<Q>, Q: ?Sized + Hash + Eq,101 pub fn get<Q>(&self, value: &Q) -> Option<&T> 102 where 103 T: Borrow<Q>, 104 Q: ?Sized + Hash + Eq, 105 { 106 self.0.get(value) 107 } 108 retain(&mut self, f: impl FnMut(&T) -> bool)109 pub fn retain(&mut self, f: impl FnMut(&T) -> bool) { 110 self.0.retain(f); 111 } 112 } 113 } 114 115 pub struct Iter<'s, 'a, T>(slice::Iter<'s, &'a T>); 116 117 impl<'s, 'a, T> Iterator for Iter<'s, 'a, T> { 118 type Item = &'a T; 119 next(&mut self) -> Option<Self::Item>120 fn next(&mut self) -> Option<Self::Item> { 121 self.0.next().copied() 122 } 123 size_hint(&self) -> (usize, Option<usize>)124 fn size_hint(&self) -> (usize, Option<usize>) { 125 self.0.size_hint() 126 } 127 } 128 129 impl<'a, T> Debug for OrderedSet<&'a T> 130 where 131 T: Debug, 132 { fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result133 fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result { 134 formatter.debug_set().entries(self).finish() 135 } 136 } 137