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

im_rc/ord/
set.rs
