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

imbl/ord/
set.rs
