use std;
use std::collections::HashSet;
use std::hash::Hash;
use std::borrow::Borrow;
/// The number of elements stored in an array before moving up to the
/// `HashSet` implementation.
pub const CAPACITY: usize = 8;
/// A set that is a `HashSet` when it has many elements, but is just
/// an array for small set sizes.
///
/// As with the `HashSet` type, a `Set` requires that the
/// elements implement the Eq and Hash traits. This can frequently be
/// achieved by using #[derive(PartialEq, Eq, Hash)]. In addition,
/// `Set` requires that the elements implement the `Copy` trait,
/// and really they should be pretty small, since Set always
/// stores room for `CAPACITY` elements.
#[derive(Debug, Clone)]
pub struct Set<T: Copy + Eq + Hash> {
inner: SS<T>,
}
#[derive(Debug, Clone)]
enum SS<T: Copy+Eq+Hash> {
Small(usize, [T;CAPACITY]),
Large(HashSet<T>),
}
/// An iterator for consuming sets.
pub struct IntoIter<T: Copy+Eq+Hash> {
inner: IntoIt<T>,
}
enum IntoIt<T: Copy+Eq+Hash> {
Small(std::vec::IntoIter<T>),
Large(std::collections::hash_set::IntoIter<T>),
}
/// An iterator for sets.
pub struct Iter<'a, T: 'a+Copy+Eq+Hash> {
inner: It<'a, T>,
}
enum It<'a, T: 'a+Copy+Eq+Hash> {
Small(std::slice::Iter<'a, T>),
Large(std::collections::hash_set::Iter<'a, T>),
}
impl<T: Copy+Eq+Hash> Set<T> {
/// Creates an empty set..
pub fn new() -> Set<T> {
Set { inner: SS::Small(0, unsafe { std::mem::uninitialized() }) }
}
/// Creates an empty set with the specified capacity.
pub fn with_capacity(cap: usize) -> Set<T> {
if cap > CAPACITY {
Set { inner: SS::Large(HashSet::with_capacity(cap)) }
} else {
Set::new()
}
}
/// Returns the number of elements in the set.
pub fn len(&self) -> usize {
match self.inner {
SS::Large(ref s) => s.len(),
SS::Small(len, _) => len,
}
}
/// Reserves capacity for at least `additional` more elements to be
/// inserted in the set. The collection may reserve more space
/// to avoid frequent reallocations.
pub fn reserve(&mut self, additional: usize) {
match self.inner {
SS::Large(ref mut s) => {
s.reserve(additional);
return;
},
SS::Small(len, arr) => {
let mut s = HashSet::with_capacity(additional+CAPACITY);
for i in 0..len {
s.insert(arr[i]);
}
*self = Set { inner: SS::Large(s) }
},
}
}
/// Adds a value to the set.
///
/// If the set did not have this value present, `true` is returned.
///
/// If the set did have this value present, `false` is returned.
pub fn insert(&mut self, elem: T) -> bool {
match self.inner {
SS::Large(ref mut s) => {
return s.insert(elem);
},
SS::Small(ref mut len, ref mut arr) => {
for i in 0 .. *len {
if arr[i] == elem {
return false;
}
}
if *len < CAPACITY {
arr[*len] = elem;
*len += 1;
return true;
}
},
}
match self.inner {
SS::Large(_) => unreachable!(),
SS::Small(len, arr) => {
let mut s = HashSet::with_capacity(1+CAPACITY);
for i in 0..len {
s.insert(arr[i]);
}
s.insert(elem);
*self = Set { inner: SS::Large(s) };
true
},
}
}
/// Removes an element, and returns true if that element was present.
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>, Q: Hash + Eq,
{
match self.inner {
SS::Large(ref mut s) => s.remove(value),
SS::Small(ref mut len, ref mut arr) => {
for i in 0..*len {
if arr[i].borrow() == value {
*len -= 1;
for j in i..*len {
arr[j] = arr[j+1];
}
return true;
}
}
false
},
}
}
/// Returns true if the set contains a value.
pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>, Q: Hash + Eq,
{
match self.inner {
SS::Large(ref s) => {
s.contains(value)
},
SS::Small(len, ref arr) => {
for i in 0 .. len {
if arr[i].borrow() == value {
return true;
}
}
false
},
}
}
/// Returns an iterator over the set.
pub fn iter(&self) -> Iter<T> {
Iter {
inner:
match self.inner {
SS::Large(ref s) => {
It::Large(s.iter())
},
SS::Small(len, ref arr) => {
It::Small(arr[0..len].iter())
},
}
}
}
/// Clears the set, returning all elements in an iterator.
pub fn drain(&mut self) -> IntoIter<T> {
let mut s = Set::new();
std::mem::swap(&mut s, self);
IntoIter {
inner:
match s.inner {
SS::Large(s) => {
IntoIt::Large(s.into_iter())
},
SS::Small(len, ref arr) => {
IntoIt::Small(Vec::from(&arr[0..len]).into_iter())
},
}
}
}
}
impl<T: Hash+Copy+Eq> std::iter::FromIterator<T> for Set<T> {
fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> Self {
let iter = iter.into_iter();
let (sz,_) = iter.size_hint();
let mut c = Set::with_capacity(sz);
for i in iter {
c.insert(i);
}
c
}
}
impl<'a, T: 'a+Eq+Hash+Copy> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
match self.inner {
It::Large(ref mut it) => it.next(),
It::Small(ref mut it) => it.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self.inner {
It::Large(ref it) => it.size_hint(),
It::Small(ref it) => it.size_hint(),
}
}
}
impl<T: Eq+Hash+Copy> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
match self.inner {
IntoIt::Large(ref mut it) => it.next(),
IntoIt::Small(ref mut it) => it.next(),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
match self.inner {
IntoIt::Large(ref it) => it.size_hint(),
IntoIt::Small(ref it) => it.size_hint(),
}
}
}
impl<'a, T: Eq+Hash+Copy> IntoIterator for &'a Set<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<T: Eq+Hash+Copy> IntoIterator for Set<T> {
type Item = T;
type IntoIter = IntoIter<T>;
/// Creates a consuming iterator, that is, one that moves each value out
/// of the set in arbitrary order. The set cannot be used after calling
/// this.
///
/// # Examples
///
/// ```
/// use david_set::Set;
/// let mut set: Set<u32> = Set::new();
/// set.insert(2);
/// set.insert(5);
///
/// // Not possible to collect to a Vec<String> with a regular `.iter()`.
/// let v: Vec<_> = set.into_iter().collect();
///
/// // Will print in an arbitrary order.
/// for x in &v {
/// println!("{}", x);
/// }
/// ```
fn into_iter(self) -> IntoIter<T> {
IntoIter {
inner:
match self.inner {
SS::Large(s) => {
IntoIt::Large(s.into_iter())
},
SS::Small(len, arr) => {
IntoIt::Small(Vec::from(&arr[0..len]).into_iter())
},
}
}
}
}
impl<'a, 'b, T: Eq+Hash+Copy> std::ops::Sub<&'b Set<T>> for &'a Set<T> {
type Output = Set<T>;
/// Returns the difference of `self` and `rhs` as a new `Set<T>`.
///
/// # Examples
///
/// ```
/// use david_set::Set;
///
/// let a: Set<u32> = vec![1, 2, 3].into_iter().collect();
/// let b: Set<u32> = vec![3, 4, 5].into_iter().collect();
///
/// let set = &a - &b;
///
/// let mut i = 0;
/// let expected = [1, 2];
/// for x in &set {
/// assert!(expected.contains(x));
/// i += 1;
/// }
/// assert_eq!(i, expected.len());
/// ```
fn sub(self, rhs: &Set<T>) -> Set<T> {
let mut s = Set::with_capacity(self.len());
for v in self.iter() {
if !rhs.contains(v) {
s.insert(*v);
}
}
s
}
}
impl<T: Eq+Hash+Copy> Extend<T> for Set<T> {
/// Adds a bunch of elements to the set
///
/// # Examples
///
/// ```
/// use david_set::Set;
///
/// let mut a: Set<u32> = vec![1, 2, 3].into_iter().collect();
/// a.extend(vec![3, 4, 5]);
///
/// let mut i = 0;
/// let expected = [1, 2, 3, 4, 5];
/// for x in &a {
/// assert!(expected.contains(x));
/// i += 1;
/// }
/// assert_eq!(i, expected.len());
/// ```
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let iter = iter.into_iter();
let (sz,_) = iter.size_hint();
self.reserve(sz);
for i in iter {
self.insert(i);
}
}
}
impl<'a, 'b, T: Eq+Hash+Copy> std::ops::BitOr<&'b Set<T>> for &'a Set<T> {
type Output = Set<T>;
/// Returns the union of `self` and `rhs` as a new `Set<T>`.
///
/// # Examples
///
/// ```
/// use david_set::Set;
///
/// let a: Set<u32> = vec![1, 2, 3].into_iter().collect();
/// let b: Set<u32> = vec![3, 4, 5].into_iter().collect();
///
/// let set = &a | &b;
///
/// let mut i = 0;
/// let expected = [1, 2, 3, 4, 5];
/// for x in &set {
/// assert!(expected.contains(x));
/// i += 1;
/// }
/// assert_eq!(i, expected.len());
/// ```
fn bitor(self, rhs: &Set<T>) -> Set<T> {
let mut s: Set<T> = Set::with_capacity(self.len() + rhs.len());
for &x in self.iter() {
s.insert(x);
}
for &x in rhs.iter() {
s.insert(x);
}
s
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
let mut ss: Set<usize> = Set::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::<Set<usize>>());
println!(" hash size: {}", std::mem::size_of::<HashSet<usize>>());
assert!(std::mem::size_of::<Set<usize>>() <=
2*std::mem::size_of::<HashSet<usize>>());
}
}