use std::hash::Hash;
use allocative::Allocative;
use crate::unordered_map;
use crate::unordered_map::UnorderedMap;
use crate::Equivalent;
use crate::Hashed;
use crate::StarlarkHashValue;
#[derive(Clone, Allocative, Debug)]
pub struct UnorderedSet<T> {
map: UnorderedMap<T, ()>,
}
impl<T> Default for UnorderedSet<T> {
#[inline]
fn default() -> UnorderedSet<T> {
UnorderedSet::new()
}
}
impl<T> UnorderedSet<T> {
#[inline]
pub const fn new() -> UnorderedSet<T> {
UnorderedSet {
map: UnorderedMap::new(),
}
}
#[inline]
pub fn with_capacity(n: usize) -> UnorderedSet<T> {
UnorderedSet {
map: UnorderedMap::with_capacity(n),
}
}
#[inline]
pub fn insert(&mut self, k: T) -> bool
where
T: Hash + Eq,
{
self.map.insert(k, ()).is_none()
}
#[inline]
pub fn clear(&mut self) {
self.map.clear();
}
#[inline]
pub fn is_empty(&self) -> bool {
self.map.is_empty()
}
#[inline]
pub fn len(&self) -> usize {
self.map.len()
}
#[inline]
pub fn contains<Q>(&self, value: &Q) -> bool
where
Q: Hash + Equivalent<T> + ?Sized,
{
self.map.contains_key(value)
}
#[inline]
pub fn contains_hashed<Q>(&self, value: Hashed<&Q>) -> bool
where
Q: Equivalent<T> + ?Sized,
{
self.map.contains_key_hashed(value)
}
#[inline]
pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<T> {
RawEntryBuilderMut {
entry: self.map.raw_entry_mut(),
}
}
fn iter(&self) -> impl Iterator<Item = &T> {
self.map.entries_unordered().map(|(k, _)| k)
}
pub fn entries_sorted(&self) -> Vec<&T>
where
T: Ord,
{
let mut entries = Vec::from_iter(self.iter());
entries.sort_unstable();
entries
}
}
impl<T: Eq + Hash> PartialEq for UnorderedSet<T> {
#[inline]
fn eq(&self, other: &Self) -> bool {
self.map == other.map
}
}
impl<T: Eq + Hash> Eq for UnorderedSet<T> {}
impl<T: Eq + Hash> FromIterator<T> for UnorderedSet<T> {
#[inline]
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> UnorderedSet<T> {
UnorderedSet {
map: UnorderedMap::from_iter(iter.into_iter().map(|v| (v, ()))),
}
}
}
pub struct RawEntryBuilderMut<'a, T> {
entry: unordered_map::RawEntryBuilderMut<'a, T, ()>,
}
impl<'a, T> RawEntryBuilderMut<'a, T> {
#[inline]
pub fn from_entry<Q>(self, entry: &Q) -> RawEntryMut<'a, T>
where
Q: Hash + Equivalent<T> + ?Sized,
{
let entry = Hashed::new(entry);
self.from_entry_hashed(entry)
}
#[inline]
pub fn from_entry_hashed<Q>(self, entry: Hashed<&Q>) -> RawEntryMut<'a, T>
where
Q: ?Sized + Equivalent<T>,
{
self.from_hash(entry.hash(), |k| entry.key().equivalent(k))
}
#[inline]
pub fn from_hash<F>(self, hash: StarlarkHashValue, is_match: F) -> RawEntryMut<'a, T>
where
F: for<'b> FnMut(&'b T) -> bool,
{
match self.entry.from_hash(hash, is_match) {
unordered_map::RawEntryMut::Occupied(e) => {
RawEntryMut::Occupied(RawOccupiedEntryMut { entry: e })
}
unordered_map::RawEntryMut::Vacant(e) => {
RawEntryMut::Vacant(RawVacantEntryMut { entry: e })
}
}
}
}
pub struct RawOccupiedEntryMut<'a, T> {
entry: unordered_map::RawOccupiedEntryMut<'a, T, ()>,
}
pub struct RawVacantEntryMut<'a, T> {
entry: unordered_map::RawVacantEntryMut<'a, T, ()>,
}
pub enum RawEntryMut<'a, T> {
Occupied(RawOccupiedEntryMut<'a, T>),
Vacant(RawVacantEntryMut<'a, T>),
}
impl<'a, T> RawOccupiedEntryMut<'a, T> {
#[inline]
pub fn remove(self) -> T {
self.entry.remove_entry().0
}
#[inline]
pub fn insert(&mut self, value: T) -> T {
self.entry.insert_key(value)
}
}
impl<'a, T> RawVacantEntryMut<'a, T> {
#[inline]
pub fn insert(self, value: T)
where
T: Hash,
{
let value = Hashed::new(value);
self.insert_hashed(value);
}
#[inline]
pub fn insert_hashed(self, value: Hashed<T>)
where
T: Hash,
{
self.entry.insert_hashed(value, ());
}
}
#[cfg(test)]
mod tests {
use crate::unordered_set::UnorderedSet;
#[test]
fn test_insert() {
let mut set = UnorderedSet::new();
assert!(set.insert(10));
assert!(!set.insert(10));
assert!(set.insert(20));
assert!(!set.insert(20));
assert_eq!(set.len(), 2);
}
#[test]
fn test_entries_sorted() {
let mut set = UnorderedSet::new();
set.insert(20);
set.insert(10);
set.insert(30);
assert_eq!(set.entries_sorted(), vec![&10, &20, &30]);
}
}