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

sp_im/ord/
set.rs
