use core::borrow::Borrow;
use core::fmt;
use core::hash::{BuildHasher, Hash};
use core::iter::{Chain, FromIterator, FusedIterator};
#[cfg(feature = "serde")]
use core::marker::PhantomData;
use core::ops::{BitAnd, BitOr, BitXor, Sub};
#[cfg(feature = "serde")]
use serde::de::{Deserialize, Deserializer, SeqAccess, Visitor};
#[cfg(feature = "serde")]
use serde::ser::{Serialize, Serializer};
#[cfg(feature = "serde")]
use super::size_hint;
use super::map::{self, DefaultHashBuilder, HashMap, Keys};
#[derive(Clone)]
pub struct HashSet<T, S = DefaultHashBuilder> {
map: HashMap<T, (), S>,
}
impl<T: Hash + Eq> HashSet<T, DefaultHashBuilder> {
#[inline]
pub fn new() -> HashSet<T, DefaultHashBuilder> {
HashSet {
map: HashMap::new(),
}
}
#[inline]
pub fn with_capacity(capacity: usize) -> HashSet<T, DefaultHashBuilder> {
HashSet {
map: HashMap::with_capacity(capacity),
}
}
}
impl<T, S> HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn with_hasher(hasher: S) -> HashSet<T, S> {
HashSet {
map: HashMap::with_hasher(hasher),
}
}
#[inline]
pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashSet<T, S> {
HashSet {
map: HashMap::with_capacity_and_hasher(capacity, hasher),
}
}
#[inline]
pub fn hasher(&self) -> &S {
self.map.hasher()
}
#[inline]
pub fn capacity(&self) -> usize {
self.map.capacity()
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.map.reserve(additional)
}
#[inline]
pub fn shrink_to_fit(&mut self) {
self.map.shrink_to_fit()
}
#[inline]
pub fn shrink_to(&mut self, min_capacity: usize) {
self.map.shrink_to(min_capacity)
}
#[inline]
pub fn iter(&self) -> Iter<T> {
Iter {
iter: self.map.keys(),
}
}
#[inline]
pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> {
Difference {
iter: self.iter(),
other,
}
}
#[inline]
pub fn symmetric_difference<'a>(
&'a self,
other: &'a HashSet<T, S>,
) -> SymmetricDifference<'a, T, S> {
SymmetricDifference {
iter: self.difference(other).chain(other.difference(self)),
}
}
#[inline]
pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> {
Intersection {
iter: self.iter(),
other,
}
}
#[inline]
pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> {
Union {
iter: self.iter().chain(other.difference(self)),
}
}
#[inline]
pub fn len(&self) -> usize {
self.map.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.map.is_empty()
}
#[inline]
pub fn drain(&mut self) -> Drain<T> {
Drain {
iter: self.map.drain(),
}
}
#[inline]
pub fn clear(&mut self) {
self.map.clear()
}
#[inline]
pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.contains_key(value)
}
#[inline]
pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.get_key_value(value).map(|(k, _)| k)
}
pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool {
self.iter().all(|v| !other.contains(v))
}
pub fn is_subset(&self, other: &HashSet<T, S>) -> bool {
self.iter().all(|v| other.contains(v))
}
#[inline]
pub fn is_superset(&self, other: &HashSet<T, S>) -> bool {
other.is_subset(self)
}
#[inline]
pub fn insert(&mut self, value: T) -> bool {
self.map.insert(value, ()).is_none()
}
#[inline]
pub fn replace(&mut self, value: T) -> Option<T> {
match self.map.entry(value) {
map::Entry::Occupied(occupied) => Some(occupied.replace_key()),
map::Entry::Vacant(vacant) => {
vacant.insert(());
None
}
}
}
#[inline]
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.remove(value).is_some()
}
#[inline]
pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.remove_entry(value).map(|(k, _)| k)
}
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&T) -> bool,
{
self.map.retain(|k, _| f(k));
}
}
impl<T, S> PartialEq for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
fn eq(&self, other: &HashSet<T, S>) -> bool {
if self.len() != other.len() {
return false;
}
self.iter().all(|key| other.contains(key))
}
}
impl<T, S> Eq for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<T, S> fmt::Debug for HashSet<T, S>
where
T: Eq + Hash + fmt::Debug,
S: BuildHasher,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
impl<T, S> FromIterator<T> for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher + Default,
{
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> HashSet<T, S> {
let mut set = HashSet::with_hasher(Default::default());
set.extend(iter);
set
}
}
impl<T, S> Extend<T> for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
#[inline]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
self.map.extend(iter.into_iter().map(|k| (k, ())));
}
}
impl<'a, T, S> Extend<&'a T> for HashSet<T, S>
where
T: 'a + Eq + Hash + Copy,
S: BuildHasher,
{
#[inline]
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
impl<T, S> Default for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher + Default,
{
#[inline]
fn default() -> HashSet<T, S> {
HashSet {
map: HashMap::default(),
}
}
}
impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = HashSet<T, S>;
fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
self.union(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = HashSet<T, S>;
fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
self.intersection(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = HashSet<T, S>;
fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
self.symmetric_difference(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = HashSet<T, S>;
fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
self.difference(rhs).cloned().collect()
}
}
pub struct Iter<'a, K: 'a> {
iter: Keys<'a, K, ()>,
}
pub struct IntoIter<K> {
iter: map::IntoIter<K, ()>,
}
pub struct Drain<'a, K: 'a> {
iter: map::Drain<'a, K, ()>,
}
pub struct Intersection<'a, T: 'a, S: 'a> {
iter: Iter<'a, T>,
other: &'a HashSet<T, S>,
}
pub struct Difference<'a, T: 'a, S: 'a> {
iter: Iter<'a, T>,
other: &'a HashSet<T, S>,
}
pub struct SymmetricDifference<'a, T: 'a, S: 'a> {
iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>>,
}
pub struct Union<'a, T: 'a, S: 'a> {
iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
}
impl<'a, T, S> IntoIterator for &'a HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
type IntoIter = Iter<'a, T>;
#[inline]
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<T, S> IntoIterator for HashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = T;
type IntoIter = IntoIter<T>;
#[inline]
fn into_iter(self) -> IntoIter<T> {
IntoIter {
iter: self.map.into_iter(),
}
}
}
impl<'a, K> Clone for Iter<'a, K> {
#[inline]
fn clone(&self) -> Iter<'a, K> {
Iter {
iter: self.iter.clone(),
}
}
}
impl<'a, K> Iterator for Iter<'a, K> {
type Item = &'a K;
#[inline]
fn next(&mut self) -> Option<&'a K> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K> ExactSizeIterator for Iter<'a, K> {
#[inline]
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K> FusedIterator for Iter<'a, K> {}
impl<'a, K: fmt::Debug> fmt::Debug for Iter<'a, K> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<K> Iterator for IntoIter<K> {
type Item = K;
#[inline]
fn next(&mut self) -> Option<K> {
self.iter.next().map(|(k, _)| k)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<K> ExactSizeIterator for IntoIter<K> {
#[inline]
fn len(&self) -> usize {
self.iter.len()
}
}
impl<K> FusedIterator for IntoIter<K> {}
impl<K: fmt::Debug> fmt::Debug for IntoIter<K> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
impl<'a, K> Iterator for Drain<'a, K> {
type Item = K;
#[inline]
fn next(&mut self) -> Option<K> {
self.iter.next().map(|(k, _)| k)
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K> ExactSizeIterator for Drain<'a, K> {
#[inline]
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, K> FusedIterator for Drain<'a, K> {}
impl<'a, K: fmt::Debug> fmt::Debug for Drain<'a, K> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let entries_iter = self.iter.iter().map(|(k, _)| k);
f.debug_list().entries(entries_iter).finish()
}
}
impl<'a, T, S> Clone for Intersection<'a, T, S> {
#[inline]
fn clone(&self) -> Intersection<'a, T, S> {
Intersection {
iter: self.iter.clone(),
..*self
}
}
}
impl<'a, T, S> Iterator for Intersection<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
loop {
let elt = self.iter.next()?;
if self.other.contains(elt) {
return Some(elt);
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
}
impl<'a, T, S> fmt::Debug for Intersection<'a, T, S>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<'a, T, S> FusedIterator for Intersection<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<'a, T, S> Clone for Difference<'a, T, S> {
#[inline]
fn clone(&self) -> Difference<'a, T, S> {
Difference {
iter: self.iter.clone(),
..*self
}
}
}
impl<'a, T, S> Iterator for Difference<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
loop {
let elt = self.iter.next()?;
if !self.other.contains(elt) {
return Some(elt);
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
}
impl<'a, T, S> FusedIterator for Difference<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<'a, T, S> fmt::Debug for Difference<'a, T, S>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> {
#[inline]
fn clone(&self) -> SymmetricDifference<'a, T, S> {
SymmetricDifference {
iter: self.iter.clone(),
}
}
}
impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, T, S> FusedIterator for SymmetricDifference<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<'a, T, S> fmt::Debug for SymmetricDifference<'a, T, S>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<'a, T, S> Clone for Union<'a, T, S> {
#[inline]
fn clone(&self) -> Union<'a, T, S> {
Union {
iter: self.iter.clone(),
}
}
}
impl<'a, T, S> FusedIterator for Union<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<'a, T, S> fmt::Debug for Union<'a, T, S>
where
T: fmt::Debug + Eq + Hash,
S: BuildHasher,
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
f.debug_list().entries(self.clone()).finish()
}
}
impl<'a, T, S> Iterator for Union<'a, T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
#[cfg(feature = "serde")]
impl<T, H> Serialize for HashSet<T, H>
where
T: Serialize + Eq + Hash,
H: BuildHasher,
{
#[inline]
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
serializer.collect_seq(self)
}
}
#[cfg(feature = "serde")]
impl<'de, T, S> Deserialize<'de> for HashSet<T, S>
where
T: Deserialize<'de> + Eq + Hash,
S: BuildHasher + Default,
{
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
struct SeqVisitor<T, S> {
marker: PhantomData<HashSet<T, S>>,
}
impl<'de, T, S> Visitor<'de> for SeqVisitor<T, S>
where
T: Deserialize<'de> + Eq + Hash,
S: BuildHasher + Default,
{
type Value = HashSet<T, S>;
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("a sequence")
}
#[inline]
fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
let mut values = HashSet::with_capacity_and_hasher(
size_hint::cautious(seq.size_hint()),
S::default(),
);
while let Some(value) = seq.next_element()? {
values.insert(value);
}
Ok(values)
}
}
let visitor = SeqVisitor { marker: PhantomData };
deserializer.deserialize_seq(visitor)
}
fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
where
D: Deserializer<'de>,
{
struct SeqInPlaceVisitor<'a, T: 'a, S: 'a>(&'a mut HashSet<T, S>);
impl<'a, 'de, T, S> Visitor<'de> for SeqInPlaceVisitor<'a, T, S>
where
T: Deserialize<'de> + Eq + Hash,
S: BuildHasher + Default,
{
type Value = ();
fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
formatter.write_str("a sequence")
}
#[inline]
fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
where
A: SeqAccess<'de>,
{
self.0.clear();
self.0.reserve(size_hint::cautious(seq.size_hint()));
while let Some(value) = seq.next_element()? {
self.0.insert(value);
}
Ok(())
}
}
deserializer.deserialize_seq(SeqInPlaceVisitor(place))
}
}
#[allow(dead_code)]
fn assert_covariance() {
fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
v
}
fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
v
}
fn into_iter<'new>(v: IntoIter<&'static str>) -> IntoIter<&'new str> {
v
}
fn difference<'a, 'new>(
v: Difference<'a, &'static str, DefaultHashBuilder>,
) -> Difference<'a, &'new str, DefaultHashBuilder> {
v
}
fn symmetric_difference<'a, 'new>(
v: SymmetricDifference<'a, &'static str, DefaultHashBuilder>,
) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder> {
v
}
fn intersection<'a, 'new>(
v: Intersection<'a, &'static str, DefaultHashBuilder>,
) -> Intersection<'a, &'new str, DefaultHashBuilder> {
v
}
fn union<'a, 'new>(
v: Union<'a, &'static str, DefaultHashBuilder>,
) -> Union<'a, &'new str, DefaultHashBuilder> {
v
}
fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
d
}
}