ordermap/
set.rs

1//! A hash set implemented using `OrderMap`
2
3use std::cmp::Ordering;
4use std::collections::hash_map::RandomState;
5use std::fmt;
6use std::iter::{FromIterator, Chain};
7use std::hash::{Hash, BuildHasher};
8use std::mem::replace;
9use std::ops::RangeFull;
10use std::ops::{BitAnd, BitOr, BitXor, Sub};
11use std::slice;
12use std::vec;
13
14use super::{OrderMap, Equivalent};
15
16type Bucket<T> = super::Bucket<T, ()>;
17
18/// A hash set where the iteration order of the values is independent of their
19/// hash values.
20///
21/// The interface is closely compatible with the standard `HashSet`, but also
22/// has additional features.
23///
24/// # Order
25///
26/// The values have a consistent order that is determined by the sequence of
27/// insertion and removal calls on the set. The order does not depend on the
28/// values or the hash function at all. Note that insertion order and value
29/// are not affected if a re-insertion is attempted once an element is
30/// already present.
31///
32/// All iterators traverse the set *in order*.  Set operation iterators like
33/// `union` produce a concatenated order, as do their matching "bitwise"
34/// operators.  See their documentation for specifics.
35///
36/// # Indices
37///
38/// The values are indexed in a compact range without holes in the range
39/// `0..self.len()`. For example, the method `.get_full` looks up the index for
40/// a value, and the method `.get_index` looks up the value by index.
41///
42/// # Examples
43///
44/// ```
45/// use ordermap::OrderSet;
46///
47/// // Collects which letters appear in a sentence.
48/// let letters: OrderSet<_> = "a short treatise on fungi".chars().collect();
49/// 
50/// assert!(letters.contains(&'s'));
51/// assert!(letters.contains(&'t'));
52/// assert!(letters.contains(&'u'));
53/// assert!(!letters.contains(&'y'));
54/// ```
55#[derive(Clone)]
56pub struct OrderSet<T, S = RandomState> {
57    map: OrderMap<T, (), S>,
58}
59
60impl<T, S> fmt::Debug for OrderSet<T, S>
61    where T: fmt::Debug + Hash + Eq,
62          S: BuildHasher,
63{
64    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
65        if cfg!(not(feature = "test_debug")) {
66            f.debug_set().entries(self.iter()).finish()
67        } else {
68            // Let the inner `OrderMap` print all of its details
69            f.debug_struct("OrderSet").field("map", &self.map).finish()
70        }
71    }
72}
73
74impl<T> OrderSet<T> {
75    /// Create a new set. (Does not allocate.)
76    pub fn new() -> Self {
77        OrderSet { map: OrderMap::new() }
78    }
79
80    /// Create a new set with capacity for `n` elements.
81    /// (Does not allocate if `n` is zero.)
82    ///
83    /// Computes in **O(n)** time.
84    pub fn with_capacity(n: usize) -> Self {
85        OrderSet { map: OrderMap::with_capacity(n) }
86    }
87}
88
89impl<T, S> OrderSet<T, S> {
90    /// Create a new set with capacity for `n` elements.
91    /// (Does not allocate if `n` is zero.)
92    ///
93    /// Computes in **O(n)** time.
94    pub fn with_capacity_and_hasher(n: usize, hash_builder: S) -> Self
95        where S: BuildHasher
96    {
97        OrderSet { map: OrderMap::with_capacity_and_hasher(n, hash_builder) }
98    }
99
100    /// Return the number of elements in the set.
101    ///
102    /// Computes in **O(1)** time.
103    pub fn len(&self) -> usize {
104        self.map.len()
105    }
106
107    /// Returns true if the set contains no elements.
108    ///
109    /// Computes in **O(1)** time.
110    pub fn is_empty(&self) -> bool {
111        self.map.is_empty()
112    }
113
114    /// Create a new set with `hash_builder`
115    pub fn with_hasher(hash_builder: S) -> Self
116        where S: BuildHasher
117    {
118        OrderSet { map: OrderMap::with_hasher(hash_builder) }
119    }
120
121    /// Return a reference to the set's `BuildHasher`.
122    pub fn hasher(&self) -> &S
123        where S: BuildHasher
124    {
125        self.map.hasher()
126    }
127
128    /// Computes in **O(1)** time.
129    pub fn capacity(&self) -> usize {
130        self.map.capacity()
131    }
132}
133
134impl<T, S> OrderSet<T, S>
135    where T: Hash + Eq,
136          S: BuildHasher,
137{
138    /// Remove all elements in the set, while preserving its capacity.
139    ///
140    /// Computes in **O(n)** time.
141    pub fn clear(&mut self) {
142        self.map.clear();
143    }
144
145    /// FIXME Not implemented fully yet
146    pub fn reserve(&mut self, additional: usize) {
147        self.map.reserve(additional);
148    }
149
150    /// Insert the value into the set.
151    ///
152    /// If an equivalent item already exists in the set, it returns
153    /// `false` leaving the original value in the set and without
154    /// altering its insertion order. Otherwise, it inserts the new
155    /// item and returns `true`.
156    ///
157    /// Computes in **O(1)** time (amortized average).
158    pub fn insert(&mut self, value: T) -> bool {
159        self.map.insert(value, ()).is_none()
160    }
161
162    /// Return an iterator over the values of the set, in their order
163    pub fn iter(&self) -> Iter<T> {
164        Iter {
165            iter: self.map.keys().iter
166        }
167    }
168
169    /// Return an iterator over the values that are in `self` but not `other`.
170    ///
171    /// Values are produced in the same order that they appear in `self`.
172    pub fn difference<'a, S2>(&'a self, other: &'a OrderSet<T, S2>) -> Difference<'a, T, S2>
173        where S2: BuildHasher
174    {
175        Difference {
176            iter: self.iter(),
177            other: other,
178        }
179    }
180
181    /// Return an iterator over the values that are in `self` or `other`,
182    /// but not in both.
183    ///
184    /// Values from `self` are produced in their original order, followed by
185    /// values from `other` in their original order.
186    pub fn symmetric_difference<'a, S2>(&'a self, other: &'a OrderSet<T, S2>)
187        -> SymmetricDifference<'a, T, S, S2>
188        where S2: BuildHasher
189    {
190        SymmetricDifference {
191            iter: self.difference(other).chain(other.difference(self)),
192        }
193    }
194
195    /// Return an iterator over the values that are in both `self` and `other`.
196    ///
197    /// Values are produced in the same order that they appear in `self`.
198    pub fn intersection<'a, S2>(&'a self, other: &'a OrderSet<T, S2>) -> Intersection<'a, T, S2>
199        where S2: BuildHasher
200    {
201        Intersection {
202            iter: self.iter(),
203            other: other,
204        }
205    }
206
207    /// Return an iterator over all values that are in `self` or `other`.
208    ///
209    /// Values from `self` are produced in their original order, followed by
210    /// values that are unique to `other` in their original order.
211    pub fn union<'a, S2>(&'a self, other: &'a OrderSet<T, S2>) -> Union<'a, T, S>
212        where S2: BuildHasher
213    {
214        Union {
215            iter: self.iter().chain(other.difference(self)),
216        }
217    }
218
219    /// Return `true` if an equivalent to `value` exists in the set.
220    ///
221    /// Computes in **O(1)** time (average).
222    pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
223        where Q: Hash + Equivalent<T>,
224    {
225        self.map.contains_key(value)
226    }
227
228    /// Return a reference to the value stored in the set, if it is present,
229    /// else `None`.
230    ///
231    /// Computes in **O(1)** time (average).
232    pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T>
233        where Q: Hash + Equivalent<T>,
234    {
235        self.map.get_full(value).map(|(_, x, &())| x)
236    }
237
238    /// Return item index and value
239    pub fn get_full<Q: ?Sized>(&self, value: &Q) -> Option<(usize, &T)>
240        where Q: Hash + Equivalent<T>,
241    {
242        self.map.get_full(value).map(|(i, x, &())| (i, x))
243    }
244
245    /// Adds a value to the set, replacing the existing value, if any, that is
246    /// equal to the given one. Returns the replaced value.
247    ///
248    /// Computes in **O(1)** time (average).
249    pub fn replace(&mut self, value: T) -> Option<T>
250    {
251        use super::Entry::*;
252
253        match self.map.entry(value) {
254            Vacant(e) => { e.insert(()); None },
255            Occupied(e) => {
256                // FIXME uses private fields!
257                let old_key = &mut e.map.entries[e.index].key;
258                Some(replace(old_key, e.key))
259            }
260        }
261    }
262
263    /// FIXME Same as .swap_remove
264    ///
265    /// Computes in **O(1)** time (average).
266    pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool
267        where Q: Hash + Equivalent<T>,
268    {
269        self.swap_remove(value)
270    }
271
272    /// Remove the value from the set, and return `true` if it was present.
273    ///
274    /// Like `Vec::swap_remove`, the value is removed by swapping it with the
275    /// last element of the set and popping it off. **This perturbs
276    /// the postion of what used to be the last element!**
277    ///
278    /// Return `false` if `value` was not in the set.
279    ///
280    /// Computes in **O(1)** time (average).
281    pub fn swap_remove<Q: ?Sized>(&mut self, value: &Q) -> bool
282        where Q: Hash + Equivalent<T>,
283    {
284        self.map.swap_remove(value).is_some()
285    }
286
287    /// FIXME Same as .swap_take
288    ///
289    /// Computes in **O(1)** time (average).
290    pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
291        where Q: Hash + Equivalent<T>,
292    {
293        self.swap_take(value)
294    }
295
296    /// Removes and returns the value in the set, if any, that is equal to the
297    /// given one.
298    ///
299    /// Like `Vec::swap_remove`, the value is removed by swapping it with the
300    /// last element of the set and popping it off. **This perturbs
301    /// the postion of what used to be the last element!**
302    ///
303    /// Return `None` if `value` was not in the set.
304    ///
305    /// Computes in **O(1)** time (average).
306    pub fn swap_take<Q: ?Sized>(&mut self, value: &Q) -> Option<T>
307        where Q: Hash + Equivalent<T>,
308    {
309        self.map.swap_remove_full(value).map(|(_, x, ())| x)
310    }
311
312    /// Remove the value from the set return it and the index it had.
313    ///
314    /// Like `Vec::swap_remove`, the value is removed by swapping it with the
315    /// last element of the set and popping it off. **This perturbs
316    /// the postion of what used to be the last element!**
317    ///
318    /// Return `None` if `value` was not in the set.
319    pub fn swap_remove_full<Q: ?Sized>(&mut self, value: &Q) -> Option<(usize, T)>
320        where Q: Hash + Equivalent<T>,
321    {
322        self.map.swap_remove_full(value).map(|(i, x, ())| (i, x))
323    }
324
325    /// Remove the last value
326    ///
327    /// Computes in **O(1)** time (average).
328    pub fn pop(&mut self) -> Option<T> {
329        self.map.pop().map(|(x, ())| x)
330    }
331
332    /// Scan through each value in the set and keep those where the
333    /// closure `keep` returns `true`.
334    ///
335    /// The elements are visited in order, and remaining elements keep their
336    /// order.
337    ///
338    /// Computes in **O(n)** time (average).
339    pub fn retain<F>(&mut self, mut keep: F)
340        where F: FnMut(&T) -> bool,
341    {
342        self.map.retain(move |x, &mut ()| keep(x))
343    }
344
345    /// Sort the set’s values by their default ordering.
346    ///
347    /// See `sort_by` for details.
348    pub fn sort(&mut self)
349        where T: Ord,
350    {
351        self.map.sort_keys()
352    }
353
354    /// Sort the set’s values in place using the comparison function `compare`.
355    ///
356    /// Computes in **O(n log n)** time and **O(n)** space. The sort is stable.
357    pub fn sort_by<F>(&mut self, mut compare: F)
358        where F: FnMut(&T, &T) -> Ordering,
359    {
360        self.map.sort_by(move |a, _, b, _| compare(a, b));
361    }
362
363    /// Sort the values of the set and return a by value iterator of
364    /// the values with the result.
365    ///
366    /// The sort is stable.
367    pub fn sorted_by<F>(self, mut cmp: F) -> IntoIter<T>
368        where F: FnMut(&T, &T) -> Ordering
369    {
370        IntoIter {
371            iter: self.map.sorted_by(move |a, &(), b, &()| cmp(a, b)).iter,
372        }
373    }
374
375    /// Clears the `OrderSet`, returning all values as a drain iterator.
376    /// Keeps the allocated memory for reuse.
377    pub fn drain(&mut self, range: RangeFull) -> Drain<T> {
378        Drain {
379            iter: self.map.drain(range).iter,
380        }
381    }
382}
383
384impl<T, S> OrderSet<T, S> {
385    /// Get a value by index
386    ///
387    /// Valid indices are *0 <= index < self.len()*
388    ///
389    /// Computes in **O(1)** time.
390    pub fn get_index(&self, index: usize) -> Option<&T> {
391        self.map.get_index(index).map(|(x, &())| x)
392    }
393
394    /// Remove the key-value pair by index
395    ///
396    /// Valid indices are *0 <= index < self.len()*
397    ///
398    /// Computes in **O(1)** time (average).
399    pub fn swap_remove_index(&mut self, index: usize) -> Option<T> {
400        self.map.swap_remove_index(index).map(|(x, ())| x)
401    }
402}
403
404
405pub struct IntoIter<T> {
406    iter: vec::IntoIter<Bucket<T>>,
407}
408
409impl<T> Iterator for IntoIter<T> {
410    type Item = T;
411
412    iterator_methods!(|entry| entry.key);
413}
414
415impl<T> DoubleEndedIterator for IntoIter<T> {
416    fn next_back(&mut self) -> Option<Self::Item> {
417        self.iter.next_back().map(|entry| entry.key)
418    }
419}
420
421impl<T> ExactSizeIterator for IntoIter<T> {
422    fn len(&self) -> usize {
423        self.iter.len()
424    }
425}
426
427
428pub struct Iter<'a, T: 'a> {
429    iter: slice::Iter<'a, Bucket<T>>,
430}
431
432impl<'a, T> Iterator for Iter<'a, T> {
433    type Item = &'a T;
434
435    iterator_methods!(|entry| &entry.key);
436}
437
438impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
439    fn next_back(&mut self) -> Option<Self::Item> {
440        self.iter.next_back().map(|entry| &entry.key)
441    }
442}
443
444impl<'a, T> ExactSizeIterator for Iter<'a, T> {
445    fn len(&self) -> usize {
446        self.iter.len()
447    }
448}
449
450pub struct Drain<'a, T: 'a> {
451    iter: vec::Drain<'a, Bucket<T>>,
452}
453
454impl<'a, T> Iterator for Drain<'a, T> {
455    type Item = T;
456
457    iterator_methods!(|bucket| bucket.key);
458}
459
460impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
461    double_ended_iterator_methods!(|bucket| bucket.key);
462}
463
464impl<'a, T, S> IntoIterator for &'a OrderSet<T, S>
465    where T: Hash + Eq,
466          S: BuildHasher,
467{
468    type Item = &'a T;
469    type IntoIter = Iter<'a, T>;
470
471    fn into_iter(self) -> Self::IntoIter {
472        self.iter()
473    }
474}
475
476impl<T, S> IntoIterator for OrderSet<T, S>
477    where T: Hash + Eq,
478          S: BuildHasher,
479{
480    type Item = T;
481    type IntoIter = IntoIter<T>;
482
483    fn into_iter(self) -> Self::IntoIter {
484        IntoIter {
485            iter: self.map.into_iter().iter,
486        }
487    }
488}
489
490impl<T, S> FromIterator<T> for OrderSet<T, S>
491    where T: Hash + Eq,
492          S: BuildHasher + Default,
493{
494    fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> Self {
495        let iter = iterable.into_iter().map(|x| (x, ()));
496        OrderSet { map: OrderMap::from_iter(iter) }
497    }
498}
499
500impl<T, S> Extend<T> for OrderSet<T, S>
501    where T: Hash + Eq,
502          S: BuildHasher,
503{
504    fn extend<I: IntoIterator<Item=T>>(&mut self, iterable: I) {
505        let iter = iterable.into_iter().map(|x| (x, ()));
506        self.map.extend(iter);
507    }
508}
509
510impl<'a, T, S> Extend<&'a T> for OrderSet<T, S>
511    where T: Hash + Eq + Copy,
512          S: BuildHasher,
513{
514    fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iterable: I) {
515        let iter = iterable.into_iter().map(|&x| x);
516        self.extend(iter);
517    }
518}
519
520
521impl<T, S> Default for OrderSet<T, S>
522    where S: BuildHasher + Default,
523{
524    /// Return an empty `OrderSet`
525    fn default() -> Self {
526        OrderSet { map: OrderMap::default() }
527    }
528}
529
530impl<T, S1, S2> PartialEq<OrderSet<T, S2>> for OrderSet<T, S1>
531    where T: Hash + Eq,
532          S1: BuildHasher,
533          S2: BuildHasher
534{
535    fn eq(&self, other: &OrderSet<T, S2>) -> bool {
536        self.len() == other.len() && self.is_subset(other)
537    }
538}
539
540impl<T, S> Eq for OrderSet<T, S>
541    where T: Eq + Hash,
542          S: BuildHasher
543{
544}
545
546impl<T, S> OrderSet<T, S>
547    where T: Eq + Hash,
548          S: BuildHasher
549{
550    /// Returns `true` if `self` has no elements in common with `other`.
551    pub fn is_disjoint<S2>(&self, other: &OrderSet<T, S2>) -> bool
552        where S2: BuildHasher
553    {
554        if self.len() <= other.len() {
555            self.iter().all(move |value| !other.contains(value))
556        } else {
557            other.iter().all(move |value| !self.contains(value))
558        }
559    }
560
561    /// Returns `true` if all elements of `self` are contained in `other`.
562    pub fn is_subset<S2>(&self, other: &OrderSet<T, S2>) -> bool
563        where S2: BuildHasher
564    {
565        self.len() <= other.len() && self.iter().all(move |value| other.contains(value))
566    }
567
568    /// Returns `true` if all elements of `other` are contained in `self`.
569    pub fn is_superset<S2>(&self, other: &OrderSet<T, S2>) -> bool
570        where S2: BuildHasher
571    {
572        other.is_subset(self)
573    }
574}
575
576
577pub struct Difference<'a, T: 'a, S: 'a> {
578    iter: Iter<'a, T>,
579    other: &'a OrderSet<T, S>,
580}
581
582impl<'a, T, S> Iterator for Difference<'a, T, S>
583    where T: Eq + Hash,
584          S: BuildHasher
585{
586    type Item = &'a T;
587
588    fn next(&mut self) -> Option<Self::Item> {
589        while let Some(item) = self.iter.next() {
590            if !self.other.contains(item) {
591                return Some(item);
592            }
593        }
594        None
595    }
596
597    fn size_hint(&self) -> (usize, Option<usize>) {
598        (0, self.iter.size_hint().1)
599    }
600}
601
602impl<'a, T, S> DoubleEndedIterator for Difference<'a, T, S>
603    where T: Eq + Hash,
604          S: BuildHasher
605{
606    fn next_back(&mut self) -> Option<Self::Item> {
607        while let Some(item) = self.iter.next_back() {
608            if !self.other.contains(item) {
609                return Some(item);
610            }
611        }
612        None
613    }
614}
615
616
617pub struct Intersection<'a, T: 'a, S: 'a> {
618    iter: Iter<'a, T>,
619    other: &'a OrderSet<T, S>,
620}
621
622impl<'a, T, S> Iterator for Intersection<'a, T, S>
623    where T: Eq + Hash,
624          S: BuildHasher
625{
626    type Item = &'a T;
627
628    fn next(&mut self) -> Option<Self::Item> {
629        while let Some(item) = self.iter.next() {
630            if self.other.contains(item) {
631                return Some(item);
632            }
633        }
634        None
635    }
636
637    fn size_hint(&self) -> (usize, Option<usize>) {
638        (0, self.iter.size_hint().1)
639    }
640}
641
642impl<'a, T, S> DoubleEndedIterator for Intersection<'a, T, S>
643    where T: Eq + Hash,
644          S: BuildHasher
645{
646    fn next_back(&mut self) -> Option<Self::Item> {
647        while let Some(item) = self.iter.next_back() {
648            if self.other.contains(item) {
649                return Some(item);
650            }
651        }
652        None
653    }
654}
655
656
657pub struct SymmetricDifference<'a, T: 'a, S1: 'a, S2: 'a> {
658    iter: Chain<Difference<'a, T, S2>, Difference<'a, T, S1>>,
659}
660
661impl<'a, T, S1, S2> Iterator for SymmetricDifference<'a, T, S1, S2>
662    where T: Eq + Hash,
663          S1: BuildHasher,
664          S2: BuildHasher,
665{
666    type Item = &'a T;
667
668    fn next(&mut self) -> Option<Self::Item> {
669        self.iter.next()
670    }
671
672    fn size_hint(&self) -> (usize, Option<usize>) {
673        self.iter.size_hint()
674    }
675
676    fn fold<B, F>(self, init: B, f: F) -> B
677        where F: FnMut(B, Self::Item) -> B
678    {
679        self.iter.fold(init, f)
680    }
681}
682
683impl<'a, T, S1, S2> DoubleEndedIterator for SymmetricDifference<'a, T, S1, S2>
684    where T: Eq + Hash,
685          S1: BuildHasher,
686          S2: BuildHasher,
687{
688    fn next_back(&mut self) -> Option<Self::Item> {
689        self.iter.next_back()
690    }
691}
692
693
694pub struct Union<'a, T: 'a, S: 'a> {
695    iter: Chain<Iter<'a, T>, Difference<'a, T, S>>,
696}
697
698impl<'a, T, S> Iterator for Union<'a, T, S>
699    where T: Eq + Hash,
700          S: BuildHasher,
701{
702    type Item = &'a T;
703
704    fn next(&mut self) -> Option<Self::Item> {
705        self.iter.next()
706    }
707
708    fn size_hint(&self) -> (usize, Option<usize>) {
709        self.iter.size_hint()
710    }
711
712    fn fold<B, F>(self, init: B, f: F) -> B
713        where F: FnMut(B, Self::Item) -> B
714    {
715        self.iter.fold(init, f)
716    }
717}
718
719impl<'a, T, S> DoubleEndedIterator for Union<'a, T, S>
720    where T: Eq + Hash,
721          S: BuildHasher,
722{
723    fn next_back(&mut self) -> Option<Self::Item> {
724        self.iter.next_back()
725    }
726}
727
728
729impl<'a, 'b, T, S1, S2> BitAnd<&'b OrderSet<T, S2>> for &'a OrderSet<T, S1>
730    where T: Eq + Hash + Clone,
731          S1: BuildHasher + Default,
732          S2: BuildHasher,
733{
734    type Output = OrderSet<T, S1>;
735
736    /// Returns the set intersection, cloned into a new set.
737    ///
738    /// Values are collected in the same order that they appear in `self`.
739    fn bitand(self, other: &'b OrderSet<T, S2>) -> Self::Output {
740        self.intersection(other).cloned().collect()
741    }
742}
743
744impl<'a, 'b, T, S1, S2> BitOr<&'b OrderSet<T, S2>> for &'a OrderSet<T, S1>
745    where T: Eq + Hash + Clone,
746          S1: BuildHasher + Default,
747          S2: BuildHasher,
748{
749    type Output = OrderSet<T, S1>;
750
751    /// Returns the set union, cloned into a new set.
752    ///
753    /// Values from `self` are collected in their original order, followed by
754    /// values that are unique to `other` in their original order.
755    fn bitor(self, other: &'b OrderSet<T, S2>) -> Self::Output {
756        self.union(other).cloned().collect()
757    }
758}
759
760impl<'a, 'b, T, S1, S2> BitXor<&'b OrderSet<T, S2>> for &'a OrderSet<T, S1>
761    where T: Eq + Hash + Clone,
762          S1: BuildHasher + Default,
763          S2: BuildHasher,
764{
765    type Output = OrderSet<T, S1>;
766
767    /// Returns the set symmetric-difference, cloned into a new set.
768    ///
769    /// Values from `self` are collected in their original order, followed by
770    /// values from `other` in their original order.
771    fn bitxor(self, other: &'b OrderSet<T, S2>) -> Self::Output {
772        self.symmetric_difference(other).cloned().collect()
773    }
774}
775
776impl<'a, 'b, T, S1, S2> Sub<&'b OrderSet<T, S2>> for &'a OrderSet<T, S1>
777    where T: Eq + Hash + Clone,
778          S1: BuildHasher + Default,
779          S2: BuildHasher,
780{
781    type Output = OrderSet<T, S1>;
782
783    /// Returns the set difference, cloned into a new set.
784    ///
785    /// Values are collected in the same order that they appear in `self`.
786    fn sub(self, other: &'b OrderSet<T, S2>) -> Self::Output {
787        self.difference(other).cloned().collect()
788    }
789}
790
791
792#[cfg(test)]
793mod tests {
794    use super::*;
795    use util::enumerate;
796
797    #[test]
798    fn it_works() {
799        let mut set = OrderSet::new();
800        assert_eq!(set.is_empty(), true);
801        set.insert(1);
802        set.insert(1);
803        assert_eq!(set.len(), 1);
804        assert!(set.get(&1).is_some());
805        assert_eq!(set.is_empty(), false);
806    }
807
808    #[test]
809    fn new() {
810        let set = OrderSet::<String>::new();
811        println!("{:?}", set);
812        assert_eq!(set.capacity(), 0);
813        assert_eq!(set.len(), 0);
814        assert_eq!(set.is_empty(), true);
815    }
816
817    #[test]
818    fn insert() {
819        let insert = [0, 4, 2, 12, 8, 7, 11, 5];
820        let not_present = [1, 3, 6, 9, 10];
821        let mut set = OrderSet::with_capacity(insert.len());
822
823        for (i, &elt) in enumerate(&insert) {
824            assert_eq!(set.len(), i);
825            set.insert(elt);
826            assert_eq!(set.len(), i + 1);
827            assert_eq!(set.get(&elt), Some(&elt));
828        }
829        println!("{:?}", set);
830
831        for &elt in &not_present {
832            assert!(set.get(&elt).is_none());
833        }
834    }
835
836    #[test]
837    fn insert_2() {
838        let mut set = OrderSet::with_capacity(16);
839
840        let mut values = vec![];
841        values.extend(0..16);
842        values.extend(128..267);
843
844        for &i in &values {
845            let old_set = set.clone();
846            set.insert(i);
847            for value in old_set.iter() {
848                if !set.get(value).is_some() {
849                    println!("old_set: {:?}", old_set);
850                    println!("set: {:?}", set);
851                    panic!("did not find {} in set", value);
852                }
853            }
854        }
855
856        for &i in &values {
857            assert!(set.get(&i).is_some(), "did not find {}", i);
858        }
859    }
860
861    #[test]
862    fn insert_dup() {
863        let mut elements = vec![0, 2, 4, 6, 8];
864        let mut set: OrderSet<u8> = elements.drain(..).collect();
865        {
866            let (i, v) = set.get_full(&0).unwrap();
867            assert_eq!(set.len(), 5);
868            assert_eq!(i, 0);
869            assert_eq!(*v, 0);
870        }
871        {
872            let inserted = set.insert(0);
873            let (i, v) = set.get_full(&0).unwrap();
874            assert_eq!(set.len(), 5);
875            assert_eq!(inserted, false);
876            assert_eq!(i, 0);
877            assert_eq!(*v, 0);
878        }
879    }
880
881    #[test]
882    fn insert_order() {
883        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
884        let mut set = OrderSet::new();
885
886        for &elt in &insert {
887            set.insert(elt);
888        }
889
890        assert_eq!(set.iter().count(), set.len());
891        assert_eq!(set.iter().count(), insert.len());
892        for (a, b) in insert.iter().zip(set.iter()) {
893            assert_eq!(a, b);
894        }
895        for (i, v) in (0..insert.len()).zip(set.iter()) {
896            assert_eq!(set.get_index(i).unwrap(), v);
897        }
898    }
899
900    #[test]
901    fn grow() {
902        let insert = [0, 4, 2, 12, 8, 7, 11];
903        let not_present = [1, 3, 6, 9, 10];
904        let mut set = OrderSet::with_capacity(insert.len());
905
906
907        for (i, &elt) in enumerate(&insert) {
908            assert_eq!(set.len(), i);
909            set.insert(elt);
910            assert_eq!(set.len(), i + 1);
911            assert_eq!(set.get(&elt), Some(&elt));
912        }
913
914        println!("{:?}", set);
915        for &elt in &insert {
916            set.insert(elt * 10);
917        }
918        for &elt in &insert {
919            set.insert(elt * 100);
920        }
921        for (i, &elt) in insert.iter().cycle().enumerate().take(100) {
922            set.insert(elt * 100 + i as i32);
923        }
924        println!("{:?}", set);
925        for &elt in &not_present {
926            assert!(set.get(&elt).is_none());
927        }
928    }
929
930    #[test]
931    fn remove() {
932        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
933        let mut set = OrderSet::new();
934
935        for &elt in &insert {
936            set.insert(elt);
937        }
938
939        assert_eq!(set.iter().count(), set.len());
940        assert_eq!(set.iter().count(), insert.len());
941        for (a, b) in insert.iter().zip(set.iter()) {
942            assert_eq!(a, b);
943        }
944
945        let remove_fail = [99, 77];
946        let remove = [4, 12, 8, 7];
947
948        for &value in &remove_fail {
949            assert!(set.swap_remove_full(&value).is_none());
950        }
951        println!("{:?}", set);
952        for &value in &remove {
953        //println!("{:?}", set);
954            let index = set.get_full(&value).unwrap().0;
955            assert_eq!(set.swap_remove_full(&value), Some((index, value)));
956        }
957        println!("{:?}", set);
958
959        for value in &insert {
960            assert_eq!(set.get(value).is_some(), !remove.contains(value));
961        }
962        assert_eq!(set.len(), insert.len() - remove.len());
963        assert_eq!(set.iter().count(), insert.len() - remove.len());
964    }
965
966    #[test]
967    fn swap_remove_index() {
968        let insert = [0, 4, 2, 12, 8, 7, 11, 5, 3, 17, 19, 22, 23];
969        let mut set = OrderSet::new();
970
971        for &elt in &insert {
972            set.insert(elt);
973        }
974
975        let mut vector = insert.to_vec();
976        let remove_sequence = &[3, 3, 10, 4, 5, 4, 3, 0, 1];
977
978        // check that the same swap remove sequence on vec and set
979        // have the same result.
980        for &rm in remove_sequence {
981            let out_vec = vector.swap_remove(rm);
982            let out_set = set.swap_remove_index(rm).unwrap();
983            assert_eq!(out_vec, out_set);
984        }
985        assert_eq!(vector.len(), set.len());
986        for (a, b) in vector.iter().zip(set.iter()) {
987            assert_eq!(a, b);
988        }
989    }
990
991    #[test]
992    fn partial_eq_and_eq() {
993        let mut set_a = OrderSet::new();
994        set_a.insert(1);
995        set_a.insert(2);
996        let mut set_b = set_a.clone();
997        assert_eq!(set_a, set_b);
998        set_b.remove(&1);
999        assert_ne!(set_a, set_b);
1000
1001        let set_c: OrderSet<_> = set_b.into_iter().collect();
1002        assert_ne!(set_a, set_c);
1003        assert_ne!(set_c, set_a);
1004    }
1005
1006    #[test]
1007    fn extend() {
1008        let mut set = OrderSet::new();
1009        set.extend(vec![&1, &2, &3, &4]);
1010        set.extend(vec![5, 6]);
1011        assert_eq!(set.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4, 5, 6]);
1012    }
1013
1014    #[test]
1015    fn comparisons() {
1016        let set_a: OrderSet<_> = (0..3).collect();
1017        let set_b: OrderSet<_> = (3..6).collect();
1018        let set_c: OrderSet<_> = (0..6).collect();
1019        let set_d: OrderSet<_> = (3..9).collect();
1020
1021        assert!(!set_a.is_disjoint(&set_a));
1022        assert!(set_a.is_subset(&set_a));
1023        assert!(set_a.is_superset(&set_a));
1024
1025        assert!(set_a.is_disjoint(&set_b));
1026        assert!(set_b.is_disjoint(&set_a));
1027        assert!(!set_a.is_subset(&set_b));
1028        assert!(!set_b.is_subset(&set_a));
1029        assert!(!set_a.is_superset(&set_b));
1030        assert!(!set_b.is_superset(&set_a));
1031
1032        assert!(!set_a.is_disjoint(&set_c));
1033        assert!(!set_c.is_disjoint(&set_a));
1034        assert!(set_a.is_subset(&set_c));
1035        assert!(!set_c.is_subset(&set_a));
1036        assert!(!set_a.is_superset(&set_c));
1037        assert!(set_c.is_superset(&set_a));
1038
1039        assert!(!set_c.is_disjoint(&set_d));
1040        assert!(!set_d.is_disjoint(&set_c));
1041        assert!(!set_c.is_subset(&set_d));
1042        assert!(!set_d.is_subset(&set_c));
1043        assert!(!set_c.is_superset(&set_d));
1044        assert!(!set_d.is_superset(&set_c));
1045    }
1046
1047    #[test]
1048    fn iter_comparisons() {
1049        use std::iter::empty;
1050
1051        fn check<'a, I1, I2>(iter1: I1, iter2: I2)
1052            where I1: Iterator<Item = &'a i32>,
1053                  I2: Iterator<Item = i32>,
1054        {
1055            assert!(iter1.cloned().eq(iter2));
1056        }
1057
1058        let set_a: OrderSet<_> = (0..3).collect();
1059        let set_b: OrderSet<_> = (3..6).collect();
1060        let set_c: OrderSet<_> = (0..6).collect();
1061        let set_d: OrderSet<_> = (3..9).rev().collect();
1062
1063        check(set_a.difference(&set_a), empty());
1064        check(set_a.symmetric_difference(&set_a), empty());
1065        check(set_a.intersection(&set_a), 0..3);
1066        check(set_a.union(&set_a), 0..3);
1067
1068        check(set_a.difference(&set_b), 0..3);
1069        check(set_b.difference(&set_a), 3..6);
1070        check(set_a.symmetric_difference(&set_b), 0..6);
1071        check(set_b.symmetric_difference(&set_a), (3..6).chain(0..3));
1072        check(set_a.intersection(&set_b), empty());
1073        check(set_b.intersection(&set_a), empty());
1074        check(set_a.union(&set_b), 0..6);
1075        check(set_b.union(&set_a), (3..6).chain(0..3));
1076
1077        check(set_a.difference(&set_c), empty());
1078        check(set_c.difference(&set_a), 3..6);
1079        check(set_a.symmetric_difference(&set_c), 3..6);
1080        check(set_c.symmetric_difference(&set_a), 3..6);
1081        check(set_a.intersection(&set_c), 0..3);
1082        check(set_c.intersection(&set_a), 0..3);
1083        check(set_a.union(&set_c), 0..6);
1084        check(set_c.union(&set_a), 0..6);
1085
1086        check(set_c.difference(&set_d), 0..3);
1087        check(set_d.difference(&set_c), (6..9).rev());
1088        check(set_c.symmetric_difference(&set_d), (0..3).chain((6..9).rev()));
1089        check(set_d.symmetric_difference(&set_c), (6..9).rev().chain(0..3));
1090        check(set_c.intersection(&set_d), 3..6);
1091        check(set_d.intersection(&set_c), (3..6).rev());
1092        check(set_c.union(&set_d), (0..6).chain((6..9).rev()));
1093        check(set_d.union(&set_c), (3..9).rev().chain(0..3));
1094    }
1095
1096    #[test]
1097    fn ops() {
1098        let empty = OrderSet::<i32>::new();
1099        let set_a: OrderSet<_> = (0..3).collect();
1100        let set_b: OrderSet<_> = (3..6).collect();
1101        let set_c: OrderSet<_> = (0..6).collect();
1102        let set_d: OrderSet<_> = (3..9).rev().collect();
1103
1104        assert_eq!(&set_a & &set_a, set_a);
1105        assert_eq!(&set_a | &set_a, set_a);
1106        assert_eq!(&set_a ^ &set_a, empty);
1107        assert_eq!(&set_a - &set_a, empty);
1108
1109        assert_eq!(&set_a & &set_b, empty);
1110        assert_eq!(&set_b & &set_a, empty);
1111        assert_eq!(&set_a | &set_b, set_c);
1112        assert_eq!(&set_b | &set_a, set_c);
1113        assert_eq!(&set_a ^ &set_b, set_c);
1114        assert_eq!(&set_b ^ &set_a, set_c);
1115        assert_eq!(&set_a - &set_b, set_a);
1116        assert_eq!(&set_b - &set_a, set_b);
1117
1118        assert_eq!(&set_a & &set_c, set_a);
1119        assert_eq!(&set_c & &set_a, set_a);
1120        assert_eq!(&set_a | &set_c, set_c);
1121        assert_eq!(&set_c | &set_a, set_c);
1122        assert_eq!(&set_a ^ &set_c, set_b);
1123        assert_eq!(&set_c ^ &set_a, set_b);
1124        assert_eq!(&set_a - &set_c, empty);
1125        assert_eq!(&set_c - &set_a, set_b);
1126
1127        assert_eq!(&set_c & &set_d, set_b);
1128        assert_eq!(&set_d & &set_c, set_b);
1129        assert_eq!(&set_c | &set_d, &set_a | &set_d);
1130        assert_eq!(&set_d | &set_c, &set_a | &set_d);
1131        assert_eq!(&set_c ^ &set_d, &set_a | &(&set_d - &set_b));
1132        assert_eq!(&set_d ^ &set_c, &set_a | &(&set_d - &set_b));
1133        assert_eq!(&set_c - &set_d, set_a);
1134        assert_eq!(&set_d - &set_c, &set_d - &set_b);
1135    }
1136}
ordermap/set.rs

ordermap/
set.rs
