compare/
lib.rs

1//! Comparators.
2//!
3//! A comparator is any type that implements the [`Compare`](trait.Compare.html) trait,
4//! which imposes a [total order](https://en.wikipedia.org/wiki/Total_order). Its
5//! [`compare`](trait.Compare.html#tymethod.compare) method accepts two values, which may
6//! be of the same type or different types, and returns an ordering on them.
7//!
8//! Comparators are useful for parameterizing the behavior of sort methods and certain
9//! data structures.
10//!
11//! The most basic comparator is [`Natural`](struct.Natural.html), which simply delegates
12//! to the type's implementation of [`Ord`]
13//! (http://doc.rust-lang.org/std/cmp/trait.Ord.html):
14//!
15//! ```
16//! use compare::{Compare, natural};
17//! use std::cmp::Ordering::{Less, Equal, Greater};
18//!
19//! let a = &1;
20//! let b = &2;
21//!
22//! let cmp = natural();
23//! assert_eq!(cmp.compare(a, b), Less);
24//! assert_eq!(cmp.compare(b, a), Greater);
25//! assert_eq!(cmp.compare(a, a), Equal);
26//! ```
27//!
28//! There are convenience methods for checking each of the six relations:
29//!
30//! ```
31//! use compare::{Compare, natural};
32//!
33//! let a = &1;
34//! let b = &2;
35//!
36//! let cmp = natural();
37//! assert!(cmp.compares_lt(a, b));
38//! assert!(cmp.compares_le(a, b));
39//! assert!(cmp.compares_ge(b, a));
40//! assert!(cmp.compares_gt(b, a));
41//! assert!(cmp.compares_eq(a, a));
42//! assert!(cmp.compares_ne(a, b));
43//! ```
44//!
45//! The `Compare` trait also provides default methods that
46//! consume a comparator to produce a new one with different behavior, similar to
47//! [iterator adaptors](http://doc.rust-lang.org/std/iter/trait.IteratorExt.html). For
48//! example, all comparators can be [reversed](trait.Compare.html#method.rev):
49//!
50//! ```
51//! use compare::{Compare, natural};
52//! use std::cmp::Ordering::Greater;
53//!
54//! let cmp = natural().rev();
55//! assert_eq!(cmp.compare(&1, &2), Greater);
56//! ```
57//!
58//! It is possible to implement a comparator that is not based on the natural ordering of
59//! a type by using a closure of type `Fn(&L, &R) -> Ordering`. For example, slices
60//! can be compared by their length instead of their contents:
61//!
62//! ```
63//! use compare::Compare;
64//! use std::cmp::Ordering::{Less, Greater};
65//!
66//! let a = [1, 2, 3];
67//! let b = [4, 5];
68//!
69//! let cmp = |l: &[i32], r: &[i32]| l.len().cmp(&r.len());
70//! assert_eq!(cmp.compare(&a, &b), Greater);
71//!
72//! let cmp = cmp.rev();
73//! assert_eq!(cmp.compare(&a, &b), Less);
74//! ```
75//!
76//! Comparators can be combined [lexicographically]
77//! (https://en.wikipedia.org/wiki/Lexicographical_order) in order to compare values
78//! first by one key, [then](trait.Compare.html#method.then), if the first keys were
79//! equal, by another:
80//!
81//! ```
82//! use compare::Compare;
83//! use std::cmp::Ordering::{Less, Equal, Greater};
84//!
85//! struct Pet { name: &'static str, age: u8 }
86//!
87//! let fido4 = &Pet { name: "Fido", age: 4 };
88//! let ruff2 = &Pet { name: "Ruff", age: 2 };
89//! let fido3 = &Pet { name: "Fido", age: 3 };
90//!
91//! let name_cmp = |l: &Pet, r: &Pet| l.name.cmp(r.name);
92//! assert_eq!(name_cmp.compare(fido4, ruff2), Less);
93//! assert_eq!(name_cmp.compare(fido4, fido3), Equal);
94//! assert_eq!(name_cmp.compare(ruff2, fido3), Greater);
95//!
96//! let age_cmp = |l: &Pet, r: &Pet| l.age.cmp(&r.age);
97//! assert_eq!(age_cmp.compare(fido4, ruff2), Greater);
98//! assert_eq!(age_cmp.compare(fido4, fido3), Greater);
99//! assert_eq!(age_cmp.compare(ruff2, fido3), Less);
100//!
101//! let name_age_cmp = name_cmp.then(age_cmp);
102//! assert_eq!(name_age_cmp.compare(fido4, ruff2), Less);
103//! assert_eq!(name_age_cmp.compare(fido4, fido3), Greater);
104//! assert_eq!(name_age_cmp.compare(ruff2, fido3), Greater);
105//! ```
106//!
107//! It is often repetitive to compare two values of the same type by the same key, so the
108//! [key-extraction logic](struct.Extract.html) can be factored out, simplifying the
109//! previous example:
110//!
111//! ```
112//! use compare::{Compare, Extract};
113//! use std::cmp::Ordering::{Less, Greater};
114//!
115//! struct Pet { name: &'static str, age: u8 }
116//!
117//! let fido4 = &Pet { name: "Fido", age: 4 };
118//! let ruff2 = &Pet { name: "Ruff", age: 2 };
119//! let fido3 = &Pet { name: "Fido", age: 3 };
120//!
121//! let name_age_cmp = Extract::new(|p: &Pet| p.name)
122//!              .then(Extract::new(|p: &Pet| p.age));
123//!
124//! assert_eq!(name_age_cmp.compare(fido4, ruff2), Less);
125//! assert_eq!(name_age_cmp.compare(fido4, fido3), Greater);
126//! assert_eq!(name_age_cmp.compare(ruff2, fido3), Greater);
127//! ```
128
129#![no_std]
130
131use core::borrow::Borrow;
132use core::cmp::Ordering::{self, Less, Equal, Greater};
133use core::default::Default;
134use core::marker::PhantomData;
135use core::fmt::{self, Debug};
136
137/// Returns the maximum of two values according to the given comparator, or `r` if they
138/// are equal.
139///
140/// # Examples
141///
142/// ```
143/// use compare::{Extract, max};
144///
145/// struct Foo { key: char, id: u8 }
146///
147/// let f1 = &Foo { key: 'a', id: 1};
148/// let f2 = &Foo { key: 'a', id: 2};
149/// let f3 = &Foo { key: 'b', id: 3};
150///
151/// let cmp = Extract::new(|f: &Foo| f.key);
152/// assert_eq!(max(&cmp, f1, f2).id, f2.id);
153/// assert_eq!(max(&cmp, f1, f3).id, f3.id);
154/// ```
155// FIXME: convert to default method on `Compare` once where clauses permit equality
156// (https://github.com/rust-lang/rust/issues/20041)
157pub fn max<'a, C: ?Sized, T: ?Sized>(cmp: &C, l: &'a T, r: &'a T) -> &'a T
158    where C: Compare<T> {
159
160    if cmp.compares_ge(r, l) { r } else { l }
161}
162
163/// Returns the minimum of two values according to the given comparator, or `l` if they
164/// are equal.
165///
166/// # Examples
167///
168/// ```
169/// use compare::{Extract, min};
170///
171/// struct Foo { key: char, id: u8 }
172///
173/// let f1 = &Foo { key: 'b', id: 1};
174/// let f2 = &Foo { key: 'b', id: 2};
175/// let f3 = &Foo { key: 'a', id: 3};
176///
177/// let cmp = Extract::new(|f: &Foo| f.key);
178/// assert_eq!(min(&cmp, f1, f2).id, f1.id);
179/// assert_eq!(min(&cmp, f1, f3).id, f3.id);
180/// ```
181// FIXME: convert to default method on `Compare` once where clauses permit equality
182// (https://github.com/rust-lang/rust/issues/20041)
183pub fn min<'a, C: ?Sized, T: ?Sized>(cmp: &C, l: &'a T, r: &'a T) -> &'a T
184    where C: Compare<T> {
185
186    if cmp.compares_le(l, r) { l } else { r }
187}
188
189/// A comparator imposing a [total order](https://en.wikipedia.org/wiki/Total_order).
190///
191/// See the [`compare` module's documentation](index.html) for detailed usage.
192///
193/// The `compares_*` methods may be overridden to provide more efficient implementations.
194pub trait Compare<L: ?Sized, R: ?Sized = L> {
195    /// Compares two values, returning `Less`, `Equal`, or `Greater` if `l` is less
196    /// than, equal to, or greater than `r`, respectively.
197    fn compare(&self, l: &L, r: &R) -> Ordering;
198
199    /// Checks if `l` is less than `r`.
200    fn compares_lt(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Less }
201
202    /// Checks if `l` is less than or equal to `r`.
203    fn compares_le(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Greater }
204
205    /// Checks if `l` is greater than or equal to `r`.
206    fn compares_ge(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Less }
207
208    /// Checks if `l` is greater than `r`.
209    fn compares_gt(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Greater }
210
211    /// Checks if `l` is equal to `r`.
212    fn compares_eq(&self, l: &L, r: &R) -> bool { self.compare(l, r) == Equal }
213
214    /// Checks if `l` is not equal to `r`.
215    fn compares_ne(&self, l: &L, r: &R) -> bool { self.compare(l, r) != Equal }
216
217    /// Borrows the comparator's parameters before comparing them.
218    ///
219    /// # Examples
220    ///
221    /// ```
222    /// use compare::{Compare, natural};
223    /// use std::cmp::Ordering::{Less, Equal, Greater};
224    ///
225    /// let a_str = "a";
226    /// let a_string = a_str.to_string();
227    ///
228    /// let b_str = "b";
229    /// let b_string = b_str.to_string();
230    ///
231    /// let cmp = natural().borrowing();
232    /// assert_eq!(cmp.compare(a_str, &a_string), Equal);
233    /// assert_eq!(cmp.compare(a_str, b_str), Less);
234    /// assert_eq!(cmp.compare(&b_string, a_str), Greater);
235    /// ```
236    fn borrowing(self) -> Borrowing<Self, L, R> where Self: Sized { Borrowing(self, PhantomData) }
237
238    /// Reverses the ordering of the comparator.
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// use compare::{Compare, natural};
244    /// use std::cmp::Ordering::{Less, Equal, Greater};
245    ///
246    /// let a = &1;
247    /// let b = &2;
248    ///
249    /// let cmp = natural().rev();
250    /// assert_eq!(cmp.compare(a, b), Greater);
251    /// assert_eq!(cmp.compare(b, a), Less);
252    /// assert_eq!(cmp.compare(a, a), Equal);
253    /// ```
254    fn rev(self) -> Rev<Self> where Self: Sized { Rev(self) }
255
256    /// Swaps the comparator's parameters, maintaining the underlying ordering.
257    ///
258    /// This is useful for providing a comparator `C: Compare<T, U>` in a context that
259    /// expects `C: Compare<U, T>`.
260    ///
261    /// # Examples
262    ///
263    /// ```
264    /// use compare::Compare;
265    /// use std::cmp::Ordering::{Less, Equal, Greater};
266    ///
267    /// let cmp = |l: &u8, r: &u16| (*l as u16).cmp(r);
268    /// assert_eq!(cmp.compare(&1u8, &2u16), Less);
269    /// assert_eq!(cmp.compare(&2u8, &1u16), Greater);
270    /// assert_eq!(cmp.compare(&1u8, &1u16), Equal);
271    ///
272    /// let cmp = cmp.swap();
273    /// assert_eq!(cmp.compare(&2u16, &1u8), Less);
274    /// assert_eq!(cmp.compare(&1u16, &2u8), Greater);
275    /// assert_eq!(cmp.compare(&1u16, &1u8), Equal);
276    /// ```
277    fn swap(self) -> Swap<Self> where Self: Sized { Swap(self) }
278
279    /// [Lexicographically](https://en.wikipedia.org/wiki/Lexicographical_order) combines
280    /// the comparator with another.
281    ///
282    /// The retuned comparator compares values first using `self`, then, if they are
283    /// equal, using `then`.
284    ///
285    /// # Examples
286    ///
287    /// ```
288    /// use compare::{Compare, Extract};
289    /// use std::cmp::Ordering::{Less, Equal};
290    ///
291    /// struct Foo { key1: char, key2: u8 }
292    ///
293    /// let f1 = &Foo { key1: 'a', key2: 2};
294    /// let f2 = &Foo { key1: 'a', key2: 3};
295    ///
296    /// let cmp = Extract::new(|foo: &Foo| foo.key1);
297    /// assert_eq!(cmp.compare(f1, f2), Equal);
298    ///
299    /// let cmp = cmp.then(Extract::new(|foo: &Foo| foo.key2));
300    /// assert_eq!(cmp.compare(f1, f2), Less);
301    /// ```
302    fn then<D>(self, then: D) -> Then<Self, D> where D: Compare<L, R>, Self: Sized {
303        Then(self, then)
304    }
305}
306
307impl<F: ?Sized, L: ?Sized, R: ?Sized> Compare<L, R> for F
308    where F: Fn(&L, &R) -> Ordering {
309
310    fn compare(&self, l: &L, r: &R) -> Ordering { (*self)(l, r) }
311}
312
313/// A comparator that borrows its parameters before comparing them.
314///
315/// See [`Compare::borrow`](trait.Compare.html#method.borrow) for an example.
316pub struct Borrowing<C, Lb: ?Sized, Rb: ?Sized = Lb>(C, PhantomData<fn(&Lb, &Rb)>)
317    where C: Compare<Lb, Rb>;
318
319impl<C, L: ?Sized, R: ?Sized, Lb: ?Sized, Rb: ?Sized> Compare<L, R> for Borrowing<C, Lb, Rb>
320    where C: Compare<Lb, Rb>, L: Borrow<Lb>, R: Borrow<Rb> {
321
322    fn compare(&self, l: &L, r: &R) -> Ordering { self.0.compare(l.borrow(), r.borrow()) }
323    fn compares_lt(&self, l: &L, r: &R) -> bool { self.0.compares_lt(l.borrow(), r.borrow()) }
324    fn compares_le(&self, l: &L, r: &R) -> bool { self.0.compares_le(l.borrow(), r.borrow()) }
325    fn compares_ge(&self, l: &L, r: &R) -> bool { self.0.compares_ge(l.borrow(), r.borrow()) }
326    fn compares_gt(&self, l: &L, r: &R) -> bool { self.0.compares_gt(l.borrow(), r.borrow()) }
327    fn compares_eq(&self, l: &L, r: &R) -> bool { self.0.compares_eq(l.borrow(), r.borrow()) }
328    fn compares_ne(&self, l: &L, r: &R) -> bool { self.0.compares_ne(l.borrow(), r.borrow()) }
329}
330
331impl<C, Lb: ?Sized, Rb: ?Sized> Clone for Borrowing<C, Lb, Rb>
332    where C: Compare<Lb, Rb> + Clone {
333
334    fn clone(&self) -> Self { Borrowing(self.0.clone(), PhantomData) }
335}
336
337impl<C, Lb: ?Sized, Rb: ?Sized> Copy for Borrowing<C, Lb, Rb>
338    where C: Compare<Lb, Rb> + Copy {}
339
340impl<C, Lb: ?Sized, Rb: ?Sized> Default for Borrowing<C, Lb, Rb>
341    where C: Compare<Lb, Rb> + Default {
342
343    fn default() -> Self { Borrowing(Default::default(), PhantomData) }
344}
345
346impl<C, Lb: ?Sized, Rb: ?Sized> PartialEq for Borrowing<C, Lb, Rb>
347    where C: Compare<Lb, Rb> + PartialEq {
348
349    fn eq(&self, other: &Self) -> bool { self.0 == other.0 }
350}
351
352impl<C, Lb: ?Sized, Rb: ?Sized> Eq for Borrowing<C, Lb, Rb> where C: Compare<Lb, Rb> + Eq {}
353
354impl<C, Lb: ?Sized, Rb: ?Sized> Debug for Borrowing<C, Lb, Rb>
355    where C: Compare<Lb, Rb> + Debug {
356
357    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "Borrowing({:?})", self.0) }
358}
359
360/// A comparator that extracts a sort key from a value.
361///
362/// # Examples
363///
364/// ```
365/// use compare::{Compare, Extract};
366/// use std::cmp::Ordering::Greater;
367///
368/// let a = [1, 2, 3];
369/// let b = [4, 5];
370///
371/// let cmp = Extract::new(|s: &[i32]| s.len());
372/// assert_eq!(cmp.compare(&a, &b), Greater);
373/// ```
374#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
375pub struct Extract<E, C> {
376    ext: E,
377    cmp: C,
378}
379
380impl<E, K> Extract<E, Natural<K>> where K: Ord {
381    /// Returns a comparator that extracts a sort key using `ext` and compares it according to its
382    /// natural ordering.
383    pub fn new<T: ?Sized>(ext: E) -> Self where E: Fn(&T) -> K {
384        Extract { ext: ext, cmp: natural() }
385    }
386}
387
388// FIXME: convert to default method on `Compare` once where clauses permit equality
389// (https://github.com/rust-lang/rust/issues/20041)
390impl<E, C> Extract<E, C> {
391    /// Returns a comparator that extracts a sort key using `ext` and compares it using
392    /// `cmp`.
393    pub fn with_cmp<T: ?Sized, K>(ext: E, cmp: C) -> Self
394        where E: Fn(&T) -> K, C: Compare<K> { Extract { ext: ext, cmp: cmp } }
395}
396
397impl<E, C, T: ?Sized, K> Compare<T> for Extract<E, C> where E: Fn(&T) -> K, C: Compare<K> {
398    fn compare(&self, l: &T, r: &T) -> Ordering {
399        self.cmp.compare(&(self.ext)(l), &(self.ext)(r))
400    }
401
402    fn compares_lt(&self, l: &T, r: &T) -> bool {
403        self.cmp.compares_lt(&(self.ext)(l), &(self.ext)(r))
404    }
405
406    fn compares_le(&self, l: &T, r: &T) -> bool {
407        self.cmp.compares_le(&(self.ext)(l), &(self.ext)(r))
408    }
409
410    fn compares_ge(&self, l: &T, r: &T) -> bool {
411        self.cmp.compares_ge(&(self.ext)(l), &(self.ext)(r))
412    }
413
414    fn compares_gt(&self, l: &T, r: &T) -> bool {
415        self.cmp.compares_gt(&(self.ext)(l), &(self.ext)(r))
416    }
417
418    fn compares_eq(&self, l: &T, r: &T) -> bool {
419        self.cmp.compares_eq(&(self.ext)(l), &(self.ext)(r))
420    }
421
422    fn compares_ne(&self, l: &T, r: &T) -> bool {
423        self.cmp.compares_ne(&(self.ext)(l), &(self.ext)(r))
424    }
425}
426
427/// A comparator that [lexicographically]
428/// (https://en.wikipedia.org/wiki/Lexicographical_order) combines two others.
429///
430/// See [`Compare::then`](trait.Compare.html#method.then) for an example.
431#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
432pub struct Then<C, D>(C, D);
433
434impl<C, D, L: ?Sized, R: ?Sized> Compare<L, R> for Then<C, D>
435    where C: Compare<L, R>, D: Compare<L, R> {
436
437    fn compare(&self, l: &L, r: &R) -> Ordering {
438        match self.0.compare(l, r) {
439            Equal => self.1.compare(l, r),
440            order => order,
441        }
442    }
443}
444
445/// A comparator that delegates to [`Ord`]
446/// (http://doc.rust-lang.org/std/cmp/trait.Ord.html).
447///
448/// # Examples
449///
450/// ```
451/// use compare::{Compare, natural};
452/// use std::cmp::Ordering::{Less, Equal, Greater};
453///
454/// let a = &1;
455/// let b = &2;
456///
457/// let cmp = natural();
458/// assert_eq!(cmp.compare(a, b), Less);
459/// assert_eq!(cmp.compare(b, a), Greater);
460/// assert_eq!(cmp.compare(a, a), Equal);
461/// ```
462pub struct Natural<T: Ord + ?Sized>(PhantomData<fn(&T)>);
463
464/// Returns a comparator that delegates to `Ord`.
465pub fn natural<T: Ord + ?Sized>() -> Natural<T> { Natural(PhantomData) }
466
467impl<T: Ord + ?Sized> Compare<T> for Natural<T> {
468    fn compare(&self, l: &T, r: &T) -> Ordering { Ord::cmp(l, r) }
469    fn compares_lt(&self, l: &T, r: &T) -> bool { PartialOrd::lt(l, r) }
470    fn compares_le(&self, l: &T, r: &T) -> bool { PartialOrd::le(l, r) }
471    fn compares_ge(&self, l: &T, r: &T) -> bool { PartialOrd::ge(l, r) }
472    fn compares_gt(&self, l: &T, r: &T) -> bool { PartialOrd::gt(l, r) }
473    fn compares_eq(&self, l: &T, r: &T) -> bool { PartialEq::eq(l, r) }
474    fn compares_ne(&self, l: &T, r: &T) -> bool { PartialEq::ne(l, r) }
475}
476
477impl<T: Ord + ?Sized> Clone for Natural<T> {
478    fn clone(&self) -> Self { *self }
479}
480
481impl<T: Ord + ?Sized> Copy for Natural<T> {}
482
483impl<T: Ord + ?Sized> Default for Natural<T> {
484    fn default() -> Self { natural() }
485}
486
487impl<T: Ord + ?Sized> PartialEq for Natural<T> {
488    fn eq(&self, _other: &Self) -> bool { true }
489}
490
491impl<T: Ord + ?Sized> Eq for Natural<T> {}
492
493impl<T: Ord + ?Sized> Debug for Natural<T> {
494    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "Natural") }
495}
496
497/// A comparator that reverses the ordering of another.
498///
499/// See [`Compare::rev`](trait.Compare.html#method.rev) for an example.
500#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
501pub struct Rev<C>(C);
502
503impl<C, L: ?Sized, R: ?Sized> Compare<L, R> for Rev<C> where C: Compare<L, R> {
504    fn compare(&self, l: &L, r: &R) -> Ordering { self.0.compare(l, r).reverse() }
505    fn compares_lt(&self, l: &L, r: &R) -> bool { self.0.compares_gt(l, r) }
506    fn compares_le(&self, l: &L, r: &R) -> bool { self.0.compares_ge(l, r) }
507    fn compares_ge(&self, l: &L, r: &R) -> bool { self.0.compares_le(l, r) }
508    fn compares_gt(&self, l: &L, r: &R) -> bool { self.0.compares_lt(l, r) }
509    fn compares_eq(&self, l: &L, r: &R) -> bool { self.0.compares_eq(l, r) }
510    fn compares_ne(&self, l: &L, r: &R) -> bool { self.0.compares_ne(l, r) }
511}
512
513/// A comparator that swaps another's parameters, maintaining the underlying ordering.
514///
515/// This is useful for providing a comparator `C: Compare<T, U>` in a context that
516/// expects `C: Compare<U, T>`.
517///
518/// See [`Compare::swap`](trait.Compare.html#method.swap) for an example.
519#[derive(Clone, Copy, Default, PartialEq, Eq, Debug)]
520pub struct Swap<C>(C);
521
522impl<C, L: ?Sized, R: ?Sized> Compare<R, L> for Swap<C>
523    where C: Compare<L, R> {
524
525    fn compare(&self, r: &R, l: &L) -> Ordering { self.0.compare(l, r) }
526    fn compares_lt(&self, r: &R, l: &L) -> bool { self.0.compares_lt(l, r) }
527    fn compares_le(&self, r: &R, l: &L) -> bool { self.0.compares_le(l, r) }
528    fn compares_ge(&self, r: &R, l: &L) -> bool { self.0.compares_ge(l, r) }
529    fn compares_gt(&self, r: &R, l: &L) -> bool { self.0.compares_gt(l, r) }
530    fn compares_eq(&self, r: &R, l: &L) -> bool { self.0.compares_eq(l, r) }
531    fn compares_ne(&self, r: &R, l: &L) -> bool { self.0.compares_ne(l, r) }
532}
compare/lib.rs

compare/
lib.rs
