immutable_map/
set.rs

1use std::borrow::Borrow;
2use std::cmp::Ordering;
3use std::fmt;
4use std::fmt::Debug;
5use std::iter::{FromIterator, Peekable};
6use std::rc::Rc;
7
8use tree;
9use tree::TreeNode;
10use Bound;
11
12/// An immutable set based on weight-balanced binary tree.
13/// See https://yoichihirai.com/bst.pdf for the balancing algorithm.
14///
15/// # Examples
16///
17/// ```
18/// use immutable_map::TreeSet;
19///
20/// let set_0 = TreeSet::new();
21///
22/// // `insert` returns new copies with the given key and value inserted, and does not change
23/// // the original map
24/// let set_1 = set_0.insert(3);
25/// let set_2 = set_1.insert(4);
26///
27/// assert!(!set_1.contains(&4));
28/// assert!(set_2.contains(&4));
29/// ```
30#[derive(Clone, Default)]
31pub struct TreeSet<V> {
32    root: Option<Rc<TreeNode<V, ()>>>,
33}
34
35pub type TreeSetIter<'r, V> = tree::Keys<tree::Iter<'r, V, ()>>;
36pub type TreeSetRevIter<'r, V> = tree::Keys<tree::RevIter<'r, V, ()>>;
37pub type TreeSetRange<'r, V> = tree::Keys<tree::Range<'r, V, ()>>;
38
39impl<V> TreeSet<V> {
40    /// Makes a new empty TreeSet
41    ///
42    /// # Examples
43    ///
44    /// ```
45    /// use immutable_map::TreeSet;
46    ///
47    /// let set = TreeSet::new();
48    /// let new_set = set.insert(1);
49    /// ```
50    pub fn new() -> TreeSet<V> {
51        TreeSet { root: None }
52    }
53
54    /// Returns the number of elements in the set.
55    ///
56    /// # Examples
57    ///
58    /// ```
59    /// use immutable_map::TreeSet;
60    ///
61    /// let set = TreeSet::new().insert(1).insert(2);
62    /// assert_eq!(2, set.len());
63    /// ```
64    pub fn len(&self) -> usize {
65        tree::size(&self.root)
66    }
67
68    /// Returns true if the set contains no elements.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// use immutable_map::TreeSet;
74    ///
75    /// let empty_set = TreeSet::new();
76    /// let new_set = empty_set.insert(1);
77    ///
78    /// assert!(empty_set.is_empty());
79    /// assert!(!new_set.is_empty());
80    /// ```
81    pub fn is_empty(&self) -> bool {
82        self.root.is_none()
83    }
84
85    /// Gets an iterator over the entries of the set, in sorted order.
86    ///
87    /// # Examples
88    ///
89    /// ```
90    /// use immutable_map::TreeSet;
91    ///
92    /// let set = TreeSet::new().insert(2).insert(3).insert(1);
93    ///
94    /// for element in set.iter() {
95    ///     println!("{}", element);
96    /// }
97    ///
98    /// let first_value = set.iter().next().unwrap();
99    /// assert_eq!(1, *first_value);
100    /// ```
101    pub fn iter<'r>(&'r self) -> TreeSetIter<'r, V> {
102        tree::Keys::new(tree::Iter::new(&self.root))
103    }
104
105    /// Gets an iterator over the entries of the set, in decreasing order.
106    ///
107    /// # Examples
108    ///
109    /// ```
110    /// use immutable_map::TreeSet;
111    ///
112    /// let set = TreeSet::new().insert(2).insert(3).insert(1);
113    ///
114    /// for element in set.rev_iter() {
115    ///     println!("{}", element);
116    /// }
117    ///
118    /// let first_value = set.rev_iter().next().unwrap();
119    /// assert_eq!(3, *first_value);
120    /// ```
121    pub fn rev_iter<'r>(&'r self) -> TreeSetRevIter<'r, V> {
122        tree::Keys::new(tree::RevIter::new(&self.root))
123    }
124}
125
126impl<V: Ord> TreeSet<V> {
127    /// Returns a reference to the value in the set, if any, that is equal to the given value.
128    ///
129    /// The value may be any borrowed form of the set's value type, but the ordering on the
130    /// borrowed form must match the ordering on the value type.
131    pub fn get<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&V>
132        where V: Borrow<Q>
133    {
134        fn f<'r, V: Borrow<Q>, Q: Ord + ?Sized>(node: &'r Option<Rc<TreeNode<V, ()>>>, key: &Q)
135                -> Option<&'r V>
136        {
137            tree::find_exact(node, |x| key.cmp(x.borrow())).map(|p| &p.0)
138        }
139
140        f(&self.root, key)
141    }
142
143    /// Returns true if the value is in the set, if any, that is equal to the given value.
144    ///
145    /// The value may be any borrowed form of the set's value type, but the ordering on the
146    /// borrowed form must match the ordering on the value type.
147    ///
148    /// # Examples
149    ///
150    /// ```
151    /// use immutable_map::TreeSet;
152    ///
153    /// let set: TreeSet<String> = ["One".to_string(), "Two".to_string(), "Three".to_string()].iter().cloned().collect();
154    ///
155    /// assert_eq!(true, set.contains("Two"));
156    /// assert_eq!(false, set.contains("Four"));
157    /// ```
158    pub fn contains<Q: Ord + ?Sized>(&self, key: &Q) -> bool
159        where V: Borrow<Q>
160    {
161        self.get(key).is_some()
162    }
163
164    /// Constructs a double-ended iterator over a sub-range of elements in the set, starting at
165    /// min, and ending at max. If min is Unbounded, then it will be treated as "negative
166    /// infinity", and if max is Unbounded, then it will be treated as "positive infinity". Thus
167    /// range(Unbounded, Unbounded) will yield the whole collection.
168    ///
169    /// # Examples
170    ///
171    /// ```
172    /// use immutable_map::TreeSet;
173    /// use immutable_map::Bound::*;
174    ///
175    /// let set = TreeSet::new().insert(8).insert(3).insert(5);
176    ///
177    /// for elem in set.range(Included(&4), Included(&8)) {
178    ///     println!("{}", elem);
179    /// }
180    ///
181    /// let values: Vec<_> = set.range(Included(&4), Included(&8)).cloned().collect();
182    ///
183    /// assert_eq!(values, [5, 8]);
184    /// ```
185    pub fn range<'r, Q: Ord>(&'r self, min: Bound<&Q>, max: Bound<&Q>)
186            -> TreeSetRange<'r, V>
187        where V: Borrow<Q>
188    {
189        tree::Keys::new(tree::Range::new(&self.root, min, max))
190    }
191
192    /// Visits the values representing the intersection, in ascending order.
193    ///
194    /// # Examples
195    ///
196    /// ```
197    /// use immutable_map::TreeSet;
198    ///
199    /// let a = TreeSet::new().insert(1).insert(2);
200    /// let b = TreeSet::new().insert(2).insert(3);
201    ///
202    /// let intersection: Vec<_> = a.intersection(&b).cloned().collect();
203    /// assert_eq!(intersection, [2]);
204    /// ```
205    pub fn intersection<'r>(&'r self, other: &'r TreeSet<V>) -> Intersection<'r, V> {
206        Intersection {
207            a: tree::Iter::new(&self.root).peekable(),
208            b: tree::Iter::new(&other.root).peekable()
209        }
210    }
211
212    /// Visits the values representing the union, in ascending order.
213    ///
214    /// # Examples
215    ///
216    /// ```
217    /// use immutable_map::TreeSet;
218    ///
219    /// let a = TreeSet::new().insert(1).insert(2);
220    /// let b = TreeSet::new().insert(2).insert(3);
221    ///
222    /// let union: Vec<_> = a.union(&b).cloned().collect();
223    /// assert_eq!(union, [1, 2, 3]);
224    /// ```
225    pub fn union<'r>(&'r self, other: &'r TreeSet<V>) -> Union<'r, V> {
226        Union {
227            a: tree::Iter::new(&self.root).peekable(),
228            b: tree::Iter::new(&other.root).peekable()
229        }
230    }
231
232    /// Visits the values representing the difference of `self` and `other`, in ascending order.
233    ///
234    /// # Examples
235    ///
236    /// ```
237    /// use immutable_map::TreeSet;
238    ///
239    /// let a = TreeSet::new().insert(1).insert(2);
240    /// let b = TreeSet::new().insert(2).insert(3);
241    ///
242    /// let difference: Vec<_> = a.difference(&b).cloned().collect();
243    /// assert_eq!(difference, [1]);
244    /// ```
245    pub fn difference<'r>(&'r self, other: &'r TreeSet<V>) -> Difference<'r, V> {
246        Difference {
247            a: tree::Iter::new(&self.root).peekable(),
248            b: tree::Iter::new(&other.root).peekable()
249        }
250    }
251
252    /// Visits the values representing the symmetric difference, in ascending order.
253    ///
254    /// # Examples
255    ///
256    /// ```
257    /// use immutable_map::TreeSet;
258    ///
259    /// let a = TreeSet::new().insert(1).insert(2);
260    /// let b = TreeSet::new().insert(2).insert(3);
261    ///
262    /// let symm_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
263    /// assert_eq!(symm_diff, [1, 3]);
264    /// ```
265    pub fn symmetric_difference<'r>(&'r self, other: &'r TreeSet<V>) -> SymmetricDifference<'r, V> {
266        SymmetricDifference {
267            a: tree::Iter::new(&self.root).peekable(),
268            b: tree::Iter::new(&other.root).peekable()
269        }
270    }
271
272    /// Returns true if the set has no elements in common with other.
273    /// This is equivalent to checking for an empty intersection.
274    ///
275    /// # Examples
276    ///
277    /// ```
278    /// use immutable_map::TreeSet;
279    ///
280    /// let a = TreeSet::new().insert(1).insert(2);
281    /// let b = TreeSet::new().insert(2).insert(3);
282    /// let c = TreeSet::new().insert(3).insert(4);
283    ///
284    /// assert_eq!(false, a.is_disjoint(&b));
285    /// assert_eq!(true, a.is_disjoint(&c));
286    /// ```
287    pub fn is_disjoint(&self, other: &TreeSet<V>) -> bool {
288        self.intersection(other).next().is_none()
289    }
290
291    /// Returns true if `self` is a subset of `other`.
292    ///
293    /// # Examples
294    ///
295    /// ```
296    /// use immutable_map::TreeSet;
297    ///
298    /// let sup = TreeSet::new().insert(1).insert(2).insert(3);
299    /// let a = TreeSet::new().insert(2);
300    /// let b = TreeSet::new().insert(3).insert(4);
301    ///
302    /// assert_eq!(true, a.is_subset(&sup));
303    /// assert_eq!(false, b.is_subset(&sup));
304    /// ```
305    pub fn is_subset(&self, other: &TreeSet<V>) -> bool {
306        self.difference(other).next().is_none()
307    }
308
309    /// Returns true if `self` is a superset of `other`.
310    ///
311    /// # Examples
312    ///
313    /// ```
314    /// use immutable_map::TreeSet;
315    ///
316    /// let sub = TreeSet::new().insert(1).insert(2);
317    /// let a = TreeSet::new().insert(1).insert(2).insert(3);
318    /// let b = TreeSet::new().insert(2).insert(3);
319    ///
320    /// assert_eq!(true, a.is_superset(&sub));
321    /// assert_eq!(false, b.is_superset(&sub));
322    /// ```
323    pub fn is_superset(&self, other: &TreeSet<V>) -> bool {
324        other.difference(self).next().is_none()
325    }
326}
327
328impl<V: Ord> TreeSet<V> where V: Clone {
329    /// Returns a new set with the value added to the set, replacing the existing value, if any.
330    ///
331    /// # Examples
332    ///
333    /// ```
334    /// use immutable_map::TreeSet;
335    ///
336    /// let empty_set = TreeSet::new();
337    /// let new_set = empty_set.insert(3);
338    ///
339    /// assert_eq!(false, empty_set.contains(&3));
340    /// assert_eq!(true, new_set.contains(&3));
341    /// ```
342    pub fn insert(&self, value: V) -> TreeSet<V>
343    {
344        let root = tree::insert(&self.root, (value, ()));
345        TreeSet { root: Some(Rc::new(root)) }
346    }
347
348    /// Return a new copy of `TreeSet` with the value inserted.
349    ///
350    /// Returns `None` if the set already has the value
351    ///
352    /// # Examples
353    ///
354    /// ```
355    /// use immutable_map::TreeSet;
356    ///
357    /// let set = TreeSet::new().insert(2).insert(3);
358    ///
359    /// assert_eq!(None, set.insert_if_absent(2));
360    ///
361    /// let new_set = set.insert_if_absent(1).unwrap();
362    ///
363    /// assert_eq!(true, new_set.contains(&1));
364    /// ```
365    pub fn insert_if_absent(&self, value: V) -> Option<TreeSet<V>>
366    {
367        tree::insert_if_absent(&self.root, (value, ())).map(|root|
368            TreeSet { root: Some(Rc::new(root)) }
369        )
370    }
371
372    /// Returns a new set with the smallest element removed from the set, and the smallest element.
373    /// Returns `None` if the set was empty
374    ///
375    /// # Examples
376    ///
377    /// ```
378    /// use immutable_map::TreeSet;
379    ///
380    /// let empty_set = TreeSet::new();
381    /// assert_eq!(None, empty_set.delete_min());
382    ///
383    /// let new_set = empty_set.insert(2).insert(3).insert(1);
384    /// let (set, removed) = new_set.delete_min().unwrap();
385    ///
386    /// assert_eq!(false, set.contains(&1));
387    /// assert_eq!(&1, removed);
388    /// ```
389    pub fn delete_min(&self) -> Option<(TreeSet<V>, &V)>
390    {
391        if let Some(ref root) = self.root {
392            let (new_root, v) = tree::delete_min(&root);
393            Some((
394                TreeSet { root: new_root },
395                &v.0
396            ))
397        } else {
398            None
399        }
400    }
401
402    /// Returns a new set with the largest element removed from the set, and the largest element.
403    /// Returns `None` if the set was empty
404    ///
405    /// # Examples
406    ///
407    /// ```
408    /// use immutable_map::TreeSet;
409    ///
410    /// let empty_set = TreeSet::new();
411    /// assert_eq!(None, empty_set.delete_max());
412    ///
413    /// let new_set = empty_set.insert(2).insert(3).insert(1);
414    /// let (set, removed) = new_set.delete_max().unwrap();
415    ///
416    /// assert_eq!(false, set.contains(&3));
417    /// assert_eq!(&3, removed);
418    /// ```
419    pub fn delete_max(&self) -> Option<(TreeSet<V>, &V)>
420    {
421        if let Some(ref root) = self.root {
422            let (new_root, v) = tree::delete_max(&root);
423            Some((
424                TreeSet { root: new_root },
425                &v.0
426            ))
427        } else {
428            None
429        }
430    }
431
432    /// Returns the new set with the value removed, and the removed value
433    ///
434    /// Returns `None` if the original set did not contain the value
435    ///
436    /// The value may be any borrowed form of the set's value type, but the ordering on the
437    /// borrowed form must match the ordering on the value type.
438    ///
439    /// # Examples
440    ///
441    /// ```
442    /// use immutable_map::TreeSet;
443    ///
444    /// let empty_set = TreeSet::new();
445    /// assert_eq!(None, empty_set.remove(&2));
446    ///
447    /// let set = empty_set.insert(2).insert(3).insert(1);
448    ///
449    /// let (new_set, removed) = set.remove(&2).unwrap();
450    ///
451    /// assert_eq!(false, new_set.contains(&2));
452    /// assert_eq!(&2, removed);
453    /// ```
454    pub fn remove<Q: Ord + ?Sized>(&self, key: &Q) -> Option<(TreeSet<V>, &V)>
455        where V: Borrow<Q>
456    {
457        tree::remove(&self.root, key).map(|(new_root, v)|
458            (TreeSet { root: new_root }, &v.0)
459        )
460    }
461}
462
463impl<V: Debug + Ord> Debug for TreeSet<V> {
464    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
465        f.debug_set().entries(self.iter()).finish()
466    }
467}
468
469impl<'r, V: Ord> IntoIterator for &'r TreeSet<V> {
470    type Item = &'r V;
471    type IntoIter = tree::Keys<tree::Iter<'r, V, ()>>;
472
473    fn into_iter(self) -> tree::Keys<tree::Iter<'r, V, ()>> {
474        self.iter()
475    }
476}
477
478impl <V: PartialEq> PartialEq for TreeSet<V> {
479    fn eq(&self, other: &TreeSet<V>) -> bool {
480        self.len() == other.len()
481            && self.iter().zip(other.iter()).all(|(a, b)| a == b)
482    }
483}
484
485impl <V: Eq> Eq for TreeSet<V> {}
486
487impl <V: PartialOrd> PartialOrd for TreeSet<V> {
488    fn partial_cmp(&self, other: &TreeSet<V>) -> Option<Ordering> {
489        self.iter().partial_cmp(other.iter())
490    }
491}
492
493impl <V: Ord> Ord for TreeSet<V> {
494    fn cmp(&self, other: &TreeSet<V>) -> Ordering {
495        self.iter().cmp(other.iter())
496    }
497}
498
499impl <V: Ord + Clone> FromIterator<V> for TreeSet<V> {
500    fn from_iter<T>(iter: T) -> TreeSet<V> where T: IntoIterator<Item=V> {
501        let mut s = TreeSet::new();
502        for v in iter {
503            s = s.insert(v);
504        }
505        s
506    }
507}
508
509#[derive(Clone)]
510pub struct Intersection<'r, V: 'r> {
511    a: Peekable<tree::Iter<'r, V, ()>>,
512    b: Peekable<tree::Iter<'r, V, ()>>
513}
514
515impl<'r, V: Ord + 'r> Iterator for Intersection<'r, V> {
516    type Item = &'r V;
517
518    fn next(&mut self) -> Option<&'r V> {
519        loop {
520            let cmp = match (self.a.peek(), self.b.peek()) {
521                (None, _) => return None,
522                (_, None) => return None,
523                (Some(a), Some(b)) => a.cmp(b)
524            };
525
526            match cmp {
527                Ordering::Less => {
528                    self.a.next();
529                },
530                Ordering::Equal => {
531                    self.b.next();
532                    return self.a.next().map(|pair| pair.0);
533                },
534                Ordering::Greater => {
535                    self.b.next();
536                }
537            }
538        }
539    }
540}
541
542#[derive(Clone)]
543pub struct Union<'r, V: 'r> {
544    a: Peekable<tree::Iter<'r, V, ()>>,
545    b: Peekable<tree::Iter<'r, V, ()>>
546}
547
548impl <'r, V: Ord + 'r> Iterator for Union<'r, V> {
549    type Item = &'r V;
550
551    fn next(&mut self) -> Option<&'r V> {
552        loop {
553            let cmp = match (self.a.peek(), self.b.peek()) {
554                (_, None) => Ordering::Less,
555                (None, _) => Ordering::Greater,
556                (Some(a), Some(b)) => a.cmp(b)
557            };
558
559            match cmp {
560                Ordering::Less => {
561                    return self.a.next().map(|pair| pair.0);
562                },
563                Ordering::Equal => {
564                    self.b.next();
565                    return self.a.next().map(|pair| pair.0);
566                },
567                Ordering::Greater => {
568                    return self.b.next().map(|pair| pair.0);
569                }
570            }
571        }
572    }
573}
574
575#[derive(Clone)]
576pub struct Difference<'r, V: 'r> {
577    a: Peekable<tree::Iter<'r, V, ()>>,
578    b: Peekable<tree::Iter<'r, V, ()>>
579}
580
581impl<'r, V: Ord + 'r> Iterator for Difference<'r, V> {
582    type Item = &'r V;
583
584    fn next(&mut self) -> Option<&'r V> {
585        loop {
586            let cmp = match (self.a.peek(), self.b.peek()) {
587                (_, None) => Ordering::Less,
588                (None, _) => return None,
589                (Some(a), Some(b)) => a.cmp(b)
590            };
591
592            match cmp {
593                Ordering::Less => {
594                    return self.a.next().map(|pair| pair.0);
595                },
596                Ordering::Equal => {
597                    self.a.next();
598                    self.b.next();
599                },
600                Ordering::Greater => {
601                    self.b.next();
602                }
603            }
604        }
605    }
606}
607
608#[derive(Clone)]
609pub struct SymmetricDifference<'r, V: 'r> {
610    a: Peekable<tree::Iter<'r, V, ()>>,
611    b: Peekable<tree::Iter<'r, V, ()>>
612}
613
614impl<'r, V: Ord + 'r> Iterator for SymmetricDifference<'r, V> {
615    type Item = &'r V;
616
617    fn next(&mut self) -> Option<&'r V> {
618        loop {
619            let cmp = match (self.a.peek(), self.b.peek()) {
620                (_, None) => Ordering::Less,
621                (None, _) => Ordering::Greater,
622                (Some(a), Some(b)) => a.cmp(b)
623            };
624
625            match cmp {
626                Ordering::Less => {
627                    return self.a.next().map(|pair| pair.0);
628                },
629                Ordering::Equal => {
630                    self.a.next();
631                    self.b.next();
632                },
633                Ordering::Greater => {
634                    return self.b.next().map(|pair| pair.0);
635                }
636            }
637        }
638    }
639}
640
641#[cfg(test)]
642mod test {
643    use tree::balanced;
644    use Bound;
645
646    use super::TreeSet;
647
648    #[test]
649    fn test_insert() {
650        let r0 = TreeSet::new();
651        let r1 = r0.insert((4, 'd'));
652        let r2 = r1.insert((7, 'g'));
653        let r3 = r2.insert((12, 'l'));
654        let r4 = r3.insert((15, 'o'));
655        let r5 = r4.insert((3, 'c'));
656        let r6 = r5.insert((5, 'e'));
657        let r7 = r6.insert((14, 'n'));
658        let r8 = r7.insert((18, 'r'));
659        let r9 = r8.insert((16, 'p'));
660        let r10 = r9.insert((17, 'q'));
661
662        let expected = vec![
663            (3, 'c'), (4, 'd'), (5, 'e'), (7, 'g'),
664            (12, 'l'), (14, 'n'), (15, 'o'), (16, 'p'),
665            (17, 'q'), (18, 'r')
666        ];
667
668        let res: Vec<(usize, char)> = r10.iter().cloned().collect();
669
670        assert_eq!(expected, res);
671        assert_eq!(10, r10.len());
672        assert!(balanced(&r10.root));
673        assert!(r10.contains(&(12, 'l')));
674    }
675
676    #[test]
677    fn test_delete_min() {
678        let r0 = TreeSet::new();
679        let r1 = r0.insert(4);
680        let r2 = r1.insert(7);
681        let r3 = r2.insert(12);
682        let r4 = r3.insert(15);
683        let r5 = r4.insert(3);
684        let r6 = r5.insert(5);
685        let (r7, v) = r6.delete_min().unwrap();
686
687        let expected = vec![4, 5, 7, 12, 15];
688
689        let res: Vec<usize> = r7.iter().cloned().collect();
690
691        assert_eq!(expected, res);
692        assert_eq!(&3, v);
693    }
694
695    #[test]
696    fn test_delete_max() {
697        let r0 = TreeSet::new();
698        let r1 = r0.insert(4);
699        let r2 = r1.insert(7);
700        let r3 = r2.insert(12);
701        let r4 = r3.insert(15);
702        let r5 = r4.insert(3);
703        let r6 = r5.insert(5);
704        let (r7, v) = r6.delete_max().unwrap();
705
706        let expected = vec![3, 4, 5, 7, 12];
707        let res: Vec<usize> = r7.iter().cloned().collect();
708
709        assert_eq!(expected, res);
710        assert_eq!(&15, v);
711    }
712
713    #[test]
714    fn test_remove() {
715        let r0 = TreeSet::new();
716        let r1 = r0.insert(4);
717        let r2 = r1.insert(7);
718        let r3 = r2.insert(12);
719        let r4 = r3.insert(15);
720        let r5 = r4.insert(3);
721        let r6 = r5.insert(5);
722        let (r7, v) = r6.remove(&7).unwrap();
723
724        let expected = vec![3, 4, 5, 12, 15];
725        let res: Vec<usize> = r7.iter().cloned().collect();
726
727        assert_eq!(expected, res);
728        assert_eq!(&7, v);
729    }
730
731    #[test]
732    fn test_iter() {
733        let r0 = TreeSet::new();
734        let r1 = r0.insert(4);
735        let r2 = r1.insert(7);
736        let r3 = r2.insert(12);
737        let r4 = r3.insert(15);
738        let r5 = r4.insert(3);
739        let r6 = r5.insert(5);
740        let r7 = r6.insert(14);
741        let r8 = r7.insert(18);
742        let r9 = r8.insert(16);
743        let r10 = r9.insert(17);
744
745        let expected = vec![3, 4, 5, 7, 12, 14, 15, 16, 17, 18];
746        let res: Vec<usize> = r10.iter().cloned().collect();
747
748        assert_eq!(expected, res);
749
750        assert_eq!((10, Some(10)), r10.iter().size_hint());
751    }
752
753    #[test]
754    fn test_rev_iter() {
755        let r0 = TreeSet::new();
756        let r1 = r0.insert(4);
757        let r2 = r1.insert(7);
758        let r3 = r2.insert(12);
759        let r4 = r3.insert(15);
760        let r5 = r4.insert(3);
761        let r6 = r5.insert(5);
762        let r7 = r6.insert(14);
763        let r8 = r7.insert(18);
764        let r9 = r8.insert(16);
765        let r10 = r9.insert(17);
766
767        let expected = vec![18, 17, 16, 15, 14, 12, 7, 5, 4, 3];
768        let res: Vec<usize> = r10.rev_iter().cloned().collect();
769
770        assert_eq!(expected, res);
771
772        assert_eq!((10, Some(10)), r10.rev_iter().size_hint());
773    }
774
775    #[test]
776    fn test_is_empty() {
777        let r0 = TreeSet::new();
778        let r1 = r0.insert(4);
779        let r2 = r1.insert(7);
780
781        assert!(r0.is_empty());
782        assert!(!r1.is_empty());
783        assert!(!r2.is_empty());
784    }
785
786    #[test]
787    fn test_range() {
788        let r0 = TreeSet::new();
789        let r1 = r0.insert(4);
790        let r2 = r1.insert(7);
791        let r3 = r2.insert(12);
792        let r4 = r3.insert(15);
793        let r5 = r4.insert(3);
794        let r6 = r5.insert(5);
795        let r7 = r6.insert(14);
796        let r8 = r7.insert(18);
797        let r9 = r8.insert(16);
798        let r10 = r9.insert(17);
799
800        let expected = vec![7, 12, 14, 15, 16];
801
802        let res: Vec<usize> = r10.range(Bound::Included(&6), Bound::Excluded(&17))
803                                 .cloned().collect();
804
805        assert_eq!(expected, res);
806    }
807
808    #[test]
809    fn test_range_rev() {
810        let r0 = TreeSet::new();
811        let r1 = r0.insert(4);
812        let r2 = r1.insert(7);
813        let r3 = r2.insert(12);
814        let r4 = r3.insert(15);
815        let r5 = r4.insert(3);
816        let r6 = r5.insert(5);
817        let r7 = r6.insert(14);
818        let r8 = r7.insert(18);
819        let r9 = r8.insert(16);
820        let r10 = r9.insert(17);
821
822        let expected = vec![16, 15, 14, 12, 7];
823
824        let res: Vec<usize> = r10.range(Bound::Included(&6), Bound::Excluded(&17))
825                                 .rev()
826                                 .cloned().collect();
827
828        assert_eq!(expected, res);
829    }
830
831    #[test]
832    fn test_debug() {
833        let r0 = TreeSet::new();
834        let r1 = r0.insert(7);
835        let r2 = r1.insert(4);
836
837        assert_eq!("{4, 7}", &format!("{:?}", r2));
838    }
839
840    #[test]
841    fn test_eq() {
842        let a = TreeSet::new().insert(3).insert(1).insert(2);
843        let b = TreeSet::new().insert(2).insert(3).insert(1).insert(2);
844
845        assert_eq!(a, b);
846    }
847
848    #[test]
849    fn test_neq() {
850        let a = TreeSet::new().insert(3).insert(1).insert(2);
851        let b = TreeSet::new().insert(2).insert(4).insert(1);
852
853        assert!(a != b);
854    }
855}
856
857#[cfg(test)]
858mod quickcheck {
859    use set::TreeSet;
860    use Bound;
861
862    use quickcheck::TestResult;
863    use rand::{Rng, StdRng};
864
865    fn filter_input<V: PartialEq>(input: Vec<V>) -> Vec<V> {
866        let mut res: Vec<V> = Vec::new();
867
868        for v in input {
869            if res.iter().all(|x| x != &v) {
870                res.push(v);
871            }
872        }
873
874        res
875    }
876
877    quickcheck! {
878        fn check_length(xs: Vec<isize>) -> bool {
879            let input = filter_input(xs);
880            let m: TreeSet<isize> = input.iter().cloned().collect();
881
882            m.len() == input.len()
883        }
884    }
885
886    quickcheck! {
887        fn check_is_empty(xs: Vec<isize>) -> bool {
888            let input = filter_input(xs);
889            let m: TreeSet<isize> = input.iter().cloned().collect();
890
891            m.is_empty() == input.is_empty()
892        }
893    }
894
895    quickcheck! {
896        fn check_iter(xs: Vec<isize>) -> bool {
897            let mut input = filter_input(xs);
898            let m: TreeSet<isize> = input.iter().cloned().collect();
899
900            input.sort();
901
902            let collected: Vec<isize> = m.iter().cloned().collect();
903
904            collected == input
905        }
906    }
907
908    quickcheck! {
909        fn check_iter_size_hint(xs: Vec<isize>) -> bool {
910            let input = filter_input(xs);
911            let m: TreeSet<isize> = input.iter().cloned().collect();
912
913            let n = m.len();
914            m.iter().size_hint() == (n, Some(n))
915        }
916    }
917
918    quickcheck! {
919        fn check_rev_iter(xs: Vec<isize>) -> bool {
920            let mut input = filter_input(xs);
921            let m: TreeSet<isize> = input.iter().cloned().collect();
922
923            input.sort();
924            input.reverse();
925
926            let collected: Vec<isize> = m.rev_iter().cloned().collect();
927
928            collected == input
929        }
930    }
931
932    quickcheck! {
933        fn check_contains(xs: Vec<isize>) -> bool {
934            let input = filter_input(xs);
935            let m: TreeSet<isize> = input.iter().cloned().collect();
936
937            input.into_iter().all(|v| m.contains(&v))
938        }
939    }
940
941    quickcheck! {
942        fn check_remove(xs: Vec<isize>) -> TestResult {
943            if xs.is_empty() {
944                return TestResult::discard();
945            }
946
947            let input = filter_input(xs);
948            let m: TreeSet<isize> = input.iter().cloned().collect();
949            let mut rng = StdRng::new().unwrap();
950
951            let &v = rng.choose(&input).unwrap();
952
953            if let Some((m_removed, &removed)) = m.remove(&v) {
954                TestResult::from_bool(
955                    m_removed.len() == m.len() - 1 && removed == v
956                )
957            } else {
958                TestResult::failed()
959            }
960        }
961    }
962
963    quickcheck! {
964        fn check_remove_all(xs: Vec<isize>) -> bool {
965            let input = filter_input(xs);
966            let mut m: TreeSet<isize> = input.iter().cloned().collect();
967            let mut rng = StdRng::new().unwrap();
968            let mut remove_list = input.clone();
969            rng.shuffle(&mut remove_list);
970
971            for v in remove_list {
972                let new_m = if let Some((m_removed, _)) = m.remove(&v) {
973                    m_removed
974                } else {
975                    return false;
976                };
977                m = new_m;
978                if m.contains(&v) {
979                    return false;
980                }
981            }
982
983            m.is_empty()
984        }
985    }
986
987    quickcheck! {
988        fn check_delete_min(xs: Vec<isize>) -> bool {
989            let input = filter_input(xs);
990            let m: TreeSet<isize> = input.iter().cloned().collect();
991
992            if let Some((m_removed, &v)) = m.delete_min() {
993                m_removed.len() == m.len() - 1 && Some(v) == input.into_iter().min()
994            } else {
995                true
996            }
997        }
998    }
999
1000    quickcheck! {
1001        fn check_delete_max(xs: Vec<isize>) -> bool {
1002            let input = filter_input(xs);
1003            let m: TreeSet<isize> = input.iter().cloned().collect();
1004
1005            if let Some((m_removed, &v)) = m.delete_max() {
1006                m_removed.len() == m.len() - 1 && Some(v) == input.into_iter().max()
1007            } else {
1008                true
1009            }
1010        }
1011    }
1012
1013    fn match_bound<T: Ord>(x: &T, min: &Bound<T>, max: &Bound<T>) -> bool {
1014        let min_match = match *min {
1015            Bound::Unbounded => true,
1016            Bound::Included(ref lower) => lower <= x,
1017            Bound::Excluded(ref lower) => lower < x
1018        };
1019
1020        let max_match = match *max {
1021            Bound::Unbounded => true,
1022            Bound::Included(ref upper) => x <= upper,
1023            Bound::Excluded(ref upper) => x < upper
1024        };
1025
1026        min_match && max_match
1027    }
1028
1029    quickcheck! {
1030        fn check_range(xs: Vec<isize>, min_bound: Bound<isize>, max_bound: Bound<isize>) -> bool
1031        {
1032            let input = filter_input(xs);
1033            let m: TreeSet<isize> = input.iter().cloned().collect();
1034
1035            let min = match min_bound {
1036                Bound::Unbounded => Bound::Unbounded,
1037                Bound::Included(ref s) => Bound::Included(s),
1038                Bound::Excluded(ref s) => Bound::Excluded(s),
1039            };
1040
1041            let max = match max_bound {
1042                Bound::Unbounded => Bound::Unbounded,
1043                Bound::Included(ref s) => Bound::Included(s),
1044                Bound::Excluded(ref s) => Bound::Excluded(s),
1045            };
1046
1047            let res: Vec<isize> = m.range(min, max).cloned().collect();
1048
1049            for window in res.windows(2) {
1050                if window[0] >= window[1] {
1051                    return false;
1052                }
1053            }
1054
1055            for v in input {
1056                let is_match = match_bound(&v, &min_bound, &max_bound);
1057                let is_res = res.contains(&v);
1058
1059                if is_match != is_res {
1060                    return false;
1061                }
1062            }
1063
1064            true
1065        }
1066    }
1067
1068    quickcheck! {
1069        fn check_range_rev(xs: Vec<isize>, min_bound: Bound<isize>, max_bound: Bound<isize>)
1070                -> bool
1071        {
1072            let input = filter_input(xs);
1073            let m: TreeSet<isize> = input.iter().cloned().collect();
1074
1075            let min = match min_bound {
1076                Bound::Unbounded => Bound::Unbounded,
1077                Bound::Included(ref s) => Bound::Included(s),
1078                Bound::Excluded(ref s) => Bound::Excluded(s),
1079            };
1080
1081            let max = match max_bound {
1082                Bound::Unbounded => Bound::Unbounded,
1083                Bound::Included(ref s) => Bound::Included(s),
1084                Bound::Excluded(ref s) => Bound::Excluded(s),
1085            };
1086
1087            let res: Vec<isize> = m.range(min, max).rev().cloned().collect();
1088
1089            for window in res.windows(2) {
1090                if window[0] <= window[1] {
1091                    return false;
1092                }
1093            }
1094
1095            for v in input {
1096                let is_match = match_bound(&v, &min_bound, &max_bound);
1097                let is_res = res.contains(&v);
1098
1099                if is_match != is_res {
1100                    return false;
1101                }
1102            }
1103
1104            true
1105        }
1106    }
1107
1108    quickcheck! {
1109        fn check_eq(xs: Vec<isize>) -> bool
1110        {
1111            let mut rng = StdRng::new().unwrap();
1112            let input0 = filter_input(xs);
1113            let mut input1 = input0.clone();
1114            rng.shuffle(&mut input1);
1115
1116            let m0: TreeSet<isize> = input0.into_iter().collect();
1117            let m1: TreeSet<isize> = input1.into_iter().collect();
1118
1119            m0 == m1
1120        }
1121    }
1122
1123    quickcheck! {
1124        fn check_neq(xs: Vec<isize>) -> TestResult
1125        {
1126            if xs.is_empty() {
1127                return TestResult::discard();
1128            }
1129            let mut rng = StdRng::new().unwrap();
1130            let input0 = filter_input(xs);
1131            let mut input1 = input0.clone();
1132            rng.shuffle(&mut input1);
1133            input1.pop();
1134
1135            let m0: TreeSet<isize> = input0.into_iter().collect();
1136            let m1: TreeSet<isize> = input1.into_iter().collect();
1137
1138            TestResult::from_bool(m0 != m1)
1139        }
1140    }
1141
1142    quickcheck! {
1143        fn check_intersection(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1144            let xs = filter_input(input0);
1145            let ys = filter_input(input1);
1146
1147            let mut intersection: Vec<_> = xs.iter().filter(|x| ys.contains(x)).cloned().collect();
1148
1149            intersection.sort();
1150
1151            let x_set: TreeSet<isize> = xs.into_iter().collect();
1152            let y_set: TreeSet<isize> = ys.into_iter().collect();
1153
1154            let res: Vec<isize> = x_set.intersection(&y_set).cloned().collect();
1155
1156            res == intersection
1157        }
1158    }
1159
1160    quickcheck! {
1161        fn check_union(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1162            let xs = filter_input(input0);
1163            let ys = filter_input(input1);
1164
1165            let mut union = xs.clone();
1166            for y in &ys {
1167                if !union.contains(y) {
1168                    union.push(*y);
1169                }
1170            }
1171
1172            union.sort();
1173
1174            let x_set: TreeSet<isize> = xs.into_iter().collect();
1175            let y_set: TreeSet<isize> = ys.into_iter().collect();
1176
1177            let res: Vec<isize> = x_set.union(&y_set).cloned().collect();
1178
1179            res == union
1180        }
1181    }
1182
1183    quickcheck! {
1184        fn check_difference(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1185            let xs = filter_input(input0);
1186            let ys = filter_input(input1);
1187
1188            let mut difference: Vec<_> = xs.iter().filter(|x| !ys.contains(x)).cloned().collect();
1189
1190            difference.sort();
1191
1192            let x_set: TreeSet<isize> = xs.into_iter().collect();
1193            let y_set: TreeSet<isize> = ys.into_iter().collect();
1194
1195            let res: Vec<isize> = x_set.difference(&y_set).cloned().collect();
1196
1197            res == difference
1198        }
1199    }
1200
1201    quickcheck! {
1202        fn check_symmetric_difference(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1203            let xs = filter_input(input0);
1204            let ys = filter_input(input1);
1205
1206            let mut symm_diff = Vec::new();
1207            for x in &xs {
1208                if !ys.contains(x) {
1209                    symm_diff.push(*x);
1210                }
1211            }
1212
1213            for y in &ys {
1214                if !xs.contains(y) {
1215                    symm_diff.push(*y);
1216                }
1217            }
1218
1219            symm_diff.sort();
1220
1221            let x_set: TreeSet<isize> = xs.into_iter().collect();
1222            let y_set: TreeSet<isize> = ys.into_iter().collect();
1223
1224            let res: Vec<isize> = x_set.symmetric_difference(&y_set).cloned().collect();
1225
1226            res == symm_diff
1227        }
1228    }
1229
1230    quickcheck! {
1231        fn check_is_disjoint(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1232            let xs = filter_input(input0);
1233            let ys = filter_input(input1);
1234
1235            let is_disjoint = xs.iter().all(|x| !ys.contains(x));
1236
1237            let x_set: TreeSet<isize> = xs.into_iter().collect();
1238            let y_set: TreeSet<isize> = ys.into_iter().collect();
1239
1240            is_disjoint == x_set.is_disjoint(&y_set)
1241        }
1242    }
1243
1244    quickcheck! {
1245        fn check_is_subset(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1246            let xs = filter_input(input0);
1247            let ys = filter_input(input1);
1248
1249            let is_subset = xs.iter().all(|x| ys.contains(x));
1250
1251            let x_set: TreeSet<isize> = xs.into_iter().collect();
1252            let y_set: TreeSet<isize> = ys.into_iter().collect();
1253
1254            is_subset == x_set.is_subset(&y_set)
1255        }
1256    }
1257
1258    quickcheck! {
1259        fn check_is_superset(input0: Vec<isize>, input1: Vec<isize>) -> bool {
1260            let xs = filter_input(input0);
1261            let ys = filter_input(input1);
1262
1263            let is_superset = ys.iter().all(|y| xs.contains(y));
1264
1265            let x_set: TreeSet<isize> = xs.into_iter().collect();
1266            let y_set: TreeSet<isize> = ys.into_iter().collect();
1267
1268            is_superset == x_set.is_superset(&y_set)
1269        }
1270    }
1271
1272    quickcheck! {
1273        fn check_insert_if_absent(xs: Vec<isize>, value: isize) -> bool
1274        {
1275            let input = filter_input(xs);
1276
1277            let s: TreeSet<isize> = input.iter().cloned().collect();
1278
1279            if input.iter().any(|&x| x == value) {
1280                None == s.insert_if_absent(value)
1281            } else {
1282                let res = s.insert_if_absent(value);
1283                res.is_some() && res.unwrap().contains(&value)
1284            }
1285        }
1286    }
1287}
immutable_map/set.rs

immutable_map/
set.rs
