imbl/ord/
set.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4
5//! An ordered set.
6//!
7//! An immutable ordered set implemented as a [B+ tree][1].
8//!
9//! Most operations on this type of set are O(log n). A
10//! [`GenericHashSet`] is usually a better choice for
11//! performance, but the `OrdSet` has the advantage of only requiring
12//! an [`Ord`][std::cmp::Ord] constraint on its values, and of being
13//! ordered, so values always come out from lowest to highest, where a
14//! [`GenericHashSet`] has no guaranteed ordering.
15//!
16//! [1]: https://en.wikipedia.org/wiki/B%2B_tree
17
18use std::borrow::Borrow;
19use std::cmp::Ordering;
20use std::collections;
21use std::fmt::{Debug, Error, Formatter};
22use std::hash::{BuildHasher, Hash, Hasher};
23use std::iter::{FromIterator, FusedIterator, Sum};
24use std::ops::{Add, Mul, RangeBounds};
25
26use archery::SharedPointerKind;
27use equivalent::Comparable;
28
29use super::map;
30use crate::hashset::GenericHashSet;
31use crate::shared_ptr::DefaultSharedPtr;
32use crate::GenericOrdMap;
33
34/// Construct a set from a sequence of values.
35///
36/// # Examples
37///
38/// ```
39/// # #[macro_use] extern crate imbl;
40/// # use imbl::ordset::OrdSet;
41/// # fn main() {
42/// assert_eq!(
43///   ordset![1, 2, 3],
44///   OrdSet::from(vec![1, 2, 3])
45/// );
46/// # }
47/// ```
48#[macro_export]
49macro_rules! ordset {
50    () => { $crate::ordset::OrdSet::new() };
51
52    ( $($x:expr),* ) => {{
53        let mut l = $crate::ordset::OrdSet::new();
54        $(
55            l.insert($x);
56        )*
57            l
58    }};
59}
60
61/// Type alias for [`GenericOrdSet`] that uses [`DefaultSharedPtr`] as the pointer type.
62///
63/// [GenericOrdSet]: ./struct.GenericOrdSet.html
64/// [DefaultSharedPtr]: ../shared_ptr/type.DefaultSharedPtr.html
65pub type OrdSet<A> = GenericOrdSet<A, DefaultSharedPtr>;
66
67/// An ordered set.
68///
69/// An immutable ordered map implemented as a [B+ tree][1].
70///
71/// Most operations on this type of set are O(log n). A
72/// [`GenericHashSet`] is usually a better choice for
73/// performance, but the `OrdSet` has the advantage of only requiring
74/// an [`Ord`][std::cmp::Ord] constraint on its values, and of being
75/// ordered, so values always come out from lowest to highest, where a
76/// [`GenericHashSet`] has no guaranteed ordering.
77///
78/// [1]: https://en.wikipedia.org/wiki/B%2B_tree
79pub struct GenericOrdSet<A, P: SharedPointerKind> {
80    map: GenericOrdMap<A, (), P>,
81}
82
83impl<A, P: SharedPointerKind> GenericOrdSet<A, P> {
84    /// Construct an empty set.
85    #[inline]
86    #[must_use]
87    pub fn new() -> Self {
88        GenericOrdSet {
89            map: GenericOrdMap::new(),
90        }
91    }
92
93    /// Construct a set with a single value.
94    ///
95    /// # Examples
96    ///
97    /// ```
98    /// # #[macro_use] extern crate imbl;
99    /// # type OrdSet<T> = imbl::ordset::OrdSet<T>;
100    /// let set = OrdSet::unit(123);
101    /// assert!(set.contains(&123));
102    /// ```
103    #[inline]
104    #[must_use]
105    pub fn unit(a: A) -> Self {
106        GenericOrdSet {
107            map: GenericOrdMap::unit(a, ()),
108        }
109    }
110
111    /// Test whether a set is empty.
112    ///
113    /// Time: O(1)
114    ///
115    /// # Examples
116    ///
117    /// ```
118    /// # #[macro_use] extern crate imbl;
119    /// # use imbl::ordset::OrdSet;
120    /// assert!(
121    ///   !ordset![1, 2, 3].is_empty()
122    /// );
123    /// assert!(
124    ///   OrdSet::<i32>::new().is_empty()
125    /// );
126    /// ```
127    #[inline]
128    #[must_use]
129    pub fn is_empty(&self) -> bool {
130        self.len() == 0
131    }
132
133    /// Get the size of a set.
134    ///
135    /// Time: O(1)
136    ///
137    /// # Examples
138    ///
139    /// ```
140    /// # #[macro_use] extern crate imbl;
141    /// # use imbl::ordset::OrdSet;
142    /// assert_eq!(3, ordset![1, 2, 3].len());
143    /// ```
144    #[inline]
145    #[must_use]
146    pub fn len(&self) -> usize {
147        self.map.len()
148    }
149
150    /// Test whether two sets refer to the same content in memory.
151    ///
152    /// This is true if the two sides are references to the same set,
153    /// or if the two sets refer to the same root node.
154    ///
155    /// This would return true if you're comparing a set to itself, or
156    /// if you're comparing a set to a fresh clone of itself.
157    ///
158    /// Time: O(1)
159    pub fn ptr_eq(&self, other: &Self) -> bool {
160        self.map.ptr_eq(&other.map)
161    }
162
163    /// Discard all elements from the set.
164    ///
165    /// This leaves you with an empty set, and all elements that
166    /// were previously inside it are dropped.
167    ///
168    /// Time: O(n)
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// # #[macro_use] extern crate imbl;
174    /// # use imbl::OrdSet;
175    /// let mut set = ordset![1, 2, 3];
176    /// set.clear();
177    /// assert!(set.is_empty());
178    /// ```
179    pub fn clear(&mut self) {
180        self.map.clear();
181    }
182}
183
184impl<A, P> GenericOrdSet<A, P>
185where
186    A: Ord,
187    P: SharedPointerKind,
188{
189    /// Get the smallest value in a set.
190    ///
191    /// If the set is empty, returns `None`.
192    ///
193    /// Time: O(log n)
194    #[must_use]
195    pub fn get_min(&self) -> Option<&A> {
196        self.map.get_min().map(|v| &v.0)
197    }
198
199    /// Get the largest value in a set.
200    ///
201    /// If the set is empty, returns `None`.
202    ///
203    /// Time: O(log n)
204    #[must_use]
205    pub fn get_max(&self) -> Option<&A> {
206        self.map.get_max().map(|v| &v.0)
207    }
208
209    /// Create an iterator over the contents of the set.
210    #[must_use]
211    pub fn iter(&self) -> Iter<'_, A, P> {
212        Iter {
213            it: self.map.iter(),
214        }
215    }
216
217    /// Create an iterator over a range inside the set.
218    #[must_use]
219    pub fn range<R, Q>(&self, range: R) -> RangedIter<'_, A, P>
220    where
221        R: RangeBounds<Q>,
222        Q: Comparable<A> + ?Sized,
223    {
224        RangedIter {
225            it: self.map.range(range),
226        }
227    }
228
229    /// Get an iterator over the differences between this set and
230    /// another, i.e. the set of entries to add or remove to this set
231    /// in order to make it equal to the other set.
232    ///
233    /// This function will avoid visiting nodes which are shared
234    /// between the two sets, meaning that even very large sets can be
235    /// compared quickly if most of their structure is shared.
236    ///
237    /// Time: O(n) (where n is the number of unique elements across
238    /// the two sets, minus the number of elements belonging to nodes
239    /// shared between them)
240    #[must_use]
241    pub fn diff<'a, 'b>(&'a self, other: &'b Self) -> DiffIter<'a, 'b, A, P> {
242        DiffIter {
243            it: self.map.diff(&other.map),
244        }
245    }
246
247    /// Test if a value is part of a set.
248    ///
249    /// Time: O(log n)
250    ///
251    /// # Examples
252    ///
253    /// ```
254    /// # #[macro_use] extern crate imbl;
255    /// # use imbl::ordset::OrdSet;
256    /// let mut set = ordset!{1, 2, 3};
257    /// assert!(set.contains(&1));
258    /// assert!(!set.contains(&4));
259    /// ```
260    #[inline]
261    #[must_use]
262    pub fn contains<Q>(&self, value: &Q) -> bool
263    where
264        Q: Comparable<A> + ?Sized,
265    {
266        self.map.contains_key(value)
267    }
268
269    /// Returns a reference to the element in the set, if any, that is equal to the value.
270    /// The value may be any borrowed form of the set’s element type, but the ordering on
271    /// the borrowed form must match the ordering on the element type.
272    ///
273    /// This is useful when the elements in the set are unique by for example an id,
274    /// and you want to get the element out of the set by using the id.
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// # #[macro_use] extern crate imbl;
280    /// # use std::borrow::Borrow;
281    /// # use std::cmp::Ordering;
282    /// # use imbl::ordset::OrdSet;
283    /// # #[derive(Clone)]
284    /// // Implements Eq and ord by delegating to id
285    /// struct FancyItem {
286    ///     id: u32,
287    ///     data: String,
288    /// }
289    /// # impl Eq for FancyItem {}
290    /// # impl PartialEq<Self> for FancyItem {fn eq(&self, other: &Self) -> bool { self.id.eq(&other.id)}}
291    /// # impl PartialOrd<Self> for FancyItem {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {self.id.partial_cmp(&other.id)}}
292    /// # impl Ord for FancyItem {fn cmp(&self, other: &Self) -> Ordering {self.id.cmp(&other.id)}}
293    /// # impl Borrow<u32> for FancyItem {fn borrow(&self) -> &u32 {&self.id}}
294    /// let mut set = ordset!{
295    ///     FancyItem {id: 0, data: String::from("Hello")},
296    ///     FancyItem {id: 1, data: String::from("Test")}
297    /// };
298    /// assert_eq!(set.get(&1).unwrap().data, "Test");
299    /// assert_eq!(set.get(&0).unwrap().data, "Hello");
300    ///
301    /// ```
302    pub fn get<Q>(&self, value: &Q) -> Option<&A>
303    where
304        Q: Comparable<A> + ?Sized,
305    {
306        self.map.get_key_value(value).map(|(k, _)| k)
307    }
308
309    /// Get the closest smaller value in a set to a given value.
310    ///
311    /// If the set contains the given value, this is returned.
312    /// Otherwise, the closest value in the set smaller than the
313    /// given value is returned. If the smallest value in the set
314    /// is larger than the given value, `None` is returned.
315    ///
316    /// # Examples
317    ///
318    /// ```rust
319    /// # #[macro_use] extern crate imbl;
320    /// # use imbl::OrdSet;
321    /// let set = ordset![1, 3, 5, 7, 9];
322    /// assert_eq!(Some(&5), set.get_prev(&6));
323    /// ```
324    #[must_use]
325    pub fn get_prev<Q>(&self, value: &Q) -> Option<&A>
326    where
327        Q: Comparable<A> + ?Sized,
328    {
329        self.map.get_prev(value).map(|(k, _)| k)
330    }
331
332    /// Get the closest larger value in a set to a given value.
333    ///
334    /// If the set contains the given value, this is returned.
335    /// Otherwise, the closest value in the set larger than the
336    /// given value is returned. If the largest value in the set
337    /// is smaller than the given value, `None` is returned.
338    ///
339    /// # Examples
340    ///
341    /// ```rust
342    /// # #[macro_use] extern crate imbl;
343    /// # use imbl::OrdSet;
344    /// let set = ordset![1, 3, 5, 7, 9];
345    /// assert_eq!(Some(&5), set.get_next(&4));
346    /// ```
347    #[must_use]
348    pub fn get_next<Q>(&self, value: &Q) -> Option<&A>
349    where
350        Q: Comparable<A> + ?Sized,
351    {
352        self.map.get_next(value).map(|(k, _)| k)
353    }
354
355    /// Test whether a set is a subset of another set, meaning that
356    /// all values in our set must also be in the other set.
357    ///
358    /// Time: O(n log m) where m is the size of the other set
359    #[must_use]
360    pub fn is_subset<RS>(&self, other: RS) -> bool
361    where
362        RS: Borrow<Self>,
363    {
364        let other = other.borrow();
365        if other.len() < self.len() {
366            return false;
367        }
368        self.iter().all(|a| other.contains(a))
369    }
370
371    /// Test whether a set is a proper subset of another set, meaning
372    /// that all values in our set must also be in the other set. A
373    /// proper subset must also be smaller than the other set.
374    ///
375    /// Time: O(n log m) where m is the size of the other set
376    #[must_use]
377    pub fn is_proper_subset<RS>(&self, other: RS) -> bool
378    where
379        RS: Borrow<Self>,
380    {
381        self.len() != other.borrow().len() && self.is_subset(other)
382    }
383
384    /// Check invariants
385    #[cfg(any(test, fuzzing))]
386    #[allow(unreachable_pub)]
387    pub fn check_sane(&self)
388    where
389        A: std::fmt::Debug,
390    {
391        self.map.check_sane();
392    }
393}
394
395impl<A, P> GenericOrdSet<A, P>
396where
397    A: Ord + Clone,
398    P: SharedPointerKind,
399{
400    /// Insert a value into a set.
401    ///
402    /// Time: O(log n)
403    ///
404    /// # Examples
405    ///
406    /// ```
407    /// # #[macro_use] extern crate imbl;
408    /// # use imbl::ordset::OrdSet;
409    /// let mut set = ordset!{};
410    /// set.insert(123);
411    /// set.insert(456);
412    /// assert_eq!(
413    ///   set,
414    ///   ordset![123, 456]
415    /// );
416    /// ```
417    #[inline]
418    pub fn insert(&mut self, a: A) -> Option<A> {
419        self.map.insert_key_value(a, ()).map(|(k, _)| k)
420    }
421
422    /// Remove a value from a set.
423    ///
424    /// Time: O(log n)
425    #[inline]
426    pub fn remove<Q>(&mut self, value: &Q) -> Option<A>
427    where
428        Q: Comparable<A> + ?Sized,
429    {
430        self.map.remove_with_key(value).map(|(k, _)| k)
431    }
432
433    /// Remove the smallest value from a set.
434    ///
435    /// Time: O(log n)
436    pub fn remove_min(&mut self) -> Option<A> {
437        // FIXME implement this at the node level for better efficiency
438        let key = self.get_min()?.clone();
439        self.remove(&key)
440    }
441
442    /// Remove the largest value from a set.
443    ///
444    /// Time: O(log n)
445    pub fn remove_max(&mut self) -> Option<A> {
446        // FIXME implement this at the node level for better efficiency
447        let key = self.get_max()?.clone();
448        self.remove(&key)
449    }
450
451    /// Construct a new set from the current set with the given value
452    /// added.
453    ///
454    /// Time: O(log n)
455    ///
456    /// # Examples
457    ///
458    /// ```
459    /// # #[macro_use] extern crate imbl;
460    /// # use imbl::ordset::OrdSet;
461    /// let set = ordset![456];
462    /// assert_eq!(
463    ///   set.update(123),
464    ///   ordset![123, 456]
465    /// );
466    /// ```
467    #[must_use]
468    pub fn update(&self, a: A) -> Self {
469        let mut out = self.clone();
470        out.insert(a);
471        out
472    }
473
474    /// Construct a new set with the given value removed if it's in
475    /// the set.
476    ///
477    /// Time: O(log n)
478    #[must_use]
479    pub fn without<Q>(&self, value: &Q) -> Self
480    where
481        Q: Comparable<A> + ?Sized,
482    {
483        let mut out = self.clone();
484        out.remove(value);
485        out
486    }
487
488    /// Remove the smallest value from a set, and return that value as
489    /// well as the updated set.
490    ///
491    /// Time: O(log n)
492    #[must_use]
493    pub fn without_min(&self) -> (Option<A>, Self) {
494        match self.get_min() {
495            Some(v) => (Some(v.clone()), self.without(v)),
496            None => (None, self.clone()),
497        }
498    }
499
500    /// Remove the largest value from a set, and return that value as
501    /// well as the updated set.
502    ///
503    /// Time: O(log n)
504    #[must_use]
505    pub fn without_max(&self) -> (Option<A>, Self) {
506        match self.get_max() {
507            Some(v) => (Some(v.clone()), self.without(v)),
508            None => (None, self.clone()),
509        }
510    }
511
512    /// Construct the union of two sets.
513    ///
514    /// Time: O(n log n)
515    ///
516    /// # Examples
517    ///
518    /// ```
519    /// # #[macro_use] extern crate imbl;
520    /// # use imbl::ordset::OrdSet;
521    /// let set1 = ordset!{1, 2};
522    /// let set2 = ordset!{2, 3};
523    /// let expected = ordset!{1, 2, 3};
524    /// assert_eq!(expected, set1.union(set2));
525    /// ```
526    #[must_use]
527    pub fn union(self, other: Self) -> Self {
528        let (mut to_mutate, to_consume) = if self.len() >= other.len() {
529            (self, other)
530        } else {
531            (other, self)
532        };
533        for value in to_consume {
534            to_mutate.insert(value);
535        }
536        to_mutate
537    }
538
539    /// Construct the union of multiple sets.
540    ///
541    /// Time: O(n log n)
542    #[must_use]
543    pub fn unions<I>(i: I) -> Self
544    where
545        I: IntoIterator<Item = Self>,
546    {
547        i.into_iter().fold(Self::default(), Self::union)
548    }
549
550    /// Construct the symmetric difference between two sets.
551    ///
552    /// This is an alias for the
553    /// [`symmetric_difference`][symmetric_difference] method.
554    ///
555    /// Time: O(n log n)
556    ///
557    /// # Examples
558    ///
559    /// ```
560    /// # #[macro_use] extern crate imbl;
561    /// # use imbl::ordset::OrdSet;
562    /// let set1 = ordset!{1, 2};
563    /// let set2 = ordset!{2, 3};
564    /// let expected = ordset!{1, 3};
565    /// assert_eq!(expected, set1.difference(set2));
566    /// ```
567    ///
568    /// [symmetric_difference]: #method.symmetric_difference
569    #[deprecated(
570        since = "2.0.1",
571        note = "to avoid conflicting behaviors between std and imbl, the `difference` alias for `symmetric_difference` will be removed."
572    )]
573    #[must_use]
574    pub fn difference(self, other: Self) -> Self {
575        self.symmetric_difference(other)
576    }
577
578    /// Construct the symmetric difference between two sets.
579    ///
580    /// Time: O(n log n)
581    ///
582    /// # Examples
583    ///
584    /// ```
585    /// # #[macro_use] extern crate imbl;
586    /// # use imbl::ordset::OrdSet;
587    /// let set1 = ordset!{1, 2};
588    /// let set2 = ordset!{2, 3};
589    /// let expected = ordset!{1, 3};
590    /// assert_eq!(expected, set1.symmetric_difference(set2));
591    /// ```
592    #[must_use]
593    pub fn symmetric_difference(mut self, other: Self) -> Self {
594        for value in other {
595            if self.remove(&value).is_none() {
596                self.insert(value);
597            }
598        }
599        self
600    }
601
602    /// Construct the relative complement between two sets, that is the set
603    /// of values in `self` that do not occur in `other`.
604    ///
605    /// Time: O(m log n) where m is the size of the other set
606    ///
607    /// # Examples
608    ///
609    /// ```
610    /// # #[macro_use] extern crate imbl;
611    /// # use imbl::ordset::OrdSet;
612    /// let set1 = ordset!{1, 2};
613    /// let set2 = ordset!{2, 3};
614    /// let expected = ordset!{1};
615    /// assert_eq!(expected, set1.relative_complement(set2));
616    /// ```
617    #[must_use]
618    pub fn relative_complement(mut self, other: Self) -> Self {
619        for value in other {
620            let _ = self.remove(&value);
621        }
622        self
623    }
624
625    /// Construct the intersection of two sets.
626    ///
627    /// Time: O(n log n)
628    ///
629    /// # Examples
630    ///
631    /// ```
632    /// # #[macro_use] extern crate imbl;
633    /// # use imbl::ordset::OrdSet;
634    /// let set1 = ordset!{1, 2};
635    /// let set2 = ordset!{2, 3};
636    /// let expected = ordset!{2};
637    /// assert_eq!(expected, set1.intersection(set2));
638    /// ```
639    #[must_use]
640    pub fn intersection(self, other: Self) -> Self {
641        let mut out = Self::default();
642        for value in other {
643            if self.contains(&value) {
644                out.insert(value);
645            }
646        }
647        out
648    }
649
650    /// Split a set into two, with the left hand set containing values
651    /// which are smaller than `split`, and the right hand set
652    /// containing values which are larger than `split`.
653    ///
654    /// The `split` value itself is discarded.
655    ///
656    /// Time: O(n)
657    #[must_use]
658    pub fn split<Q>(self, split: &Q) -> (Self, Self)
659    where
660        Q: Comparable<A> + ?Sized,
661    {
662        let (left, _, right) = self.split_member(split);
663        (left, right)
664    }
665
666    /// Split a set into two, with the left hand set containing values
667    /// which are smaller than `split`, and the right hand set
668    /// containing values which are larger than `split`.
669    ///
670    /// Returns a tuple of the two sets and a boolean which is true if
671    /// the `split` value existed in the original set, and false
672    /// otherwise.
673    ///
674    /// Time: O(n)
675    #[must_use]
676    pub fn split_member<Q>(self, split: &Q) -> (Self, bool, Self)
677    where
678        Q: Comparable<A> + ?Sized,
679    {
680        let mut left = Self::default();
681        let mut right = Self::default();
682        let mut present = false;
683        for value in self {
684            match split.compare(&value).reverse() {
685                Ordering::Less => {
686                    left.insert(value);
687                }
688                Ordering::Equal => {
689                    present = true;
690                }
691                Ordering::Greater => {
692                    right.insert(value);
693                }
694            }
695        }
696        (left, present, right)
697    }
698
699    /// Construct a set with only the `n` smallest values from a given
700    /// set.
701    ///
702    /// Time: O(n)
703    #[must_use]
704    pub fn take(&self, n: usize) -> Self {
705        self.iter().take(n).cloned().collect()
706    }
707
708    /// Construct a set with the `n` smallest values removed from a
709    /// given set.
710    ///
711    /// Time: O(n)
712    #[must_use]
713    pub fn skip(&self, n: usize) -> Self {
714        self.iter().skip(n).cloned().collect()
715    }
716}
717
718// Core traits
719
720impl<A, P: SharedPointerKind> Clone for GenericOrdSet<A, P> {
721    /// Clone a set.
722    ///
723    /// Time: O(1)
724    #[inline]
725    fn clone(&self) -> Self {
726        GenericOrdSet {
727            map: self.map.clone(),
728        }
729    }
730}
731
732// TODO: Support PartialEq for OrdSet that have different P
733impl<A: Ord, P: SharedPointerKind> PartialEq for GenericOrdSet<A, P> {
734    fn eq(&self, other: &Self) -> bool {
735        self.map.eq(&other.map)
736    }
737}
738
739impl<A: Ord, P: SharedPointerKind> Eq for GenericOrdSet<A, P> {}
740
741impl<A: Ord, P: SharedPointerKind> PartialOrd for GenericOrdSet<A, P> {
742    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
743        Some(self.cmp(other))
744    }
745}
746
747impl<A: Ord, P: SharedPointerKind> Ord for GenericOrdSet<A, P> {
748    fn cmp(&self, other: &Self) -> Ordering {
749        self.iter().cmp(other.iter())
750    }
751}
752
753impl<A: Ord + Hash, P: SharedPointerKind> Hash for GenericOrdSet<A, P> {
754    fn hash<H>(&self, state: &mut H)
755    where
756        H: Hasher,
757    {
758        for i in self.iter() {
759            i.hash(state);
760        }
761    }
762}
763
764impl<A, P: SharedPointerKind> Default for GenericOrdSet<A, P> {
765    fn default() -> Self {
766        GenericOrdSet::new()
767    }
768}
769
770impl<A: Ord + Clone, P: SharedPointerKind> Add for GenericOrdSet<A, P> {
771    type Output = GenericOrdSet<A, P>;
772
773    fn add(self, other: Self) -> Self::Output {
774        self.union(other)
775    }
776}
777
778impl<A: Ord + Clone, P: SharedPointerKind> Add for &GenericOrdSet<A, P> {
779    type Output = GenericOrdSet<A, P>;
780
781    fn add(self, other: Self) -> Self::Output {
782        self.clone().union(other.clone())
783    }
784}
785
786impl<A: Ord + Clone, P: SharedPointerKind> Mul for GenericOrdSet<A, P> {
787    type Output = GenericOrdSet<A, P>;
788
789    fn mul(self, other: Self) -> Self::Output {
790        self.intersection(other)
791    }
792}
793
794impl<A: Ord + Clone, P: SharedPointerKind> Mul for &GenericOrdSet<A, P> {
795    type Output = GenericOrdSet<A, P>;
796
797    fn mul(self, other: Self) -> Self::Output {
798        self.clone().intersection(other.clone())
799    }
800}
801
802impl<A: Ord + Clone, P: SharedPointerKind> Sum for GenericOrdSet<A, P> {
803    fn sum<I>(it: I) -> Self
804    where
805        I: Iterator<Item = Self>,
806    {
807        it.fold(Self::new(), |a, b| a + b)
808    }
809}
810
811impl<A, R, P> Extend<R> for GenericOrdSet<A, P>
812where
813    A: Ord + Clone + From<R>,
814    P: SharedPointerKind,
815{
816    fn extend<I>(&mut self, iter: I)
817    where
818        I: IntoIterator<Item = R>,
819    {
820        for value in iter {
821            self.insert(From::from(value));
822        }
823    }
824}
825
826impl<A: Ord + Debug, P: SharedPointerKind> Debug for GenericOrdSet<A, P> {
827    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
828        f.debug_set().entries(self.iter()).finish()
829    }
830}
831
832// Iterators
833
834/// An iterator over the elements of a set.
835pub struct Iter<'a, A, P: SharedPointerKind> {
836    it: map::Iter<'a, A, (), P>,
837}
838
839// We impl Clone instead of deriving it, because we want Clone even if K and V aren't.
840impl<'a, A, P: SharedPointerKind> Clone for Iter<'a, A, P> {
841    fn clone(&self) -> Self {
842        Iter {
843            it: self.it.clone(),
844        }
845    }
846}
847
848impl<'a, A, P: SharedPointerKind> Iterator for Iter<'a, A, P>
849where
850    A: 'a + Ord,
851{
852    type Item = &'a A;
853
854    /// Advance the iterator and return the next value.
855    ///
856    /// Time: O(1)*
857    fn next(&mut self) -> Option<Self::Item> {
858        self.it.next().map(|(k, _)| k)
859    }
860
861    fn size_hint(&self) -> (usize, Option<usize>) {
862        self.it.size_hint()
863    }
864}
865
866impl<'a, A, P> DoubleEndedIterator for Iter<'a, A, P>
867where
868    A: 'a + Ord,
869    P: SharedPointerKind,
870{
871    fn next_back(&mut self) -> Option<Self::Item> {
872        self.it.next_back().map(|(k, _)| k)
873    }
874}
875
876impl<'a, A, P> ExactSizeIterator for Iter<'a, A, P>
877where
878    A: 'a + Ord,
879    P: SharedPointerKind,
880{
881}
882
883impl<'a, A, P> FusedIterator for Iter<'a, A, P>
884where
885    A: 'a + Ord,
886    P: SharedPointerKind,
887{
888}
889
890/// A ranged iterator over the elements of a set.
891///
892/// The only difference from `Iter` is that this one doesn't implement
893/// `ExactSizeIterator` because we can't know the size of the range without first
894/// iterating over it to count.
895pub struct RangedIter<'a, A, P: SharedPointerKind> {
896    it: map::RangedIter<'a, A, (), P>,
897}
898
899impl<'a, A, P> Iterator for RangedIter<'a, A, P>
900where
901    A: 'a + Ord,
902    P: SharedPointerKind,
903{
904    type Item = &'a A;
905
906    /// Advance the iterator and return the next value.
907    ///
908    /// Time: O(1)*
909    fn next(&mut self) -> Option<Self::Item> {
910        self.it.next().map(|(k, _)| k)
911    }
912
913    fn size_hint(&self) -> (usize, Option<usize>) {
914        self.it.size_hint()
915    }
916}
917
918impl<'a, A, P> DoubleEndedIterator for RangedIter<'a, A, P>
919where
920    A: 'a + Ord,
921    P: SharedPointerKind,
922{
923    fn next_back(&mut self) -> Option<Self::Item> {
924        self.it.next_back().map(|(k, _)| k)
925    }
926}
927
928/// A consuming iterator over the elements of a set.
929pub struct ConsumingIter<A, P: SharedPointerKind> {
930    it: map::ConsumingIter<A, (), P>,
931}
932
933impl<A, P: SharedPointerKind> Clone for ConsumingIter<A, P> {
934    fn clone(&self) -> Self {
935        Self {
936            it: self.it.clone(),
937        }
938    }
939}
940
941impl<A, P> Iterator for ConsumingIter<A, P>
942where
943    A: Clone,
944    P: SharedPointerKind,
945{
946    type Item = A;
947
948    /// Advance the iterator and return the next value.
949    ///
950    /// Time: O(1)*
951    fn next(&mut self) -> Option<Self::Item> {
952        self.it.next().map(|v| v.0)
953    }
954
955    fn size_hint(&self) -> (usize, Option<usize>) {
956        self.it.size_hint()
957    }
958}
959
960impl<A, P> DoubleEndedIterator for ConsumingIter<A, P>
961where
962    A: Clone,
963    P: SharedPointerKind,
964{
965    fn next_back(&mut self) -> Option<Self::Item> {
966        self.it.next_back().map(|v| v.0)
967    }
968}
969
970impl<A, P> ExactSizeIterator for ConsumingIter<A, P>
971where
972    A: Clone,
973    P: SharedPointerKind,
974{
975}
976
977impl<A, P> FusedIterator for ConsumingIter<A, P>
978where
979    A: Clone,
980    P: SharedPointerKind,
981{
982}
983
984/// An iterator over the difference between two sets.
985pub struct DiffIter<'a, 'b, A, P: SharedPointerKind> {
986    it: map::DiffIter<'a, 'b, A, (), P>,
987}
988
989/// A description of a difference between two ordered sets.
990#[derive(PartialEq, Eq, Debug)]
991pub enum DiffItem<'a, 'b, A> {
992    /// This value has been added to the new set.
993    Add(&'b A),
994    /// This value has been removed from the new set.
995    Remove(&'a A),
996}
997
998impl<'a, 'b, A, P> Iterator for DiffIter<'a, 'b, A, P>
999where
1000    A: Ord + PartialEq,
1001    P: SharedPointerKind,
1002{
1003    type Item = DiffItem<'a, 'b, A>;
1004
1005    /// Advance the iterator and return the next value.
1006    ///
1007    /// Time: O(1)*
1008    fn next(&mut self) -> Option<Self::Item> {
1009        self.it.next().map(|item| match item {
1010            map::DiffItem::Add(k, _) => DiffItem::Add(k),
1011            map::DiffItem::Remove(k, _) => DiffItem::Remove(k),
1012            // Note that since the underlying map keys are unique and the values
1013            // are fixed `()`, we can never have an update.
1014            map::DiffItem::Update { .. } => unreachable!(),
1015        })
1016    }
1017}
1018
1019impl<'a, 'b, A, P> FusedIterator for DiffIter<'a, 'b, A, P>
1020where
1021    A: Ord + PartialEq,
1022    P: SharedPointerKind,
1023{
1024}
1025
1026impl<A, R, P> FromIterator<R> for GenericOrdSet<A, P>
1027where
1028    A: Ord + Clone + From<R>,
1029    P: SharedPointerKind,
1030{
1031    fn from_iter<T>(i: T) -> Self
1032    where
1033        T: IntoIterator<Item = R>,
1034    {
1035        let mut out = Self::new();
1036        for item in i {
1037            out.insert(From::from(item));
1038        }
1039        out
1040    }
1041}
1042
1043impl<'a, A, P> IntoIterator for &'a GenericOrdSet<A, P>
1044where
1045    A: 'a + Ord,
1046    P: SharedPointerKind,
1047{
1048    type Item = &'a A;
1049    type IntoIter = Iter<'a, A, P>;
1050
1051    fn into_iter(self) -> Self::IntoIter {
1052        self.iter()
1053    }
1054}
1055
1056impl<A, P> IntoIterator for GenericOrdSet<A, P>
1057where
1058    A: Ord + Clone,
1059    P: SharedPointerKind,
1060{
1061    type Item = A;
1062    type IntoIter = ConsumingIter<A, P>;
1063
1064    fn into_iter(self) -> Self::IntoIter {
1065        ConsumingIter {
1066            it: self.map.into_iter(),
1067        }
1068    }
1069}
1070
1071// Conversions
1072
1073impl<A, OA, P1, P2> From<&GenericOrdSet<&A, P2>> for GenericOrdSet<OA, P1>
1074where
1075    A: ToOwned<Owned = OA> + Ord + ?Sized,
1076    OA: Ord + Clone,
1077    P1: SharedPointerKind,
1078    P2: SharedPointerKind,
1079{
1080    fn from(set: &GenericOrdSet<&A, P2>) -> Self {
1081        set.iter().map(|a| (*a).to_owned()).collect()
1082    }
1083}
1084
1085impl<'a, A, P> From<&'a [A]> for GenericOrdSet<A, P>
1086where
1087    A: Ord + Clone,
1088    P: SharedPointerKind,
1089{
1090    fn from(slice: &'a [A]) -> Self {
1091        slice.iter().cloned().collect()
1092    }
1093}
1094
1095impl<A: Ord + Clone, P: SharedPointerKind> From<Vec<A>> for GenericOrdSet<A, P> {
1096    fn from(vec: Vec<A>) -> Self {
1097        vec.into_iter().collect()
1098    }
1099}
1100
1101impl<A: Ord + Clone, P: SharedPointerKind> From<&Vec<A>> for GenericOrdSet<A, P> {
1102    fn from(vec: &Vec<A>) -> Self {
1103        vec.iter().cloned().collect()
1104    }
1105}
1106
1107impl<A: Eq + Hash + Ord + Clone, P: SharedPointerKind> From<collections::HashSet<A>>
1108    for GenericOrdSet<A, P>
1109{
1110    fn from(hash_set: collections::HashSet<A>) -> Self {
1111        hash_set.into_iter().collect()
1112    }
1113}
1114
1115impl<A: Eq + Hash + Ord + Clone, P: SharedPointerKind> From<&collections::HashSet<A>>
1116    for GenericOrdSet<A, P>
1117{
1118    fn from(hash_set: &collections::HashSet<A>) -> Self {
1119        hash_set.iter().cloned().collect()
1120    }
1121}
1122
1123impl<A: Ord + Clone, P: SharedPointerKind> From<collections::BTreeSet<A>> for GenericOrdSet<A, P> {
1124    fn from(btree_set: collections::BTreeSet<A>) -> Self {
1125        btree_set.into_iter().collect()
1126    }
1127}
1128
1129impl<A: Ord + Clone, P: SharedPointerKind> From<&collections::BTreeSet<A>> for GenericOrdSet<A, P> {
1130    fn from(btree_set: &collections::BTreeSet<A>) -> Self {
1131        btree_set.iter().cloned().collect()
1132    }
1133}
1134
1135impl<A: Hash + Eq + Ord + Clone, S: BuildHasher, P1: SharedPointerKind, P2: SharedPointerKind>
1136    From<GenericHashSet<A, S, P2>> for GenericOrdSet<A, P1>
1137{
1138    fn from(hashset: GenericHashSet<A, S, P2>) -> Self {
1139        hashset.into_iter().collect()
1140    }
1141}
1142
1143impl<A: Hash + Eq + Ord + Clone, S: BuildHasher, P1: SharedPointerKind, P2: SharedPointerKind>
1144    From<&GenericHashSet<A, S, P2>> for GenericOrdSet<A, P1>
1145{
1146    fn from(hashset: &GenericHashSet<A, S, P2>) -> Self {
1147        hashset.into_iter().cloned().collect()
1148    }
1149}
1150
1151#[cfg(test)]
1152mod test {
1153    use super::*;
1154    use crate::proptest::*;
1155    use proptest::proptest;
1156    use static_assertions::{assert_impl_all, assert_not_impl_any};
1157
1158    assert_impl_all!(OrdSet<i32>: Send, Sync);
1159    assert_not_impl_any!(OrdSet<*const i32>: Send, Sync);
1160    assert_covariant!(OrdSet<T> in T);
1161
1162    #[test]
1163    fn match_strings_with_string_slices() {
1164        let mut set: OrdSet<String> = From::from(&ordset!["foo", "bar"]);
1165        set = set.without("bar");
1166        assert!(!set.contains("bar"));
1167        set.remove("foo");
1168        assert!(!set.contains("foo"));
1169    }
1170
1171    #[test]
1172    fn consuming_iter_len() {
1173        let set = ordset![1, 2, 3, 4, 5];
1174        let mut it = set.into_iter();
1175        assert_eq!(it.len(), 5);
1176        it.next();
1177        assert_eq!(it.len(), 4);
1178    }
1179
1180    #[test]
1181    fn ranged_iter() {
1182        let set = ordset![1, 2, 3, 4, 5];
1183        let range: Vec<i32> = set.range::<_, i32>(..).cloned().collect();
1184        assert_eq!(vec![1, 2, 3, 4, 5], range);
1185        let range: Vec<i32> = set.range::<_, i32>(..).rev().cloned().collect();
1186        assert_eq!(vec![5, 4, 3, 2, 1], range);
1187        let range: Vec<i32> = set.range(2..5).cloned().collect();
1188        assert_eq!(vec![2, 3, 4], range);
1189        let range: Vec<i32> = set.range(2..5).rev().cloned().collect();
1190        assert_eq!(vec![4, 3, 2], range);
1191        let range: Vec<i32> = set.range(3..).cloned().collect();
1192        assert_eq!(vec![3, 4, 5], range);
1193        let range: Vec<i32> = set.range(3..).rev().cloned().collect();
1194        assert_eq!(vec![5, 4, 3], range);
1195        let range: Vec<i32> = set.range(..4).cloned().collect();
1196        assert_eq!(vec![1, 2, 3], range);
1197        let range: Vec<i32> = set.range(..4).rev().cloned().collect();
1198        assert_eq!(vec![3, 2, 1], range);
1199        let range: Vec<i32> = set.range(..=3).cloned().collect();
1200        assert_eq!(vec![1, 2, 3], range);
1201        let range: Vec<i32> = set.range(..=3).rev().cloned().collect();
1202        assert_eq!(vec![3, 2, 1], range);
1203    }
1204
1205    proptest! {
1206        #[test]
1207        fn proptest_a_set(ref s in ord_set(".*", 10..100)) {
1208            assert!(s.len() < 100);
1209            assert!(s.len() >= 10);
1210        }
1211
1212        #[test]
1213        fn long_ranged_iter(max in 1..1000) {
1214            let range = 0..max;
1215            let expected: Vec<i32> = range.clone().collect();
1216            let set: OrdSet<i32> = OrdSet::from_iter(range.clone());
1217            let result: Vec<i32> = set.range::<_, i32>(..).cloned().collect();
1218            assert_eq!(expected, result);
1219
1220            let expected: Vec<i32> = range.clone().rev().collect();
1221            let set: OrdSet<i32> = OrdSet::from_iter(range);
1222            let result: Vec<i32> = set.range::<_, i32>(..).rev().cloned().collect();
1223            assert_eq!(expected, result);
1224        }
1225    }
1226}
imbl/ord/set.rs

imbl/ord/
set.rs
