extern crate linked_hash_map;
#[cfg(feature = "serde")]
pub mod serde;
use linked_hash_map as map;
use linked_hash_map::{Keys, LinkedHashMap};
use std::borrow::Borrow;
use std::collections::hash_map::RandomState;
use std::fmt;
use std::hash::{BuildHasher, Hash, Hasher};
use std::iter::{Chain, FromIterator};
use std::ops::{BitAnd, BitOr, BitXor, Sub};
pub struct LinkedHashSet<T, S = RandomState> {
map: LinkedHashMap<T, (), S>,
}
impl<T: Hash + Eq> LinkedHashSet<T, RandomState> {
#[inline]
pub fn new() -> LinkedHashSet<T, RandomState> {
LinkedHashSet { map: LinkedHashMap::new() }
}
#[inline]
pub fn with_capacity(capacity: usize) -> LinkedHashSet<T, RandomState> {
LinkedHashSet { map: LinkedHashMap::with_capacity(capacity) }
}
}
impl<T, S> LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
#[inline]
pub fn with_hasher(hasher: S) -> LinkedHashSet<T, S> {
LinkedHashSet { map: LinkedHashMap::with_hasher(hasher) }
}
#[inline]
pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> LinkedHashSet<T, S> {
LinkedHashSet { map: LinkedHashMap::with_capacity_and_hasher(capacity, hasher) }
}
pub fn hasher(&self) -> &S {
self.map.hasher()
}
#[inline]
pub fn capacity(&self) -> usize {
self.map.capacity()
}
pub fn reserve(&mut self, additional: usize) {
self.map.reserve(additional)
}
pub fn shrink_to_fit(&mut self) {
self.map.shrink_to_fit()
}
pub fn iter(&self) -> Iter<T> {
Iter { iter: self.map.keys() }
}
pub fn difference<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Difference<'a, T, S> {
Difference {
iter: self.iter(),
other,
}
}
pub fn symmetric_difference<'a>(&'a self,
other: &'a LinkedHashSet<T, S>)
-> SymmetricDifference<'a, T, S> {
SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) }
}
pub fn intersection<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Intersection<'a, T, S> {
Intersection {
iter: self.iter(),
other,
}
}
pub fn union<'a>(&'a self, other: &'a LinkedHashSet<T, S>) -> Union<'a, T, S> {
Union { iter: self.iter().chain(other.difference(self)) }
}
pub fn len(&self) -> usize {
self.map.len()
}
pub fn is_empty(&self) -> bool {
self.map.is_empty()
}
pub fn clear(&mut self) {
self.map.clear()
}
pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.contains_key(value)
}
pub fn refresh<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.get_refresh(value).is_some()
}
pub fn is_disjoint(&self, other: &LinkedHashSet<T, S>) -> bool {
self.iter().all(|v| !other.contains(v))
}
pub fn is_subset(&self, other: &LinkedHashSet<T, S>) -> bool {
self.iter().all(|v| other.contains(v))
}
#[inline]
pub fn is_superset(&self, other: &LinkedHashSet<T, S>) -> bool {
other.is_subset(self)
}
pub fn insert(&mut self, value: T) -> bool {
self.map.insert(value, ()).is_none()
}
pub fn insert_if_absent(&mut self, value: T) -> bool {
if !self.map.contains_key(&value) {
self.map.insert(value, ()).is_none()
}
else {
false
}
}
pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
where
T: Borrow<Q>,
Q: Hash + Eq,
{
self.map.remove(value).is_some()
}
pub fn front(&self) -> Option<&T> {
self.map.front().map(|(k, _)| k)
}
pub fn pop_front(&mut self) -> Option<T> {
self.map.pop_front().map(|(k, _)| k)
}
pub fn back(&mut self) -> Option<&T> {
self.map.back().map(|(k, _)| k)
}
pub fn pop_back(&mut self) -> Option<T> {
self.map.pop_back().map(|(k, _)| k)
}
}
impl<T: Hash + Eq + Clone, S: BuildHasher + Clone> Clone for LinkedHashSet<T, S> {
fn clone(&self) -> Self {
let map = self.map.clone();
Self { map }
}
}
impl<T, S> PartialEq for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
fn eq(&self, other: &LinkedHashSet<T, S>) -> bool {
if self.len() != other.len() {
return false;
}
self.iter().all(|key| other.contains(key))
}
}
impl<T, S> Hash for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
fn hash<H: Hasher>(&self, state: &mut H) {
for e in self {
e.hash(state);
}
}
}
impl<T, S> Eq for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
}
impl<T, S> fmt::Debug for LinkedHashSet<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 LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher + Default,
{
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> LinkedHashSet<T, S> {
let mut set = LinkedHashSet::with_hasher(Default::default());
set.extend(iter);
set
}
}
impl<T, S> Extend<T> for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
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 LinkedHashSet<T, S>
where
T: 'a + Eq + Hash + Copy,
S: BuildHasher,
{
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
}
impl<T, S> Default for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher + Default,
{
fn default() -> LinkedHashSet<T, S> {
LinkedHashSet { map: LinkedHashMap::default() }
}
}
impl<'a, 'b, T, S> BitOr<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = LinkedHashSet<T, S>;
fn bitor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
self.union(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> BitAnd<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = LinkedHashSet<T, S>;
fn bitand(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
self.intersection(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> BitXor<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = LinkedHashSet<T, S>;
fn bitxor(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<T, S> {
self.symmetric_difference(rhs).cloned().collect()
}
}
impl<'a, 'b, T, S> Sub<&'b LinkedHashSet<T, S>> for &'a LinkedHashSet<T, S>
where
T: Eq + Hash + Clone,
S: BuildHasher + Default,
{
type Output = LinkedHashSet<T, S>;
fn sub(self, rhs: &LinkedHashSet<T, S>) -> LinkedHashSet<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 Intersection<'a, T: 'a, S: 'a> {
iter: Iter<'a, T>,
other: &'a LinkedHashSet<T, S>,
}
pub struct Difference<'a, T: 'a, S: 'a> {
iter: Iter<'a, T>,
other: &'a LinkedHashSet<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 LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<T, S> IntoIterator for LinkedHashSet<T, S>
where
T: Eq + Hash,
S: BuildHasher,
{
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
IntoIter { iter: self.map.into_iter() }
}
}
impl<'a, K> Clone for Iter<'a, K> {
fn clone(&self) -> Iter<'a, K> {
Iter { iter: self.iter.clone() }
}
}
impl<'a, K> Iterator for Iter<'a, K> {
type Item = &'a K;
fn next(&mut self) -> Option<&'a K> {
self.iter.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<'a, K> ExactSizeIterator for Iter<'a, K> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
fn next_back(&mut self) -> Option<&'a T> {
self.iter.next_back()
}
}
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;
fn next(&mut self) -> Option<K> {
self.iter.next().map(|(k, _)| k)
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<K> ExactSizeIterator for IntoIter<K> {
fn len(&self) -> usize {
self.iter.len()
}
}
impl<K> DoubleEndedIterator for IntoIter<K> {
fn next_back(&mut self) -> Option<K> {
self.iter.next_back().map(|(k, _)| k)
}
}
impl<'a, T, S> Clone for Intersection<'a, T, S> {
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;
fn next(&mut self) -> Option<&'a T> {
loop {
match self.iter.next() {
None => return None,
Some(elt) => {
if self.other.contains(elt) {
return Some(elt);
}
}
}
}
}
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> Clone for Difference<'a, T, S> {
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;
fn next(&mut self) -> Option<&'a T> {
loop {
match self.iter.next() {
None => return None,
Some(elt) => {
if !self.other.contains(elt) {
return Some(elt);
}
}
}
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
let (_, upper) = self.iter.size_hint();
(0, upper)
}
}
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> {
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;
fn next(&mut self) -> Option<&'a T> {
self.iter.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
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> {
fn clone(&self) -> Union<'a, T, S> {
Union { iter: self.iter.clone() }
}
}
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;
fn next(&mut self) -> Option<&'a T> {
self.iter.next()
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
#[cfg(test)]
mod test_set {
use super::*;
#[test]
fn test_zero_capacities() {
type HS = LinkedHashSet<i32>;
let s = HS::new();
assert_eq!(s.capacity(), 0);
let s = HS::default();
assert_eq!(s.capacity(), 0);
let s = HS::with_hasher(RandomState::new());
assert_eq!(s.capacity(), 0);
let s = HS::with_capacity(0);
assert_eq!(s.capacity(), 0);
let s = HS::with_capacity_and_hasher(0, RandomState::new());
assert_eq!(s.capacity(), 0);
let mut s = HS::new();
s.insert(1);
s.insert(2);
s.remove(&1);
s.remove(&2);
s.shrink_to_fit();
assert_eq!(s.capacity(), 0);
let mut s = HS::new();
s.reserve(0);
assert_eq!(s.capacity(), 0);
}
#[test]
fn test_disjoint() {
let mut xs = LinkedHashSet::new();
let mut ys = LinkedHashSet::new();
assert!(xs.is_disjoint(&ys));
assert!(ys.is_disjoint(&xs));
assert!(xs.insert(5));
assert!(ys.insert(11));
assert!(xs.is_disjoint(&ys));
assert!(ys.is_disjoint(&xs));
assert!(xs.insert(7));
assert!(xs.insert(19));
assert!(xs.insert(4));
assert!(ys.insert(2));
assert!(ys.insert(-11));
assert!(xs.is_disjoint(&ys));
assert!(ys.is_disjoint(&xs));
assert!(ys.insert(7));
assert!(!xs.is_disjoint(&ys));
assert!(!ys.is_disjoint(&xs));
}
#[test]
fn test_subset_and_superset() {
let mut a = LinkedHashSet::new();
assert!(a.insert(0));
assert!(a.insert(5));
assert!(a.insert(11));
assert!(a.insert(7));
let mut b = LinkedHashSet::new();
assert!(b.insert(0));
assert!(b.insert(7));
assert!(b.insert(19));
assert!(b.insert(250));
assert!(b.insert(11));
assert!(b.insert(200));
assert!(!a.is_subset(&b));
assert!(!a.is_superset(&b));
assert!(!b.is_subset(&a));
assert!(!b.is_superset(&a));
assert!(b.insert(5));
assert!(a.is_subset(&b));
assert!(!a.is_superset(&b));
assert!(!b.is_subset(&a));
assert!(b.is_superset(&a));
}
#[test]
fn test_iterate() {
let mut a = LinkedHashSet::new();
for i in 0..32 {
assert!(a.insert(i));
}
let mut observed: u32 = 0;
for k in &a {
observed |= 1 << *k;
}
assert_eq!(observed, 0xFFFF_FFFF);
}
#[test]
fn test_intersection() {
let mut a = LinkedHashSet::new();
let mut b = LinkedHashSet::new();
assert!(a.insert(11));
assert!(a.insert(1));
assert!(a.insert(3));
assert!(a.insert(77));
assert!(a.insert(103));
assert!(a.insert(5));
assert!(a.insert(-5));
assert!(b.insert(2));
assert!(b.insert(11));
assert!(b.insert(77));
assert!(b.insert(-9));
assert!(b.insert(-42));
assert!(b.insert(5));
assert!(b.insert(3));
let mut i = 0;
let expected = [3, 5, 11, 77];
for x in a.intersection(&b) {
assert!(expected.contains(x));
i += 1
}
assert_eq!(i, expected.len());
}
#[test]
fn test_difference() {
let mut a = LinkedHashSet::new();
let mut b = LinkedHashSet::new();
assert!(a.insert(1));
assert!(a.insert(3));
assert!(a.insert(5));
assert!(a.insert(9));
assert!(a.insert(11));
assert!(b.insert(3));
assert!(b.insert(9));
let mut i = 0;
let expected = [1, 5, 11];
for x in a.difference(&b) {
assert!(expected.contains(x));
i += 1
}
assert_eq!(i, expected.len());
}
#[test]
fn test_symmetric_difference() {
let mut a = LinkedHashSet::new();
let mut b = LinkedHashSet::new();
assert!(a.insert(1));
assert!(a.insert(3));
assert!(a.insert(5));
assert!(a.insert(9));
assert!(a.insert(11));
assert!(b.insert(-2));
assert!(b.insert(3));
assert!(b.insert(9));
assert!(b.insert(14));
assert!(b.insert(22));
let mut i = 0;
let expected = [-2, 1, 5, 11, 14, 22];
for x in a.symmetric_difference(&b) {
assert!(expected.contains(x));
i += 1
}
assert_eq!(i, expected.len());
}
#[test]
fn test_union() {
let mut a = LinkedHashSet::new();
let mut b = LinkedHashSet::new();
assert!(a.insert(1));
assert!(a.insert(3));
assert!(a.insert(5));
assert!(a.insert(9));
assert!(a.insert(11));
assert!(a.insert(16));
assert!(a.insert(19));
assert!(a.insert(24));
assert!(b.insert(-2));
assert!(b.insert(1));
assert!(b.insert(5));
assert!(b.insert(9));
assert!(b.insert(13));
assert!(b.insert(19));
let mut i = 0;
let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
for x in a.union(&b) {
assert!(expected.contains(x));
i += 1
}
assert_eq!(i, expected.len());
}
#[test]
fn test_from_iter() {
let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let set: LinkedHashSet<_> = xs.iter().cloned().collect();
for x in &xs {
assert!(set.contains(x));
}
}
#[test]
fn test_move_iter() {
let hs = {
let mut hs = LinkedHashSet::new();
hs.insert('a');
hs.insert('b');
hs
};
let v = hs.into_iter().collect::<Vec<char>>();
assert!(v == ['a', 'b'] || v == ['b', 'a']);
}
#[test]
fn test_eq() {
let mut s1 = LinkedHashSet::new();
s1.insert(1);
s1.insert(2);
s1.insert(3);
let mut s2 = LinkedHashSet::new();
s2.insert(1);
s2.insert(2);
assert!(s1 != s2);
s2.insert(3);
assert_eq!(s1, s2);
}
#[test]
fn test_show() {
let mut set = LinkedHashSet::new();
let empty = LinkedHashSet::<i32>::new();
set.insert(1);
set.insert(2);
let set_str = format!("{:?}", set);
assert!(set_str == "{1, 2}" || set_str == "{2, 1}");
assert_eq!(format!("{:?}", empty), "{}");
}
#[test]
fn test_extend_ref() {
let mut a = LinkedHashSet::new();
a.insert(1);
a.extend(&[2, 3, 4]);
assert_eq!(a.len(), 4);
assert!(a.contains(&1));
assert!(a.contains(&2));
assert!(a.contains(&3));
assert!(a.contains(&4));
let mut b = LinkedHashSet::new();
b.insert(5);
b.insert(6);
a.extend(&b);
assert_eq!(a.len(), 6);
assert!(a.contains(&1));
assert!(a.contains(&2));
assert!(a.contains(&3));
assert!(a.contains(&4));
assert!(a.contains(&5));
assert!(a.contains(&6));
}
}
#[cfg(test)]
mod test_linked {
use super::*;
macro_rules! set {
($($el:expr),*) => {{
let mut set = LinkedHashSet::new();
$(
set.insert($el);
)*
set
}}
}
#[test]
fn order_is_maintained() {
let set = set![123, 234, 56, 677];
assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![123, 234, 56, 677]);
}
#[test]
fn clone_order_is_maintained() {
let set = set![123, 234, 56, 677];
assert_eq!(
set.clone().into_iter().collect::<Vec<_>>(),
vec![123, 234, 56, 677]
);
}
#[test]
fn delegate_front() {
let set = set![123, 234, 56, 677];
assert_eq!(set.front(), Some(&123));
}
#[test]
fn delegate_pop_front() {
let mut set = set![123, 234, 56, 677];
assert_eq!(set.pop_front(), Some(123));
assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![234, 56, 677]);
}
#[test]
fn delegate_back() {
let mut set = set![123, 234, 56, 677];
assert_eq!(set.back(), Some(&677));
}
#[test]
fn delegate_pop_back() {
let mut set = set![123, 234, 56, 677];
assert_eq!(set.pop_back(), Some(677));
assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![123, 234, 56]);
}
#[test]
fn double_ended_iter() {
let set = set![123, 234, 56, 677];
let mut iter = set.iter();
assert_eq!(iter.next(), Some(&123));
assert_eq!(iter.next(), Some(&234));
assert_eq!(iter.next_back(), Some(&677));
assert_eq!(iter.next_back(), Some(&56));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
#[test]
fn double_ended_into_iter() {
let mut iter = set![123, 234, 56, 677].into_iter();
assert_eq!(iter.next(), Some(123));
assert_eq!(iter.next_back(), Some(677));
assert_eq!(iter.next_back(), Some(56));
assert_eq!(iter.next_back(), Some(234));
assert_eq!(iter.next(), None);
assert_eq!(iter.next_back(), None);
}
}